FB的k-d tree面试题 - JobHunting版 - 未名存档

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

JobHunting版 - FB的k-d tree面试题

相关主题
● Google 面试题一道	● amazon一道面试题
● 问一道google面试题(from careercup)	● 问一道google题(from careercup)
● 求教两道面试题	● 请教careercup上的一道题
● 问个google面试题	● 问F家一道题
● 问一个CareerCup上的题	● Move on了，附送一个G题
● 发个G店面的题目	● 贡献一道电面题
● 这个算法题算难吗	● google phone interview question
● 问一道G家经典老题	● 问个Array Puzzle题

相关话题的讨论汇总
话题: tree话题: fb话题: 面试题话题: careercup话题: 的话

进入JobHunting版参与讨论

1

(共1页)

h****e 发帖数: 928	1 这是在CareerCup上看到的，就是给出所有点的最近3个相邻点： http://www.careercup.com/question?id=12266664 要是用brute-force的话，写O(N*N)的程序非常简单，不适合 FB的风格。要是用k-d tree的话，我觉得实现起来挺复杂的。不知道大虾们是怎么看这道题的。有更简单的方法吗？
n****e 发帖数: 678	2 同问，有没有k-d tree的sample codes？
p*****2 发帖数: 21240	3 啥是k-d tree呀。
h****e 发帖数: 928	4 网上有一些implementation，但是看起来都挺长的： - Java http://home.wlu.edu/~levys/software/kd/ - C http://code.google.com/p/kdtree/ 难道真的要把这些code背下来然后当场写出来？
p*****2 发帖数: 21240	5 好像没见到有考这个东西的吧。【在 h****e 的大作中提到】 : 网上有一些implementation，但是看起来都挺长的： : - Java : http://home.wlu.edu/~levys/software/kd/ : - C : http://code.google.com/p/kdtree/ : 难道真的要把这些code背下来然后当场写出来？
i**********e 发帖数: 1145	6 不可能面试叫你写这东西。 careercup的题很多都是假题，不要盲目相信。那题是 facebook puzzle 里面以前的题目，不排除可能拿来做面试，但是代码写起来也比较长，顶多让你说说思路。真正的面试题通常都不超过30行，顶多50行左右。超过的话意味着： 1）你代码不够简洁 2）你的思路完全不在正确的方向【在 h****e 的大作中提到】 : 网上有一些implementation，但是看起来都挺长的： : - Java : http://home.wlu.edu/~levys/software/kd/ : - C : http://code.google.com/p/kdtree/ : 难道真的要把这些code背下来然后当场写出来？
h****e 发帖数: 928	7 这是在CareerCup上看到的，见首帖。又搜了一把，找到源头了，是Facebook的一道Puzzle题: http://kanwei.com/code/2009/02/18/facebook-smallworld.html 他是用Ruby写的。希望onsite不会考到吧。
h****e 发帖数: 928	8 谢谢！真是这样的话，onsite就不会考到了，因为可以直接说出用k-d tree，算法复杂度是O(nlogn)。【在 i**********e 的大作中提到】 : 不可能面试叫你写这东西。 : careercup的题很多都是假题，不要盲目相信。 : 那题是 facebook puzzle 里面以前的题目，不排除可能拿来做面试，但是代码写起来 : 也比较长，顶多让你说说思路。 : 真正的面试题通常都不超过30行，顶多50行左右。超过的话意味着： : 1）你代码不够简洁 : 2）你的思路完全不在正确的方向

1

(共1页)

进入JobHunting版参与讨论

相关主题
● 问个Array Puzzle题	● 问一个CareerCup上的题
● 请教一个math puzzle题	● 发个G店面的题目
● Facebook Puzzle Gattaca	● 这个算法题算难吗
● 求一面试题解答	● 问一道G家经典老题
● Google 面试题一道	● amazon一道面试题
● 问一道google面试题(from careercup)	● 问一道google题(from careercup)
● 求教两道面试题	● 请教careercup上的一道题
● 问个google面试题	● 问F家一道题

相关话题的讨论汇总
话题: tree话题: fb话题: 面试题话题: careercup话题: 的话

未名新帖统计// 7月16日

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

* 这里只显示发帖超过25的版面，努力灌水吧:-)