狗家onsite面经

Dawnwss 发表于 2021-04-05 23:48:43
麻烦问一下BQ轮都问些什么样的问题呀？有问简历吗？

贴这里了   https://www.1point3acres.com/bbs/thread-744495-1-1.html

vanquishz 发表于 2021-04-05 23:31:12
楼主其他轮难度怎么样？有hard程度吗？

感觉有hard，感觉没有原题全是leetcode改编版

贴这里了   https://www.1point3acres.com/bbs/thread-744495-1-1.html

2Hurric 发表于 2021-04-06 07:55:50
感谢分享。顺序的话是不是可以从最外层推向最内层，然后dp 存<rob, notRob>最大值的pair。不过我好奇用dfs with memo的方法理论上不也是dp嘛，他是说必须要用bottom up

没有别的限制，就只有偷了一家，周围8个不能偷。我也觉得有循环依赖，所以没法加memo

想了半天也不觉得这题能用DP。 DP里面的状态， 如果只有一个值，就是常见的比如到这个点的max， 根本没有足够的信息去推导下一个状态是valid还是invalid。我是觉得这题还得用DFS。。。

这题 太变态

LC1349嘛楼主

PocketOffer 发表于 2021-4-11 07:53
LC1349嘛楼主

有点类似

Blazer 发表于 2021-4-7 02:32
public int findMax(int[][] arr){        int m = arr.length, n = arr[0].length;
        int[][]  ...

不对吧，dp[i-2][j] 到dp[i][j]你要考虑i-1 row所有的选择情况。然后这个i-1 row怎么选又会depends on其他state。所以这个解法会进死胡同

xiana406 发表于 2021-4-6 19:50
有其他轮次的题目信息吗？这道题感觉定义dp[j]表示矩形((0, 0), (i, j))(假设用左上角，右下角代表矩形)小 ...

我个人觉得不对。例如dp[i-2][j] + dp[i][j-2] - dp[i-2][j-2].这一步：怎么能保证在dp[i-2][j] 与 dp[i][j-2]是最优的时候，它们重复计算的部分一定是dp[i-2][j-2]? 从面积上是对的，但是策略上怎么证明？你这个式子默认是dp[i-2][j-2]被重复计算了，但是在dp[i-2][j] 与 dp[i][j-2]中，它们针对子问题[i-2][j-2], 可能采取的是不同的策略。减法默认是采取了相同的策略所以才能减去，也就是默认dp[i-2][j]与dp[i][j-2]都包含了dp[i-2][j-2].你怎么证明呢？

Blazer 发表于 2021-4-6 14:32
public int findMax(int[][] arr){        int m = arr.length, n = arr[0].length;
        int[][]  ...

我认为你的answer是错的. 你 define dp[i][j] = optimal answer for subproblem mat[0:i][0:j] that uses mat[i][j]. 然后你说 mat[i][j] = f(mat[i - 2][j - 2], mat[i - 2][j - 1], mat[i - 1][j - 2], mat[i][k - 1]) where f() means "function of."
但这并不能保证 optimality.