分享一下上午11点面的youtube电面

bluestarwing 发表于 2015-6-19 12:26
lz是refer的还是海投的？

refer被拒了……然后这次是自己投的…

bluestarwing 发表于 2015-6-19 12:26
lz是refer的还是海投的？

感觉投简历也要看运气、看遇到的hr。。我有个公司 refer了三次才有hr联系我……

第二题，BST 怎么还会找出现次数最多的数字？有duplicate？

houqingniao 发表于 2015-6-19 14:01
第二题，BST 怎么还会找出现次数最多的数字？有duplicate？

是的。还说了duplicate 都插到left。 不知道这句有什么用。。。

milanelllo13 发表于 2015-6-19 12:45
refer被拒了……然后这次是自己投的…

好吧，同样期待海投有效...谢lz！！！good luck

如果相同的都差到左子樹, 那 BST 就會成了特殊的形狀與規則
只要碰到相同的, 連續的左子樹都會是相同的, 直到找到不同為止
下面是我實作的代碼

1. public static int findMostFreqNum(TreeNode<Integer> root){

复制代码

1. public static int findMostFreqNum(TreeNode<Integer> root){
   
2.        
   
3.         TreeNode<Integer> ptr = null;
   
4.         Queue<TreeNode<Integer>> q = new LinkedList<>();
   
5.         q.offer(root);
   
6.        
   
7.         int maxCount = 0;
   
8.         int maxNum = Integer.MIN_VALUE;
   
9.        
   
10.         while(!q.isEmpty()){
    
11.                 ptr = q.poll();
    
12.                 int curNum = ptr.t;
    
13.                 int curCount = 1;
    
14.                 if(ptr.right != null) q.offer(ptr.right);
    
15.                 while(ptr.left != null && ptr.left.t == curNum) {
    
16.                         curCount++;
    
17.                         ptr = ptr.left;
    
18.                 }
    
19.                 if(ptr.left != null) q.offer(ptr.left);
    
20.                 if(curCount > maxCount){
    
21.                         maxNum  = curNum;
    
22.                         maxCount = curCount;
    
23.                 }
    
24.         }
    
25.        
    
26.         return maxNum;
    
27. }

复制代码

jack900001 发表于 2015-6-23 13:08

可是这样就没有用到BST的特点了,比如右边的大于root。我用的inorder traverse, 两种都是O(n).不知道面试官是想要哪种答案。

jack900001 发表于 2015-6-23 13:08

第二题不能用hashmap做么？

莫非第二题要用到传说中的O（n) time and O(1) space 的in order traversal?