12/16 Google实习电面面经

wukey 发表于 2015-12-18 05:39
第一轮的第一道题我是用按层遍历树的方法去构建这个树，因为输入是2的指数，可以知道树的深度，所以在遍 ...

给的数，比如1011，一定是2的倍数么？
如果是的话，还简单一些。。
我感觉这题，有点，不容易想出来啊。

xiaozhuxiaozhu 发表于 2015-12-18 07:41
给的数，比如1011，一定是2的倍数么？
如果是的话，还简单一些。。
我感觉这题，有点，不容易想出来啊 ...

是的，我问过之后，面试官说会是2的倍数。

1. 第二轮第一题：
   
2. dp[i][j]=dp[i][j-1]+sum, where sum is the cumulative sum of the elements on top of matrix[i][j]

复制代码

你有结果了么

面试三天后得到进pool的消息

楼主 请问电面一般都是两道题吗

rchen29 发表于 2015-12-30 14:40
楼主 请问电面一般都是两道题吗

据我所知，每轮一般是两道题

写了下第一题的代码

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. }

复制代码