## Sorting Interview Questions

- 0of 0 votes
Design a system like friend's functionality in facebook. should have all features of facebook's friends functionality. like for each person , he can have any number of friends , he will get suggestions for new firends , showing common friends if we visits any other profile . algo should be scalable , robust .

- 1of 1 vote
How to design a multi key hash map ( key count can be dynamic. if there are two keys , initiallly which can be used to find the value , keys can be increased to three as well ex: consider school structure. Intially , consider , student id is key , later , should be searchable even with key name , later with grade.

- 0of 0 votes
Given 2 sorted lists that are of even and equal size, output the median. If there is no middle number, return the average of the 2 middle numbers

- 0of 0 votes
Given a list of n sorted lists of numbers, write a method that returns one giant list of all the numbers in order.

Example input:

NSArray* input = @[

@[@2, @5, @10],

@[@25, @100, @105],

@[@7, @56, @42],

.......

];

- 1of 1 vote
Given an array say [0,1,2,3,5,6,7,11,12,14,20]

given a number say 5.

Now find the sum of elements which sum to 5

eg:2+3=5, 0+5=5 etc.

I guess the interviewer wanted all possible combinations eg 0+2+3=5, etc

- -1of 1 vote
Implement a sorting algorithm for a single linked list.

- 1of 1 vote
Write a program for finding a minimum element in rotated sorted array(either ascending or descending ) and array contains duplicates.

- 0of 0 votes
Write a program find minimum element in the rotated sorted array( ascending or descending ) and array having duplicates elements.

- 1of 1 vote
Given a sorted array of integers, write a function that will return the number with the biggest number of repetitions.

(Asked to refine the solution to be more efficient)

- -1of 1 vote
Explain Mergesort and Hashtable

- -1of 1 vote
Explain Binary Search Tree. What is its time complexity?

- -4of 4 votes
In 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

- 0of 0 votes
Given 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:`class TestResult { int studentId; String testDate; int testScore; } public class FinalScoreQuestion { Map <Integer, Double> calculateFinalScores (List<TestResult> results) { }`

- 0of 0 votes
Merge the given 2 input sorted arrays of numbers into one . The merged array stays sorted .

- -3of 5 votes
need to implement a weather report functionality. user will provide the city name , need to return the weather report.

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.

- 0of 0 votes
merge two unsorted linked-list into one new sorted linked list, off course in a efficient way

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

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)

- 0of 0 votes
We have n number of sorted array for fixed length.

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.

- 0of 0 votes
(screening round)

Given two sorted arrays, merge them into result array with sorting. Time and Space Complexity.

- 0of 0 votes
Given 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.

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.

- 0of 0 votes
Sort an array of characters in linear time complexity (and linear space complexity if that's possible).

- 0of 0 votes
Write a method to sort an array of strings so that all the anagrams are next to each other.

- 0of 0 votes
In this problem, you have to implement a variation of Insertion Sort as described below.

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

- 0of 0 votes
Q1. F2F Round 1 Amazon(Bangalore)

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.

- 0of 0 votes
Q4. Written Exam Amazon(Bangalore)

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.

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

- 0of 0 votes
Implement merge-sort?

- 0of 0 votes
for 2 sorted arrays one with size X and another with size X+Y which has only Y elements. merge these arrays in to second array such that resultant array at end will be sorted.

- 0of 0 votes
How will you sort 1 million floating point numbers?

- 0of 0 votes
The Max

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?