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 Statesclass 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