旷视感知算法面经

项目相关问了40分钟左右，对模型的具体实现和验证非常感兴趣，论文要求详细讲解创新点，不过问的问题都比较常规，也没有问八股

手撕代码是三道题

1. 链表中环的入口节点

快慢指针，同时从head出发，fast走两步，slow走一步，第一次相遇后把fast放到开始，步长改成1，下次相遇就是入口结点

2. 打家劫舍2（首尾相连）

   dp[i] = max(dp[i-1], dp[i-2]+nums[i])
   dp[0] = nums[0]
   dp[1] = max(nums[:2])

首尾相连的情况下，首尾不能同时取，所以直接对nums[:n-1]和nums[1:]分别动规就行，时间复杂度是o(n)，空间复杂度可以用循环数组优化成o(1)

3. 打家劫舍3（树形结构）
   
   思路是维护一个字典，每个结点分别计算取该点的最大值和不取该点的最大值，更新的时候直接在字典里更新，最后返回root的对应的值即可。
   需要注意的是，在不取p点的时候，p->left和p->right也都有可能不取，所以在更新的时候需要用到dp[p][1]=max(dp[p.left])+max(dp[p.right])

   class Solution:
    def rob(self, root: TreeNode) -> int:
        # dp[p][0]代表取该点
        # dp[p][1]代表不取该点
        # dp[p][0] = dp[p.left][1] + dp[p.right][1]
        # dp[p][1] = max(dp[p.left])+max(dp[p.right])
        self.dp = {}
        def dfs(root):
            if root is None:
                return
            dfs(root.left)
            dfs(root.right)
            tmp0 = root.val
            tmp1 = 0
            if root.left is not None:
                tmp0 += self.dp[root.left][1]
                tmp1 += max(self.dp[root.left])
            if root.right is not None:
                tmp0 += self.dp[root.right][1]
                tmp1 += max(self.dp[root.right])
            self.dp[root] = [tmp0,tmp1]
        dfs(root)
        return max(self.dp[root])

不太清楚旷视的上海岗位什么情况，面试完之后换了个北京的hr给我打电话说岗位调到了北京，还有两轮复试