12/16 Google实习电面面经

11月13号找了地里的前辈内推Google。
昨天刚考完最后一门，今天中午12点就两轮背靠背的电话面试（面试官离的近，所以甚至连电话都没挂，连着打了两个小时）。


废话不多说，上面经。



第一轮是一个美国哥们，
第一道题输入一个由10组成的字符串（背景是1代表一个youtube视频中有音频的部分，0代表没有音频的部分）。设计一个Binary Tree类，使最下一

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

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

面经，特地来回馈一下，求大米和祝福！



补充内容 (2016-1-14 05:50):
感谢大家打赏大米！进展：面试三天后得知进pool，在pool里三周后match上一个irvine office的组。

xiaozhuxiaozhu 发表于 2015-12-17 16:11
lz能分享下，你们做的这些题么

第一轮的第一道题我是用按层遍历树的方法去构建这个树，因为输入是2的指数，可以知道树的深度，所以在遍历过程中只要没到目标深度就new两个子节点，如果到了目标深度就把输入的值赋给这层所有的节点。
第一道题的follow up，是分治的思路用递归实现，每次将字符串分半，如果当前子串全部由同一个元素组成，就赋值，如果不是就继续分成两半考虑。

第二轮第一题是比较简单的DP。第二题理解了题目之后其实跟第一轮的第一题差不多，也是按层遍历。

这是我的想法哈，大家多交流。

写了下第一题的代码

1. public class BinayTreeExpressString {
   
2.        
   
3.         static class Node {
   
4.                 int val;
   
5.                 Node left;
   
6.                 Node right;
   
7.                 public Node(int val) {
   
8.                         this.val = val;
   
9.                 }
   
10.         }
    
11.         public static  Node useBinayTreeExpressString(String str) {
    
12.                 if (str == null || str.length() == 0) {
    
13.                         return null;
    
14.                 }
    
15.                 if (str.length() == 1) {
    
16.                         return new Node(Integer.valueOf(str.charAt(0)));
    
17.                 }
    
18.                 int len = str.length();
    
19.                 int level = (int)(Math.log(len) / Math.log(2));
    
20.                 Node root = new Node(-1);
    
21.                 int index = 0;
    
22.                 Queue<Node> queue = new LinkedList<Node>();
    
23.                 queue.offer(root);
    
24.                 System.out.println(level);
    
25.                 while (index < level) {
    
26.                         index++;
    
27.                         if (index < level) {
    
28.                                 int size = queue.size();
    
29.                                 for (int i = 0; i < size; i++) {
    
30.                                         Node cur = queue.poll();
    
31.                                         cur.left = new Node(-1);
    
32.                                         queue.offer(cur.left);
    
33.                                         cur.right = new Node(-1);
    
34.                                         queue.offer(cur.right);
    
35.                                 }
    
36.                         } else {
    
37.                                 for (int i = 0; i < str.length();) {
    
38.                                         Node cur = queue.poll();
    
39.                                         cur.left = new Node((str.charAt(i++) - '0'));
    
40.                                         if (i < str.length()) {
    
41.                                                 cur.right = new Node((str.charAt(i++) - '0'));
    
42.                                         }
    
43.                                 }
    
44.                         }
    
45.                 }
    
46.                 return root;
    
47.         }
    
48.         public static Node useBinayTreeExpressStringFollowUp(String str) {
    
49.                 if (str == null || str.length() == 0) {
    
50.                         return null;
    
51.                 }
    
52.                 if (str.length() == 1) {
    
53.                         return new Node((str.charAt(0) - '0'));
    
54.                 }
    
55.                 return helper(str, 0, str.length() - 1);
    
56.         }
    
57.         private static Node helper(String str, int start, int end) {
    
58.                 if (start > end) {
    
59.                         return null;
    
60.                 }
    
61.                 if (start == end || isAllTheSame(str, start, end)) {
    
62.                         return new Node((str.charAt(start) - '0'));
    
63.                 }
    
64.                 int mid = (end - start) / 2 + start;
    
65.                 Node node = new Node(-1);
    
66.                 node.left = helper(str, start, mid);
    
67.                 node.right = helper(str, mid + 1, end);
    
68.                 return node;
    
69.         }
    
70.         private static boolean isAllTheSame(String str, int start, int end) {
    
71.                 char c = str.charAt(start++);
    
72.                 while (start <= end) {
    
73.                         if (str.charAt(start) != c) {
    
74.                                 return false;
    
75.                         }
    
76.                         start++;
    
77.                 }
    
78.                 return true;
    
79.         }
    
80.        
    
81.         public static void print(Node node) {
    
82.                 if (node == null) {
    
83.                         return;
    
84.                 }
    
85.                 print(node.left);
    
86.                 if (node.left == null && node.right == null) {
    
87.                         System.out.print(node.val);
    
88.                 }
    
89.                 print(node.right);
    
90.         }
    
91.         public static void printTree(Node node) {
    
92.                 if (node == null) {
    
93.                         return;
    
94.                 }
    
95.                 printTree(node.left);
    
96.                         System.out.print(node.val);
    
97.                 printTree(node.right);
    
98.         }
    
99.         public static void main(String[] args) {
    
100. //                Node node = useBinayTreeExpressString("1011");
     
101.                 Node node = useBinayTreeExpressStringFollowUp("1011");
     
102.                 printTree(node);
     
103.         }
     
104. }

复制代码

同学能提供下你当时给出的solution吗？

lz能分享下，你们做的这些题么

感觉第二题不就是traverse tree吗？

LZ，每轮回答了2个题？看来时间还是蛮充裕的，我就做了一个题就没时间了

祝楼主好运了~ 希望年底拿大奖！！！

ohyline 发表于 2015-12-18 00:31
祝楼主好运了~ 希望年底拿大奖！！！

谢谢！也祝你好运！

johnjavabean 发表于 2015-12-17 16:03
同学能提供下你当时给出的solution吗？

请看对楼下同学的回复~ 大家多交流

liruoyuxgd2006 发表于 2015-12-18 00:06
LZ，每轮回答了2个题？看来时间还是蛮充裕的，我就做了一个题就没时间了

对，我的思路也是traverse tree。是的，每轮做了两道，但这几个题都不难的样子，所以可能有第三道题我没有做到。