Google MTV 电面+Onsite

电面：

1.      一个Dictionary，一个String，把String中去掉0或者任意多个character，得到一个字典中存在的String，求这样最长的String。

2.      给一个String，只包含d和i, d表示数值下降，i表示升高。从1到9之间选择一串数字，每个数字只用一次，找到一个符合String pattern的序列。String长度不超过8，肯定能找到一个valid序列。

比如：iii -> 1234

           ididid -> 1835294

电面后等了很久才给的Onsite，原来是电面面试官出去玩了。。。

Onsite：

1.      类似MS Paint，一个matrix，格子中有不同颜色，给一个点，把周围所有连续且颜色相同的都换成新颜色。

类似System design。有非常多的书，计算出每个单词出现次数。资源包括很大的场地，无数的笔和纸，很多学生可供调配，怎么

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

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

长。。。

abc2ddddefg 变成 abc1x24xdefg

abc5xefg 变成 abc1x5xefg

abc55555xefg 变成 abc5x5xefg

3.      (1) 就是LeetCodeminStack。

(2) 每个Node都求子树Value总和，然后遍历所有Node，尝试切断左树和右树，求差值，记录最小值。

4.  BFS+DP，用HashMap保存每个node每个parentNode取值固定时候的可能最大值，然后遍历。

blactangeri 发表于 2015-10-16 08:55
另外N-ary tree的解法能不能详细说下。谢谢

直接上代码吧，这样比较清楚！没有测试，可能有小bug，但是思路就是DFS + DP

1. class TreeNode {
   
2.     int val;
   
3.     List<TreeNode> children;
   
4.     public TreeNode() {
   
5.         val = 0;
   
6.         children = new ArrayList<TreeNode>();
   
7.     }
   
8. }
   
9. 
   
10. class Wapper {
    
11.     TreeNode node;
    
12.     int parentVal;
    
13.     public Wapper(TreeNode node, int parentVal) {
    
14.         this.node = node;
    
15.         this.parentVal = parentVal;
    
16.     }
    
17.     @Override
    
18.     public boolean equals(Wapper an) {
    
19.     return this.node == an.node && this.parentVal == an.parentVal;
    
20.     }
    
21. }
    
22. 
    
23. public int maxVal(TreeNode root) {
    
24.     if(root == null) return 0;
    
25.     HashMap<Wapper, Integer> map = new HashMap<Wapper, Integer>();
    
26.     return maxValRec(root, -1, map);
    
27. }
    
28. 
    
29. public int maxValRec(TreeNode node, int parentVal, HashMap<Wapper, Integer> map) {
    
30.     if(node == null) return 0;
    
31.     Wapper wa = new Wapper(node, parentVal);
    
32.     if(map.containsKey(wa)) return map.get(wa);
    
33. 
    
34.     int bestVal = 0;
    
35.     int max = 0;
    
36.     for(int i=1; i<=10; i++) {
    
37.         if(i == parentVal) continue;
    
38.         int sum = i;
    
39.         for(TreeNode child : node.children)
    
40.             sum += maxValRec(child, i, map);
    
41.         if(sum > max) {
    
42.         max = sum;
    
43.         bestVal = i;
    
44.         }
    
45.     }
    
46.     node.val = bestVal;
    
47.     map.put(wa, max);
    
48.     return max;
    
49. }

复制代码

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

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

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

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

谢分享，LZ为啥会有两个店面连个oniste？

宝贝忆彼岸 发表于 2015-10-15 22:55
谢分享，LZ为啥会有两个店面连个oniste？

是电面面了两道题哈~

宝贝忆彼岸 发表于 2015-10-15 22:55
谢分享，LZ为啥会有两个店面连个oniste？

明白你在问什么了。。。前面的是题，后面的是我当时的解法

lz好厉害,应该offer到手了!~~问个问题,第四轮. N-ary tree, 为什么greedy的方法不可以?比如root给10,所有children给9,然后children的children又给10? 每一层取与之前一层不一样的. 只有两种情况 1: root为9,所以是9,10,9,10.. 轮流取; 2: root取10, 10,9,10,9.. 轮流取.

oopghi 发表于 2015-10-15 22:59
明白你在问什么了。。。前面的是题，后面的是我当时的解法

嗯嗯，看到了。。。。我真是SB了，刚起来脑子还晕着呢。。。。

多谢分享！感觉楼主offer要来的样子～～

oopghi 发表于 2015-10-16 02:03
想了半天才想到了反例，nothingtrouble这个解法不一定能得到最优解，比如这个树：
这是按照nothingtroub ...

确实是这样,谢谢lz指正.