报个facebook intern offer一枚

上周五拿到的facebook发来的offer，下面把面试经验总结一下：
第一面：
时间：2016.2.26
第一题是sort 3 colors变形，就是给一堆tasks，有一个API getPriority可以获得每一个task ID的优先级(low, medium, high),
要求对所有task进行排序，使得low tasks在最左边，medium的在中间，high的在最右边。
第二题是 print a linked list reversely，递归和非递归两个版本都要写出

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

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

e learning相关的组
都会问到system design。个人觉得选组很重要，因为涉及到return offer以及是否对相关projects真的感兴趣。

楼主当时选组的时候也是一头雾水，大家如果有team match相关的问题留言给我哈。

sealove999 发表于 2016-4-15 14:21
第三面，第一题

改了一下

1. public class Solution {
   
2.   public List<Point> kn1(List<Point> pts, int k) {
   
3.     Queue<Point> maxheap =
   
4.         new PriorityQueue<>((p1, p2) -> (p2.x * p2.x + p2.y * p2.y) - (p1.x * p1.x + p1.y * p1.y));
   
5.     for (Point p : pts) { // nlgk
   
6.       maxheap.offer(p);
   
7.       if (maxheap.size() > k) {
   
8.         maxheap.poll();
   
9.       }
   
10.     }
    
11.     return maxheap.stream().collect(Collectors.toList());
    
12.   }
    
13. 
    
14.   public List<Point> kn2(List<Point> pts, int k) {
    
15.     Queue<Point> minheap =
    
16.         new PriorityQueue<>((p1, p2) -> (p1.x * p1.x + p1.y * p1.y) - (p2.x * p2.x + p2.y * p2.y));
    
17.     minheap.addAll(pts);
    
18.     List<Point> ret = new ArrayList<>();
    
19.     for (int i = 0; i < k; i++) { // klgn
    
20.       ret.add(minheap.poll());
    
21.     }
    
22.     return ret;
    
23.   }
    
24. 
    
25.   int comp(Point pt1, Point pt2) {
    
26.     return pt1.x * pt1.x + pt1.y * pt1.y - pt2.x * pt2.x - pt2.y * pt2.y;
    
27.   }
    
28. 
    
29.   int qs(List<Point> arr, int low, int high) {
    
30.     Point p = arr.get(high); // high -> p
    
31.     while (low < high) {
    
32.       while (low < high && comp(arr.get(low), p) <= 0) { // <=
    
33.         low++;
    
34.       }
    
35.       arr.set(high, arr.get(low)); // low -> high
    
36.       while (low < high && comp(p, arr.get(high)) <= 0) { // <=
    
37.         high--;
    
38.       }
    
39.       arr.set(low, arr.get(high)); // high -> low
    
40.     }
    
41.     arr.set(high, p); // p -> high
    
42.     return high;
    
43.   }
    
44. 
    
45.   public List<Point> kn3(List<Point> pts, int k) {
    
46.     int low = 0;
    
47.     int high = pts.size() - 1;
    
48.     while (low < high) {
    
49.       int mid = qs(pts, low, high);
    
50.       if (mid < k) {
    
51.         low = mid + 1;
    
52.       } else if (k < mid) {
    
53.         high = mid - 1;
    
54.       } else { // k == mid
    
55.         return pts.subList(0, k);
    
56.       }
    
57.     }
    
58.     return pts.subList(0, k); // low < high
    
59.   }
    
60. 
    
61.   void recursion(List<Point> pts, int k, int start, int end) {
    
62.     int mid = qs(pts, start, end);
    
63.     if (mid < k) {
    
64.       recursion(pts, k, mid + 1, end);
    
65.     } else if (k < mid) {
    
66.       recursion(pts, k, start, mid - 1);
    
67.     }
    
68.   }
    
69. 
    
70.   public List<Point> kn3_(List<Point> pts, int k) {
    
71.     recursion(pts, k, 0, pts.size() - 1);
    
72.     return pts.subList(0, k);
    
73.   }
    
74. 
    
75.   public static void main(String[] args) {
    
76.     Solution s = new Solution();
    
77.     List<Point> pts = new ArrayList<>();
    
78.     pts.add(new Point(0, 1));
    
79.     pts.add(new Point(1, 1));
    
80.     pts.add(new Point(2, 2));
    
81.     pts.add(new Point(0, 2));
    
82.     pts.add(new Point(1, 1));
    
83.     Collections.shuffle(pts);
    
84.     System.out.println(s.kn1(pts, 3));
    
85.     Collections.shuffle(pts);
    
86.     System.out.println(s.kn2(pts, 3));
    
87.     Collections.shuffle(pts);
    
88.     System.out.println(s.kn3(pts, 3));
    
89.     Collections.shuffle(pts);
    
90.     System.out.println(s.kn3_(pts, 3));
    
91.   }
    
92. }
    

复制代码

第三面，第一题

1. public class Solution {
   
2.   public List<Point> kn1(List<Point> pts, int k) {
   
3.     Queue<Point> maxheap =
   
4.         new PriorityQueue<>((p1, p2) -> (p2.x * p2.x + p2.y * p2.y) - (p1.x * p1.x + p1.y * p1.y));
   
5.     for (Point p : pts) { // nlgk
   
6.       maxheap.offer(p);
   
7.       if (maxheap.size() > k) {
   
8.         maxheap.poll();
   
9.       }
   
10.     }
    
11.     return maxheap.stream().collect(Collectors.toList());
    
12.   }
    
13. 
    
14.   public List<Point> kn2(List<Point> pts, int k) {
    
15.     Queue<Point> minheap =
    
16.         new PriorityQueue<>((p1, p2) -> (p1.x * p1.x + p1.y * p1.y) - (p2.x * p2.x + p2.y * p2.y));
    
17.     minheap.addAll(pts);
    
18.     List<Point> ret = new ArrayList<>();
    
19.     for (int i = 0; i < k; i++) { // klgn
    
20.       ret.add(minheap.poll());
    
21.     }
    
22.     return ret;
    
23.   }
    
24. 
    
25.   int comp(Point pt1, Point pt2) {
    
26.     return pt1.x * pt1.x + pt1.y * pt1.y - pt2.x * pt2.x - pt2.y * pt2.y;
    
27.   }
    
28. 
    
29.   int qs(List<Point> arr, int low, int high) {
    
30.     Point p = arr.get(high); // high -> p
    
31.     while (low < high) {
    
32.       while (low < high && comp(arr.get(low), p) <= 0) { // <=
    
33.         low++;
    
34.       }
    
35.       arr.set(high, arr.get(low)); // low -> high
    
36.       while (low < high && comp(p, arr.get(high)) <= 0) { // <=
    
37.         high--;
    
38.       }
    
39.       arr.set(low, arr.get(high)); // high -> low
    
40.     }
    
41.     arr.set(high, p); // p -> high
    
42.     return high;
    
43.   }
    
44. 
    
45.   public List<Point> kn3(List<Point> pts, int k) {
    
46.     int low = 0;
    
47.     int high = pts.size() - 1;
    
48.     while (low < high) {
    
49.       int mid = qs(pts, low, high);
    
50.       if (mid < k) {
    
51.         low = mid + 1;
    
52.       } else if (k < mid) {
    
53.         high = mid - 1;
    
54.       } else { // k == mid
    
55.         return pts.subList(0, k);
    
56.       }
    
57.     }
    
58.     return pts.subList(0, k); // low < high
    
59.   }
    
60. 
    
61.   public static void main(String[] args) {
    
62.     Solution s = new Solution();
    
63.     List<Point> pts = new ArrayList<>();
    
64.     pts.add(new Point(0, 1));
    
65.     pts.add(new Point(1, 1));
    
66.     pts.add(new Point(2, 2));
    
67.     pts.add(new Point(0, 2));
    
68.     pts.add(new Point(1, 1));
    
69.     System.out.println(s.kn1(pts, 3));
    
70.     System.out.println(s.kn2(pts, 3));
    
71.     System.out.println(s.kn3(pts, 3));
    
72.   }
    
73. }
    

复制代码

第一面，第一题

1. public class Solution {
   
2.   int getPriority(int id) {
   
3.     return id % 3;
   
4.   }
   
5. 
   
6.   public void sort(int[] arr) {
   
7.     int l_w = 0; // writer
   
8.     int m_w = 0;
   
9.     for (int r = 0; r < arr.length; r++) { // reader
   
10.       int p = getPriority(arr[r]);
    
11.       if (p == 0) { // low
    
12.         int tmp = arr[r];
    
13.         arr[r] = arr[m_w];
    
14.         arr[m_w] = arr[l_w];
    
15.         arr[l_w] = tmp;
    
16.         l_w++;
    
17.         m_w++;
    
18.       } else if (p == 1) { // medium
    
19.         int tmp = arr[r];
    
20.         arr[r] = arr[m_w];
    
21.         arr[m_w] = tmp;
    
22.         m_w++;
    
23.       } else if (p == 2) { // high
    
24.         // nop
    
25.       }
    
26.     }
    
27.   }
    
28. 
    
29.   public static void main(String[] args) {
    
30.     Solution s = new Solution();
    
31.     List<Integer> list = IntStream.range(0, 100).boxed().collect(Collectors.toList());
    
32.     Collections.shuffle(list);
    
33.     int[] arr = list.stream().mapToInt(x -> x).toArray();
    
34.     System.out.println(Arrays.toString(Arrays.stream(arr).map(x -> s.getPriority(x)).toArray()));
    
35.     s.sort(arr);
    
36.     System.out.println(Arrays.toString(Arrays.stream(arr).map(x -> s.getPriority(x)).toArray()));
    
37.   }
    
38. }
    

复制代码

那道sort color变形 , 有没有规定能不能用 std:: swap ?

wtcupup 发表于 2016-4-4 05:39
那道sort color变形 , 有没有规定能不能用 std:: swap ?

可以用swap，但是要尽量减少swap的次数

第一面，第二题

1. public class Solution {
   
2.   ListNode reverse(ListNode head) {
   
3.     ListNode myhead = new ListNode(-1);
   
4.     while (head != null) {
   
5.       ListNode ln = head;
   
6.       head = head.next;
   
7. 
   
8.       ln.next = myhead.next;
   
9.       myhead.next = ln;
   
10.     }
    
11.     return myhead.next;
    
12.   }
    
13. 
    
14.   public void printALinkedListReversely1(ListNode head) {
    
15.     if (head != null) {
    
16.       ListNode ln = reverse(head);
    
17.       for (ListNode p = ln; p != null; p = p.next) {
    
18.         System.out.println(p.val);
    
19.       }
    
20.       reverse(ln);
    
21.     }
    
22.   }
    
23. 
    
24.   public void printALinkedListReversely2(ListNode head) {
    
25.     if (head != null) {
    
26.       printALinkedListReversely2(head.next);
    
27.       System.out.println(head.val);
    
28.     }
    
29.   }
    
30. 
    
31.   public static void main(String[] args) {
    
32.     Solution s = new Solution();
    
33.     ListNode ln1 = new ListNode(1);
    
34.     ListNode ln2 = new ListNode(2);
    
35.     ListNode ln3 = new ListNode(3);
    
36.     ListNode ln4 = new ListNode(4);
    
37.     ListNode ln5 = new ListNode(5);
    
38.     ln1.next = ln2;
    
39.     ln2.next = ln3;
    
40.     ln3.next = ln4;
    
41.     ln4.next = ln5;
    
42.     s.printALinkedListReversely1(ln1);
    
43.     System.out.println();
    
44.     s.printALinkedListReversely2(ln1);
    
45.   }
    
46. }
    

复制代码

fb的summer intern面到这么晚啊

求问system design是啥题目？

第三问，第二题

1. public class Solution {
   
2.   public String addBinaryDigits(String s1, String s2) {
   
3.     StringBuilder sb = new StringBuilder();
   
4.     int i = 1;
   
5.     int carry = 0;
   
6.     while (s1.length() - i >= 0 && s2.length() - i >= 0) {
   
7.       int b1 = s1.charAt(s1.length() - i) - '0';
   
8.       int b2 = s2.charAt(s2.length() - i) - '0';
   
9.       int sum = b1 + b2 + carry;
   
10.       sb.insert(0, sum % 2);
    
11.       carry = sum / 2;
    
12.       i++;
    
13.     }
    
14.     while (s1.length() - i >= 0) {
    
15.       int b1 = s1.charAt(s1.length() - i) - '0';
    
16.       int sum = b1 + carry;
    
17.       sb.insert(0, sum % 2);
    
18.       carry = sum / 2;
    
19.       i++;
    
20.     }
    
21.     while (s2.length() - i >= 0) {
    
22.       int b2 = s2.charAt(s2.length() - i) - '0';
    
23.       int sum = b2 + carry;
    
24.       sb.insert(0, sum % 2);
    
25.       carry = sum / 2;
    
26.       i++;
    
27.     }
    
28.     if (carry > 0) {
    
29.       sb.insert(0, carry);
    
30.     }
    
31.     return sb.toString();
    
32.   }
    
33. 
    
34.   public static void main(String[] args) {
    
35.     Solution s = new Solution();
    
36.     System.out.println(s.addBinaryDigits("1010111000011100110", "1111001000000110000100"));
    
37.   }
    
38. }
    

复制代码