Hi Guys,
I gave my google interview last year and got screwed by this one super difficult queation. I took the entire time to just understand what the questions is, and will try my best to summarize it here. Hope I get some directions on it.

So, there is a huge file having array of 8 bit numbers. We need to find a sub array of which is the smallest sub sequence that is missing in this file (i.e the sub sequence is not present as a sub array in this file).
Eg: 0,2,3 : Ans: {1} ( {1} is the subarray which is the smallest sub sequence missing)
Eg : 0,1,2 Ans : {0,0} ( all sequence of size 1 are present but first sequence of sub array size 2 i.e {0,0} is missing)

I took a lot of time to understand what is the definition of the sub sequence. Also, since it is 8 bits the number can be max value of 255 (thats what the interviewer said, although i believe the max value should be 11111111 i.e 256).

We discussed the brute force way i.e create all subsequence permutations from size 1 to N , and check if that subarray is present in that array, the first missing one is the answer, but this would be exponential running time.

Close to the end, I could understand that I would somehow need to create the sub arrays of all sizes i.e 1 to N, and then sort it so that this array has subsequences in sorted manner, and then find the first missing one from it (my version of solution which may not be the best one).

Looking forward to some smart minds to suggest a more smarter way to parse and tranform the data so that we can reduce the running time.

Note: If anyone else has come across a similar question and feel I might have interpreted the question wrong, please feel free to comment.