## Sorting Interview Questions

- -4of 6 votes

AnswersIn what situations bubble sort, selection sort, insertion sort, merge sort, quick sort and heap sort will have best time complexity. Provide example for each sort and explain

- sivaji8 September 28, 2013 in United States| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Sorting - 0of 0 votes

AnswersGiven a list of test results (each with a test date, Student ID, and the student’s Score), return the Final Score for each student. A student’s Final Score is calculated as the average of his/her 5 highest test scores. You can assume each student has at least 5 test scores.

You may use the JDK or the standard template library. The solution will be evaluated on correctness, runtime complexity (big-O), and adherence to coding best practices. A complete answer will include the following:

Document your assumptions

Explain your approach and how you intend to solve the problem

Provide code comments where applicable

Explain the big-O run time complexity of your solution. Justify your answer.

Identify any additional data structures you used and justify why you used them.

Only provide your best answer to each part of the question.

Use the following skeleton for your solutions.

Java:

- aopencv June 16, 2013 in United States`class TestResult { int studentId; String testDate; int testScore; } public class FinalScoreQuestion { Map <Integer, Double> calculateFinalScores (List<TestResult> results) { }`

| Report Duplicate | Flag | PURGE

Amazon SDE1 Algorithm Java Problem Solving Sorting - 0of 0 votes

AnswersMerge the given 2 input sorted arrays of numbers into one . The merged array stays sorted .

- meek May 31, 2013 in United States| Report Duplicate | Flag | PURGE

Amazon Software Engineer in Test Arrays Java Problem Solving Sorting - -5of 7 votes

Answersneed to implement a weather report functionality. user will provide the city name , need to return the weather report.

- gopi.komanduri May 29, 2013 in India

if weather station exists n functioning properly , will return the weather report of that station .

else ,

will return the nearest available weather station report.

interviewer looking for optimized manner.

looking for datastructures to stores the cities n algo to return the report.| Report Duplicate | Flag | PURGE

Mentor Graphics Analyst Algorithm Arrays Bit Manipulation Brain Teasers C C# C++ Cache Coding Computer Architecture & Low Level Data Mining Data Structures Dynamic Programming General Questions and Comments Graphics Hash Table Ideas Linked Lists Math & Computation Object Oriented Design Problem Solving Sets Sorting Stacks String Manipulation Terminology & Trivia Threads Trees and Graphs XML - 0of 0 votes

Answersmerge two unsorted linked-list into one new sorted linked list, off course in a efficient way

- nguptak February 15, 2013 in United States| Report Duplicate | Flag | PURGE

Software Engineer / Developer Linked Lists Sorting - 2of 2 votes

AnswersI have 10 million 10-bit integers to sort, how would you sort them and what's the time complexity?

- chriscareercup November 12, 2012 in United States

Follow-on question: Instead of sorting integers, I now have 10 million pairs to sort. Each pair consists of a 10-bit integer and an object, the sort order is determined by the 10-bit integer. Will your original sort algorithm hold or do you need sort it differently?

(A word of advice: Ask as many questions as you want during the interview, but you MUST be quick. Also, don't mention anything until you've thought it through clearly, otherwise you're just inviting more questions. Time is of essence, you're too slow if this question takes you more than 15 minutes to come up with the optimal solution, because remember, you have to leave time for explanations and other questions)| Report Duplicate | Flag | PURGE

Amazon Software Engineer / Developer Sorting - 1of 1 vote

AnswersWe have n number of sorted array for fixed length.

- Harsh123 November 04, 2012 in India for Kindle

Now we have to merge these and need to save finaly result array into given array.

Note- we can't use extra space except the given array.| Report Duplicate | Flag | PURGE

Amazon Software Engineer / Developer Algorithm Arrays Data Structures Sorting - 0of 0 votes

Answers(screening round)

- eyeonu.imtiyaz October 30, 2012 in United States

Given two sorted arrays, merge them into result array with sorting. Time and Space Complexity.| Report Duplicate | Flag | PURGE

Amazon Software Engineer / Developer Sorting - 1of 1 vote

AnswersGiven an array containing sequence of bits (0 or 1), you have to sort this array in the ascending order i.e. all 0' in first part of array followed by all 1's. The constraints is that you can swap only the adjacent elements in the array. Find the minimum number of swaps required to sort the given input array.

- Ankit October 29, 2012 in India

Example: Given the array (0,0,1,0,1,0,1,1) the minimum number of swaps is 3.

Note: You just need to complete the function given below for this task. The function is given a binary string as input and returns the required answer.| Report Duplicate | Flag | PURGE

Amazon Software Engineer / Developer Arrays Data Structures Sorting - 0of 0 votes

AnswersSort an array of characters in linear time complexity (and linear space complexity if that's possible).

- jeanclaude October 17, 2012 in United States for Kindle| Report Duplicate | Flag | PURGE

Amazon Software Engineer in Test Sorting - 0of 0 votes

AnswersWrite a method to sort an array of strings so that all the anagrams are next to each other.

- Pawan Sharma June 05, 2012 in India| Report Duplicate | Flag | PURGE

Microsoft Sorting - 0of 0 votes

AnswersIn this problem, you have to implement a variation of Insertion Sort as described below.

- dev May 27, 2012 in United States

Suppose X is an array of N positive integers to be sorted. In this scheme, another array Y is used to store the

sorted integers. This array is to be viewed as a circular array, ie. index (N-1)+1 = index 0 and index 0-1 =

index N-1. The sorted integers get stored in a circular manner in Y, ie, it is possible that the index of the

smallest integer may be greater than the index of the largest integer.

Eg. 6 8 _ _ _ 1 2 4 5 is a view of the array Y sometime into the algorithm. ’_’ indicates unused locations of

the array. Smallest integer 1 is at index 5, largest integer 8 is at index 1. So the sorted array in Y is to be

generated by printing the contents from index 5 to 1, assuming the array wraps around at the end, ie. after

index 8, the next index is 0.

Assume that h holds the index of the smallest integer in Y and t holds the index of the largest integer in Y.

Initially,

1. h = t = 0

2. Y[0] = X[0] ie. the first integer in X[] is copied as the first integer in Y[].

3. All other elements in Y[] are initialised to a dummy value -1.

The rest of the integers in X[] are now inserted one by one into Y[] such that Y[] always contains a sorted

list of integers, with the smallest integer at index h and the largest at index t. This is done in the following

manner:

Let I be the next integer from X[] to be inserted into Y[]. Scan the array Y downwards from index h (with

wrap-around at the end) till index t and find out the place in Y[] where I has to fit in. If I fits in at either end

of the list, then insert it at the appropriate place in Y[]. Modify either t or h as appropriate to indicate the new

array structure; ie. either t is incremented or h is decremented (with wrap-around).

If I fits in somewhere in the middle of the list, then I should be inserted by shifting all the S smaller integers

one place to the left or by shifting all the L larger integers one place to the right, depending on the number of

integers to be shifted. That is, if S < L, the smaller integers should be shifted one place to the left and if S >=

L, the larger integers should be shifted one place to the right. Again either h or t should be modified

appropriately.

Example

Integers to be sorted X[]: 25 57 37 48 12 92 86 33

Contents of Y[] after inserting each integer from X[]:

Initially (t=0, h=0)

25 –1 –1 –1 –1 –1 –1 –1

57 fits in at end (t=1)

25 57 –1 –1 –1 –1 –1 –1

37 fits in middle, S=1, L=1, so shift 57 right. (t=2)

25 37 57 –1 –1 –1 –1 –1

48 fist in middle, S=2, L=1, So shift 57 right. (t=3)

25 37 48 57 –1 –1 –1 –1

12 fits in at beginning, circular property, (h=8, t=3)

25 37 48 57 –1 –1 –1 12

92 fits in at end (t=4).

25 37 48 57 92 –1 –1 12

86 fits in middle, S=5, L=1, so shift 92 right, (t=5).

25 37 48 57 86 92 –1 12

33 fits in middle, S=2, L=5, so shift 12, 25 left (h=7, t=5).

33 37 48 57 86 92 12 25

Input Specification

The input will consist of a single line containing an integer N followed by the N integers to be sorted. All

integers are positive and are separated by a single space. There will be no duplicates among the N integers.

Output Specification

The output should consist of N lines, each line containing N integers. The N integers are the contents of Y[]

(ie. Y[0] to Y[N-1]) after the insertion of each integer from X[]. All integers on a line should be separated by

a single space. N will be less than 50.

Sample Input/Output

Input

8 25 57 37 48 12 92 86 33

Output

25 -1 -1 -1 -1 -1 -1 -1

25 57 -1 -1 -1 -1 -1 -1

25 37 57 -1 -1 -1 -1 -1

25 37 48 57 -1 -1 -1 -1

25 37 48 57 -1 -1 -1 12

25 37 48 57 92 -1 -1 12

25 37 48 57 86 92 -1 12

33 37 48 57 86 92 12 25| Report Duplicate | Flag | PURGE

Lunatic Server Solutions Java Developer Data Structures Sorting - 0of 0 votes

AnswersQ1. F2F Round 1 Amazon(Bangalore)

- Nitin Gupta May 12, 2012 in India

Given a character array as input. Array contains only three types of characters 'R', 'G' and 'B'. Sort the array such that all 'R's comes before 'G's and all 'G's comes before 'B's.

Constraint :- No extra space allowed(except O(1) space like variables) and minimize the time complexity.

You can only traverse the array once.| Report Duplicate | Flag | PURGE

Amazon Software Engineer / Developer Algorithm Arrays C C# C++ Coding Data Structures Java Sorting - 0of 0 votes

AnswersQ4. Written Exam Amazon(Bangalore)

- Nitin Gupta May 12, 2012 in India

Given an array of integers A[1....n-1] where 'N' is the length of array A[ ]. Construct an array B such that B[i] = min(A[i], A[i+1], ......., A[i-K+1]), where K will be given.

Array B will have N-K+1 elements.

Constraint: Extra space allowed O(K) and time complexity allowed O(N.K) or lower.| Report Duplicate | Flag | PURGE

Amazon Software Engineer / Developer Algorithm Arrays C C# C++ Coding Data Structures Java Sorting - 0of 0 votes

AnswersGiven a large file with million lines of data(phone numbers), give a most efficient way to sort the phone numbers.

- qwerty March 10, 2011| Report Duplicate | Flag | PURGE

Amazon Software Engineer / Developer Sorting - 0of 0 votes

AnswersImplement merge-sort?

- bk February 07, 2011| Report Duplicate | Flag | PURGE

One97 Software Engineer / Developer Sorting - 0of 0 votes

AnswersHow will you sort 1 million floating point numbers?

- dynamic June 29, 2010| Report Duplicate | Flag | PURGE

Flipkart Software Engineer / Developer Sorting - 0of 0 votes

AnswersThe Max

- raady April 12, 2010

Bubble sort is O(n) at best, O(n^2) at worst, and its memory usage is O(1) . Merge sort is always O(n log n), but its memory usage is O(n). Explain which algorithm you would use to implement a function that takes an array of integers and returns the max integer in the collection, assuming that the length of the array is less than 1002. What if the array length is greater than 1002?| Report Duplicate | Flag | PURGE

Rapleaf Software Engineer / Developer Sorting - 1of 1 vote

AnswersA sorted array is shifted circulary(i.e. m elements from start are removed from start and added in the end). So now the array is sorted from 0 to size(array)- m and from size(array)- m to size(array).

- AnonymousUser March 28, 2010

Given an element X find it in the array in efficient way. Code.| Report Duplicate | Flag | PURGE

Amazon Software Engineer / Developer Sorting - 1of 1 vote

AnswersGiven an array of n numbers in which all the members are less than or equal to k (k<n). device an algorithm of order O(k) to find the first repeating element.

- Ramesh January 14, 2010| Report Duplicate | Flag | PURGE

Microsoft Software Engineer / Developer Algorithm Arrays Brain Teasers Data Structures Ideas Math & Computation Sorting - 0of 0 votes

AnswersWhich of the following is true about asort?

- Annonymous.... November 01, 2009

• Sorts highest to lowest by value maintaining key association.

• Sorts lowest to highest by key maintaining key association.

• Sorts highest to lowest by key, re-indexing the array.

• Sorts lowest to highest by value, re-indexing the array.| Report Duplicate | Flag | PURGE

Achieve Internet Software Engineer / Developer Sorting - 0of 0 votes

AnswerWhich of the following maintain index associations?

- Annonymous.... November 01, 2009

• ksort

• asort

• sort| Report Duplicate | Flag | PURGE

Achieve Internet Software Engineer / Developer Sorting - 0of 0 votes

AnswersWhy might quick sort might be better than merge sort.

- ez pz March 20, 2009| Report Duplicate | Flag | PURGE

Bloomberg LP Financial Software Developer Sorting

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.