Uber Software Engineer Interview Experience — A Tournament-Ranking Question and the Interviewer's Wrong Hints

The interviewer's tone was very friendly. For the second question though, I think it's genuinely hard to come up with if you haven't seen something like it before — the corner cases are rough.

I went through about six months of interview experience posts and didn't see this question anywhere. It's not even in the LeetCode Uber tag.

The problem: [1, 2, 3, 4, 5, 6, 7, 8] represents ranks, where a smaller number means a better rank. Index 0 and 1 compete, then 2 and 3, and so on. Whichever has the smaller rank number survives.

[1, 3, 5, 7]
[1, 5]
[1]

So the first question is just a simulation — pretty simple, you just output each round. Just watch out for the odd n case.

The second question asks you to generate a valid input for the first question, with the requirement that a smaller rank number must always get eliminated later than any larger rank number. It's basically an upgraded version of a certain LeetCode problem, without the n = 2^x restriction.

For example:

1 8 4 7 2 6 3 5
1, 4, 2, 3
1, 2
1

It's not that hard, but after the interview I realized the interviewer had led me down the wrong path. At the start I asked if I could iterate from the bottom up, and he said yes — but actually iterating only works cleanly when n = 2^x. Recursion would have been a lot simpler.

Later he said I didn't need to worry about the odd n case and should solve even n first. That hint was wrong too — odd n has to be handled, because n / 2 can end up odd once you go down a level.

I ended up writing an iterative version and ran out of time to fix it. Here's the answer I came up with:

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<Integer>> simu(int[] input) {
        List<Integer> cur = new ArrayList<>();
        for (int i = 0; i < input.length; i++) {
            cur.add(input[i]);
        }
        List<List<Integer>> res = new ArrayList<>();
        while (cur.size() > 1) {
            List<Integer> 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!");
    }
}