FB的k-d tree面试题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

FB的k-d tree面试题

FB的k-d tree面试题# JobHunting - 待字闺中

h*e2012-04-16 07:04

1 楼

这是在CareerCup上看到的，就是给出所有点的最近3个相邻点：
http://www.careercup.com/question?id=12266664
要是用brute-force的话，写O(N*N)的程序非常简单，不适合
FB的风格。
要是用k-d tree的话，我觉得实现起来挺复杂的。不知道
大虾们是怎么看这道题的。有更简单的方法吗？

n*e2012-04-16 07:04

2 楼

同问，
有没有k-d tree的sample codes？

p*22012-04-16 07:04

3 楼

啥是k-d tree呀。

h*e2012-04-16 07:04

4 楼

网上有一些implementation，但是看起来都挺长的：
- Java
http://home.wlu.edu/~levys/software/kd/
- C
http://code.google.com/p/kdtree/
难道真的要把这些code背下来然后当场写出来？

p*22012-04-16 07:04

5 楼

好像没见到有考这个东西的吧。

【在 h****e 的大作中提到】

: 网上有一些implementation，但是看起来都挺长的：
: - Java
: http://home.wlu.edu/~levys/software/kd/
: - C
: http://code.google.com/p/kdtree/
: 难道真的要把这些code背下来然后当场写出来？

i*e2012-04-16 07:04

6 楼

不可能面试叫你写这东西。
careercup的题很多都是假题，不要盲目相信。
那题是 facebook puzzle 里面以前的题目，不排除可能拿来做面试，但是代码写起来
也比较长，顶多让你说说思路。
真正的面试题通常都不超过30行，顶多50行左右。超过的话意味着：
1）你代码不够简洁
2）你的思路完全不在正确的方向

【在 h****e 的大作中提到】

h*e2012-04-16 07:04

7 楼

这是在CareerCup上看到的，见首帖。
又搜了一把，找到源头了，是Facebook的一道Puzzle题:
http://kanwei.com/code/2009/02/18/facebook-smallworld.html
他是用Ruby写的。希望onsite不会考到吧。

h*e2012-04-16 07:04

8 楼

谢谢！真是这样的话，onsite就不会考到了，因为可以直接说出
用k-d tree，算法复杂度是O(nlogn)。

【在 i**********e 的大作中提到】

: 不可能面试叫你写这东西。
: careercup的题很多都是假题，不要盲目相信。
: 那题是 facebook puzzle 里面以前的题目，不排除可能拿来做面试，但是代码写起来
: 也比较长，顶多让你说说思路。
: 真正的面试题通常都不超过30行，顶多50行左右。超过的话意味着：
: 1）你代码不够简洁
: 2）你的思路完全不在正确的方向