Google US phone screen experience l4/l5
Recently had a phone screen with this question: find min substring length not found in 4gb file. I was pretty thrown off by this, none of my standard leetcode prep made me face something like this.
I suggested brute force with hashing but was quickly redirected. I was told the min substring length was within five or so. At the moment my intuition couldn't figure out why so I suggested coding up something and later proving the constraint but was redirected towards the proof.
I then spent quite a bit of time drawing out the examples. I was hinted to draw out an example and try to make all substrings within an shorter string using just a and b but I couldn't do it. I thought it might be due to some prefix suffix graph but I was then hinted to use pigeonhole principle.
From there i wrote out the equation and indicated max iterations for which we are guaranteed to have a missing substring. I was also hinted that I could use a bitset, though i didn't ask for this hint.
After, I suggested coding but this was around the 38 minute mark. I was told it was OK and that it was just a technical discussion. I feel code was simple and I could have coded it but at the time I was nervous so I just decided to continue. Later, I was asked what I would do if file was larger than 8gb, and I suggested making multiple passes through the file and clearing the bitset, and making sure every number in the bitset range was met and my interviewer seemed satisfied. Ultimately, I was not able to write out any code for the programming interview.
What could I have done differently to improve? And what can I do to practice these kinds of questions with large disk files? I certainly didn't expect it.