CareerCup

Was the interviewer completely bonkers?

This is the Rabbit sequence, with a twist, a difficult mathematical problem (for closed form) to solve in an interview for software developers.

For N>1 A(N) is a prefix of A(N+1) and the remaining part is an element of { A(i) with i >0 }.
The proposed solution consists in removing the prefix, recursively.

static char get(int N, int i) {
        if (N == 1) return "()".charAt(i);
        else return "(())()".charAt(cut(4, 6, i));
    }

    static int cut(int a, int b, int i) {
        int n = a + b;
        if (i >= n) i = cut(b, n, i);
        return i >= b ? i - b : i;
    }

Tested against the brute force solution.