Given a file containing at most ten million 7-digit integers with no duplicates. What is an efficient way to print these numbers in ascending order using just 1.5MB RAM and reading the data just once? What if duplicates were permitted?
I have come across above question at google but id not find any relevant answer. Based on google research/answers and my understanding I believe this can be approach and algorithm(consider the language as Java though it does not matter for most of the points) with specific queries against each point
Assuming any integer is 4 byte integer in java. I do not think length(like 7 digit or 6 digit) should matter here ?
Number of integers that can be accomodated under 1.5 MB ram = 1.5/4 = 375k (where 4 represents the 4 byte integer) which comes out to be .3 million integers. It means .3 million integers can be sorted in one go under 1.5 MB memory
Now sort first .3 million integers in memory and write them in temp file.
Pick another lot of .3 million and do merge sort of this with temp file created in step 3 and create new temp file. Delete the one in step 3.
Repeat step 4 till the process is complete i.e. 10/.3= 34 times.
Is this algorithm correct ? If yes I am not how allowing duplicates will impact here ?