Palantir电面面经

1. LRU cache
2. given an array of integers, return an array whose ith value is the median of the first i integers in the input
follo

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

the interview questions before?

And I received a thank you email...

能不能用逆向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暂时存储 中位数
楼主觉得这个方法对么？

北美农民 发表于 2014-11-5 10:45
第二题follow up不会...

当时我没问random access可不可以write，还是只能read, 可以write的话，insertion sort就解决了，不能的话，我只会n^2Log(M), M是数据范围，我瞎逼扯了一个只能read的n^2搞法，然后面试官还说就是他想问的，后来想想是错的，估计可能是时间快到了，要让我问问题了

1guangnian 发表于 2014-11-5 23:38
behavior不行啊。。当时做题目做的很郁闷，没有好好聊。。。而且把人家认成fb打来的了。。

我突然觉得如果是面g家的时候把g当成了fb 说不定还有分加......  

lz 在nyc的两个on site加油～～～

祝好运～～

thank you email？不应该你发嘛

Meily0503 发表于 2014-11-5 09:55
thank you email？不应该你发嘛

说明人家委婉的把我据了呀

1guangnian 发表于 2014-11-5 10:00
说明人家委婉的把我据了呀

他不识货。。。

Meily0503 发表于 2014-11-5 10:02
他不识货。。。

看清了我的本质

第二题follow up不会...

楼主， 没懂第二题的意思。。。{1,3,5} output is {1,2,3}么？

adiggo 发表于 2014-11-5 11:00
楼主， 没懂第二题的意思。。。{1,3,5} output is {1,2,3}么？

yep.....

1guangnian 发表于 2014-11-5 11:02
yep.....

follow  up是说一个array中不能hold所有的element， 所以相当于有多个array， 然后来找median array么？