FB onsite

3/31 电面 top k nearest points.
4/24 onsite:
        1. read4k, one time

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

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

今天接到电话已挂，说是有一轮coding没有给出optimal solution

top k nearest points.  最优解是 quick selection 吧

1.   public static class Point{
   
2.         int x;
   
3.         int y;
   
4.         double distance;
   
5.         public Point(int x , int y){
   
6.             this.x = x;
   
7.             this.y = y;
   
8.             distance=0;
   
9.         }
   
10.         @Override
    
11.         public String toString(){
    
12.             return "["+this.x+","+this.y+"]";
    
13.         }
    
14.     }
    
15.    
    
16.     public List<Point> topKPoints(List<Point> points, Point target, int k){
    
17.          List<Point>  ret = new ArrayList<Point>();
    
18.         for(Point p : points){
    
19.             p.distance = distance(p,target);
    
20.         }
    
21.         
    
22.         partition(points,0,points.size()-1, k);
    
23.         for(int i=0;i<k;i++){
    
24.             ret.add(points.get(i));
    
25.         }
    
26.         return ret;
    
27.     }
    
28.    
    
29.    
    
30.     public void partition(List<Point> arr, int lo, int hi, int k){
    
31.         int i=lo; int j=hi;
    
32.         while(i<j){
    
33.             int offset =quickSelect(arr, i, j);
    
34.             if(offset ==k-1) return;
    
35.             else if(offset<k-1){
    
36.                 i=offset+1;
    
37.             }
    
38.             else {
    
39.                 j=offset-1;
    
40.             }
    
41.         }
    
42.     }
    
43.     @SuppressWarnings("empty-statement")
    
44.     public int quickSelect(List<Point> arr, int lo, int hi){
    
45.         int i=lo; int j =hi+1;
    
46.         while(true){
    
47.             while(arr.get(++i).distance<arr.get(lo).distance)
    
48.                 if(i==hi) break;
    
49.             while(arr.get(--j).distance>arr.get(lo).distance);
    
50.             if(i>=j) break;
    
51.             exch(arr, i, j);
    
52.         }
    
53.         exch(arr, lo, j);
    
54.         return j;
    
55.     }
    
56.    
    
57.     public void exch(List<Point> arr, int i, int j){
    
58.         Point temp = arr.get(i);
    
59.         arr.set(i, arr.get(j));
    
60.         arr.set(j,temp);
    
61.     }
    
62.    
    
63.     public double distance(Point a, Point b){
    
64.         return Math.sqrt((a.x -b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
    
65.     }

复制代码

补充内容 (2017-5-18 13:26):
复杂度 O(N) ， 如果是 用pq的话 复杂度 为 O(NlgK)

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

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

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

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

lz不会是被黑了吧？这两个题的最优解不是地里都有么？

...还是感谢楼主分享！楼主可以说说ＰＯＩ怎么答有中面是面试官的方向吗？

How to reduce copy.  read4 这题怎么达的 ?

LZ是那一轮没有给出最优解呀，除了第一轮的follow up，其余看起来都很正常呀

axieyanga 发表于 2017-5-18 13:25
top k nearest points.  最优解是 quick selection 吧

请问quick select如果选前5大的数是要跑5次么？

hakusama1024 发表于 2017-5-24 07:00
请问quick select如果选前5大的数是要跑5次么？

不是啊 , 假如总共 n 个点， 不管找 top k ， 复杂度永远是 logn 不是k

axieyanga 发表于 2017-5-26 02:14
不是啊 , 假如总共 n 个点， 不管找 top k ， 复杂度永远是 logn 不是k

logn就可以么。请问是怎么做的。