python面试总结4(算法与内置数据结构)

算法与内置数据结构

常用算法和数据结构
1. sorted
2. dict/list/set/tuple
分析时间/空间复杂度
实现常见数据结构和算法

数据结构/算法	语言内置	内置库
线性结构	list(列表)/tuple(元祖)	array(数组,不常用)/collection.namedtuple
链式结构		collections.deque(双端队列)
字典结构	dict(字典)	collections.Counter(计数器)/OrderedDict(有序字典)
集合结构	set(集合)/frozenset(不可变集合)
排序算法	sorted
二分算法		bisect模块
堆算法		heapq模块
缓存算法		functors.lru_cache(Least Recent Used,python3)

coolections模块提供了一些内置数据结构的扩展

collections

Point = collections.namedtuple('Point','x','y')

p = Point(1,2)

namedtuple让tuple属性可读

de = collections.deque()

de.append(1)

de.appendleft(0)

c = collections.Counter()

c = coolections.Counter('abcab')

python dict 底层结构

dict底层使用的哈希表

为了支持快速查找使用了哈希表作为底层结构
哈希表平均查找时间复杂度O(1)
Cpython解释器使用二次探查解决哈希冲突问题

python list/tuple区别

都是线性结构支持下标访问
list是可变对象，tuple保存的引用不可变

t = ([1],2,3)

t[0].append(1)

t

([1,1],2,3)

保存的引用不可变指的是你没法替换掉这个对象，但是如果对系那个本身是一个可变对象，是可以修改这个引用指向的可变对象的

list没发作为字典的key, tuple可以(可变对象不可hash)

什么是LRUCache？

Least-Recently-Used 替换掉最近最少使用的对象

缓存剔除策略,当缓存空间不够用的时候需要一种方式剔除key
常见的有LRU, LFU等
LRU通过使用一个循环双端队列不断把最新访问的key放到表头实现

字典用来缓存，循环双端链表用来记录访问顺序

利用python内置的dict + collections.OrderedDict实现
dict 用来当作k/v键值对的缓存
OrderedDict用来实现更新最近访问的key

from collections import OrderedDict

class LRUCache:

  def __init__(self, capacity=128):

    self.od = OrderedDict()

    self.capacity = capacity

  def get(self, key): #每次访问更新最新使用的key

    if key in self.od:

      val = self.od[key]

      self.od.move_to_end(key)

      return val

    else:

      return -1

  def put(self, key, value): # 更新k/v

    if key in self.od:

      del self.od[key]

      self.od[key] = value # 更新key 到表头

    else:  # insert

      self.od[key] = value

      # 判断当前容量是否已经满了

      if len(self.od) > self.capacity:

        self.od.popitem(last=False)

      code/lrucache.py

算法常考点

排序+查找,重中之重

常考排序算法: 冒泡排序、快速排序、归并排序、堆排序
线性查找，二分查找等
能独立实现代码(手写), 能够分析时间空间复杂度

python web 后端常考数据结构

常见的数据结构链表、队列、栈、二叉树、堆
使用内置结构实现高级数据结构，比如内置的list/deque实现栈
leetcode或者《剑指offer》上的常见题

常考数据结构之链表

链表有单链表、双链表、循环双链表

如何使用python 来表示链表结构
实现链表常见操作，比如插入节点，反转链表，合并多个链表等
Leetcode练习常见链表题目

数据结构之链表

# Definition for singly-linked list.

# class ListNode:

#     def __init__(self, x):

#         self.val = x

#         self.next = None

class Solution:

    def reverseList(self, head: ListNode) -> ListNode:

    pre = None

    cur = head

    while cur:

      nextnode = cur.next

      cur.next = pre

      pre = cur

      cur = nextnode

    ruture pre

数据结构之队列

队列(queue)是先进先出结构

如何使用python实现队列
实现队列的apend和pop操作,如何做到先做先出
使用python的list或者collections.deque实现队列

from collections import deque

class Queue:

   def __init__(self):

       self.items = deque()

   def append(self, val):

       retuen self.items.append(val)

   def pop(self):

       return self.items.popleft()

    def empty(self):

       return len(self.items) == 0

 def test_queue():

     q = Queue()

     q.append(0)

     q.append(1)

     q.append(2)

     print(q.pop())

     print(q.pop())

     print(q.pop())

 test_queue()()

0

1

2

常考数据结构之栈

栈(stack)是后进先出结构

如何使用python实现栈?
实现栈的push 和 pop 操作, 如何做到后进先出
同样可以用python list 或者collections.deque实现栈

from collections import deque

class Stack(object):

    def __init__(self):

        self.deque = deque() # 或者用list

    def push(self, value):

         self.deque.append(value)

    def pop(self):

         return self.deque.pop()

一个常考问题: 如何用两个栈实现队列?

常考数据结构之字典与集合

python dict/set 底层都是哈希表

哈希表的实现原理，底层其实就是一个数组
根据哈希函数快速定位一个元素，平均查找，非常快
不断加入元素会引起哈希表重新开辟空间，拷贝之前元素到新数组

巴特西