新鲜亚麻店面

两个BQs要求谈谈工作中如何处理conflicts

然后coding：
找出一个BST里从根节点到叶子所有paths里最长的那个path

很简单的题，trick在于写出一个O(n)的解法之后如何improve到sub O(n)。这时候就需要问他问题，比如

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

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

我要面L6，她说不行，不行就不行吧，还骗我说可以先面L5，面得好可以考虑给L6。我差点就信了后来一打听没这个事情，再跟她交涉她才说坦白说不行，好气！

统一回复一下关于sub O(N)的问题：

这个地方我当时也有点晕，心里想怎么可能做到低于O(N)呢。其实这就是需要和面试官交流的地方，面试官自然而然地会指出你先前的算法是给一个最优解，但是如果并不需要最优解呢？如果要求规定时间内必须返回一个解但是只要求这个解是能拿到的比较好的解就okay的话怎么做呢？那最简单的解法就是给在判断下一跳是去左子树还是右子树的时候随机决定，这样走到一个叶子节点的时候我们就有了一个path以及这个path上节点的个数，同时我们也知道这一路走下来大概得花费多长时间。那么这时候用给定的时间除以这个单次的时间，我们就知道可以重复多少次这种random path traverse，比如说十次吧，那我们最终就从这十次里面选一个path最长的返回就好了。

当然这只是我的做法，面试官说就是想看看会不会跟他交流来确定这个问题到底是要干什么，最后这轮电面也顺利pass了。相信大家一定有其他更好的做法。

mtvskywalker 发表于 2021-1-24 06:35
统一回复一下关于sub O(N)的问题：

这个地方我当时也有点晕，心里想怎么可能做到低于O(N)呢。其实这就是 ...

我觉得不需要专门在code里randomize，因为没遍历前谁也不知道tree的形状。只需要做常规的iterative的dfs，但是while loop里加入time limit，等时间快到了就直接返回当时探测到的最大值就行了。

mtvskywalker 发表于 2021-1-9 01:49
刷题不多，不知道对应蠡口的题号啊，哪位大神来补充一下

最长是指节点数最多还是节点的和最大？sub O(n)是什么意思？谢谢啦

请问第一题有题号吗

楼主是就一轮VO？

油冬冬 发表于 2021-1-8 09:44
请问第一题有题号吗

刷题不多，不知道对应蠡口的题号啊，哪位大神来补充一下

Zbeeee 发表于 2021-1-8 09:49
楼主是就一轮VO？

店面店面，哈哈

油冬冬 发表于 2021-1-10 01:11
最长是指节点数最多还是节点的和最大？sub O(n)是什么意思？谢谢啦

是指节点数最多。sub O(n)指的是time complexity比O(n)要小。

怎么做到sub (N)可以多给点细节指导吗，谢谢

mtvskywalker 发表于 2021-1-10 01:28
是指节点数最多。sub O(n)指的是time complexity比O(n)要小。

能稍微详细说一下是如何实现的吗？没怎么看懂。已加米