重发LiveRamp的OA，有原题截图，free response好坑//非故意重发，只是想大家看到原题

马克下！

天墨 发表于 2015-10-1 05:57
感谢楼主分享。。感觉它家面试的bar还是很高的。。。~~~~(>_

是嘛？其实我觉得我答得都很水啊，倒是听说他家不怎么招人是真的。等我二面之后争取再来跟进一些吧~~~

rhett.lhy 发表于 2015-10-1 04:33
这题可以用并查集来做吧？每次新来一个A=k的时候，把k插入到当前排好序的叶子当中，然后看左右邻居是不是在 ...

可是感觉UF的话memory或者runtime会不符合要求啊？sry我可能没截上，这两个都有要求限制，好像是O(N)我记得

Laurinda93 发表于 2015-10-1 10:12
可是感觉UF的话memory或者runtime会不符合要求啊？sry我可能没截上，这两个都有要求限制，好像是O(N)我记 ...

并查集的话总的时间复杂度是O(K log*K+ log K log*K) = O(K log * K), log*k (log star k) 基本上可以认为是一个constant，所以总时间复杂度约等于O(N).

lz帖的第一个implementation的复杂度是O(XD)的。

补充内容 (2015-10-1 12:08):
写错了……我想说的是disjoint set的复杂度是O(N logN log*N) ~ O(N logN), N是总共有多少个leaf。我不觉得这题能有O(N)的算法吧……

Laurinda93 发表于 2015-10-1 10:12
可是感觉UF的话memory或者runtime会不符合要求啊？sry我可能没截上，这两个都有要求限制，好像是O(N)我记 ...

我上一个回复写错了……我想说的是disjoint set的复杂度是O(N logN log*N) ~ O(N logN), N是总共有多少个leaf。我不觉得这题能有O(N)的算法吧……

第一个N是process所有的leaf，logN是找当前这个leaf的左边和右边最近的leaf，log*N是disjoint set操作。

补充内容 (2015-10-1 12:12):
时间复杂度是O(N logN log*N)，空间复杂度是O(min{N, X})。所以肯定是比lz贴的时间复杂度O(XD)空间复杂度O(X)的solution要好的，如果那个解法符合要求的话，并查集肯定也符合要求吧……

lz能在墙外网盘再放一遍吗？Google Drive公开链接/Dropbox啥的。。下了百度速度太慢。。。一下午都没下下来。。。

O(N logN log*N) implementation

1.    
   
2. public static int frogJump(int[] arr, int X, int D) {
   
3. 
   
4.         class DisjointSet {
   
5. 
   
6.             private java.util.concurrent.ConcurrentSkipListMap<Integer, Integer> parent;
   
7. 
   
8.             public DisjointSet() {
   
9.                 parent = new java.util.concurrent.ConcurrentSkipListMap<>();
   
10.             }
    
11. 
    
12.             public boolean check(int x, int y) {
    
13.                 return findRoot(x) != -1 && findRoot(x) == findRoot(y);
    
14.             }
    
15. 
    
16.             public void addLeaf(int x) {
    
17.                 parent.put(x, x);
    
18.                 if (0 < x && x < X) {
    
19.                     int other = parent.lowerKey(x);
    
20.                     if (x - other <= D) {
    
21.                         merge(x, other);
    
22.                     }
    
23.                     other = parent.higherKey(x);
    
24.                     if (other - x <= D) {
    
25.                         merge(x, other);
    
26.                     }
    
27.                 }
    
28.             }
    
29. 
    
30.             public int findRoot(int x) {
    
31.                 if (parent.get(x) == null) {
    
32.                     return -1;
    
33.                 }
    
34.                 if (parent.get(x) == x) {
    
35.                     return x;
    
36.                 }
    
37.                 int ans = findRoot(parent.get(x));
    
38.                 parent.put(x, ans);
    
39.                 return ans;
    
40.             }
    
41. 
    
42.             public void merge(int x, int y) {
    
43.                 int rx = findRoot(x);
    
44.                 int ry = findRoot(y);
    
45.                 parent.put(ry, rx);
    
46.             }
    
47.         }
    
48.         // end of disjoint set definition
    
49. 
    
50.         if (X <= D) {
    
51.             return 0;
    
52.         }
    
53. 
    
54.         DisjointSet ds = new DisjointSet();
    
55.         ds.addLeaf(0);
    
56.         ds.addLeaf(X);
    
57. 
    
58.         for (int i=0; i<arr.length; i++) {
    
59.             ds.addLeaf(arr[i]);
    
60.             if (ds.check(0, X)) {
    
61.                 return i;
    
62.             }
    
63.         }
    
64.         return -1;
    
65.     }
    

复制代码

补充内容 (2015-10-2 07:50):
再稍微优化一下，不处理重复的leaf的话，就是O(N logK log*K)了，K = min{X, N}

稍微改了下处理重复叶子的问题。现在应该是O(N logK log*K)了，K = min{X, N}

1.    
   
2. public static int frogJump(int[] arr, int X, int D) {
   
3. 
   
4.         class DisjointSet {
   
5. 
   
6.             private java.util.concurrent.ConcurrentSkipListMap<Integer, Integer> parent;
   
7. 
   
8.             public DisjointSet() {
   
9.                 parent = new java.util.concurrent.ConcurrentSkipListMap<>();
   
10.             }
    
11. 
    
12.             public boolean check(int x, int y) {
    
13.                 return findRoot(x) != -1 && findRoot(x) == findRoot(y);
    
14.             }
    
15. 
    
16.             public boolean addLeaf(int x) {
    
17.                 if (parent.containsKey(x)) {
    
18.                     return false;
    
19.                 }
    
20.                 parent.put(x, x);
    
21.                 if (0 < x && x < X) {
    
22.                     int other = parent.lowerKey(x);
    
23.                     if (x - other <= D) {
    
24.                         merge(x, other);
    
25.                     }
    
26.                     other = parent.higherKey(x);
    
27.                     if (other - x <= D) {
    
28.                         merge(x, other);
    
29.                     }
    
30.                 }
    
31.                 return true;
    
32.             }
    
33. 
    
34.             public int findRoot(int x) {
    
35.                 if (parent.get(x) == null) {
    
36.                     return -1;
    
37.                 }
    
38.                 if (parent.get(x) == x) {
    
39.                     return x;
    
40.                 }
    
41.                 int ans = findRoot(parent.get(x));
    
42.                 parent.put(x, ans);
    
43.                 return ans;
    
44.             }
    
45. 
    
46.             public void merge(int x, int y) {
    
47.                 int rx = findRoot(x);
    
48.                 int ry = findRoot(y);
    
49.                 parent.put(ry, rx);
    
50.             }
    
51.         }
    
52.         // end of disjoint set definition
    
53. 
    
54.         if (X <= D) {
    
55.             return 0;
    
56.         }
    
57. 
    
58.         DisjointSet ds = new DisjointSet();
    
59.         ds.addLeaf(0);
    
60.         ds.addLeaf(X);
    
61. 
    
62.         for (int i=0; i<arr.length; i++) {
    
63.             if (ds.addLeaf(arr[i]) && ds.check(0, X)) {
    
64.                 return i;
    
65.             }
    
66.         }
    
67.         return -1;
    
68.     }

复制代码

tldxk 发表于 2015-10-2 07:32
lz能在墙外网盘再放一遍吗？Google Drive公开链接/Dropbox啥的。。下了百度速度太慢。。。一下午都没下下来 ...

这两天好多面试忙得有点晕，不出意外地话 我周六做完一个OA,应该会再来写个面经，到时候还要传不少东西，我到时候一起OK吗？

谢谢楼主整理啊，今天申请就给发了OA，还有好多题目没刷。。。