# Jumps of a pawn - Java interview [closed]

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.

• So if A[0] = 100000 and on the first step it jumps out of the array, your function will return 2 because it executes times ++ followed by return times+1. I don't think 2 is the correct answer for that case (I think it should be 1). I'm thinking that perhaps on every case you are returning a number 1 greater than the actual answer.
– JS1
Apr 24, 2018 at 23:10
• No it will return 0 instead, because next = N. I must return times + 1 in all situations. But the direction is correct. How to catch these corner cases..... Apr 24, 2018 at 23:21
• Ok it returns 0 for no jump, but if it jumps once it will return 2. So there's still something wrong because it can never return 1.
– JS1
Apr 25, 2018 at 11:58
• So I mean instead of returning times at last, return times + 1. Apr 26, 2018 at 0:13
• Does the code function correctly? If not, it isn't ready for review (see help center) and the question may be deleted. If you've tested it, I recommend that you edit to add a summary of the testing - ideally as reproducible unit tests. May 9, 2018 at 9:25

    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.

• Technically this is a question about faulty code and thus off topic (it will probably be closed soon). We shouldn't answer off-topic questions to prevent people from asking them anyway hoping to get an answer before it's closed. On the other hand this answer does provide a nice review about the code as if it would be working and most likely solves the errors as a side effect. So I'm upvoting this anyway while voting to close the question :)
– Imus
Apr 25, 2018 at 8:12
• @imus Thanks for giving the reason why the downvote, first time here sorry. So this is more of a "check my style" not a "check my fault" forum.. I thought both will do. And thanks @Josiah, I think what you said is valid. 1) I don't remember why I use Map, but the req was not that rigid about the size, but the "path space" tip is useful. 2)the comment was added when I reviewed my first version of code, I missed the "index < 0" case, so I added them and fixed the code. 3) print was not necessary, agree; the web reminds me of that, too. 4) next` should be index, not index-1, correct. Apr 25, 2018 at 8:37