Snapchat MLE 电面

据说是新的Ads组，面试官是个白哥，电面上来直接做题，题感觉真的很难。对于一个mxn的matri

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

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

暴力解法，然后improve的时候时间就到了。

一维的好做吧。用monotonic queue。O(n)的时间。二维的话：
如果是n*m的2d matrix。对于每一行，先按照一维的做，window size是k。做完以后每一行会得到m-k个数，一共n行。这个时候新的矩阵变成了n*（m-k），每个元素是原本矩阵每行window size = k时候的最大值。
然后对于新的矩阵，每一列，再按照一维的做，window size还是k。做完以后每一列有n-k个数，一共（m-k）列。这个新的(n-k)*(m-k)矩阵就是答案。时间复杂度O(nm)

这是洛谷的一道绿题 https://www.luogu.com.cn/problem/P2216，洛谷题求的是小窗口里最大值和最小值差的极值，所以维护了两个队列，这题维护一个队列。

电面这个难度醉了，考竞赛题至于吗？？？对我这种菜逼即使看出单调队列的思路，也不会实现啊，更别提他家要当场调试通过了。现在面试真的卷

摸摸楼主。这个Max Value 是指matrix 的sum吗？能不能也用monotonous queue来存sum？但求sum的话感觉又得用2D Prefix sum，好麻烦啊

可以每一列用一个monotonous descending stack来存，假如是超过k个之前就pop掉，然后就转化成239了不是？

Tyrant89 发表于 2020-12-30 16:26
可以每一列用一个monotonous descending stack来存，假如是超过k个之前就pop掉，然后就转化成239了不是？

不是太理解层主的意思。。。。 可否详细解释下？

Tyrant89 发表于 2020-12-30 16:26
可以每一列用一个monotonous descending stack来存，假如是超过k个之前就pop掉，然后就转化成239了不是？

同求楼主解释一下吧

这题好像是常考题但是刷题网没有收录，感觉太难受了

OnlyRabbit 发表于 2020-12-23 05:30
摸摸楼主。这个Max Value 是指matrix 的sum吗？能不能也用monotonous queue来存sum？但求sum的话感觉又得用 ...

对的，就是moving matrix的max value

wwx_27 发表于 2021-1-22 13:53
这题好像是常考题但是刷题网没有收录，感觉太难受了

电面就考这种题，我也是醉了