I recently failed my 60 minute long phone screen with GS, let me reveal the tasks:
1st question:
lengthOfCycle(arr, startInd)
integer array of size N.
Elements of the array is >= 0.
Starting from arr[startInd], follow each element to the index it points to.
Find a cycle and return its length. No cycle is found -> -1
Example:
lengthOfCycle([1, 0], 0) == 2
lengthOfCycle([1, 2, 0], 0) == 3
lengthOfCycle([1, 2, 3, 1], 0) == 3
That was the one I struggled the most. Also, my line was not good and I experienced periodic breaks.
Honestly not the best thing for concentration.
After half of the hour, the interviewer suggested switching to another one. I ended up with a for loop and a HashSet for tracking indices. But it didn’t work correctly for all cases.
2nd question:
Similar to trapping rain water
That one was familiar to me, so I figured out brute force (nested for loops) very fast.
However I didn’t code the optimized version, since I wanted to complete my 1st problem solution, maybe that had a negative impact.
Only after I left the line I was able to figure out the correct solution for the first one (I hope):
public static void main(String[] args) {
assert lengthOfCycle(new int[]{1, 2, 0}, 0) == 3;
assert lengthOfCycle(new int[]{1, 0}, 0) == 2;
assert lengthOfCycle(new int[]{1, 2, 3, 1}, 0) == 3;
assert lengthOfCycle(new int[]{1, 2, 3, 4}, 0) == -1;
assert lengthOfCycle(new int[]{1, 2, 3, 4}, -1) == -1;
assert lengthOfCycle(new int[]{1, 2, 3, 4}, 4) == -1;
assert lengthOfCycle(new int[]{2, 3, 4, 0}, 0) == -1;
assert lengthOfCycle(new int[]{2, 3, 0}, 0) == 2;
}
public static int lengthOfCycle(int[] arr, int startInd) {
if (startInd < 0 || startInd >= arr.length) {
return -1;
}
Map<Integer, Integer> map = new HashMap<>();
map.put(0, -1);
int i = startInd;
while (i < arr.length) {
if (map.containsKey(arr[i])) {
return i - map.get(arr[i]);
}
map.put(arr[i], i);
i = arr[i];
}
return -1;
}
Also, I was hoping that my first solution will be eventually considered as a “half-correct”, but it wasn’t.