Palantir 电面面经

被一个小三弟给整得没边了。题目很简单，但是对方的头脑实在让人无语。
前菜是找Kth smallest element in an array。唰唰唰用quick select写完。问time complexity，答average O(nlogn)。三弟说不对，是O(n)。答b

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

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

的是start with a huge number say 1,000,000,000。然后binary search找。就这，我真主动要求跪了。

这还真不是烙印黑你

写一个代码，

楼主的FOLLOW UP我没怎么看懂，如果是在RANGE里的KTH的话。。那不是直接在写FIND的WRAPPER时候把首尾INDEX传进去不就好了嘛。。

    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);
        
        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);
    }
   
    private void swap(int[] nums, int left, int right)
    {
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
    }

brianyu 发表于 2016-1-24 13:41
来长见识了，展开说说

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

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

，，，我怎么和三哥感觉一样呀。。。

三哥说得对，平均时间确实是O(n)的……

clfhaha1234 发表于 2016-1-24 13:23
三哥说得对，平均时间确实是O(n)的……

来长见识了，展开说说

brianyu 发表于 2016-1-24 13:41
来长见识了，展开说说

感觉就是select的话，只要判断在不在峰值左右吧。至于左右的不用排序了。sort的话都要排序吧

类与对象tju 发表于 2016-1-24 13:47
感觉就是select的话，只要判断在不在峰值左右吧。至于左右的不用排序了。sort的话都要排序吧

的确是，面了两周的确脑子浆糊了。

上面代码是kth largest的。。随便改改就好

确实是平均O(n)