Hello leetcoders,
I recently failed my 60 minute long phone screen with GS, let me reveal the tasks:
1st question:
Given an 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.
int lengthOfCycle(int[] arr, int startIndex) {
// todo
}Examples:
lengthOfCycle([1, 0], 0); // 2
lengthOfCycle([1, 2, 0], 0); // 3
lengthOfCycle([1, 2, 3, 1], 0); // 3That 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 (https://leetcode.com/problems/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):
solution
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;
assert lengthOfCycleFloydTortoiseAndHare(new int[]{1, 2, 0}, 0) == 3;
assert lengthOfCycleFloydTortoiseAndHare(new int[]{1, 0}, 0) == 2;
assert lengthOfCycleFloydTortoiseAndHare(new int[]{1, 2, 3, 1}, 0) == 3;
assert lengthOfCycleFloydTortoiseAndHare(new int[]{1, 2, 3, 4}, 0) == -1;
assert lengthOfCycleFloydTortoiseAndHare(new int[]{1, 2, 3, 4}, -1) == -1;
assert lengthOfCycleFloydTortoiseAndHare(new int[]{1, 2, 3, 4}, 4) == -1;
assert lengthOfCycleFloydTortoiseAndHare(new int[]{2, 3, 4, 0}, 0) == -1;
assert lengthOfCycleFloydTortoiseAndHare(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 currentInd = startInd, idx = 0;
while (currentInd < arr.length) {
if (map.containsKey(arr[currentInd])) {
return idx - map.get(arr[currentInd]);
}
map.put(arr[currentInd], idx++);
currentInd = arr[currentInd];
}
return -1;
}
// UPDATE -------------
// Here's another solution using Floyd's Tortoise and Hare pointers!
// Not very easy to come up with, especially during the interview, though good to know
// Special thanks to @Sithis for the idea!
public static int lengthOfCycleFloydTortoiseAndHare(int[] arr, int startInd) {
if (startInd < 0 || startInd >= arr.length) {
return -1;
}
int slow = arr[startInd];
int fast = arr[arr[startInd]];
// trying to detect a cycle at first
while (slow != fast) {
// out of bounds - no cycle
if (fast >= arr.length) {
return -1;
}
slow = arr[slow];
fast = arr[arr[fast]];
}
// yes, there is a cycle for sure, we need to find the starting point
fast = 0;
while (fast != slow) {
fast = arr[fast];
slow = arr[slow];
}
// okay, we have found the starting point, so move away from it again and count the length of the cycle
int length = 1;
slow = arr[slow];
while (fast != slow) {
length++;
slow = arr[slow];
}
return length;
}Also, I was hoping that my first solution will be eventually considered as a "half-correct", but it wasn't.