Google Onsite

这周2面的，现在在等结果，面得其实不好，recruiter说这周末或者下周初给我update，所以现在感到特别煎熬。。。发个面筋，希望能帮到大家，也希望大家能bless我拿到offer。
其实题目都不难，可能是因为我是在职的原因。
我就不写我的做法了，现在心里太乱了。。。

1. 第一轮是写一个bounded bloc

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

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

pass，我的最初解是two pass，所以two pass写到一半他就说让写one pass的。写one pass的时候有bug，被指出来后，想到一个方法，面试官说是对的，不过不是面试官希望的。最后也没能写完，感到特别无力。。。

写了下打印树的题，最后输出格式还是有一些差异

1. public class PrintStructrue {
   
2. 
   
3.         public static void main(String[] args) {
   
4.                 PrintStructrue ps = new PrintStructrue();
   
5.                 int[][] edges = { { 7, 6 }, { 7, 5 }, { 7, 4 }, { 6, 3 }, { 6, 2 } };
   
6.                 ps.printStructure(edges);
   
7.         }
   
8. 
   
9.         public void printStructure(int[][] edges) {
   
10.                 if (edges == null || edges.length == 0) {
    
11.                         return;
    
12.                 }
    
13.                 HashMap<Integer, HashSet<Integer>> graph = buildGraph(edges);
    
14.                 HashMap<Integer, Integer> counter = new HashMap<Integer, Integer>();
    
15.                 for (HashSet<Integer> set : graph.values()) {
    
16.                         for (int ele : set) {
    
17.                                 if (counter.containsKey(ele)) {
    
18.                                         counter.put(ele, counter.get(ele) + 1);
    
19.                                 } else {
    
20.                                         counter.put(ele, 1);
    
21.                                 }
    
22.                         }
    
23.                 }
    
24.                 Queue<Integer> queue = new LinkedList<Integer>();
    
25.                 for (int ele : graph.keySet()) {
    
26.                         if (!counter.containsKey(ele)) {
    
27.                                 queue.offer(ele);
    
28.                         }
    
29.                 }
    
30.                 while (!queue.isEmpty()) {
    
31.                         int val = queue.poll();
    
32.                         print(val, graph, 0);
    
33.                 }
    
34.         }
    
35. 
    
36.         private void print(int val, HashMap<Integer, HashSet<Integer>> graph,
    
37.                         int len) {
    
38.                 for (int i = 0; i < len; i++) {
    
39.                         if (i == 0) {
    
40.                                 System.out.print(" ");
    
41.                         }
    
42.                         System.out.print("-");
    
43.                 }
    
44.                 System.out.println(val);
    
45.                 for (int i : graph.get(val)) {
    
46.                         print(i, graph, len + 1);
    
47.                 }
    
48.         }
    
49. 
    
50.         private HashMap<Integer, HashSet<Integer>> buildGraph(int[][] edges) {
    
51.                 HashMap<Integer, HashSet<Integer>> map = new HashMap<Integer, HashSet<Integer>>();
    
52.                 for (int[] edge : edges) {
    
53.                         if (!map.containsKey(edge[0])) {
    
54.                                 map.put(edge[0], new HashSet<Integer>());
    
55.                         }
    
56.                         if (!map.containsKey(edge[1])) {
    
57.                                 map.put(edge[1], new HashSet<Integer>());
    
58.                         }
    
59.                         map.get(edge[0]).add(edge[1]);
    
60.                 }
    
61.                 return map;
    
62.         }
    
63. }
    

复制代码

coin题，假设每个硬币只能用一次

1. public class CoinsChangeIII {
   
2. 
   
3.         public static void main(String[] args) {
   
4.                 int[] coins = { 1, 2, 3, 4, 5, 6, 10 };
   
5.                 List<Integer> res = minChange(coins, 9);
   
6.                 for (int i : res) {
   
7.                         System.out.print(i + " ");
   
8.                 }
   
9.         }
   
10. 
    
11.         public static List<Integer> minChange(int[] coins, int num) {
    
12.                 int[] table = new int[num + 1];
    
13.                 int[] solution = new int[num + 1];
    
14.                 Arrays.fill(table, Integer.MAX_VALUE);
    
15.                 table[0] = 0;
    
16.                 for (int i = 0; i < coins.length; i++) {
    
17.                         for (int j = num; j > 0; j--) {
    
18.                                 if (j >= coins[i] && table[j - coins[i]] != Integer.MAX_VALUE ) {
    
19.                                         if (table[j - coins[i]] + 1 < table[j]) {
    
20.                                                 table[j] = table[j - coins[i]] + 1;
    
21.                                                 solution[j] = i;
    
22.                                         }
    
23.                                 }
    
24.                         }
    
25.                 }
    
26.                
    
27.                 List<Integer> res = new ArrayList<Integer>();
    
28.                 if (table[num] == Integer.MAX_VALUE) {
    
29.                         return res;
    
30.                 }
    
31.                 while (num > 0) {
    
32.                         res.add(coins[solution[num]]);
    
33.                         num -= coins[solution[num]];
    
34.                 }
    
35.                 Collections.reverse(res);
    
36.                 return res;
    
37. 
    
38.         }
    
39. }
    

复制代码

coin题，假设每个硬币可以用多次

1. public class CoinsChangeII {
   
2. 
   
3.         public static void main(String[] args) {
   
4.                 int[] coins = { 1, 4, 5, 10 };
   
5.                 List<Integer> res = minChange(coins, 8);
   
6.                 for (int i : res) {
   
7.                         System.out.print(i + " ");
   
8.                 }
   
9.         }
   
10. 
    
11.         public static List<Integer> minChange(int[] coins, int num) {
    
12.                 int[] table = new int[num + 1];
    
13.                 int[] solution = new int[num + 1];
    
14.                 for (int i = 1; i <= num; i++) {
    
15.                         int minNum = Integer.MAX_VALUE;
    
16.                         int minIndex = Integer.MAX_VALUE;
    
17.                         for (int j = 0; j < coins.length; j++) {
    
18.                                 if (coins[j] <= i && 1 + table[i - coins[j]] < minNum) {
    
19.                                         minNum = 1 + table[i - coins[j]];
    
20.                                         minIndex = j;
    
21.                                 }
    
22.                         }
    
23.                         table[i] = minNum;
    
24.                         solution[i] = minIndex;
    
25.                 }
    
26. 
    
27.                 List<Integer> res = new ArrayList<Integer>();
    
28.                 if (table[num] == Integer.MAX_VALUE) {
    
29.                         return res;
    
30.                 }
    
31.                 while (num > 0) {
    
32.                         res.add(coins[solution[num]]);
    
33.                         num -= coins[solution[num]];
    
34.                 }
    
35. 
    
36.                 return res;
    
37. 
    
38.         }
    
39. }
    

复制代码

第三题感觉是不是应该利用hashmap《int， node》建立起来一个树？然后再遍历一下？

谢谢楼主分享～请问A-B和B-A那题应该怎么做哈？

跟楼主同一天哎，HR也跟我说下周一之前给update。。。莫非周二上午9:30左右在building 41见过的么？

楼主 请问第5题怎么做到1 pass，我能想到的是把每个target sum对应最后一步要选的coin记录下来， 最后从后往前拿出所有的coin

补充内容 (2015-12-12 13:43):
这么做其实就是2pass了吗

请问找硬币具体题目是？

请问楼主 第四题两个list 那道题，  除了sort， 或者用set直接做； 还有什么更好地办法吗？

请问楼主能详细说一下找硬币这个题的题目吗

LifeGoesOn 发表于 2015-12-12 13:43
楼主 请问第5题怎么做到1 pass，我能想到的是把每个target sum对应最后一步要选的coin记录下来， 最后从后 ...

表示不理解题目诶0。0 怎么记录target sum呢~。谢谢

leetcode昨天刚加了这个题 用dp算最少个数 同时cache每步的最优解 最后应该能同时得出最少个数以及是哪些硬币 one pass