## Sorting Interview Questions

- 0of 0 votes
Implement an algorithm that takes a adjacency list and produces a topological sort of the vertices.

INPUT:

1 2

1 3

1 4

3 5

2 5

4 5

Returns:

1 2 3 4 5

- 2of 2 votes
Round 6

Question 3 : You are given a word document, you have to print the words with frequencies. Now print the kth rank word in terms of frequency. Print top k words as well by frequencies

- 0of 0 votes
Round 5

Question 5 : Now lets say you are given k number of input streams, each stream have two method implemented, one is ReadNextNumber() and another is WriteToStream(), lets say each of the streams are sorted. How will you return a single sorted stream which contains all the streams data.

- -1of 1 vote
Round 5

Question 4 : Now lets say you have 1 PB(1000 TB) of numbers, what kind of system you would prefer, not that you can't store this data in one box. How will you sort these many numbers, what is the time complexity in seconds ?. does increasing core per machine help here ?

- -1of 1 vote
Round 5

Question 3 : Now lets say you have 1 TB(1000 GB) of numbers, how do you sort it, tell me the complexity in seconds ?, any optimization you would like to do here, ?, lets say your machine is having two core, now ?

- -1of 1 vote
Round 5

Question 2 : You are given a 1 GB of numbers, you have to sort them. Tell me the time required in seconds ?

- 0of 0 votes
Given a array where each element is maximum +-k index away from it's sorted position, find an algorithm to sort such array.

- -6of 6 votes
Sort an integer array with three functions: findMin(), findMedium(), findMax().

- 0of 0 votes
This was asked in an Online written test that was timed (60 mins). And this question was one among the three.

"Write a method to merge three sorted integer arrays into just one array"

Nothing more or less was given. Since it was a written test I assumed that the 1st array had space towards to end which can fit the other two arrays. I can code this but given the timer limitations (of 20 mins per question) I thought it was a bit too much for me to handle unless there is a more obvious way to do this. I did it using two arrays and using the resultant array, I merged it with the 3rd array. That was the best i could think of at that time.

- 2of 2 votes
{{

There are 3 machines M1, M2 and M3. Each machine is 90% full of its capacity with integers. Now you have to sort all the integers combined and then store the first 1/3rd in M1, second 1/3rd in M2 and last 1/3rd in M3.

Your objective is to minimize the number of sort operations and number of data transfer operations.

Each sort operation/data transfer operation is counted as 1 irrespective of the count of values that are being sorted/transferred.

}}

- 2of 2 votes
An efficient way to sort patient files in an array of just 3 types 'High-importance', 'Mid-importance', 'Low-importance' which are in an arbitrary order (unsorted).

The output preference should start with the highest.

1. High-importance

2. Mid-importance

3. Low-importance

[high,low,low,med,high,low]

ps I was told to take advantage of the fact that they are just only 3 types.

- 0of 0 votes
Whats the difference between quick sort and merge sort? Which one to use? Do we need file sorted before merge sort?

- 5of 5 votes
Given a Sorted integer array which is rotated N number of times. You have no idea what that N is. An element in the array can occur more for any number of time. Write a method to search the position of a given element. If there are more than one of the same element, return the position of the first element.

- -1of 1 vote
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 .

- 0of 2 votes
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

- 1of 1 vote
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],

.......

];

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

- 2of 4 votes
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?

- -3of 5 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 .

- -5of 7 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

- 2of 2 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)

- 1of 1 vote
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.