旷视感知算法面经
项目相关问了40分钟左右，对模型的具体实现和验证非常感兴趣，论文要求详细讲解创新点，不过问的问题都比较常规，也没有问八股
手撕代码是三道题
- 链表中环的入口节点
快慢指针，同时从head出发，fast走两步，slow走一步，第一次相遇后把fast放到开始，步长改成1，下次相遇就是入口结点
- 打家劫舍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（树形结构）
思路是维护一个字典，每个结点分别计算取该点的最大值和不取该点的最大值，更新的时候直接在字典里更新，最后返回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给我打电话说岗位调到了北京，还有两轮复试
#旷视面经#
查看40道真题和解析
Momenta公司福利 297人发布
