Solution

1. Given an array A[] consisting 0s, 1s and 2s, write a function that sorts A[]. The functions should put all 0s first, then all 1s and all 2s in last.

Example

Input = {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1};

Output = {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2}

Solution -1 : O(N)

Take two pointers, low and high, and move 0 to left with swap.

Reuse pointers, low and high, after 0's move 1's to the left with swap.

Solution -2 : O(N)

Take three pointers, low, mid and high.

Point low to start and mid and high to end.

Move pointers with swap such that 0 come to the left, 1 to middle, and 2 to end.

2. You are given an array of n+2 elements. All elements of the array are in range 1 to n. And all elements occur once except two numbers which occur twice. Find the two repeating numbers.

For example, array = {4, 2, 4, 5, 2, 3, 1} and n = 5

The above array has n + 2 = 7 elements with all elements occurring once except 2 and 4 which occur twice. So the output should be 4 2.

Solution - 1 : O(N)

We have to find two numbers, so to unknowns. We know the sum of n numbers is n(n+1)/2 and product is n!. Make two equations using these sum and product formulas, and get values of two unknowns using the two equations.

Let summation of all numbers in array be S and product be P

Let the numbers which are being repeated are X and Y.

X + Y = S – n(n+1)/2

XY = P/n!

Using above two equations, we can find out X and Y.

Solution - 2 : O(N)

Let the repeating numbers be X and Y, if we xor all the elements in the array and all integers from 1 to n, then the result is X xor Y.

The 1’s in binary representation of X xor Y is corresponding to the different bits between X and Y. Suppose that the kth bit of X xor Y is 1, we can xor all the elements in the array and all integers from 1 to n, whose kth bits are 1. The result will be one of X and Y.

3. Given an array arr[] of n integers, construct a Product Array prod[] (of same size) such that prod[i] is equal to the product of all the elements of arr[] except arr[i]. Solve it without division operator and in O(n).

Example:

arr[] = {10, 3, 5, 6, 2}

prod[] = {180, 600, 360, 300, 900}

Solution - 1 : O(N)

1) Construct a temporary array left[] such that left[i] contains product of all elements on left of arr[i] excluding arr[i].

2) Construct another temporary array right[] such that right[i] contains product of all elements on on right of arr[i] excluding arr[i].

3) To get prod[], multiply left[] and right[].

4. Given a binary matrix, find out the maximum size square sub-matrix with all 1s.

For example, consider the below binary matrix.

0 1 1 0 1 1 1 0 1 0 0 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 0 0 0 0

The maximum square sub-matrix with all set bits is

1 1 1 1 1 1 1 1 1

Solution - 1 : O(M*N)

Let the given binary matrix be M[R][C]. The idea of the algorithm is to construct an auxiliary size matrix S[][] in which each entry S[i][j] represents size of the square sub-matrix with all 1s including M[i][j] and M[i][j] is the rightmost and bottommost entry in sub-matrix.

1) Construct a sum matrix S[R][C] for the given M[R][C]. a) Copy first row and first columns as it is from M[][] to S[][] b) For other entries, use following expressions to construct S[][] If M[i][j] is 1 then S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1 Else /*If M[i][j] is 0*/ S[i][j] = 0 2) Find the maximum entry in S[R][C] 3) Using the value and coordinates of maximum entry in S[i], print sub-matrix of M[][]

For the given M[R][C] in above example, constructed S[R][C] would be:

0 1 1 0 1 1 1 0 1 0 0 1 1 1 0 1 1 2 2 0 1 2 2 3 1 0 0 0 0 0

The value of maximum entry in above matrix is 3 and coordinates of the entry are (4, 3). Using the maximum value and its coordinates, we can find out the required sub-matrix.

Time Complexity: O(m*n) where m is number of rows and n is number of columns in the given matrix.

Space Complexity: O(m*n) where m is number of rows and n is number of columns in the given matrix.

Algorithmic Paradigm: Dynamic Programming

5. Write a function rotate(ar[], d, n) that rotates arr[] of size n by d elements.

Array : 1 2 3 4 5 6 7

Rotation of the above array by 2 will make array

Result : 3 4 5 6 7 1 2

Solution - 1 : O(N)

Step 1: Rotate complete array. 7 6 5 4 3 2 1

Step 2: Rotate sub-array. 3 4 5 6 7 2 1

Step 3: Rotate next sub-array. 3 4 5 6 7 1 2

6. There are 2 sorted arrays A and B of size n each.

Write an algorithm to find the median of the array obtained after merging the above 2 arrays(i.e. array of

length 2n). The complexity should be O(log(n)).

Solution - 1 : O(log(n))

This method works by first getting medians of the two sorted arrays and then comparing them.

Let ar1 and ar2 be the input arrays.

1) Calculate the medians m1 and m2 of the input arrays ar1[]

and ar2[] respectively.

2) If m1 and m2 both are equal then we are done.

return m1 (or m2)

3) If m1 is greater than m2, then median is present in one

of the below two subarrays.

a) From first element of ar1 to m1 (ar1[0...|_n/2_|])

b) From m2 to last element of ar2 (ar2[|_n/2_|...n-1])

4) If m2 is greater than m1, then median is present in one

of the below two subarrays.

a) From m1 to last element of ar1 (ar1[|_n/2_|...n-1])

b) From first element of ar2 to m2 (ar2[0...|_n/2_|])

4) Repeat the above process until size of both the subarrays

becomes 2.

5) If size of the two arrays is 2 then use below formula to get

the median.

Median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2

7. A majority element in an array A[] of size n is an element that appears more than n/2 times (and hence there is at most one such element).

Write a function which takes an array and emits the majority element (if it exists), otherwise prints NONE as follows:

I/P : 3 3 4 2 4 4 2 4 4 O/P : 4 I/P : 3 3 4 2 4 4 2 4 O/P : NONE

Solution - 1 : O(N)

Moore’s Voting Algorithm. Basic idea of the algorithm is if we cancel out each occurrence of an element e with all the other elements that are different from e then e will exist till end if it is a majority element.

At the end, loop again to test if e has count n/2+1. An odd size array will always leave one element.

8. An Array m*n has elements in increasing order in each row. The elements in each column are also in

increasing order. Search an element in the array.

Solution - 1 : O(M+N)

Approach 1 - Start from (0,0) or (m-1, n-1). This won't be good, as both options are increasing data.

Approach 2 - Start from (0,n-1) or (m-1, 0). This will give right solution, as one option is less and other is greater, so always one is filtered, take more closure to the solution.

9. An Array m*n has elements in increasing order in each row. The elements in each column are also in increasing order. Print the elements in sorted order.

Solution - 1 : O(M*N)

Merge Sort for pair of rows, starting from last row.

Merge Sort for pair of columns, starting from last column.

1 5 20

2 10 30

11 13 40

12 14 50

10. A pillars of size 1 to n (say 9) are placed in increasing order. It shows 9 pillars from left and 1 pillar from right. How to rearrange to show 5 pillar from left and 4 pillar from right.

Solution 1 : O(N)

1 2 3 4 5 6 7 8 9

Move 9 after 4. 1 2 3 4 9 5 6 7 8

Flip 8 with 5. 1 2 3 4 9 8 6 7 5

(Flip largest right elemet which is rhs with next element after 9)

(Flip 6 with 7, if want to see one more element from right)

11. There are 2 arrays sorted in decreasing order of size m and n respectively.

Input: a number k <= n*n and >= 1

Output: the kth largest sum(a+b) possible. where

a (any element from array 1)

b (any element from array 2)

The Brute force approach will take O(n*n). can anyone find a better logic. thnkx in advance.

Solution - 1: O(N)

The kth largest sum means, either

1. make complete list and sort and find the kth element

2. start and make the list in sorted order, so you stop at kth element.

Approach-2 is good.

Take 3 pointers, Keep track of next pair of ai in bi

P1 a1 b1

P2 a2 b2

P3 a3 b3

a4 b4

a5 b5

Pair 1 a1 b1

P1 For a1 next pair is a1 b2

P2 For a2 next pair is a2 b1

P3 For a3 next pair is a3 b1

Pair 2 if a1 b2 > a2 b1 = a2 b1

P1 For a1 next pair is a1 b2

P2 For a2 next pair is a2 b2

P3 For a3 next pair is a3 b1

Pair 3 Min[a1 b2, a2 b2, a3b1] = a3 b1

P1 For a1 next pair is a1 b2

For a2 next pair is a2 b2 [Ignore] a1 b2 is smaller

For a3 next pair is a3 b2 [Ignore] a1 b2 is smaller

P2 For a4 next pair is a4 b1

P3 NULL

Pair 4 Min[a1 b2, a4 b1]

12. There was a party.there was a log register in which entry and exit time of all the guests was logged.you have to tell the time at which there was maximum guest in the party.

input will be the entry and exit time of all the n guests [1,4] [2,5] [9,12] [5,9] [5,12]

the output will be t=5 as there was maximum 3 guest were there namly guest(starting from 1) 2,4 and 5

Solution - 1:

Create an array of all time milestones. Asiign 1's for each guest again all In times. Count\find the max.

1 2 4 5 9 12

Guest 1 1 1 1

Guest 2 1 1 1

Guest 3 1 1

Guest 4 1 1

Guest 5 1 1 1

Ans: t = 5 and 9 Guest Count = 3

Solution - 2:

Represent each guest time with 24 bit stream.

Guest 1: 111100000000000000000000

Take 5C5, group 5 guest at a time and &

Take 5C4, group 4 guest at a time and &

Total cases, 5C5 + 5C4 + 5C3 + 5C2

13. Write a program to print all the combinations of a given array of elements.

If array contians 1,2,3 we are supposed to be able to print : 1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

14. Counting and Listing all Permutations : Johnson-Trotter Algorithm

The algorithm requires one more definition: a directed integer is said to be mobile if it is greater than its immediate neighbor in the direction it is looking at.

The Johnson-Trotter algorithm can now be described in five lines:

Initialize the first permutation with <1 <2 ... <n

while there exists a mobile integer

find the largest mobile integer k

swap k and the adjacent integer it is looking at

reverse the direction of all integers larger than k.

Using the Steinhaus–Johnson–Trotter algorithm with n = 3 would result in the following:

<1 <2 <3

<1 <3 <2

<3 <1 <2

3> <2 <1

<2 3> <1

<2 <1 3>

Using the Steinhaus–Johnson–Trotter algorithm with n = 4 would result in the following:

<1 <2 <3 <4

<1 <2 <4 <3

<1 <4 <2 <3

<4 <1 <2 <3

4> <1 <3 <2

<1 4> <3 <2

<1 <3 4> <2

<1 <3 <2 4>

<3 <1 <2 <4

<3 <1 <4 <2

<3 <4 <1 <2

<4 <3 <1 <2

4> 3> <2 <1

3> 4> <2 <1

3> <2 4> <1

3> <2 <1 4>

<2 3> <1 <4

<2 3> <4 <1

<2 <4 3> <1

<4 <2 3> <1

4> <2 <1 3>

<2 4> <1 3>

<2 <1 4> 3>

<2 <1 3> 4>

15. An element in a sorted array can be found in O(log n) time via binary search. But suppose I rotate the sorted array at some pivot unknown to you beforehand. So for instance, 1 2 3 4 5 might become 3 4 5 1 2. Now devise a way to find an element in the rotated array in O(log n) time.

The solution still works out to a binary search in the sense that you'll need to partition the array into two parts to be examined.

In a sorted array, you just look at each part and determine whether the element lives in the first part (let's call this A) or the second part (B). Since, by the definition of a sorted array, partitions A and B will be sorted, this requires no more than some simple comparisons of the partition bounds and your search key.

In a rotated sorted array, only one of A and B can be guaranteed to be sorted. If the element lies within a part which is sorted, then the solution is simple: just perform the search as if you were doing a normal binary search. If, however, you must search an unsorted part, then just recursively call your search function on the non-sorted part.

This ends up giving on a time complexity of O(lg n).

Search(set): if size of set is 1 and set[0] == item return info on set[0] divide the set into parts A and B if A is sorted and the item is in the A's range return Search(A) if B is sorted and the item is in the B's range return Search(B) if A is not sorted return Search(A) if B is not sorted return Search(B) return "not found"