## Sorting Interview Questions

- 0of 0 votes
I want to learn some big words so people think I'm smart.

I opened up a dictionary to a page in the middle and started flipping through, looking for words I didn't know. I put each word I didn't know at increasing indices in a huge array I created in memory. When I reached the end of the dictionary, I started from the beginning and did the same thing until I reached the page I started at.

Now I have an array of words that are mostly alphabetical, except they start somewhere in the middle of the alphabet, reach the end, and then start from the beginning of the alphabet. In other words, this is an alphabetically ordered array that has been "rotated." For example:

String[] words = new String[]{

"ptolemaic",

"retrograde",

"supplant",

"undulate",

"xenoepist",

"asymptote", // <-- rotates here!

"babka",

"banoffee",

"engender",

"karpatka",

"othellolagkage",

};

Write a function for finding the index of the "rotation point," which is where I started working from the beginning of the dictionary. This array is huge (there are lots of words I don't know) so we want to be efficient here.

- 0of 0 votes
You are given an array with duplicates. You have to sort the array with decreasing frequency of elements. If two elements have the same frequency, sort them by their actual value in increasing order.

Ex: [2 3 5 3 7 9 5 3 7]

Output: [3 3 3 5 5 7 7 2 9]

- 0of 0 votes
You are given a rotated sorted array of size N. You have to search a given number into it.

Example: [4,6,8,14,90,-9,-2,0,3], Search -2.

- 0of 0 votes
It was an over email interview:

Write a program that takes as input a sufficiently large text document (several are available online for testing; e.g. via Project Gutenberg), and produces as output (via stdout) an alphabetical listing of each unique word in the document (case insensitive and space separated, though be careful to consider hyphenated words), along with the lines from the input document that the word appears on. Each unique word (and the list of lines that it appears on) should be on a separate line in the output.

For example, taking the following text as input:

This is

some kind OF text it

Is an example of text

The following would be the output:

an 3

example 3

is 1 3

it 2

kind 2

of 2 3

some 2

text 2 3

this 1

- 0of 0 votes
Given a large terabytes of text file, sort the words in the file. Explain how it can be done in Mapreduce and Spark.

- -1of 1 vote
Provide a function that allow to compare two strings lexicography, having in mind that these words may contain digraphs (two letters together represents a single one i.e in Spanish ch is a single character ).

This in order to be able to sort a list of words.

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

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

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