记一次愉悦的Google Onsite体验

”说实话，我有那么一瞬间我是不愉悦的 我觉得小哥剥夺了我思考乐趣，之后整个过程就变得索然无味了起来.....“ 能说出这句话的都是真大神

Can you give an example of this statement? Thanks a lot. "follow up 好像是小哥拍脑袋想的 说那怎么找包含targe的最大环呢，我：？？？？？？ ， 随便说了句如果最大环上有个小环 岂不是可以无限长， 无限大？"

第4题写了一下

1. public class AntCrossRoad {
   
2. 
   
3.     static class Segment {
   
4.         double x;
   
5.         double top;
   
6.         double bottom;
   
7.         boolean add;
   
8.         public Segment(double x, double top, double bottom, boolean add) {
   
9.             this.x = x;
   
10.             this.top = top;
    
11.             this.bottom = bottom;
    
12.             this.add = add;
    
13.         }
    
14.     }
    
15. 
    
16.     public static boolean walkable(double[][] squares) {
    
17.         List<Segment> list = new ArrayList<>();
    
18.         for (double[] square : squares) {
    
19.             list.add(new Segment(square[0], square[1], square[3], true));
    
20.             list.add(new Segment(square[2], square[1], square[3], false));
    
21.         }
    
22.         Collections.sort(list, (s1, s2) -> Double.compare(s1.x, s2.x));
    
23.         TreeMap<Double, Integer> tm = new TreeMap<>();
    
24.         for (Segment segment : list) {
    
25.             if (!isWalkable(tm)) {
    
26.                 return false;
    
27.             }
    
28.             if (segment.add) {
    
29.                 tm.put(segment.bottom, tm.getOrDefault(segment.bottom, 0) + 1);
    
30.                 tm.put(segment.top, tm.getOrDefault(segment.top, 0) - 1);
    
31.             } else {
    
32.                 int bottom = tm.get(segment.bottom);
    
33.                 if (bottom == 1) {
    
34.                     tm.remove(segment.bottom);
    
35.                 } else {
    
36.                     tm.put(segment.bottom, bottom - 1);
    
37.                 }
    
38.                 int top = tm.get(segment.top);
    
39.                 if (top == -1) {
    
40.                     tm.remove(segment.top);
    
41.                 } else {
    
42.                     tm.put(segment.top, top + 1);
    
43.                 }
    
44.             }
    
45.         }
    
46.         return true;
    
47.     }
    
48. 
    
49.     private static boolean isWalkable(TreeMap<Double, Integer> tm) {
    
50.         if (tm.isEmpty()) {
    
51.             return true;
    
52.         }
    
53.         int layer = 0;
    
54.         for (Map.Entry<Double, Integer> entry : tm.entrySet()) {
    
55.             if (layer == 0 && entry.getKey() > 0 && entry.getKey() < 1) {
    
56.                 return true;
    
57.             }
    
58.             layer += entry.getValue();
    
59.         }
    
60.         return tm.lastKey() < 1;
    
61.     }
    
62. 
    
63.     public static void main(String[] args) {
    
64.         System.out.println(walkable(new double[][]{
    
65.                 {0.2, 0.7, 0.3, 0.4}, {0.25, 0.5, 0.5, -0.1}
    
66.         }));
    
67.         System.out.println(walkable(new double[][]{
    
68.                 {0.2, 0.7, 0.3, 0.4}, {0.25, 0.5, 0.5, -0.1}, {0.26, 1.1, 0.5, 0.6}
    
69.         }));
    
70.         System.out.println(walkable(new double[][]{
    
71.                 {1, 0.5, 2, -1}, {3, 2, 5, 0.4}
    
72.         }));
    
73.         System.out.println(walkable(new double[][]{
    
74.                 {1, 0.5, 2, -1}, {3, 2, 5, 0.4}, {4, 0.8, 6, -1}
    
75.         }));
    
76.     }
    
77. }
    

复制代码

第1题，加followup

1.     public int findMaxAward(int[] rev1, int[] rev2, int cost) {
   
2.         int f1 = 0, f2 = 0;
   
3.         for (int i = 0; i < rev1.length; i++) {
   
4.             int f1Tmp = Math.max(f1, f2 - cost) + rev1[i];
   
5.             int f2Tmp = Math.max(f2, f1 - cost) + rev2[i];
   
6.             f1 = f1Tmp;
   
7.             f2 = f2Tmp;
   
8.         }
   
9.         return Math.max(f1, f2);
   
10.     }
    
11. 
    
12.     public List<Integer> findMaxAwardWithList(int[] rev1, int[] rev2, int cost) {
    
13.         int f1 = 0, f2 = 0;
    
14.         int[][] track = new int[2][rev1.length];
    
15.         Arrays.fill(track[0], -1);
    
16.         Arrays.fill(track[1], -1);
    
17.         for (int i = 0; i < rev1.length; i++) {
    
18.             int f1Tmp = 0, f2Tmp = 0;
    
19.             if (f1 >= f2 - cost) {
    
20.                 f1Tmp = f1 + rev1[i];
    
21.                 track[0][i] = 0;
    
22.             } else {
    
23.                 f1Tmp = f2 - cost + rev1[i];
    
24.                 track[0][i] = 1;
    
25.             }
    
26.             if (f2 >= f1 - cost) {
    
27.                 f2Tmp = f2 + rev2[i];
    
28.                 track[1][i] = 1;
    
29.             } else {
    
30.                 f2Tmp = f1 - cost + rev2[i];
    
31.                 track[1][i] = 0;
    
32.             }
    
33.             f1 = f1Tmp;
    
34.             f2 = f2Tmp;
    
35.         }
    
36.         LinkedList<Integer> list = new LinkedList<>();
    
37.         int curr = f1 >= f2 ? 0 : 1;
    
38.         for (int i = rev1.length - 1; i >= 0; i--) {
    
39.             list.addFirst(curr);
    
40.             curr = track[curr][i];
    
41.         }
    
42.         return list;
    
43.     }
    
44. 
    
45.     public static void main(String[] args) {
    
46.         Rev1Rev2 rev1Rev2 = new Rev1Rev2();
    
47.         System.out.println(rev1Rev2.findMaxAwardWithList(new int[]{1, 3}, new int[]{3, 1}, 3));
    
48.         System.out.println(rev1Rev2.findMaxAwardWithList(new int[]{1, 3}, new int[]{3, 1}, 1));
    
49.         System.out.println(rev1Rev2.findMaxAwardWithList(new int[]{1, 30, 2}, new int[]{10, 1, 5}, 3));
    
50.         System.out.println(rev1Rev2.findMaxAwardWithList(new int[]{1, 5, 2}, new int[]{3, 1, 5}, 1));
    
51.     }

复制代码

3.a

1. public class FindTopKInBst {
   
2. 
   
3.     public static class TreeNode {
   
4.         int val;
   
5.         int count;
   
6.         TreeNode left;
   
7.         TreeNode right;
   
8.         TreeNode(int val, int count) {
   
9.             this.val = val;
   
10.             this.count = count;
    
11.         }
    
12.     }
    
13. 
    
14.     public static TreeNode findTopKInBst(TreeNode node, int k) {
    
15.         if (node == null || node.count < k) {
    
16.             return null;
    
17.         }
    
18.         if (node.right == null) {
    
19.             if (node.count == 1) {
    
20.                 return node;
    
21.             } else {
    
22.                 return findTopKInBst(node.left, k - 1);
    
23.             }
    
24.         } else {
    
25.             if (node.right.count == k - 1) {
    
26.                 return node;
    
27.             } else if (node.right.count >= k) {
    
28.                 return findTopKInBst(node.right, k);
    
29.             } else {
    
30.                 return findTopKInBst(node.left, k - node.right.count - 1);
    
31.             }
    
32.         }
    
33.     }
    
34. 
    
35.     public static void main(String[] args) {
    
36.         TreeNode t4 = new TreeNode(4, 7);
    
37.         TreeNode t2 = new TreeNode(2, 3);
    
38.         TreeNode t1 = new TreeNode(1, 1);
    
39.         TreeNode t3 = new TreeNode(3, 1);
    
40.         TreeNode t6 = new TreeNode(6, 3);
    
41.         TreeNode t5 = new TreeNode(5, 1);
    
42.         TreeNode t7 = new TreeNode(7, 1);
    
43.         t4.left = t2; t4.right = t6;
    
44.         t2.left = t1; t2.right = t3;
    
45.         t6.left = t5; t6.right = t7;
    
46.         System.out.println(findTopKInBst(t4, 8));
    
47.     }
    
48. }
    

复制代码

3.b

1. public class ShortestCircle {
   
2. 
   
3.     public int findShortestCircle(int[][] edges, int N, int target) {
   
4.         Map<Integer, List<Integer>> graph = new HashMap<>();
   
5.         for (int[] edge : edges) {
   
6.             List<Integer> neighbor = graph.getOrDefault(edge[0], new ArrayList<>());
   
7.             neighbor.add(edge[1]);
   
8.             graph.put(edge[0], neighbor);
   
9.             graph.put(edge[1], graph.getOrDefault(edge[1], new ArrayList<>()));
   
10.         }
    
11.         int ans = 1;
    
12.         LinkedList<Integer> queue = new LinkedList<>();
    
13.         queue.addLast(target);
    
14.         boolean[] visited = new boolean[N];
    
15.         visited[target] = true;
    
16.         while (!queue.isEmpty()) {
    
17.             int size = queue.size();
    
18.             for (int i = 0; i < size; i++) {
    
19.                 int curr = queue.removeFirst();
    
20.                 for (int next : graph.get(curr)) {
    
21.                     if (next == target) {
    
22.                         return ans;
    
23.                     }
    
24.                     if (visited[next]) {
    
25.                         continue;
    
26.                     }
    
27.                     visited[next] = true;
    
28.                     queue.addLast(next);
    
29.                 }
    
30.             }
    
31.             ans++;
    
32.         }
    
33.         return -1;
    
34.     }
    
35. 
    
36.     public static void main(String[] args) {
    
37.         ShortestCircle shortestCircle = new ShortestCircle();
    
38.         System.out.println(shortestCircle.findShortestCircle(new int[][]{{0, 0}}, 1, 0));
    
39.         System.out.println(shortestCircle.findShortestCircle(new int[][]{{0, 1}, {1, 2}}, 3, 0));
    
40.         System.out.println(shortestCircle.findShortestCircle(new int[][]{{0, 1}, {1, 2}, {2, 0}}, 3, 0));
    
41.         System.out.println(shortestCircle.findShortestCircle(new int[][]{{0, 1}, {1, 2}, {2, 3}, {2, 0}}, 4, 0));
    
42.         System.out.println(shortestCircle.findShortestCircle(new int[][]{{0, 1}, {1, 2}, {2, 3}, {2, 0}, {3, 0}}, 4, 3));
    
43.     }
    
44. }
    

复制代码

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

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

高手，刷半天也是晕的 望尘莫及

fatalme 发表于 2019-11-13 15:33
嗯，leetcode上的变种。台湾哥出的没想象的那么难。

请问是哪道啊？茫茫题海lost了

室友问我为什么跪着看面筋系列