Snap Onsite

四轮国人，仨妹子一个男manager。

1. 二叉树LCA

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

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

square和subrectangle

第一轮 事先filter 不再树的点之后 用一样的方法来做?

第四轮用o(n^4) 的方法可以吗?

二叉树LCA。注意input可能有多个点，可能有不存在树里的点,
1. 不存在的话， 可以先过滤一遍，
2. 多个点的话， 可以2，2合并， 先找2个点的lca, 再用找到的lca和新的点找lca. 如果找到root的话， 那就不用继续找了， lca就是root.

二维数组找和最大的subsquare和subrectangle
这题目测要先制造一个sum[][], 然后n^4, 移动点top left, 和right bottom点。square和长方形的区别是， square的right bottom点是往对角线移动

解法比较傻，目前没有更好的解法

补充内容 (2017-9-22 14:59):
如果有不存在的点， 那么lca应该是null. 所以没必要继续找lca了

say543 发表于 2017-9-22 14:37
第四轮用o(n^4) 的方法可以吗?

o(n^3) 用列和吧？

4的原题是这个？
85. Maximal Rectangle:  最快 O(M*N)
221. Maximal Square

Related:
84. Largest Rectangle in Histogram

fledgling 发表于 2017-9-22 15:13
o(n^3) 用列和吧？

n^4 因该是已经用到列和?

好多妹纸

gameboyying 发表于 2017-9-22 14:58
二叉树LCA。注意input可能有多个点，可能有不存在树里的点,
1. 不存在的话， 可以先过滤一遍，
2. 多个 ...

二叉树这题是不是不需要先过滤呀。。。以为不存在的话一定返回null。。

lanluotiankong 发表于 2017-9-22 15:23
4的原题是这个？
85. Maximal Rectangle:  最快 O(M*N)
221. Maximal Square

同问？感觉上就是这个两题