近期论坛无法登录的解决方案


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 2526|回复: 15
收起左侧

Palantir 电面面经

[复制链接] |试试Instant~ |关注本帖
brianyu 发表于 2016-1-24 13:11:52 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Palantir - 网上海投 - 技术电面 |Other在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
被一个小三弟给整得没边了。题目很简单,但是对方的头脑实在让人无语。
前菜是找Kth smallest element in an array。唰唰唰用quick select写完。问time complexity,答average O(nlogn)。三弟说不对,是O(n)。答best case的确是O(N)。三弟不服输,说quick sort是O(NlogN),但quick select是O(N)。列了一个根本看不懂的算式非说是。
然后是求Kth smallest element in a given range inside an array。比如array是[1, 3, 2, 5, 7, 3, 4], range [0, 3], k = 3, return 3。直接要求把array变成若干block来做。那就每个block排序,然后把最小的放priority queue呗,类似于merge k sorted linked list。结果三弟说他想要的是start with a huge number say 1,000,000,000。然后binary search找。就这,我真主动要求跪了。

评分

1

查看全部评分

yjfox 发表于 2016-2-7 00:38:14 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
这还真不是烙印黑你
回复 支持 1 反对 0

使用道具 举报

类与对象tju 发表于 2016-1-24 13:21:28 | 显示全部楼层
关注一亩三分地微博:
Warald
,,,我怎么和三哥感觉一样呀。。。
回复 支持 反对

使用道具 举报

clfhaha1234 发表于 2016-1-24 13:23:49 | 显示全部楼层
三哥说得对,平均时间确实是O(n)的……
回复 支持 反对

使用道具 举报

 楼主| brianyu 发表于 2016-1-24 13:41:36 | 显示全部楼层
clfhaha1234 发表于 2016-1-24 13:23
三哥说得对,平均时间确实是O(n)的……

来长见识了,展开说说
回复 支持 反对

使用道具 举报

类与对象tju 发表于 2016-1-24 13:47:28 | 显示全部楼层
brianyu 发表于 2016-1-24 13:41. 鍥磋鎴戜滑@1point 3 acres
来长见识了,展开说说

感觉就是select的话,只要判断在不在峰值左右吧。至于左右的不用排序了。sort的话都要排序吧
回复 支持 反对

使用道具 举报

 楼主| brianyu 发表于 2016-1-24 13:49:50 | 显示全部楼层
类与对象tju 发表于 2016-1-24 13:47
感觉就是select的话,只要判断在不在峰值左右吧。至于左右的不用排序了。sort的话都要排序吧

的确是,面了两周的确脑子浆糊了。
回复 支持 反对

使用道具 举报

clfhaha1234 发表于 2016-1-24 14:48:54 | 显示全部楼层
brianyu 发表于 2016-1-24 13:41
来长见识了,展开说说

CMU算法课第一节的内容(虽然没怎么听讲……)

F(n)=n+1/n*F(1~n-1) 解出来F(n)=O(cN+K) 近似 O(n) 的时间,当时证明方法是把估计的时间复杂度带进去,用数学归纳法证明。
回复 支持 反对

使用道具 举报

Teness 发表于 2016-2-6 03:27:06 | 显示全部楼层
写一个代码,

楼主的FOLLOW UP我没怎么看懂,如果是在RANGE里的KTH的话。。那不是直接在写FIND的WRAPPER时候把首尾INDEX传进去不就好了嘛。。
. 鍥磋鎴戜滑@1point 3 acres
    public int FindKthLargest(int[] nums, int k) {
        return FindKthLargest(nums, k, 0, nums.Length -1);
    }
   
    private int FindKthLargest(int[] nums, int k, int low, int high)
    {
        int left = low;
        int right = high -1;
        int pivit = high;
        
        while(left <= right)
        {
            if(nums[left] < nums[pivit])
            {
                left++;
            }else{
                swap(nums, left, right);
                right--;
            }
        }
        
        swap(nums, left, pivit);
        . Waral 鍗氬鏈夋洿澶氭枃绔,
        int rank = nums.Length - left;
        if(rank == k) return nums[left];. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        else if(rank < k) return FindKthLargest(nums, k, low, left - 1);
        else              return FindKthLargest(nums, k, left + 1, high);
    }.鐣欏璁哄潧-涓浜-涓夊垎鍦
    . From 1point 3acres bbs
    private void swap(int[] nums, int left, int right)
    {
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
    }
回复 支持 反对

使用道具 举报

Teness 发表于 2016-2-6 03:27:59 | 显示全部楼层
上面代码是kth largest的。。随便改改就好
回复 支持 反对

使用道具 举报

sevensevens 发表于 2016-2-6 17:23:13 | 显示全部楼层
确实是平均O(n)
回复 支持 反对

使用道具 举报

sevensevens 发表于 2016-2-6 17:24:37 | 显示全部楼层
同没有听懂followup...求楼主提示...谢谢呀!
回复 支持 反对

使用道具 举报

enirinth 发表于 2016-2-6 18:07:56 | 显示全部楼层
老印没说错....  
quick select: average O(n), worst case O(n^2)
median of medians selection: worst case O(n);
回复 支持 反对

使用道具 举报

2015fallcser 发表于 2016-2-7 00:45:20 | 显示全部楼层
这是一道送分题啊  
回复 支持 反对

使用道具 举报

hidden_track 发表于 2016-6-3 00:34:14 | 显示全部楼层
求教binary search怎么做?
回复 支持 反对

使用道具 举报

lijie 发表于 2016-6-3 05:09:01 | 显示全部楼层
第二题,根据给的范围的最小值和最大值对k值修改。
例子[1, 3, 2, 5, 7, 3, 4], range [0, 3],k=3
有0个数比范围[0,3]的最小值0小,所以k=3
如果范围为[2,5],原数组有一个1比2小,所以k=4,在原数组中找第4大的值
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-6-27 19:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表