whatsapp intern面经

电面一轮，onsite两轮。最后悲剧了。

电面:
1. 把一个sorted list转成balanced binary search tree
2. 把sorted list转成complete binary search

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

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

fortress写了一个实现。利用Fortress的并发特性，可以达到O(lgn)。然后被要求不用Fortress。我又用openmp给了一个多线程实现。

周三面whatsapp的fulltime，楼主这问题也太难了点吧，看来whatsapp还挺高冷的 估计没戏了

实习这么个面法也是蛮拼的

那个sorted list to complete BST 参考了一下前面的balanced BST的递归做法，跑了一下inorder/level order/isBST检查了一下应该没什么问题：

1. public class Solution {
   
2.     private ListNode node;
   
3. 
   
4.     private int getDividePos(int start, int end) {
   
5.         int m = end - start + 1;
   
6.         int height = (int)Math.ceil(Math.log(m + 1) / Math.log(2));
   
7.         if(3 * Math.pow(2, height - 2) - 1 >= m) {
   
8.             return end - (int) Math.pow(2, height - 2) + 1;
   
9.         }
   
10.         else {
    
11.             return start + (int) Math.pow(2, height - 1) - 1;
    
12.         }
    
13.     }
    
14. 
    
15.     private int getLength(ListNode node) {
    
16.         int length = 0;
    
17.         while(node != null) {
    
18.             length++;
    
19.             node = node.next;
    
20.         }
    
21.         return length;
    
22.     }
    
23. 
    
24.     public TreeNode convert(ListNode head) {
    
25.         if(head == null) {
    
26.             return null;
    
27.         }
    
28. 
    
29.         this.node = head;
    
30.         int length = getLength(head);
    
31.         return convert(0, length - 1);
    
32.     }
    
33. 
    
34.     private TreeNode convert(int start, int end) {
    
35.         if(start > end) {
    
36.             return null;
    
37.         }
    
38. 
    
39.         int rootIndex = getDividePos(start, end);
    
40.         TreeNode left = convert(start, rootIndex - 1);
    
41.         TreeNode root = new TreeNode(node.value);
    
42.         node = node.next;
    
43.         TreeNode right = convert(rootIndex + 1, end);
    
44.         root.left = left;
    
45.         root.right = right;
    
46.         return root;
    
47.     }
    
48. }

复制代码