meta 25ng research scientist第一轮

45min两道题，工作7年多的白男，体验不错
第一题：
留疤凛
follow up是弈迩噫瑬，可以移除k个的情况
我以为只是简单的follow up没想到是道hard的dp，我写了个recursive的做法，但没用memorizaion，面试官说looks nice


第二题
简易版巫硫囹，只问是否存在这样的subarray
follow up 1：返回所有这样的subarray，用字典记录前缀和的index即可
follow up 2：array变成一个矩阵的情况。这题我一开始没太理解，想着是返回所有和为target的path。只想到了dfs全部遍历，但我说这样的解法复杂度是n^4，面试官说没事儿先写下来。因为时间很少来不及写完就

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式

虑到时间）。我回答的不完美的地方有1）第一题follow up不是最优解；2）第二题第二个follow up没写完，同时没确认题目意思，但面试官看了我写的都说nice，也没让我改。。。

CharesFun 发表于 2024-11-20 21:30:43
请问楼主是哪个组呀，听起来像infra & sys.. 我在准备Intern面试，要是遇到DP估计就挂了qaq

General hiring没说哪个组

youryi999 发表于 2024-11-11 22:58
這link是k-Palidrome?

放错了不好意思，是这个https://www.geeksforgeeks.org/pr ... h-given-target-sum/

匿名用户 发表于 2024-11-11 18:53
感谢楼主，follow up 2好难啊，是不是lz coding太强太快了面试官临场发挥啊
他是要找 rectangular submatr ...

不是rectangle，我的理解是一条路径（8个方向的那种），那样的话就是dfs。如果是只能往右/下/右下的path的话，就有点类似这道题https://leetcode.com/problems/va ... n-during-interview/ 可以用前缀和来优化。很后悔当时没问清楚（如果我没解释明白的话欢迎再问哈）。主要也是我说了思路后他说sounds great，就让我写起来了。题目本身我做的其实也没有特别快，而且以为只会有一个follow up我看时间还多就慢慢地walk through examples。。。不然还能来得及写完

"留疤凛" -> median

"弈迩噫瑬" -> hard

感谢楼主，follow up 2好难啊，是不是lz coding太强太快了面试官临场发挥啊
他是要找 rectangular submatrices, 还是找所有可以合为target的点啊
array变成一个矩阵的情况。这题我一开始没太理解，想着是返回所有和为target的path。只想到了dfs全部遍历，但我说这样的解法复杂度是n^4，面试官说没事儿先写下来。因为时间很少来不及写完就写了个框架。面试官说ok，知道我能写出来。我面完后意识到也许path是只能向右向下或右下的，那就可以用前缀和优化（不然这个follow up和原题几乎完全无关了）

请问lz是收到hr reach out还是海投的呢

vincentyyx 发表于 2024-11-11 18:59
不是rectangle，我的理解是一条路径（8个方向的那种），那样的话就是dfs。如果是只能往右/下/右下的path ...

谢谢补充，如果是在matrix里面找路径的合为target，那是不是可以backtrack， 当sum 大于target的时候可以提早结束 (但是不适用有负数）

匿名用户 发表于 2024-11-11 19:07:44
请问lz是收到hr reach out还是海投的呢

我是内推后hr reach out

匿名用户 发表于 2024-11-11 19:28:01
谢谢补充，如果是在matrix里面找路径的合为target，那是不是可以backtrack， 当sum 大于target的时候可以提早结束 (但是不适用有负数）

对我就是这个思路。不过没法提前结束因为我问了面试官他说有正有负

vincentyyx 发表于 2024-11-11 19:43
对我就是这个思路。不过没法提前结束因为我问了面试官他说有正有负

如果有正有负就没法再stop early了，你这已经optimal了不要太紧张，估计是面试官临场发挥，祝好运！

区间dp和二维前缀和，phd按理说不会考很难的吧