微软面试2
@2020-09-29
电话面试
将二叉树同一层的节点使用 `next` 指针穿起来。两个比较废空间的办法:
- 用二叉树的方式遍历,记录每层最后一个节点,需要一个Map. Map大小是O(lgn), 栈空间是O(lgn).
- 使用BFS方式遍历,因为是按照层遍历,所以同一层遍历的时候是节点是顺序访问的,不需要Map, 只需要Queue. Queue空间是O(N).
面试官说还有空间O(1)的算法,我没有立刻给出解法。他提示一下我才知道,如果你将上一层的节点看做链表的话会怎么样呢?这是个不错的想法。
class Tree: Tree left Tree right Tree next def extendList(root): head = Tree() while root: if root.left: head.next = root.left head = head.next if root.right: head.next = root.right head = head.next return head.next def buildNext(root): head = root while head: head = extendList(head) return root
面试1
手写验证ipv4是否正确,以及找到数组中的众数
def isIPV4(s): d = 0 # to compute digit comma = True # dot count = 0 # how many digits for c in s: if c.isdigit(): if comma: comma = False count += 1 if count > 4: return False # 0255 d = ord(c) - ord('0') + d * 10 if d > 255: return False elif c == '.': if comma: return False d = 0 comma = True else: return False # 结尾需要再次验证 if count != 4 or comma: return False return True def findMostCommon(arr): ans = None c = 0 for i in range(len(arr)): if ans is None: ans = arr[i] c = 1 continue if arr[i] == ans: c += 1 else: c -= 1 if c == 0: ans = None c = 0 return ans
面试2
从流中找到median. 在这个问题上有两个扩展:
- 如果这些数的范围在[0,100]会怎么样?直接统计就好了。
- 如果90%的数在[0,100], 10%的数是其他范围呢?和上面一样,但是需要维护<0和>100的两个集合的数量
import heapq class MinHeap: def __init__(self): self.data = [] def top(): return self.data[0][1] def size(): return len(self.data) def pop(): x = heapq.heappop(self.data) return x[1] def push(x): heapq.heappush(self.data, (x, x)) class MaxHeap(MinHeap): def push(x): heapq.heappush(self.data, (-x, x)) class MedianFinder: def __init__(self): self.A = MaxHeap() self.B = MinHeap() def add(element): # 0 1 # 0 2 -> 1, 1 self.B.add(element) if (self.A.size() + 1) < self.B.size(): x = self.B.pop() self.A.push(x) def median(): asz = self.A.size() bsz = self.B.size() if asz == bsz: # TODO: no element. if asz == 0: return None x = self.A.top() y = self.B.top() return (x+y) * 0.5 return self.B.top()
另外一个就是给找到N个括号的所有匹配情况,直接用dfs就好了。有两个优化可以做:
- 可以缓存k个括号的所有情况。当 `st==0` 的时候,直接范围 `n-left` 所有括号情况就好。
- 可以将(看做1, )看做0, 遍历 `for st in range(1 << (2*N))`. 这种做法比较粗暴,但是却适合并行化。
def printBrackets(n): def dfs(buf, st, left): if left == 0: ans = buf + [')'] * st print(ans) return buf.append('(') dfs(buf, st + 1, left - 1) buf.pop() if st > 0: buf.append(')') dfs(buf, st - 1, left) buf.pop() buf = [] dfs(buf, 0, n)
面试3
面试聊到了一个真实情况下的系统设计题目,主要是找出bottleneck在什么地方。这个系统不复杂,只不过你需要详细询问每个部分的QPS/处理能力,然后找到可能的bottleneck,然后进行优化。
笔试题目是流式地处理一些数字的输入,然后打印出所有的区间,主要就是处理区间合并的问题。
class Merger: def __init__(self): self.d = {} self.ranges = set() def add(element): # find prev rane. a, b = element, element if element-1 in self.d: c, d = self.d[element-1] self.ranges.remove((c, d)) a, b = min(a, c), max(b, d) self.d.remove(c) self.d.remove(d) if element +1 in self.d: c, d = self.d[element+1] self.ranges.remove((c, d)) a, b = min(a, c), max(b, d) self.d.remove(c) self.d.remove(d) self.d[a] = (a, b) self.d[b] = (a, b) self.ranges.add((a, b))
面试4
因为聊到之前做过C++,也说自己对底层编程比较感兴趣,所以就让我写一个快速的 `strcpy` 实现。这个实现有几个假设:
- 没有内存重叠
- 使用相同的allocator分配(也就是对齐方式是一样的)
int strcpy(uchar *from, uchar* dest) { int n = strlen(from); int count = n; int align = 8 - from % 8; while(n > 0 && align > 0) { *from = *dest; from ++; dest ++; align --; n --; } while(n > 8) { int64_t* p = (int64_t*)from; int64_t* p2 = (int64_t*)dest; *p = *p2; n -= 8; from = from + 8; dest = dest + 8; } while(n) { *from = *dest; from += 1; dest += 1; n --; } return count; }