View All num of num See all Photos Google This employer has taken extra steps to respond to reviews and provide job seekers with accurate company information, photos, and reviews. Interested for your company?Learn More. www.google.com Work in HR? Unlock Free Profile Overview Reviews Salaries Interviews Jobs Photos Benefits 2.9k Reviews 11k Salaries 3.6k Interviews 1.9k Jobs Follow Add Review or Salary Follow Add Review or Salary Interview Question New Grad Software Engineer Interview(Student Candidate) Google Sort a million 32 bit integers using only 2MB of RAM Tags: See more , See less 8 Answer Add Tags Flag as Inappropriate Thank you! Your feedback has been sent to the team and we'll look into it. Oops! We're sorry but your feedback didn't make it to the team. Your input is valuable to us — would you mind trying again? Send Answer Interview Answer 2 Answers ▲ 10 ▼ 1 million integers = 4MB which is > 2MB RAM.solution: external sort - divide and conquer1. read half the list into 2MB ram and sort using quicksort (quicksort uses logn space - however 0.5m integers is less than 2MB (2000kb v 2048kb) so this should be okay).2. write sorted data to disk3. repeat for next chunk4. merging results: we need an output buffer. lets say this is 1MB. then we read 512KB from each of your chunks into input buffers. we then perform a 2-way merge of the data. when an input buffer becomes empty we can pull in the remainder of the chunk.5. when the output buffer is full we write this to disk.6. when the process completes we are left with 2x 1MB files sorted in the correct order.notes:- when choosing an input buffer size, the smaller we make it the more I/O operations we will need to perform which would significantly slow down our sorting. a smaller output buffer would also do the same. we would rather a smaller output buffer as multi-threading would allow sorting to continue while writing to disk.- we could use an additional thread to load next chunk from disk when input buffer drops below half size.- HDD mirror raid would increase sequential read and write speed to disk as well as HDD speed- compression of input would also reduce I/O- we choose quicksort over mergesort as mergesort requires O(n) space. quicksort therefore reduces the number of merge operations. Anonymous on 2010-11-09 Flag as Inappropriate Thank you! Your feedback has been sent to the team and we'll look into it. Oops! We're sorry but your feedback didn't make it to the team. Your input is valuable to us — would you mind trying again? Send ▲ 0 ▼ 1) divide those integers into 5 equal set of numbers, so each set is less than 2MB (very important for later)2) sort them using qsort or something3) find the medium of all those 5 sets4) then you are left with arrays with followingie:... 2, 5, 7, (10), 13, 14, 19...... 4, 5, 9, (12), 19, 20, 33...... 1, 2, 10, (14), 22, 23, 43... <= medium of mediums... 10, 11, 12, (17), 19, 20, 35...... 1, 2, 19, (21), 24, 29, 33...where everything left and above medium of mediums(14) is smaller than 14, and everythign right and bleow medium of mediums(14) is larger than 14.then, you merge everything left and above of 14 to a set of number smaller than 14 (samller set), you merge everything right and below to a set of sorted number which larger than 14 (larger set)then you sort remaining two group of numbers (right below and left above), take numbers smaller than 14 to merge with smaller set, and take numbers larger than 14 to merge with larger set. Anonymous on 2010-11-12 Flag as Inappropriate Thank you! Your feedback has been sent to the team and we'll look into it. Oops! We're sorry but your feedback didn't make it to the team. Your input is valuable to us — would you mind trying again? Send Add Answers or Comments To comment on this, Sign In or Sign Up.