A Senior student asked me this question, probably was an interview question.But still how can we do it?
The question:
Given an i/p file with 4 billion integers produce a integer that doesnt exist in the file given u have only 10 mb memory
Asked
Active
Viewed 101 times
2
-
So there are 294967296 missing integers (assuming by integer you mean the standard 32-bit int type)? Is there a runtime requirement? If multiple passes are allowed this is quite easy. – Zong Oct 23 '13 at 14:36
-
are **O(n^2)** solutions fine? – Sam I am says Reinstate Monica Oct 23 '13 at 14:39
-
1@SamIam Knowing that n = 4,000,000,000? Your question would raise a flag during an interview… – Bolo Oct 23 '13 at 14:42
-
if you have enough external storage, just sort the numbers, then iterate over until you find a gap – Philipp Seeger Oct 23 '13 at 14:51