发个Google Onsite

第一轮，tree版的 clone graph，状态不太好，被提醒了几次，有些无用的变量和步骤， 然后问了一下进程间通信怎么实现， 我答了通过文件或者socket

第二轮，就一道题   完完全全不会做， 面了这轮就知道悲剧了。。。
给一个un sorted array  长度为n
可以用 O(n)的时间和空间做 precomputation
然后 input是两个 int

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

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

n * k ^ -2,  对应最小值的k 就是 sqrt(2n) / 4  

补充内容 (2016-3-9 10:47):
将k 值带入 时间复杂度和空间复杂度都能得到 O(logn)

论坛匿名用户 发表于 2016-3-9 11:11
三哥提醒出来的。。。。

准确来说你这个解法还不是时间和空间都是logn的做法啊，而是sqrt(n)吧。这里的思想是macro/micro decomposition。

第二题不就是裸的线段树么。。挺容易的呀 segment tree

根據2樓提示，現學了一把segment tree, 求大神們檢查和指教，謝謝！

1. public class UnsortedArray {
   
2.     public static void main(String[] args) {
   
3.         UnsortedArray us = new UnsortedArray(new int[]{5,4,2,1,9,8,7});
   
4.         System.out.println(us.getIntervalMax(2,3) == 2);
   
5.         System.out.println(us.getIntervalMax(0,5) == 9);
   
6.         System.out.println(us.getIntervalMax(4,6) == 9);
   
7.         System.out.println(us.getIntervalMax(5,6) == 8);
   
8.         System.out.println(us.getIntervalMax(3,3) == 1);
   
9.     }
   
10.     private int[] array;
    
11.     private SegmentNode root;
    
12.     public UnsortedArray(int[] array) {
    
13.         this.array = array;
    
14. 
    
15.         if (array == null && array.length == 0) {
    
16.             throw new IllegalArgumentException();
    
17.         }
    
18. 
    
19.         Queue<SegmentNode> queue = new LinkedList<>();
    
20. 
    
21.         for (int i = 0; i < array.length; i++) {
    
22.             queue.offer(new SegmentNode(i,i,array[i]));
    
23.         }
    
24. 
    
25.         while (queue.size() >1) {
    
26.             int size = queue.size();
    
27.             for (int i = 0; i < size;) {
    
28.                 if (i == size-1) {
    
29.                     queue.offer(queue.poll());
    
30.                     break;
    
31.                 }
    
32.                 SegmentNode left = queue.poll();
    
33.                 SegmentNode right = queue.poll();
    
34. 
    
35.                 SegmentNode newNode = new SegmentNode(left.start, right.end, Math.max(left.max, right.max));
    
36.                 newNode.left = left;
    
37.                 newNode.right = right;
    
38.                 queue.offer(newNode);
    
39.                 i += 2;
    
40.             }
    
41.         }
    
42.         root = queue.poll();
    
43.     }
    
44. 
    
45.     public int getIntervalMax (int i, int j) {
    
46.         if (i < 0 || j < 0 || i >= array.length || j>= array.length ||i >j) {
    
47.             throw new IllegalArgumentException();
    
48.         }
    
49. 
    
50.         return helper(root,i,j);
    
51.     }
    
52. 
    
53.     private int helper(SegmentNode node,int i, int j) {
    
54.         if (node.start == i && node.end == j) {
    
55.             return node.max;
    
56.         }
    
57.         if (i > node.mid) {
    
58.             return helper(node.right, i, j);
    
59.         }
    
60.         if (j <= node.mid) {
    
61.             return helper(node.left, i, j);
    
62.         }
    
63. 
    
64.         return Math.max(helper(node.left, i, node.mid), helper(node.right, node.mid+1, j));
    
65. 
    
66.     }
    
67. 
    
68.     class SegmentNode {
    
69.         int start;
    
70.         int end;
    
71.         int mid;
    
72.         int max;
    
73.         SegmentNode left;
    
74.         SegmentNode right;
    
75. 
    
76.         public SegmentNode(int start, int end, int max) {
    
77.             this.start = start;
    
78.             this.end = end;
    
79.             mid = start + (end - start)/2;
    
80.             this.max = max;
    
81.         }
    
82. 
    
83.         @Override
    
84.         //for debug
    
85.         public String toString() {
    
86.             return "SegmentNode{" +
    
87.                     "start=" + start +
    
88.                     ", end=" + end +
    
89.                     ", max=" + max +
    
90.                     '}';
    
91.         }
    
92.     }
    
93. }

复制代码

第二題我也不太懂唉，自己想了一個。。不知道算不算log(n);

1. public class UnsortedArray {
   
2.     public static void main(String[] args) {
   
3.         UnsortedArray us = new UnsortedArray(new int[]{1,1,1,1,1,6,1,1,1,1});
   
4.         System.out.println(us.getIntervalMax(2,3));
   
5.         System.out.println(us.getIntervalMax(0,5));
   
6.         System.out.println(us.getIntervalMax(4,6));
   
7.         System.out.println(us.getIntervalMax(5,6));
   
8. 
   
9.     }
   
10.     private int[] array;
    
11.     private int[] maxArray;
    
12.     public UnsortedArray(int[] array) {
    
13.         this.array = array;
    
14. 
    
15.         if (array == null && array.length == 0) {
    
16.             throw new IllegalArgumentException();
    
17.         }
    
18. 
    
19.         //maxArray[i] == max value from 0 ~ i
    
20.         maxArray = new int[array.length];
    
21.         maxArray[0] = array[0];
    
22.         for (int i = 1; i < array.length; i++) {
    
23.             maxArray[i] = Math.max(maxArray[i-1], array[i]);
    
24.         }
    
25.     }
    
26. 
    
27.     public int getIntervalMax (int i, int j) {
    
28.         if (i < 0 || j < 0 || i >= array.length || j>= array.length ||i >j) {
    
29.             throw new IllegalArgumentException();
    
30.         }
    
31. 
    
32.         //if maxArray[j]'s value is not equal to maxArray[i-1], which means maxArray[j]'s value
    
33.         // must come from i~j, then just return
    
34.         //O(1)
    
35.         if (i == 0 || maxArray[j] != maxArray[i-1]) {
    
36.             return maxArray[j];
    
37.         }
    
38. 
    
39.         //find max during i~j
    
40.         //O(j-i)
    
41.         int max = array[i];
    
42.         for (int x = i +1; x <= j; x++) {
    
43.             max = Math.max(array[x], max);
    
44.         }
    
45.         return max;
    
46.     }
    
47. }

复制代码

补充内容 (2016-3-9 07:42):
無視test case...後來隨手改了一個= =

补充内容 (2016-3-9 09:01):
樓下發了個segment tree版的，現學的。。

csgtc 发表于 2016-3-9 07:37
第二题不就是裸的线段树么。。挺容易的呀 segment tree

最近才聽說的segment tree呢。。表示自己好無知啊。。求問還有什麼類似的高級一點的數據結構？想去了解下

csgtc 发表于 2016-3-9 07:37
第二题不就是裸的线段树么。。挺容易的呀 segment tree

我给他说了一下线段树了。不过我当时说的空间o(n),   他说得log n      我发错了。pre computation 是要小于o n 空间

论坛匿名用户 发表于 2016-3-9 09:20
我给他说了一下线段树了。不过我当时说的空间o(n),   他说得log n      我发错了。pre computation 是要 ...

唉。。要log(n)的話。。。-0-投降，求來個大神指教

guschen802 发表于 2016-3-9 09:31
唉。。要log(n)的話。。。-0-投降，求來個大神指教

我把当时的做法更新上去了

第二轮能想出这个做法也是够厉害的。。。

william_gong 发表于 2016-3-9 11:11
第二轮能想出这个做法也是够厉害的。。。

三哥提醒出来的。。。。