Facebook onsite

找k neighbors 也可以用到kdtree

貌似面的不难额，挂了是因为同批去的人比较强都好学校的嘛？

多谢分享~~请问第二题的array是sorted array么？

psyclaudeZ 发表于 2014-10-30 17:36
第二题如果不需要结果有序的话堆都用不着……直接上selection algorihtm, 选出跟target差绝对值第k大元素， ...

In order to use selection, do you have to use any search or sort algorithms? Or just iterate through the list?

Sorry to type in English...

kwang75 发表于 2014-11-13 00:23
In order to use selection, do you have to use any search or sort algorithms? Or just iterate throu ...

Sorry that I should've said "quick select" -> http://en.wikipedia.org/wiki/Quickselect

psyclaudeZ 发表于 2014-11-13 15:37
Sorry that I should've said "quick select" -> http://en.wikipedia.org/wiki/Quickselect

我看了一下，quick select好像是找到一个pivot，然后arrange左边（都小于pivot）和右边（都大于pivot），但并没有排序（或者说不完全保证排序）。这样如果找kth closest或者是kth smallest than target number好像都不是特别有效？不知我理解的是否正确。

我觉得最管用的还是iterate through array然后arrange一个别的array来存储差值绝对值。这个方法是否和c++里面的heap类似？我没有学过c++所以不是特别清楚。谢谢！

quick select的java 代码哪里找的到例子吗？感觉自己写不出来。。。

jg7933 发表于 2014-11-19 08:58
quick select的java 代码哪里找的到例子吗？感觉自己写不出来。。。

cc150上有原题，在moderate还是hard我不记得，不是原题也差不多，你看一下

楼主有feedback吗 为什么跪

感觉都还可以啊。。