雅虎 sde 2 电面

上周面了yahoo mail的一个组，面试官貌似是个伊朗大叔

前20分钟问了3-5道bq， 然后面了一道不在leetcode上的binary tree, randomly 返回某一个node with the same probability (uniform distribution)

最直觉的办法就是traverse一遍，把所有node放进一个array里，random choice就好

大叔问能不能improve time/space complexity

我想了半天想错方向了，然后要了提示，比如说可以每个node map with 一个数字， 以某种特定的 order, 比如inorder啥的，每次random选到那个数字，就返回对应的node

我想那就用hashmap在遍历的时候存起来，写出来代码之后大叔说那你的时间/空间复杂度好像没有啥提升

我想如果要提升，是不是只能到O(logN)了，我就说那或者加一个attribute到node里，构造成BST

后面还问了如果要add/delete node, 是不是又要重新traverse一次整棵树

我整个过程答的不太好吧，还是自己太菜了， 然后今天收到了拒信。

继续加油吧。


顺便附上一些自己整理的面经里出现的题目，求求各位看官给点大米，如果觉得还有点用的话！


lc 394 Decode String - stack
lc 278 First Bad Version - binary sea

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

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

c','d'], dependencies = ['a->b,d','b->c,f','c->g','d->e','f->g']; function dependencyResolver(‍‌‌‍‌‌‍‍‍‍‌‌‌‍‌‍‍‍‍libraries, dependencies){} 只要用indegree map就行了吧 刷题网207 210


补充一个条件，这题可能存在不相关的dependencies，所以在拓扑排序的基础上还需要 run一个bfs去存符合条件的library set最后拿来过滤


lc 821 ? 01 string 找出每个位置到所有1的距离和 例如 “0110” output： ［3，1，1，3］

感谢楼主！加油

lz面的是ic2还是ic3啊？

你好 楼主，你整理的面经题目是yahoo的吗