uber software engineer tech phone screen: simulation and input generation challenges

烙印语气很友善 第二题我认为 没做过的话很难想到 corner case 难搞

我看了近6个月面经 没看到这一题

也不是leetcode uber tag

题目是 [1, 2, 3, 4, 5, 6, 7, 8] 代表rank，数字越小rank约大

然后 index 0, 1 比赛，2,3比赛 。。。

保留rank数字小的

[1, 3, 5, 7]

[1, 5]

[1]

所以第一题是simulation, 很简单，output每一步就行，注意odd n的情况

第二题是让你生成第一题的input，要求是保障数字小的rank得比数字大的rank晚elimite

其实就是利口舞斯斯的升级版，没有 n = 2^x  的限制

比如

1 8 4 7 2 6 3 5

1, 4, 2, 3,

1, 2

1

没有那么难  但是面完我发现被烙印带沟里去了

我一开始我问能不能从下往上iterate，他说可以, 其实只有n = 2^x的情况才iterate比较好写

recursion会简单很多

后来他说不用关心odd n情况，先解决even n，-> 这个hi...

烙印语气很友善 第二题我认为 没做过的话很难想到 corner case 难搞

我看了近6个月面经 没看到这一题

也不是leetcode uber tag

题目是 [1, 2, 3, 4, 5, 6, 7, 8] 代表rank，数字越小rank约大

然后 index 0, 1 比赛，2,3比赛 。。。

保留rank数字小的

[1, 3, 5, 7]

[1, 5]

[1]

所以第一题是simulation, 很简单，output每一步就行，注意odd n的情况

第二题是让你生成第一题的input，要求是保障数字小的rank得比数字大的rank晚elimite

其实就是利口舞斯斯的升级版，没有 n = 2^x  的限制

比如

1 8 4 7 2 6 3 5

1, 4, 2, 3,

1, 2

1

没有那么难  但是面完我发现被烙印带沟里去了

我一开始我问能不能从下往上iterate，他说可以, 其实只有n = 2^x的情况才iterate比较好写

recursion会简单很多

后来他说不用关心odd n情况，先解决even n，-> 这个hint也不对，odd n必须解决，因为 n / 2 可能到下层就是odd

后面iterate写了一版来不及改了

答案我贴出来

public class Main {

public static int[] getInput(int n) {

if (n == 1) {

return new int[]{1};

}

if (n == 2) {

return new int[]{1, 2};

}

int[] res = new int[n];

if (n % 2 == 0) {

int[] pre = getInput(n / 2);

for (int i = 0; i < pre.length; i++) {

res[i * 2] = pre[i];

}

int idx = 1;

for (int i = n ; i >= n / 2 + 1; i--) {

res[idx] = i;

idx += 2;

}

} else {

int[] pre = getInput(n / 2 + 1);

for (int i = 0; i < pre.length; i++) {

res[i * 2] = pre[i];

}

int idx = 1;

for (int i = n ; i >= n / 2 + 2; i--) {

res[idx] = i;

idx += 2;

}

}

return res;

}

private static List<List> simu(int[] input) {

List cur = new ArrayList<>();

for (int i = 0; i < input.length; i++) {

cur.add(input[i]);

}

List<List> res = new ArrayList<>();

while (cur.size() > 1) {

List next = new ArrayList<>();

for (int i = 0; i <= cur.size() - 2; i += 2) {

next.add(Math.min(cur.get(i), cur.get(i + 1)));

}

if (cur.size() % 2 != 0) {

next.add(cur.get(cur.size() - 1));

}

cur = next;

res.add(cur);

}

return res;

}

public static void main(String[] args) {

int[] res = getInput(13);

for (int i = 0; i < res.length; i++) {

System.out.print(res[i] + " ");

}

System.out.println(simu(res));

System.out.println("Hello World!");

}

}