发信人: livbai (梦想人生), 信区: JobHunting
标 题: yahoo onsite
发信站: BBS 未名空间站 (Tue Jun 17 00:07:35 2014, 美东)
今天onsite，前三个面试官都是三哥。
被第二个三哥问晕了。问了我3道题。有一题是一个DP，白板写了。其他2个问题，跪了。
1.
问：无限数据流里，sample出k个。
答：reservoir sampling
问：解释一下这个算法
答：blabla
问：这个算法取每个数据的概率不一样，不可以
答：这是个经典算法，有paper证明过这个
问：好，那你现在证明一下这个算法
没研究过这个算法的证明，当场跪了。三哥坚持reservoir sampling是错误的。没办法
，我给了另外一个解法，每个data算一个random score，用heap保持score高的k个。
2.
问：给你一个binary tree，换成linked list
答：我问，是普通的binary tree? 不是BST？
问：就是最普通的任意binary tree
答：可以inorder走一遍，转换成linked list，返回inorder的第一个node作为list的
head
问：变成linked list后，怎么reconstruct回原来的binary tree。要求in place。
答：！#%&（，跪了，我觉得无解。
最后问三哥，怎么能reconstruct回去，三哥说，你多看看网上的题目，你会学到很多
知识。。。。！#%&（。。。
--
※ 修改:·livbai 於 Jun 17 00:09:09 2014 修改本文·[FROM: 24.]
※ 来源:·WWW 未名空间站 网址：mitbbs.com 移动：在应用商店搜索未名空间·[FROM: 24.]
No comments:
Post a Comment