Facebook 电面面经

zengm321 发表于 2015-1-22 03:27
BST那道，我能想到 1)deleteMin 5 次 2） inorder traverse成数组，然后select kth smallest

嗯 我的第一个解法就是你的 2）
然后followup要求降低复杂度

BST用Morris遍历可以空间O(1)

能麻烦楼主说一下第一题随机返回数组中最大的数是什么意思么？谢谢！

BST那个题，能不能用inorder traversal，用i记录扫到的值的个数，当i等于5的时候直接返回这个值就可以了，这样空间和时间最坏是O(n)最好是O(1)

然后楼主能不能解释一下数组那题，我没看懂什么意思

数组那题是这个吧：
http://www.fgdsb.com/2015/01/15/random-maximum/

鱼吃鱼翅 发表于 2015-1-22 04:52
BST那个题，能不能用inorder traversal，用i记录扫到的值的个数，当i等于5的时候直接返回这个值就可以了， ...

BST那个题：我就是这样做的

给一个数组比如： ｛1，2，3，5，5，3，2，5｝
请返回最大数的下标。
如果最大数出现了好几次，就随机返回一个，随机是指，每个最大数的下标被选中的概率是一样的

kwang75 发表于 2015-1-22 04:41
能麻烦楼主说一下第一题随机返回数组中最大的数是什么意思么？谢谢！

给一个数组比如： ｛1，2，3，5，5，3，2，5｝
请返回最大数的下标。
如果最大数出现了好几次，就随机返回一个，随机是指，每个最大数的下标被选中的概率是一样的

cjlm007 发表于 2015-1-22 05:01
数组那题是这个吧：
http://www.fgdsb.com/2015/01/15/random-maximum/

是的 这个博客好赞！我要收藏！多谢分享

哈哈哈哈 lz 我认识你~

yapingchen1990 发表于 2015-1-22 08:20
哈哈哈哈 lz 我认识你~

哈哈哈 我也认识你