CareerCup

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

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)

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.

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

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.

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

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

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

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

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.

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.

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

Implement merge-sort?

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.

How will you sort 1 million floating point numbers?

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?

A 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).
Given an element X find it in the array in efficient way. Code.

You are given an array which contains either 1 or 0 , and they are in sorted order Ex. a [] = { 1,1,1,1,0,0,0}
How will you count no of 1`s and 0's ?

Given 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.

Which of the following is true about asort?
• 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.

Which of the following maintain index associations?

• ksort
• asort
• sort

Why might quick sort might be better than merge sort.