阅后即焚电话面经

同意觉得o(n^2) 因该可以做 有需要用到dp吗?

FightForTomo 发表于 2017-7-7 10:37
那你会啥提前和面试官说声啊。

呵呵，身边在面snapchat的好几个，都是在职跳槽，他们面过的题我还没有个数？

不要吵了，楼主就是来贡献面经的
现在工作市场不太好，面试题难度也没准啊

祝楼主和大家都好运！

say543 发表于 2017-7-7 14:21
同意觉得o(n^2) 因该可以做 有需要用到dp吗?

你的算法就是记录所有（0， 0）到（i, j）的矩阵和，然后再计算（i - x, j - x）到（i, j）的subsquare么？假如n是行或者列的大小，应该是o(n^3)吧？

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

更正

1. dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + m[i][j]

复制代码

1. curSum = dp[i][j] - dp[i-len][j] - dp[i][j-len]+ dp[i-len][j-len],

复制代码

lz提出用n^3的方法之后面试官不满意吗？这道题用dp也太难了吧。。。

m1n2b3v4 发表于 2017-7-8 04:49
lz提出用n^3的方法之后面试官不满意吗？这道题用dp也太难了吧。。。

面试官说，你可以先写brute-force.... O(n^3)面试官说可以，但主要是有限的时间很难想出来状态转移方程，在加上我没bug-free写完code

感觉可以用类似rangeSum的思路做，但是当时就没往那个方向考虑