微软

• 2021.09.14 模拟面试（Mock Interview）

    - 内容：群面，考算法题，每人举手回答，说思路

    - 好处：表现较好可跳过笔试，直通面试，几率比较大，建议尝试

• 2021.11.12 一面

    - 前30分钟自我介绍，聊简历和项目。

    - 算法题：LeetCode295.数据流的中位数。

        - 给定一些坐标，求一点使得该点到这些坐标的距离之和最小。

            - 一开始我靠直觉答了求这些坐标的平均值，面试官说不对，随后告诉我是求中位数，即所有x坐标的中位数，以及所有y坐标的中位数。然后让我写数据流的中位数的代码。

class MedianFinder:

    def __init__(self):
        self.maxhp = []  # numbers smaller than median (included)
        self.minhp = []  # numbers larger than median

    def addNum(self, num: int) -> None:
        import heapq
        h1 = self.maxhp
        h2 = self.minhp
        if len(h1) == len(h2):
            heapq.heappush(h2, num)
            heapq.heappush(h1, -heapq.heappop(h2))
        else:
            heapq.heappush(h1, -num)
            heapq.heappush(h2, -heapq.heappop(h1))

    def findMedian(self) -> float:
        h1 = self.maxhp
        h2 = self.minhp
        return -h1[0] if len(h1) > len(h2) else (-h1[0]+h2[0]) / 2.

        - 如果要从堆中随机删除一个数据，用哪个元素代替原有元素，如何调整堆的结构（下沉还是上浮）

    - *题外话：本来应该11.01就面的，结果到最后一刻都没收到正式的面试链接。联系HR后安排到了11.12和11.15一二面。建议：如果是走直通面试的通道，确保自己收到带有正式面试链接的邮件，否则和HR沟通。微软面试本来就迟，早面试压力小点。

• 2021.11.15二面

    - 做题

        1. 给定一个源字符串a，一个目标字符串b，一个替代字符串c。将a中的b更换为c。例：a="Hello, world", b=" ", c="%2b"，则替换后a变为"Hello,%2bworld"

            - 最优解应该用KMP算法 ，我现场用了暴力双指针。

            - 面试官说考这道题的意义是数组扩容什么的，我没懂……

def string_search(text, keyword):
    """
    KMP Algorithm.
    >>> string_search("aaaabaaa", "aaabaaa")
    [1]
    """

    def build_lps_array(s):
        """
        lps: Longest Prefix which is also Suffix.
        >>> build_lps_array("aaabaaa")
        [0,1,2,0,1,2,3]
        """
        lps = [0] * len(s)
        i = 1  # point at origin string
        j = 0  # point at lps array
        while i < len(s):
            if s[lps[j]] == s[i]:
                lps[i] = lps[j] + 1
                i += 1
                j = i - 1
            elif lps[j]:
                j = lps[j-1]
            else:
                lps[i] = 0
                i += 1
                j = i - 1
        return lps

    lps = build_lps_array(keyword)
    s1, s2 = text, keyword
    p1, p2 = 0, 0
    res = []
    while p1 < len(s1):
        if s1[p1] == s2[p2]:
            p1 += 1
            p2 += 1
        elif p2:
            p2 = lps[p2-1]
        else:
            p1 += 1
        if p2 == len(s2):
            res.append(p1-len(s2))
            p2 = lps[p2-1]
    return res

def helper(src, tar, i):
        for j in range(len(tar)):
            if src[i+j] != tar[j]:
                return False
        return True

def replace(src, tar, rpl):
    """
    Replace TAR in SRC with RPL.
    >>> replace("He llo, wor ld", " ", "*")
    'He*llo,*wor*ld'
    """
    indexs = string_search(src, tar)
    res = []
    i, j = 0, 0
    while j < len(src):
        if j in indexs:  # 暴力法：if helper(src, tar, j):
            res.append(src[i:j])
            res.append(rpl)
            j += len(tar)
            i = j
        else:
            j += 1
    if i < j:
        res.append(src[i:j])
    return "".join(res)

        2. 在一个多叉树中找路径，使路径总和等于目标数，路径的定义为：根节点到叶节点。

            - 用最简单的dfs解法即可

def path_finder(root, target):
    def dfs(root, path, path_sum):
        if len(root.children) == 0:
            if path_sum == target:
                res.append(path[:])
            return
        for child in root.children:
            path.append(child.val)
            dfs(child, path, path_sum+child.val)
            path.pop()

    res = []
    dfs(root, [], 0)
    return res

    - 计算机基础

        1. 在浏览器中输入网址，按下Enter，到返回结果。描述这整个过程。

            - 开放题，把自己能想到的说出来就行。我计算机基础差，答得不好。

    - 项目

        - 碰到的最大的困难是什么

        - 问简历上的东西