facebook 实习面经

Jester_Z 发表于 2016-2-23 02:00
quick select的话 只用调用一次 选出来第k个就行了吧  
当你选出来第k个的时候 比k小已经都在它前面了

嗯，如果顺序不重要的话是这样的，如果需要明确的指明closest，second closest... kth closest，还是需要k次select

iwofr 发表于 2016-2-22 11:23
嗯，如果顺序不重要的话是这样的，如果需要明确的指明closest，second closest... kth closest，还是需要 ...

给这k个再排一次不就行了klogk

LZ, team match有结果了吗？

AndrewFish 发表于 2016-2-23 04:25
给这k个再排一次不就行了klogk

选k次不也是klogk，不都一样么。。。

AndrewFish 发表于 2016-2-23 04:25
给这k个再排一次不就行了klogk

选k次不也是klogk，不都一样么。。。

wk93210 发表于 2016-3-6 15:06
选k次不也是klogk，不都一样么。。。

quick select 是kn

AndrewFish 发表于 2016-3-7 08:16
quick select 是kn

－ －下午脑子浆糊了。。。又犯傻了。。。

wk93210 发表于 2016-3-7 14:05
－ －下午脑子浆糊了。。。又犯傻了。。。

是指面试么?没关系的，不要紧张，虽然我很紧张面试的时候。。。

请问楼主team match interview之后多久拿到offer的？ team match interview 有没有问 phd期间相关的project？

第二题

1. public class Solution {
   
2.   int dist(Point p1, Point p2) {
   
3.     int dx = p1.x - p2.x;
   
4.     int dy = p1.y - p2.y;
   
5.     return dx * dx + dy * dy;
   
6.   }
   
7. 
   
8.   int qs(Point[] arr, Point target, int start, int end) {
   
9.     Point pivot = arr[end]; // end out
   
10.     int targetdist = dist(pivot, target);
    
11.     while (start < end) {
    
12.       while (start < end && dist(arr[start], target) < targetdist) {
    
13.         start++;
    
14.       }
    
15.       arr[end] = arr[start]; // into end
    
16.       while (start < end && dist(arr[end], target) > targetdist) {
    
17.         end--;
    
18.       }
    
19.       arr[start] = arr[end]; // into start, end empty
    
20.     }
    
21.     arr[end] = pivot; // into end
    
22.     return end;
    
23.   }
    
24. 
    
25.   public Point[] kn(Point[] arr, Point target, int k) {
    
26.     int mid = -1;
    
27.     int low = 0;
    
28.     int high = arr.length - 1;
    
29.     do {
    
30.       mid = qs(arr, target, low, high);
    
31.       if (mid < k) {
    
32.         low = mid + 1;
    
33.       } else if (mid > k) {
    
34.         high = mid - 1;
    
35.       }
    
36.     } while (mid != k);
    
37.     return Arrays.copyOfRange(arr, 0, k);
    
38.   }
    
39. 
    
40.   public static void main(String[] args) {
    
41.     Solution s = new Solution();
    
42.     for (Point p : s.kn(new Point[] {new Point(0, 0), new Point(1, 0), new Point(0, 1),
    
43.         new Point(0, 2), new Point(2, 0), new Point(1, 2), new Point(2, 1)}, new Point(3, 0), 5))
    
44.       System.out.println(p);
    
45.   }
    
46. }
    

复制代码