Sorting algorithm Interview Questions | Glassdoor

Sorting algorithm Interview Questions

8

interview questions shared by candidates

Sorting algorithm Interview Questions

Sort: Relevance Popular Date

If you have a file containing millions of integers, how would you sort the data in the file using extremely limited resources, such a s 1GB of memory?

8 Answers

What was the answer? In my opinion, I would answer this way: Sort each x integers (x is the number of integers that the memory can hold) then save it to the a file (n files) . Then for each file maintain a current index initiated with 0. Loop through n file and take the max integer, put it into the result file, and increase the file's current index to one. Continue doing it till the end.

An integer is only 4 bytes! I am just saying, a million integers should consume about 4 MB of memory, and easily fit in 1 GB! So "millions" had better be closer to a quarter billion if memory is an issue. OK, to answer the intended question, I would solve it with statistics. Compute bucket ranges by using a random subset of the file, with bucket size chosen such that the expected portion of the entire file will fit within the memory available. Divide the file into these buckets, and sort the buckets individually. Concatenate the sorted buckets to create a single sorted file.

To Kurt: You missed one step. Concatenating buckets will not make a sorted list. You have to merge the buckets. However, for merging you do not necessarily have to load the whole bucket into memory.

List all sorting algorithms you know and their running times.

2 Answers

Name one of the more efficient sorting algorithms

2 Answers

1. Find common elements between two arrays of integers. 2. Find cycles in a graph. 3. Efficiently find duplicate elements in an array of numbers with bounded entries (for example, elements are between 0 and 99). 4. Reverse word sequence in a string inplace. 5. Efficiently find all Pythogorean triplets in a given array of integers. 6. Find all anagrams in a list of words. 7. Set operations.

2 Answers

Was asked to program quick-sort in Java.

1 Answer

when did you hear about us

1 Answer

Tell me about your wickness?

1 Answer
18 of 8 Interview Questions