Arrays

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}

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.

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}

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

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

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

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

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.

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.

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.

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.

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.

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

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.