Facebook onsite

四轮技术面试，每轮四十五分钟。每一轮先聊简历十到十五分钟，接下来做题，最后留下五分钟问问题。
1st: Given a m * n grid and the coordination of left bottom cell is

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

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

ven value

3rd: Leecode minimum window

4th: Check if a tree is BST

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

刚才写的
public int quickSelect(int[] a, int start, int end, int k) throws Exception {
                if (end - start + 1 < k)
                        throw new IllegalArgumentException();
                int pivot = a[start];
                int p1 = start + 1;
                int p2 = end;
                while (true) {
                        while (p1 <= end && a[p1] <= pivot)
                                ++p1;
                        while (p2 >= start && a[p2] > pivot)
                                --p2;
                        if (p1 > p2)
                                break;
                        swap(a, p1, p2);
                        ++p1; --p2;
                }
                swap(a, start, p2);
                if (p1 - start == k)
                        return pivot;
                if (p1 - start < k)
                        return quickSelect(a, p1, end, k - (p1 - start));
                return quickSelect(a, start, p2, k);
        }

不对 上面这个算法是O(n+klogn)的，空间O(n), 其实如果 不需要返回k个数的顺序的话，其实只要直接On的quickselect就可以了，之前以为只能用来找第k个数，其实找到的同时也做了partition，前k小的都在左边了，后面的都在右边了，因此和quickselect是一样的，时间复杂度O(n)，空间是O(n)，开一个新的数组表示差值执行quickselect，还有一个递归栈，最坏O(n), 时间不差于之前那个算法，甚至可能更好。

int Partition_InOrder(vector<pair<int, int>> &a, int low, int high)
{//inorder
    int i=low, j=high;
    pair<int,int> pivot=a[low];
    while(i<j)
    {
        while(i<j && a[j].first >= pivot.first) j--;
        while(i<j && a[i].first <= pivot.first) i++;
        if(i<j) swap(a[i], a[j]);
    }
    swap(a[i], a[low]);
    return i;
}

int QuickSelect(vector<pair<int, int> >& a, int low, int high, int k)//select kth smallest, or inorder kth ele
{// 1<=k<=high-low+1, low<=high
    if(low>high) return -1;
    int mid=Partition_InOrder(a, low, high);
    int prelen=mid-low+1;
    if(prelen==k) return a[mid].first;
    else if(prelen > k)
        return QuickSelect(a, low, mid-1, k);
    else
        return QuickSelect(a, mid+1, high, k-prelen);
}

vector<int> FindKClosest_QuickSelect(vector<int>& a, int k, int x)
{
    int n=a.size();
    if(k==n) return a;
    vector<pair<int, int>> v;
    for(int i=0;i<n;i++) v.push_back({abs(a[i]-x), i});
    QuickSelect(v, 0, n-1, k+1);
    vector<int> ans;
    for(int i=0;i<k;i++)
        ans.push_back(a[v[i].second]);
    //vector<int> ans(a.begin(), a.begin()+k-1);
    return ans;
}

第二题代码，请大神们指教

struct Node
{
    int val;
    int index;
    Node(int val_, int index_):val(val_), index(index_)
    {
    }
    bool operator<(const Node& n1) const
    {
        return val>n1.val;
    }
};
vector<int> FindKClosest(vector<int> a, int k, int x)//, 0<=k<=a.size()
{
    //for(auto &i: a) i=abs(i-x);
    vector<Node> v;
    for(int i=0;i<a.size();i++)
    {
        Node n({abs(a[i]-x), i});
        v.push_back(n);
    }
    priority_queue<Node> pq(v.begin(), v.end());
    //for(auto i: v) pq.push(i);
    vector<int> ans;
    //cout<<k<<endl;
    for(int i=0;i<k;i++)
    {
        ans.push_back(a[pq.top().index]);
        pq.pop();
    }
    return ans;
}

lz你好，我想印证下我对第二题的理解，是求在一个array里面第k个最接近given value 的数对吗？
解法因为和求第k大的数一样，维护一个大小为k 的heap，对吗？
谢谢啦！

都不难啊。。

不是第k个，是前k个。的确用heap。

这个题貌似都比较简单啊。。。

array.map(abs(self - given number))
Then use min heap

看起来并不难，好好准备应该可以crack

22691482 发表于 2014-10-31 04:07
这个题貌似都比较简单啊。。。

第一题是dp么。。

补充内容 (2014-10-31 05:19):
好吧，我想多了。。bfs就行

貌似 都很简单

第二题如果不需要结果有序的话堆都用不着……直接上selection algorihtm, 选出跟target差绝对值第k大元素，然后返回A[0]到A[k - 1]就好了……O(n)时间，O(1)额外空间……