6

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

  1. Assuming any integer is 4 byte integer in java. I do not think length(like 7 digit or 6 digit) should matter here ?

  2. 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

  3. Now sort first .3 million integers in memory and write them in temp file.

  4. 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.

  5. 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 ?

Improve this question
10

3 Answers 3

Reset to default
11

I would say you could use a bit field. That is you use one bit for each number from 0 to 9,999,999. This is 1.25 MByte of RAM.

You read the file once and mark the corresponding bit when a number is read. Then in the second pass you walk over the bitfield and print the index to all entries that have the bit set. This works because you know that there are no duplicates. The maximum 10,000,000 is just a consequence of that. The algorithm works with any number of numbers.

Regarding the question what happens if there are duplicates permitted, it is not clear to me whether one should also print the duplicates or just the numbers. The latter case will of course also work, the former not - it needs to store additional information.

Improve this answer
7
  • 2
    @DocBrown: I just did. Well, the OP made some effort on his own and did not just purely copy-and-paste. Perhaps giving a hint like gnasher729 would have been more appropriate, but I also misunderstood it until I calculated the 1.25MB and knew the solution already. I fully agree with the open letter, but see the responsibility for their education with the students themselves. Cheating in homework will affect them in the next written exam, and at college level one should know that.
    – Andreas H.
    Sep 3, 2018 at 15:23
  • 1
    This just kicks the can down the road - if the integer count increases a bit more (or their range increases, or they become floats), you won't have enough space for the bits anymore.
    – Aganju
    Sep 3, 2018 at 15:31
  • 2
    regardless of the 'not answering questions based on the supposed motive of the asker' policy, it's sad to see a correct answer on negative votes
    – Ewan
    Sep 3, 2018 at 15:52
  • @AndreasH. I was looking for same kind of direction. I believe you meant create array where value will be 1 bit i.e. either 0(or null) or 1. Now go through file , read the value and mark the corresponding index as 1. Right ? But in java we have docs.oracle.com/javase/7/docs/api/java/util/BitSet.html for the same that contain boolean value to represent bit. In java boolean array(see stackoverflow.com/questions/1907318/…) takes 1 byte. Does it mean in java it will take 1.5*8= 12MB of memory instead of 1.5 MB ?
    – M Sach
    Sep 4, 2018 at 4:34
  • @MSach: 1) yes. 2) a byte array of size 10'000'000 will take 10 MB. BitSet sounds like the appropriate thing to me. However, from the docs it seems not to be guaranteed that BitSet is actually implemented as a bit set (and thus only 1.25 MB for 10e6 size). Practically it probably will work as expected.
    – Andreas H.
    Sep 4, 2018 at 7:25
3

10 million 7 digit numbers with no duplicates sorted are: 0, 1, 2, 3, ..., 9,999,999.

Hope that gives you a hint for fewer than 10 million, using 1.25 MB of memory and running in linear time.

Improve this answer
3
  • i thought that, but then it says "at most"
    – Ewan
    Sep 3, 2018 at 14:46
  • This answer gives the answer without giving the real answer.
    – Pieter B
    Sep 3, 2018 at 14:54
  • Is 1 a "7-digit integer"? That's why I hate these quickie interview questions. And "Merge Sort" would be my quickie answer.
    – user949300
    Sep 3, 2018 at 15:45
0

Your algorithm cannot work, because the temp file gets larger every time, and you will soon be back to running out of memory.

Think about an approach where you divide the total range of the numbers into accordingly sized 'buckets', and assign one file per bucket.
Then read a bunch, assign them to their buckets, and append them to the respective 'bucket' files.
After one run through all numbers, you have now bucket files that you can each read and completely sort in memory (assuming you picked the right bucket size), and print in the right order. Most importantly, you can be sure that a later bucket does not contain a number you would have needed to print alread now.

Improve this answer
2
  • 1
    Temp file will be on hard disk. So main memory(RAM) will not be running out of memory ?
    – M Sach
    Sep 4, 2018 at 2:21
  • In your step 4, you want to merge the next batch into the temp file. For that, you have to read it back in.
    – Aganju
    Sep 4, 2018 at 4:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.