growth interview questions shared by candidates
Given a file of 4 billion 32-bit integers, find any integer that does not appear in the file using 1GB of memory. Then repeat the same task using 80MB of memory.
For 1GB: Create a boolean array (1 bit per entry) of size 4 billion + 1, initialized to false. Read the whole file. For each integer, if it's in the range 0 - 4 billion, set the array value to true. Then find any array value which is false (since the array size is 4 billion + 1 and the input is size 4 billion there is guaranteed to be one which is false). For 80MB: Read the file in 80MB chunks and sort each chunk. Write each sorted chunk to a new file with an index (e.g. filename for i'th file = file_i). Then perform an n-way merge on the files, where n is the number of files. Then read the resulting merged file and find any 2 integers which are not consecutive and return any value in the gap. If all numbers are consecutive, return either of the endpoints (plus or minus 1).
It's good to see that Ritual are continuing with the puzzle questions that Google ridded themselves of 5 years ago. *sarcasm off*