Jumps of a pawn - Java interview [closed]

Question

I have just attended a code test of some code testing site, and I think one question seems easy but I didn't get a high correctness, so if anyone can review this code snippet, I would appreciate it.

In summary:

Given an array A, with dimension N, 1<=N<=100000, A[N] within range of [-100000, 100000]. At first there is a pointer at position K (in the beginning K=0), and M=A[K], and we say the pointer will jump to position A[K+M], and call this a "jump of a pawn`. If at any moment, the pointer jumps out of the array, we must return the steps of jumps it takes. If it will never jump out, return -1.

class Solution {
    public Solution() {}

    public int solution(int[] A) {

        int next = A[0] + 0;
        int N = A.length;
        Map<Integer, Integer> count = new HashMap<Integer, Integer>();
        for (int i=0; i<N; i++) {
            count.put(i, 0);
        }

        count.put(0, 1); //already pass position 0 once
        int times = 0;
        while (next < N && next >= 0) { /* next index can be negative!!!!! Error!!!! */
            times ++;
            next = A[next] + next;
            System.out.println("Now the next index is: " + next);

            if (next >= N || next < 0) { /* next index can be negative!!!!! Error!!!! */
                System.out.println("Now jump out. ");
                return times+1;
            }
            count.put(next, count.get(next) + 1);
            if (count.get(next) > 1) {
                System.out.println("Repeated index " + next + ", will not jump out");
                return -1;
            } else {
                continue;
            }

        }
        return times + 1; //edited
    }
}

EDIT:

With this version I know that it is higher than 57% (original result of the quiz), but I cannot say it is 100% because I don't have all the test cases used in evaluation.

Answer 1

    Map<Integer, Integer> count = new HashMap<Integer, Integer>();
    for (int i=0; i<N; i++) {
        count.put(i, 0);
    }

This will consume memory linearly in the size of the array. I don't know what constraints you have on memory, but this doesn't seem like the best use of it.

1. If your average path through the array is short and memory is not at a premium, use a HashMap but do not pre-populate it with zero. That way you're actually allocating memory in proportion to the length of the path rather than the length of the array.
2. If your typical path through the array visits a significant proportion of the cells in the array, and memory is not at a premium, just use a Boolean array to store whether a cell has been visited. Arrays will be cheaper than HashMaps.
3. If you cannot really afford the memory to store the visited cells, have a look at the "hare and tortoise" algorithm for cycle finding.

/* next index can be negative!!!!! Error!!!! */

This comment appears twice, but it seems unhelpfully alarming to me. You're guarding the next index value to check whether it is within the array; you're handling both negative and excessive index values the same. That isn't an error.

System.out.println("Now the next index is: " + next);

Although useful for debugging, a function like this should not continually print out its progress. That just slows down running and annoys the person using it. (More generally, a function like this should probably avoid having any side effects.)

else {
    continue;
}

This is redundant. The loop would continue anyway.

int next = A[0] + 0;

As JSI mentioned in a comment, this is a bit confusing. It would be better to use the loop logic for all cases if you possibly can, rather than coding special cases outside. You could just start with int next = 0 (as if you're just about to jump into the array). This would let you simplify things, like having times be the actual number of jumps and therefore letting the first return clause just be return times; As written I do think the algorithm is wrong. If the first jump takes you out of the array, it will return 0 when it should return 1. The edge case you do need to handle expressly is the case where the size of the input array is 0.