- ms预面：考察LRU cache
用双向链表加dict完成。题目详细描述可参考Leetcode146。
https://leetcode-cn.com/problems/lru-cache/
代码如下：
class Node:
def __init__(self, k=None, v=None):
self.k = k
self.v = v
self.prev = None
self.next = None
class DList:
def __init__(self):
self.head = Node()
self.tail = Node()
self.length = 0
self.head.next = self.tail
self.tail.prev = self.head
def add(self, nod):
self.tail.prev.next = nod
nod.prev = self.tail.prev
self.tail.prev = nod
nod.next = self.tail
self.length += 1
def remove(self, nod):
if self.length == 0:
return
nod.prev.next = nod.next
nod.next.prev = nod.prev
self.length -= 1
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = dict()
self.active = DList()
def get(self, key: int) -> int:
if key not in self.cache.keys():
return None
nod = self.cache[key]
self.active.remove(nod)
self.active.add(nod)
return nod.v
def put(self, key: int, value: int) -> None:
nod = Node(key, value)
cur_len = len(self.cache)
if key in self.cache.keys():
self.active.remove(self.cache[key])
elif cur_len == self.capacity:
del self.cache[self.active.head.next.k]
self.active.remove(self.active.head.next)
self.active.add(nod)
self.cache[key] = nod
def print_cache(self):
p = self.active.tail.prev
while p.k or p.v:
print(p.k, p.v)
p = p.prev
if __name__ == "__main__":
lru = LRUCache(2)
lru.put(1, 1)
lru.put(2, 2)
lru.get(1)
lru.put(3, 3)
lru.put(4, 4)
lru.put(7, 3)
lru.put(4, 5)
lru.print_cache()
- ms一面：最短通行路径。应该是LC的题，但是我没找到原题。
给定一个矩阵，如
[1, 1, 0 ]
[0, 1, 1 ]
[1, 1, 0 ]
从左边走到右边，只有数值为1的地方可以走，走的方向可以是上下左右4个方向。问最短从左边走到右边的步数，如果走不到右边则返回-1。这道题如果是mid难度，那肯定算mid里较难的。
class Solution:
def __init__(self, mat):
m, n = len(mat), len(mat[0])
self.min = m*n
self.capacity = m*n
self.memo = [[0] * n for _ in range(m)]
def solve(self, mat):
for i in range(len(mat)):
self.memo = [[0] * len(mat[0]) for _ in range(len(mat))]
self.path(mat, i, 0, 0)
print(self.min)
def path(self, mat, i, j, m):
if mat[i][j] == 0 or self.memo[i][j] == 1:
return
m += 1
self.memo[i][j] = 1
if j == len(mat[0]) - 1:
print('m:', m)
self.min = min(self.min, m)
return
if j>1:
self.path(mat, i, j-1, m)
if j < len(mat[0]) - 1:
self.path(mat, i, j+1, m)
if i < len(mat) - 1:
self.path(mat, i+1, j, m)
if i>1:
self.path(mat, i-1, j, m)
def output_path(self):
if self.min == self.capacity:
print(-1)
else:
print(self.min)
if __name__ == '__main__':
# mat = [[1, 0, 0], [0, 1, 1], [1, 1, 1]]
mat = [[0, 1, 1, 0, 1],
[1, 0, 0, 1, 0],
[1, 1, 1, 1, 1],
[1, 1, 0, 1, 0]
]
sol = Solution(mat)
sol.solve(mat)
sol.output_path()
- ms二面：链表相加，动态规划（小偷偷东西）
3.1 链表相加，LC02：https://leetcode-cn.com/problems/add-two-numbers/
3.2 也没找到原题。题目如下：小偷要去偷一条街，但是不能挨家挨户偷，最少要间隔一户，每一户有的金额不一样，问小偷能偷到的最大价值是多少。比如：[1, 2, 3, 1]，则小偷最多可以偷3+1=4。
ls = [1,2,3,1]
# ls = [2,7,9,3,1]
def do(ls):
if len(ls) == 0:
return 0
if len(ls) == 1:
return ls[0]
if len(ls) == 2:
return max(ls)
if len(ls) == 3:
return max(ls[1], ls[0] + ls[2])
memo = [0] * len(ls)
memo[0] = ls[0]
memo[1] = ls[1]
memo[2] = max(ls[1], ls[0] + ls[2])
for i in range(3, len(memo)):
memo[i] = max(memo[i-1], memo[i-2] + ls[i])
return memo[-1]
print(do(ls))
- ms三面：10亿行id号，统计其中重复次数最多的前1000个id；此题为开放性讨论，不是LC原题。面试官告知的最佳方案是map reduce。
- 字节一面：最长公共子序列 LeetCode 1143
原题链接：https://leetcode-cn.com/problems/longest-common-subsequence/
def sol(text1, text2):
m, n = len(text1), len(text2)
f = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
f[i][j] = f[i - 1][j - 1] + 1
else:
f[i][j] = max(f[i - 1][j], f[i][j - 1])
return f[m][n]
if __name__ == '__main__':
a = 'abcabc'
b = 'aabbcc'
r = sol(a,b)
print(r)
- 字节二面：连最大通域面积（剑指Offer II 105）
原题链接：https://leetcode-cn.com/problems/ZL6zAn/
网友评论