Palantir电面面经

1guangnian 发表于 2014-11-6 12:43
一个新的数组呀

第二题的followup是说要求数组只能read不能改，然后还需要constant space，还要小于n^2?
这个怎么可能啊，完全答不到的，虽然不知道怎么证明...

asdfyou6 发表于 2014-11-7 05:35
第二题的followup是说要求数组只能read不能改，然后还需要constant space，还要小于n^2?
这个怎么可能啊 ...

只说是random access，如果可以write的话，n^2可以的

1guangnian 发表于 2014-11-7 05:37
只说是random access，如果可以write的话，n^2可以的

1. 什么是random access呢？
2. 题目道题要求是可不可以write啊

asdfyou6 发表于 2014-11-7 06:58
1. 什么是random access呢？
2. 题目道题要求是可不可以write啊

我当时脑补成只能read了，在那拼命想，没有再问他可不可以write，所以这点不是很清楚啊

补充内容 (2014-11-7 07:27):
我当时理解的他说的random access就是只能读

能不能用逆向insertion sort的方法？ 就是
1 建一个返回数组 result[]
2 在result 里 sort 输入数组， o (nlgn)
3 从result 的最后一个元素开始往前循环
     3.1 对每一个位置 (index = i ) 先求中位数，用一个临时变量保存中位数
     3.2 用binary search在result 数组中找到原数组中 i 位置的数，  o lgn
     3.3 把找到的删除，就是把找到的元素所有后面的知道当前循环到的位置 i 的元素往

前 shift  o(n)
     3.4 shift 完后第 i 位空出，放入之前存的中位数
所以总共复杂度就是 o(nlgn) + o(n*(lgn+n))=o(n^2)
只用了一个constant space暂时存储 中位数
楼主觉得这个方法对么？
     3.3 把找到的删除，就是把找到的元素所有后面的知道当前循环到的位置 i 的元素往前 shift  o(n)
     3.4 shift 完后第 i 位空出，放入之前存的中位数
所以总共复杂度就是 o(nlgn) + o(n*(lgn+n))=o(n^2)
只用了一个constant space暂时存储 中位数
楼主觉得这个方法对么？

我也被他家拒了，题目是find interval overlap，我觉得答得还可以。。。。。

能问一下楼主 面的是intern 还是 full time？ FDE 还是SE？

投了他家直接给了我一个简历杀

guomin1314 发表于 2014-11-9 09:56
我也被他家拒了，题目是find interval overlap，我觉得答得还可以。。。。。

同学你好， 能分享一下你的题嘛？

我做了三道，挂了，我朋友做了2道，onsite。。。回来发面经