MergeSort(headRef) 1) If head is NULL or there is only one element in the Linked List then return. 2) Else divide the linked list into two halves. FrontBackSplit(head, &a, &b); /* a and b are two halves */ 3) Sort the two halves a and b. MergeSort(a); MergeSort(b); 4) Merge the sorted a and b (using SortedMerge() discussed here) and update the head pointer using headRef. *headRef = SortedMerge(a, b);

/* sorts the linked list by changing next pointers (not data) */ void MergeSort(struct node** headRef) { struct node* head = *headRef; struct node* a; struct node* b;

/* Base case -- length 0 or 1 */ if ((head == NULL) || (head->next == NULL)) { return; }

/* Split head into 'a' and 'b' sublists */ FrontBackSplit(head, &a, &b);

/* Recursively sort the sublists */ MergeSort(&a); MergeSort(&b);

/* answer = merge the two sorted lists together */ *headRef = SortedMerge(a, b); }

/* See http://geeksforgeeks.org/?p=3622 for details of this function */ struct node* SortedMerge(struct node* a, struct node* b) { struct node* result = NULL;

/* Base cases */ if (a == NULL) return(b); else if (b==NULL) return(a);

/* Pick either a or b, and recur */ if (a->data <= b->data) { result = a; result->next = SortedMerge(a->next, b); } else { result = b; result->next = SortedMerge(a, b->next); } return(result); }

/* UTILITY FUNCTIONS */ /* Split the nodes of the given list into front and back halves, and return the two lists using the reference parameters. If the length is odd, the extra node should go in the front list. Uses the fast/slow pointer strategy. */ void FrontBackSplit(struct node* source, struct node** frontRef, struct node** backRef) { struct node* fast; struct node* slow; if (source==NULL || source->next==NULL) { /* length < 2 cases */ *frontRef = source; *backRef = NULL; } else { slow = source; fast = source->next;

/* Advance 'fast' two nodes, and advance 'slow' one node */ while (fast != NULL) { fast = fast->next; if (fast != NULL) { slow = slow->next; fast = fast->next; } }

/* 'slow' is before the midpoint in the list, so split it in two at that point. */ *frontRef = source; *backRef = slow->next; slow->next = NULL; } }

/* Function to print nodes in a given linked list */ void printList(struct node *node) { while(node!=NULL) { printf("%d ", node->data); node = node->next; } }

/* Function to insert a node at the beginging of the linked list */ void push(struct node** head_ref, int new_data) { /* allocate node */ struct node* new_node = (struct node*) malloc(sizeof(struct node));

/* put in the data */ new_node->data = new_data;

/* link the old list off the new node */ new_node->next = (*head_ref);

/* move the head to point to the new node */ (*head_ref) = new_node; }

/* Drier program to test above functions*/ int main() { /* Start with the empty list */ struct node* res = NULL; struct node* a = NULL; struct node* b = NULL;

/* Let us create a unsorted linked lists to test the functions Created lists shall be a: 2->3->20->5->10->15 */ push(&a, 15); push(&a, 10); push(&a, 5); push(&a, 20); push(&a, 3); push(&a, 2);

/* Remove duplicates from linked list */ MergeSort(&a);

printf("\n Sorted Linked List is: \n"); printList(a);

getchar(); return 0; }

Q. No. :

2

Question :

You need to organize a football tournament. There are n teams given. You need to prepare a schedule for the matches so that each team plays with every other team and on the same day no team plays twice. You want to finish the tournament as early as possible.Give schedule for tournament.

If n is the number of competitors, a pure round robin tournament requires n*(n-1)/2 games. If n is even, then in each of (n − 1) rounds, n/2 games can be run in parallel, If n is odd, there will be n rounds with(n-1)/2 games, and one competitor having no game in that round.
The standard algorithm for round-robins is to assign each competitor a number, and pair them off in the first round
Round 1. (1 plays 14, 2 plays 13, ... )
1 2 3 4 5 6 7
14 13 12 11 10 9 8
then fix one competitor (number one in this example) and rotate the others clockwise …
Round 2. (1 plays 13, 14 plays 12, ... )
1 14 2 3 4 5 6
13 12 11 10 9 8 7
ound 3. (1 plays 12, 13 plays 11, ... )
1 13 14 2 3 4 5
12 11 10 9 8 7 6
until you end up almost back at the initial position

The web is a graph-based structure, and we commonly use DFS (depth first search) and BFS (breadth first search) for traversing graphs. We can mark already visited pages the same way that we would in a BFS/DFS.
We can easily prove that this algorithm will terminate in any case.

Q. No. :

5

Question :

How do you detect the duplicate documents?
Consider you have over million urls.

Iterate through the pages and compute the hash table of each one.
Check if the hash value is in the hash table. If it is, throw out the url as a duplicate. If it is not, then keep the url and insert it in into the hash table.

Q. No. :

6

Question :

You are given 2 eggs.
* You have access to a 100-storey building.
* Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.
* You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.
* Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process

Now let x be the answer we want, the number of drops required.

So if the first egg breaks maximum we can have x-1 drops and so we must always put the first egg from height x. So we have determined that for a given x we must drop the first ball from x height. And now if the first drop of the first egg doesn’t breaks we can have x-2 drops for the second egg if the first egg breaks in the second drop.

Taking an example, lets say 16 is my answer. That I need 16 drops to find out the answer. Lets see whether we can find out the height in 16 drops. First we drop from height 16,and if it breaks we try all floors from 1 to 15.If the egg don’t break then we have left 15 drops, so we will drop it from 16+15+1 =32nd floor. The reason being if it breaks at 32nd floor we can try all the floors from 17 to 31 in 14 drops (total of 16 drops). Now if it did not break then we have left 13 drops. and we can figure out whether we can find out whether we can figure out the floor in 16 drops.

Lets take the case with 16 as the answer

1 + 15 16 if breaks at 16 checks from 1 to 15 in 15 drops
1 + 14 31 if breaks at 31 checks from 17 to 30 in 14 drops
1 + 13 45 .....
1 + 12 58
1 + 11 70
1 + 10 81
1 + 9 91
1 + 8 100 We can easily do in the end as we have enough drops to accomplish the task

Now finding out the optimal one we can see that we could have done it in either 15 or 14 drops only but how can we find the optimal one. From the above table we can see that the optimal one will be needing 0 linear trials in the last step.

Solving for 100 you get q=14.
So the answer is: 14
Drop first orb from floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100... (i.e. move up 14 then 13, then 12 floors, etc) until it breaks (or doesn't at 100).

Q. No. :

7

Question :

Write code to compare two arrays if they contain the same elements

bool hasSame(int* a, int* b, int la, int lb){
sort(a, la);
sort(b, lb);
int i=0, j=0;
while(i
if(a[i] == b[j]) return true;
if(a[i] > b[j]) j++;
else i++;
}
return false;
}

void sort(int* a, int la){
int k = rand(la); // from 0 to la-1
int spliter = a[k];
int i=0, j=la-1;
while(i
if(a[i]<=a[k]) i++;
if(a[j]>a[k]) i--;
if(a[i]>a[k] && a[j]<=a[k]){
int swap = a[i];
a[i] = a[j];
a[j] = swap;
}
}
sort(a,i);
sort(a+i, la-i);
}

Q. No. :

8

Question :

How to implement a queue using one integer. this should store value 0 to 9. example suppose queue has first value 2 then insert 4 then 6 so it should look like 246. first value should be popped as 2. then it should be 46. program should support 0 in all the levels also. example queue should handle like 01235 also, 0 as first value in queue. remember 0 just to use integer, nothing else as data storage.

Many solutions are possible. One possible solution is given below
Steps:-
1. represent each number with 4 bits as the max no. needs 4 bits.
2. take the first no. say 4. (bit representation 0100) lets put this in a variable called queueInteger.
3. another variable (say queuePointer)to take the element from queue.The value in it will be 15(which is 1111).
4. if you want to print the first number just do and (&) operation between queueInteger and queuePointer.(which is 0100 & 1111 gives 0100 which is 4).
5. Or if you want to add more elements to queue then left shift the queueInteger by 4 positions and do the or(||) operation with the new number(say 5 so queueInteger becomes 0100 0000 || 0101 gives 0100 0101).
6. Then left shift the queuePointer by 4 bits.(now it will become 1111 0000)
7. If you want to print the element then do queueInteger & queuePointer you will get4.
8. If you want to delete it you can right shift the queuePointer variable by 4 bits.

Q. No. :

9

Question :

You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number?

As the problem is only to check that Bob has phone number or not.
So You will write "Give me call Bob" If he calls you back you know he has number otherwise not.

Q. No. :

10

Question :

Find the next in order node of given node in binary tree. Write the program of same. pointer to parent node is given.

static Node nextNode(Node head){
Node returnNode;
if (head.rightChild != null){
//If we have a right child, the next obvious in order
//node would be the desendent of the right child.
returnNode = head.rightChild;
while(returnNode.leftChild != null)
returnNode = returnNode.leftChild;
}else{
//Else climb up the tree till we get the ancestor that
// that is supposed to be the next node
Node tempPointer = head;
Node curPointer = head;
while(curPointer != null && curPointer.leftChild != tempPointer){
tempPointer = curPointer;
curPointer = curPointer.parent;
}
returnNode = curPointer;
}
return returnNode;
}

Q. No. :

11

Question :

How to design the netflix movie recommendation algorithm?

Pretend there is a robot that has to navigate a maze (N x M). The robot can only move down or right and the maze can contain walls. Write an algorithm to determine the number of paths the robot can take.

Stack 1 start from beginning.
Stack 2 start from last
Stack 3 start from middle with toggle between left and right
stack 1 stack 2 stack 3
123.......312......321

Use Dynamic Programming
/**
* Find the optimal solution for a given target value and the set of denominations
* @param target
* @param denoms
* @return
*/
public CoinChangeAnswer findOptimalChange(int target, int[] denoms) {
CoinChangeAnswer soln = new CoinChangeAnswer(target,denoms);
StringBuilder sb = new StringBuilder();

// initialize the solution structure
for(int i=0; i
soln.OPT[0][i] = i;
soln.optimalChange[0][i] = sb.toString();
sb.append(denoms[0]+" ");
}

// Read through the following for more details on the explanation
// of the algorithm.
// http://condor.depaul.edu/~rjohnson/algorithm/coins.pdf
for(int i=1 ; i
for(int j=0; j
int value = j;
int targetWithPrevDenomiation = soln.OPT[i-1][j];
int ix = (value) - denoms[i];
if( ix>=0 && (denoms[i] <= value )) {
int x2 = denoms[i] + soln.OPT[i][ix];
if(x2 <= target && (1+soln.OPT[i][ix] < targetWithPrevDenomiation)) {
String temp = soln.optimalChange[i][ix] + denoms[i] + " ";
soln.optimalChange[i][j] = temp;
soln.OPT[i][j] = 1 + soln.OPT[i][ix];
} else {
soln.optimalChange[i][j] = soln.optimalChange[i-1][j]+ " ";
soln.OPT[i][j] = targetWithPrevDenomiation;
}
} else {
soln.optimalChange[i][j] = soln.optimalChange[i-1][j];
soln.OPT[i][j] = targetWithPrevDenomiation;
}
}
}
return soln;
}

Q. No. :

16

Question :

You have to make 125 packets of sugar with first one weighing 1 kg, second 2 kg, third 3 kg etc ...and 125th one weighing 125kg.You can only use one pan of the common balance for measurement for weighing sugar, the other pan had to be used for weights i.e. weights should be used for each weighing.
It has come into notice that moving weights into and out of the pan of the balance takes time and this time depends on the number on the number of weights that are moved. For example - If we need to measure 4 kg using weights 1 and 3 only, it will take twice as much time needed to measure 1 kg. Lets say we want to make sugar packets of weights 1,3,4 using weights 1 and 3 only. For this first we measure 1 kg, with 1 unit of time, we place 3 kg along with 1 kg and measure 4kg with again 1 unit of time, and finally we move 1kg out of pan to measure 3kg in 1 unit of time. So in 3 units of time we could measure 1,3 and 4kg using weights 1 and 3 only.

Now you have to make sugar packets of all weights from 1 to 125 in minimum time, in other words in minimum movement of weights. The question here is to find out the minimum number of weighs needed and the weight of each the weights used and the strategy to be followed for the creation of 125 packets of sugar.

Name the 12 balls as A1,A2,A3,A4,B1,B2,B3,B4 C1,C2,C3 and C4.We will weigh A's on one side and B's on the other side.
A1 A2 A3 A4 <---> B1 B2 B3 B4
If Both weighed same then the odd ball is among C's.
We have to find the odd ball among 4 balls using 2 weightings.For that we balance

C1 C2 with C3 N.

Now if C1 C2 equals C3 N then C4 is the odd one.

Now suppose C1 C2 is heavier than C3 N then we compare
C1 C3 to N N
Now if C1 C3 equals to N N the C2 is the odd ball.
If C1 C3 is lighter than N N, then C3 is the odd ball.
If C1 C3 is heavier than N N then C1 is the odd ball.

Coming to the situation where the first weighing resulted in unequal balance.Lets assume A's are heavier than B's.
ie .

A1 A2 A3 A4 > B1 B2 B3 B4

Now we compare

A1 A2 B1 B2 to N N N B4.

if A1 A2 B1 B2 > N N N B4

The odd ball is among A1 A2 or B4 and we also know that A1 A2 > B4 N.To find out the odd ball among A1 A2 and B4 we do compare

A1 B4 to N N .

if A1 B4 > N N then
A1 is the odd ball
if A1 B4 < b4 =" N" b2 =" N"> N B3 which we have already shown how to solve.

Solution for 13 ball problem is easy if we could solve 12 ball problem.For that lets assume we have an extra ball C5.Now if A's and B's dont weigh same we have all the steps already calculated.

Now if A's and B's weigh same then the odd one is among C's.

Now we compare

C1 C2 to C3 N.

If C1 C2 = C3 N then we can find out the odd ball from C4 and C5 by comparing it with any normal ball.
Else if C1 C2 > C3 N then we compare

C1 C3 to N N.
If C1 C3 > N N then C1 is the odd ball
If C1 C3 = N N then C2 is the odd ball
If C1 C3 < N N then C3 is the odd ball

Q. No. :

17

Question :

Write a program to shuffle an pack of cards in the most efficient way.

Given an array of integers(both positive and negative) divide the array into two parts(sub-arrays) such that the difference between the sum of elements in each array is minimum?

A simple interview problem on O(n) space and O(n) time.
step 1: Take sum of all elements. o(n)
step 2: now traverse and keep sum till now as t and remaining sum as S-t . Look for least difference between them while traversing.

Q. No. :

19

Question :

Sort an array of 0s, 1s and 2s in O(n) time and O(1) space.

Keep three variables for keeping count of 0's 1's and 2's.
Step 1: Traverse array and count 0's , 1's and 2's.
Step 2: Fill first 0's count number of places in array with 0 and so on.

Q. No. :

20

Question :

You are given 2 arrays of size ‘n’ each. You need to stable-merge these arrays such that in the new array sum of product of consecutive elements is maximized and the relative ordering of elements of A and B in C is not reversed.
eg
A= { 2, 1, 3}
B= { 3, 7, 9}
Stable merging A and B will give an array C with ’2n’ elements say C={c1, c2, c3, c4, c5, c6}
You need to find a new array C by merging (stable) A and B such that sum= c1*c2 + c3*c4 + c5* c6….. n terms is maximum.

A simple DP problem with the following recurrence
Condition : S[i+j-1] + max ( A[i] * A[i+1], A[i] * B[j], B[j]*B[j+1])
If in the above condition, the max is due to A[i]*A[i+1], then the merged array will have A[i] in (i+j)th place and A[i+1] at (i+j+1)th place and i will be i+=2, similarly if max is due to A[i]*B[j], then merged array will have A[i] in (i+j)th place and B[j] in (i+j+1)th place and same for the third one.
i is the index of the elements in A array and j in B array and S[i+j-1] is the max sum upto the current state.
const int Max = 1000;
vector a,b;
int n;

int memo[Max][Max];

int solve(int i,int j) {

if(i == n) {
int ret = 0;
for (int k=j;k
ret += b[k] * b[k+1];
++k;
}
return ret;
}
if(j == n) {
int ret = 0;
for (int k = i; k < n; k++) {
ret += a[k] * a[k+1];
++k;
}
return ret;
}

int&ret = memo[i][j];
if(ret != -1) return ret;

ret = -INF;
// Three possibilities.
// (i,i+1) ; (j,j+1) ; [(i,j) == (j,i)]
if(i + 1 < n) {
ret = max(ret, a[i] * a[i+1] + solve(i+2,j));
}
if(j + 1 < n) {
ret = max(ret, b[j] * b[j+1] + solve(i,j+2));
}
ret = max(ret, a[i]*b[j] + solve(i+1,j+1));
return ret;
}
int main() {

scanf("%d",&n);
a.resize(n); b.resize(n);

for (int i=0;i
for (int i=0;i
memset(memo, -1, sizeof memo);
printf("%d\n",solve(0,0));
return 0;

}

Q. No. :

21

Question :

Given a document and a query of K words, how do u find the smallest window that covers all the words at least once in that document? (given you know the inverted lists of all K words, that is, for each word, you have a list of all its occurrrences). This one is really hard. Could someone propose an algorithm in O(n)?

Let us suppose
I- > 1 5 7 11
am -> 3 6 9 12
one -> 7 8 99

Sort all the entries - so u get
1 3 5 6 7 8 9 11 12 99 in o(n) time as the lists are already sorted

Now, we just have to come up with a window having 3 non-similar elements. As there can be max n-k (where k=no of term we are looking it, here 3), looking at those windows and determining the min window in o(n) time

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

Let ar1 and ar2 be the input arrays.

Algorithm:

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

For the above ar1[] and ar2[], m1 is smaller than m2. So median is present in one of the following two subarrays.

[15, 26, 38] and [2, 13, 17]

Let us repeat the process for above two subarrays:

m1 = 26 m2 = 13.

m1 is greater than m2. So the subarrays become

[15, 26] and [13, 17]
Now size is 2, so median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2
= (max(15, 13) + min(26, 17))/2
= (15 + 17)/2
= 16
#include

int max(int, int); /* to get maximum of two integers */
int min(int, int); /* to get minimum of two integeres */
int median(int [], int); /* to get median of a single array */

/* This function returns median of ar1[] and ar2[].
Assumptions in this function:
Both ar1[] and ar2[] are sorted arrays
Both have n elements */
int getMedian(int ar1[], int ar2[], int n)
{
int m1; /* For median of ar1 */
int m2; /* For median of ar2 */

m1 = median(ar1, n); /* get the median of the first array */
m2 = median(ar2, n); /* get the median of the second array */

/* If medians are equal then return either m1 or m2 */
if(m1 == m2)
return m1;

/* if m1 < m2 then median must exist in ar1[m1....] and ar2[....m2] */
if (m1 < m2)
return getMedian(ar1 + n/2, ar2, n - n/2);

/* if m1 > m2 then median must exist in ar1[....m1] and ar2[m2...] */
return getMedian(ar2 + n/2, ar1, n - n/2);
}

/* Driver program to test above function */
int main()
{
int ar1[] = {1, 12, 15, 26, 38};
int ar2[] = {2, 13, 17, 30, 45};
printf("%d", getMedian(ar1, ar2, 5)) ;

getchar();
return 0;
}

/* Utility functions */
int max(int x, int y)
{
return x > y? x : y;
}

int min(int x, int y)
{
return x > y? y : x;
}

/* Function to get median of a single array */
int median(int arr[], int n)
{
if(n%2 == 0)
return (arr[n/2] + arr[n/2-1])/2;
else
return arr[n/2];
}

Q. No. :

23

Question :

You are given an array of N integers. Your job is to find maximum and second maximum element in N+logN comparisons.

nitialize int a[26] to 0;
int n = min( len(A), len(B) )

for ( i=0; i
a[ A[i]-96 ] +=1;
a[ B[i]-96 ] += 1;
}

*C = ( n == len(A) ) ? &B : &A;
for ( ; i < len(C); i++ ) {
a [ C[i]-96 ] += 1;
}

for (i = 0; i < 26; i++) {
if ( a[i] > 1 ) print (char) i + 96;
}

Q. No. :

25

Question :

Given a source array of integers with possible duplicates and a target integer, write algorithm to find out 2 numbers in source array whose sum is equal to target If pre-processing of source in the above is allowed, what pre-processing will you do to reduce the complexity of algorithm written above ?

1) Initialize Binary Hash Map M[] = {0, 0, …}
2) Do following for each element A[i] in A[]
(a) If M[x - A[i]] is set then print the pair (A[i], x – A[i])
(b) Set M[A[i]]
#include
#define MAX 100000

void printPairs(int arr[], int arr_size, int sum)
{
int i, temp;
bool binMap[MAX] = {0}; /*initialize hash map as 0*/

for(i = 0; i < arr_size; i++)
{
temp = sum - arr[i];
if(temp >= 0 && binMap[temp] == 1)
{
printf("Pair with given sum %d is (%d, %d) \n", sum, arr[i], temp);
}
binMap[arr[i]] = 1;
}
}

/* Driver program to test above function */
int main()
{
int A[] = {1, 4, 45, 6, 10, 8};
int n = 16;
int arr_size = 6;

printPairs(A, arr_size, n);

getchar();
return 0;
}
Works in O(n)

Q. No. :

26

Question :

You are given 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 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]

Q. No. :

27

Question :

we are given N blocks of height 1…N. In how many ways can we arrange these blocks in a row such that when viewed from left we can see only L blocks (rest are hidden by taller blocks) and when seen from right we see only R blocks? for N=3, L=2, R=2 there are two ways 1, 3, 2 and 2, 3, 1.

Consider the box with height 1. We can place it in the following ways:
1) leftmost position: It can be seen from left only (1 way to place)
2) rightmost position: It can be seen from right only (1 way to place)
3) Somewhere in between: Cannot be seen from either side as taller blocks will occupy both left and right side (N-2 ways to place)

After placing box with height 1, we again have the same subproblem while keeping box with height 2....and so on. This gives us the following recurrence relation:

Step 1: loop from 0 to n-1; remove all the 'a's, and squeeze the array to the left (starting at index 0) without any spaces in the array (introduced by removing 'a's) other than the end of the array. At the same time, count the number of 'b's: n_b, the index of the new end of the array: m.

Step 2: loop from n_b+m to 0: assign each one with the wanted value by moving at index m or less (or adding a 'd') to the position of index == n_b+m or less.

int i=0, pos = 0, nb = 0, ;
for(int i=0; i
if(a[i] == 'b') {
nb++;
}
if(a[i] != 'a') {
a[pos] = a[i];
pos++;
}
}
if(nb==0) return;
// if(nb+pos >= n) should extend the memory of the array first
// (may need to generate a new array)
i = pos;
pos = pos+nb;
for(; i>=0; pos--,i--) {
if(a[i]=='b') {
a[pos] = 'd';
pos--;
a[pos] = 'b';
} else {
a[pos] = a[i];
}
}

Q. No. :

29

Question :

Given two binary trees, write a compare function to check if they are equal or not. Being equal means that they have the same value and same structure.

The following is a function to check if the two trees are similar or not.It returns true if they are similar else false.
int compareTree(struct node* a, struct node* b) {
if (a==NULL && b==NULL)
return(true);
else if (a!=NULL && b!=NULL) {
return(
a->data == b->data &&
compareTree(a->left, b->left) &&
compareTree(a->right, b->right)
);
}
else return(false);
}

Q. No. :

30

Question :

Given a Binary Tree, Programmatically you need to Prove it is a Binary Search Tree

f the given binary tree is a Binary search tree,then the inorder traversal should output the elements in increasing order.We make use of this property of inorder traversal to check whether the given binary tree is a BST or not.We make note of the latest element that could have been printed and compare it with the current element.Given below is a C function to check it.
bool flag=true;
void inorder(tree T,int *lastprinted)
{
if(T==NULL)
{
printf("the tree is empty .Hence, it is a BST\n");
}
else
{
if(T->left!=NULL)
{
inorder(T->left,lastprinted);
}
if(T->data > *lastprinted)
{
*lastprinted=T->data;
}
else
{
printf("the given binary tree is not a BST\n");
flag=false;
exit(0);
}
inorder(T->right,lastprinted);
}
}

Q. No. :

31

Question :

How many lines can be drawn in a 2D plane such that they are equidistant from 3 non-collinear points ?

The three non-collinear points form a triangle. There will be 3 lines which are equidistant from all the three points.
Draw altitudes from each point to the line joining the other two points.We get 3 altitudes.Now draw a line passing through the mid point of the altitude line and parallel to line onto which the altitude is drawn.This line is equidistant from all the 3 points.Thus we get 3 lines.

Q. No. :

32

Question :

Given a Data Structure having first n integers and next n chars. A = i1 i2 i3 ... iN c1 c2 c3 ... cN.Write an in-place algorithm to rearrange the elements of the array ass A = i1 c1 i2 c2 ... in cn

we divide the array in four sections:[X,Y|A,B]
It is easy to see that with swaps we can modify it to the form [X,A|Y,B].
Now do recursion to solve [X|A] and [Y|B] separately,essentially using divide and conquer

Q. No. :

33

Question :

Find or determine non existence of a number in a sorted list of N numbers where the numbers range over M, M >> N and N large enough to span multiple disks. Algorithm to beat O(log n) bonus points for constant time algorithm

This problem can be solved using bitmaps.bitmap will be an array (say b_array) where we have one bit per M possible number. If we use a character array to store bitmaps, b_array size will be M/8, since 1 char can store 8 bits. Bitmap array will be initialized to zero first. Now for each of the N numbers its corresponding bit should be turned on(1). Corresponding bit for 'n' can be found as follows:
base = n/8; (base is the char whose certain bit needs to be set)

offset = 1 << (n mod 8); (offset is the bit to be set)

b_array[base] |= offset; (I set the particular bit)

Once this is done of all N numbers, given a number m,
we can first find corresponding bit offset and check whether it is one.

base = m/8; (base is the char whose certain bit needs to be set)

offset = 1 << (m mod 8); (offset is the bit to be set)

if (b_array[base] & offset)
// found the number
else
//number could not be found

Q. No. :

34

Question :

There is a linked list of numbers of length N. N is very large and you don’t know N. You have to write a function that will return k random numbers from the list. Numbers should be completely random.

Hint:

1. Use random function rand() (returns a number between 0 and 1) and irand()
(return either 0 or 1)
2. It should be done in O(n).

Traverse the list, generating a new random number for each entry. Keep a ‘top k’ chart of the highest random numbers, and their associated entries. When we hit the end of the list, the numbers in the chart are the required random numbers.

This random number generated for each element can be defined as a function f=absolute(irand()-rand()),which is random enough.