Sorting algorithm Interview Questions | Glassdoor

# Sorting algorithm Interview Questions

8

interview questions shared by candidates

## Sorting algorithm Interview Questions

Sort: RelevancePopular Date

### Software Engineer at Amazon was asked...

Dec 24, 2011
 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 AnswersWhat 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.Show More Responsesmillions is not too much , you can build a int array which have millions of cells. The array take only several mega bytes . Initialize to zero for every cell, then traverse the file and keep track of every integer by array , eg . 4789 will make array[4789]++ , this could handle duplicate number . Finally scan the array ...the interviewer is looking for the word "divide and conquer". read the n number of integers and write them in a binary tree. hold the left and right value in a datastructure which keeps track of the file an integer is written to. something like this class NumHolder { int min; int max; String fileName; } Map partInfo = new HashMap() for (int i=0; i 100000 //100000 = sum number that determines how many part files will be created. writeToOtherFileToo writeToPartFile update partInfo with this write }its called 'external sorting'... read more on wiki...divide the file in chunks, sort individuals chunks using quicksort and store in files. Then use merging step of merge sort on those saved files. This would be external sort.use external sorting algorithm similar to merge sort which splits and merges files instead of arrays in memory

### Financial Engineer at Palantir Technologies was asked...

Oct 7, 2011
 List all sorting algorithms you know and their running times.2 AnswersBubble, Insertion, Selection, Quick, Merge, HeapCounting sort, radix sort

### Analyst Developer at Goldman Sachs was asked...

Aug 20, 2010
 Name one of the more efficient sorting algorithms2 AnswersHash SortMerge Sort. Used in Java implementations for sorting. O(NlogN) runtime

### Software Development Engineer at Amazon was asked...

Jun 29, 2010
 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@1: Can you first mergesort the two arrays, and then do the following? That'll be nlogn runtime? I haven't tested it out... int i=0, j=0; while ( i sorted_array2[j] ){ j++; } else { //must be equal printf("Common element: %d\n", sorted_array1[i]); i++; j++; } }for #1 you just have to hash the first array and then if(contains) the hash table against each element of the second array O(n) # of comparisons

### Software QA Engineer Intern at Salesforce was asked...

Apr 13, 2012
 Was asked to program quick-sort in Java.1 Answervoid QuickSort(int[] arr, int low, int high) { while (low < high) { int pivot = (low+high)/2; int partition = Partition(arr, low, high, pivot); QuickSort(arr, low, partition); QuickSort(arr, partition+1, high); } } void Partition(int[] arr, int low, int high, int pivot) { // take pivot element to end swap(arr[pivot], arr[high]); int pivotElement = arr[high]; int finalPosition = 0; for (int i = low; i < high - 1; ++i) { if (arr[i] < pivotElement) { swap(arr[i],arr[finalPosition]); finalPosition++; } } // put pivot element in its "final position" swap(arr[finalPosition],arr[high-1]); }

### Sales Representative at Von Maur was asked...

Apr 2, 2010
 when did you hear about us1 Answerlast night while watching lost

### Custodian at Paschal’s Concessions was asked...

May 18, 2012
 Tell me about your wickness?1 AnswerNot getting the work done on time.

### Financial Software Developer Intern at Bloomberg L.P. was asked...

Mar 4, 2012
 How to find a number in an array of number Be the first to answer this question
18 of 8 Interview Questions