一、你使用过哪些常用内置算法和数据结构

仔细回想一下你用过哪些内置的算法数据结构？
1.sorted
2.dict/list/set/tuple…
3.问题：想的不全或者压根没了解和使用过

二、有用过collections模块吗

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

namedtuple代码示例：

import collections

Point = collections.namedtuple('Point', 'x, y')
p = Point(1, 2)
print(p.x)  # 1
print(p.y)  # 2

print(p[0])  # 1
print(p[1])  # 2
print(p[2])  # IndexError: tuple index out of range
print(p.x == p[0])  # True

说明：namedtuple让tuple属性可读

deque代码示例：

import collections

de = collections.deque()

de.append(1)   		# 往右边添加值
de.appendleft(0)  	# 往左边添加值
print(de)  			# deque([0, 1])

de.pop()  			# 1  取右边的值
de.popleft() 		# 0  取左边的值

说明：deque可以方便地实现queue/stack

Counter代码示例：

import collections

c = collections.Count('abcab)

print(c)  			# Counter({'a': 2, 'b': 2, 'c': 1})
print(c['a'])  		# 2

print(c.most_common())  # [('a', 2), ('b', 2), ('c', 1)]  从大到小获取每一个的数量

说明：需要计数器的地方使用Counter

OrderedDict代码示例：

import collections

od = collections.OrderedDict()
od['c'] = 'c'
od['a'] = 'a'
od['b'] = 'b'

print(list(od.keys())   # ['c', 'a', 'b']

说明：
OrderedDict的key顺序是第一次插入的顺序。
使用OrderedDict还可以实现LRUCache。

defaultdict代码示例：

import collections

dd = collections.defaultdict(int)

print(dd['a'])  # 0  当不存在时，会返回一个默认值，因为上面定义的 int 类型，所以默认值为 0

dd['b'] += 1
print(dd)  # defaultdict(int, {'a': 0, 'b': 1})

说明：defaultdict是带有默认值的字典

三、Python dict底层结构

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

注意：哈希冲突和扩容是常考题
解决哈希冲突通常有两种：
1）、链接法
2）、探查法：分为线性探查和二次探查等

四、Python list/tuple区别

list VS tuple
1.都是线性结构，支持下标访问
2.list是可变对象，tuple是不可变对象
3.list没没作为字典的 key，tuple可以（可变对象不可 hash)

注意，如何tuple里包含list，则里面这个list是可以改变的

代码示例：

t = ([1, 2], 3, 4)
t[0].append(5)
print(t)  # ([1, 2, 5], 3, 4)

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

五、什么是 LRUCache?

Least-Recently-Used替换掉最近最少使用的对象
1.缓存剔除策略，当缓存空间不够用的时候需要一种方式剔除key
2.常见的有 LRU, LFU等
3.LRU通过使用一个循环双端队列不断把最新访问的key放到表头实现

六、如何实现LRUCache

字典用来缓存，循环双端链表用来记录访问顺序
1.利用Python内置的dict + collections.OrderedDict实现
2.dict用来当做 k/v键值对的缓存
3.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):		# 更新 key/value
		if key in self.od:
			del self.od[key]
			self.od[key] = value	# 更新 key 到表头，所以上一句要先删除这个key里的value
		else:		# insert
			self.od[key] = value

			# 判断当前容量是否已经满了
			if len(self.od) > self.capacity:
				self.od.popitem(last=False)  # 删除最早的 key/value
			

请大家自己实现LRUCache，并编写单元测试