Google电面面经+给了两轮电面?

sherry900105 发表于 2015-2-26 01:09
我觉得tostring会降低印象分的吧。。。= =我也不太清楚。。。但是觉得比较讨巧的办法就是取余。。。

如果要加逗号的话应该用toCharArray然后从尾开始每三位加逗号吧

另外第二题应该可以log(n)，root没有right subtree的话就返回left subtree的最大值，用一个反方向的in order. root 有left subtree的话也是做过反方向的in order 不过返回的是第二大的值。因为in order从边缘开始所以基本上直接探索到leaf就完了，如果是balanced的话就是o(log n)最差o(n)

补充内容 (2015-2-26 15:45):
第一题看错了，确实应该取余，而且先放到char[]里面比较有效率

补充内容 (2015-2-26 15:49):
实质上第二天也说复制了，直接reverse in order返回的第二个值就是了，不管什么情况

Google是1-2轮电面，4-5轮onsite。

请问楼主 如果第二题 没有right subtree怎么办？
有没有代码分享下？

tyr034 发表于 2015-3-16 09:54
请问楼主 如果第二题 没有right subtree怎么办？
有没有代码分享下？

面试的时候他没跟我提right subtree的事情。。做判断就好了吧。。0 0反正他只要求返回倒数第二大的。。

为毛感觉google的面试题，比国内bat的还简单……

第二题：

1. public TreeNode secondLargest(TreeNode root) {
   
2.                 if(root == null)        return null;
   
3. 
   
4.                 Stack<TreeNode> path = new Stack<TreeNode>();
   
5.                 TreeNode curr = root, second = null;
   
6.                 while(curr != null) {
   
7.                         path.push(curr);
   
8.                         curr = curr.right;
   
9.                 }
   
10. 
    
11.                 curr = path.pop(); //path is not empty since root is in stack               
    
12.                 if(curr.left != null) {
    
13.                         curr = curr.left;
    
14.                         while(curr.right != null) {
    
15.                                 curr = curr.right;
    
16.                         }
    
17. 
    
18.                         second = curr;
    
19.                 } else {
    
20.                         second = (path.empty()) ? null : path.pop();
    
21.                 }
    
22. 
    
23.                 return second;               
    
24.         }

复制代码

补充内容 (2015-3-21 11:12):
可以优化成常数空间。我懒得写了。

sherry900105 发表于 2015-2-26 01:09
我觉得tostring会降低印象分的吧。。。= =我也不太清楚。。。但是觉得比较讨巧的办法就是取余。。。

弱问取余的做法是什么

写了下这两道题，应该是对的：

第一题：

public class Solution {
    public String convertNumber(int num){
        boolean isPositive = true;
        if (num < 0){
            isPositive = false;
            num = -num;
        }

        if (num == 0){
            return "0";
        }
        String res = "";
        int count = 0;
        while(num > 0){
            int mod = num%10;
            num = num/10;
            res = mod + res;
            count ++;
            if (count == 3 && num > 0){
                res = ","+res;
                count = 0;
            }
        }

        return isPositive ? res.toString() : "-"+res.toString();
    }
}


public class Main {
    public static void main(String[] args){
        Solution solt = new Solution();
        System.out.println(solt.convertNumber(100));
        System.out.println(solt.convertNumber(1001));
        System.out.println(solt.convertNumber(21));
        System.out.println(solt.convertNumber(1000000021));
        System.out.println(solt.convertNumber(-10021));
    }
}


第二题：

public class Solution {
    public TreeNode getSecondLargest(TreeNode root){
        if (root == null || (root.left == null && root.right == null)) return null;

        TreeNode cur = root; TreeNode pre = null;

        while(cur != null){
                if (cur.right != null){
                    pre = cur;
                    cur = cur.right;
                }else {
                    break;
                }
        }

        if (cur.left != null){
            pre = cur.left;
            while(pre.right != null){
                pre = pre.right;
            }
        }
        return pre;

    }
}

ucichuck 发表于 2015-4-22 15:03
写了下这两道题，应该是对的：

第一题：

第一题 如果输入是Integer.MIN_VALUE 结果就不对了。。