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

首先我昨天发过这份面经，但是因为其中一道题可能我的叙述不够完美，所以重新截了图发上来。我刚发现我投了LiveRamp几个职位，然后拿到两个OA的链接，抱着好奇的心态打开了第二个，发现和我昨天做的题目一样，就给你们截了个图。在这里还要说，LiveRamp真是给OA给的好快，感觉像是系统自动反应似的，不过我也不确定，因为投了三四个只收到两个OA。不过听说他家很少招全职，大都是return offer回去的，所以就做着玩儿呗。首先来介绍一下题目，两道题，一共就是10

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

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

面的时间，出现靠前位置的叶子（也就是没有帮助）
3. 每一秒掉下来的新叶子都有可能对全局进行影响，这个可以尝试画个图，就容易发现自己误解的地方

1.         public static int frogJump(int[] arr, int X, int D) {
   
2.                 if (arr == null || arr.length == 0 || X <= D)
   
3.                         return 0;
   
4. 
   
5.                 int[] rst = new int[X + 1];
   
6.                 Arrays.fill(rst, Integer.MAX_VALUE);
   
7.                 rst[0] = 0;
   
8.                 // position of leaf *AND* the earliest time reach this position
   
9.                 Map<Integer, Integer> leaf = new HashMap<>();
   
10.                 leaf.put(0, 0);
    
11.                 leaf.put(X, 0);
    
12.                
    
13.                 for (int i = 0; i < arr.length; i++) {
    
14.                         if (!leaf.containsKey(arr[i]))
    
15.                                 // the earliest time reach *position* arr[i] is *time* i
    
16.                                 leaf.put(arr[i], i);
    
17.                 }
    
18.                
    
19.                 for (int pos = 1; pos <= X; pos++) {
    
20.                         if (leaf.containsKey(pos)) {
    
21.                                 if (pos <= D) {
    
22.                                         rst[pos] = leaf.get(pos);
    
23.                                 } else {
    
24.                                         for (int step = 1; step <= D; step++) {
    
25.                                                 if (leaf.get(pos) < rst[pos - step]) {
    
26.                                                         rst[pos] = Math.min(rst[pos], rst[pos - step]);
    
27.                                                 } else {
    
28.                                                         rst[pos] = Math.min(rst[pos], leaf.get(pos));
    
29.                                                 }
    
30.                                         }
    
31.                                 }
    
32.                         }
    
33.                 }
    
34.                
    
35.                 return rst[X] == Integer.MAX_VALUE ? -1 : rst[X];
    
36.         }

复制代码

补充内容 (2015-10-1 03:22):
青蛙题目也放到云盘了，好多人说有权限看不到！希望有帮助！！！

稍微改了下处理重复叶子的问题。现在应该是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.     }

复制代码

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}

题里面不是给了四个参数吗(int[] A, int N, int X, int D)，为什么你写的只有三个参数？

现在OA都是青蛙过河的 没有city那个了么？

楼主拿到店面了吗？

oio14644 发表于 2015-9-23 08:57
题里面不是给了四个参数吗(int[] A, int N, int X, int D)，为什么你写的只有三个参数？

因为截图截得C语言，我写的Java，Java就是三个

LawranceH 发表于 2015-9-23 09:59
楼主拿到店面了吗？

嗯嗯呐已经拿到店面了，前两天通知的，约的下周