What is cycle stealing?

We encounter cycle stealing in the context of Direct Memory Access (DMA). Either the DMA controller can use the data bus when the CPU does not need it, or it may force the CPU to temporarily suspend operation. The latter technique is called cycle stealing. Note that cycle stealing can be done only at specific break points in an instruction cycle.

Continue

What is thrashing?

If the number of frames allocated to a low-priority process falls below the minimum number required by the computer architecture, we must suspend that process' execution. We should then page out its remaining pages, freeing all its allocated frames. This provision introduces a swap-in, swap-out level of intermediate CPU scheduling.


In fact, look at any process that does not have "enough" frames. Although it is technically possible to reduce the number of allocated frames to the minimum, there is some (larger) number of pages in active use. If the process does not have this number of frames, it will quickly page fault. At this point, it must replace some page. However, since all its pages are in active use, it must replace a page that will be needed again right away. Consequently, it quickly faults again, and again, and again. The process continues to fault, replacing pages for which it then faults and brings back in right away.

This high paging activity is called thrashing. A process is thrashing if it is spending more time paging than executing.

Continue

What are turnaround time and response time?

Turnaround time is the interval between the submission of a job and its completion. Response time is the interval between submission of a request, and the first response to that request.

Continue

What is Belady's anomaly?

Usually, on increasing the number of frames allocated to a process' virtual memory, the process execution is faster, because fewer page faults occur. Sometimes, the reverse happens, i.e., the execution time increases even when more frames are allocated to the process. This is known as the Belady's Anomaly. This is true for certain page reference patterns. This is also called the FIFO anomaly.

Continue

What is an AVL tree?

AVL trees are self-adjusting, height-balanced binary search trees and are named after the inventors: Adelson-Velskii and Landis. A balanced binary search tree has O(log n) height and hence O(log n) worst case search and insertion times. However, ordinary binary search trees have a bad worst case. When sorted data is inserted, the binary search tree is very unbalanced, essentially more of a linear list, with O(n) height and thus O(n) worst case insertion and lookup times. AVL trees overcome this problem.

An AVL tree is a binary search tree in which every node is height balanced, that is, the difference in the heights of its two subtrees is at most 1. The balance factor of a node is the height of its right subtree minus the height of its left subtree (right minus left!). An equivalent definition, then, for an AVL tree is that it is a binary search tree in which each node has a balance factor of -1, 0, or +1. Note that a balance factor of -1 means that the subtree is left-heavy, and a balance factor of +1 means that the subtree is right-heavy. Each node is associated with a Balancing factor.


Balance factor of each node = height of right subtree at that node - height of left subtree at that node.



Please be aware that we are talking about the height of the subtrees and not the weigths of the subtrees. This is a very important point. We are talking about the height!.


Here is some recursive, working! C code that sets the Balance factor for all nodes starting from the root....


#include

typedef struct node
{
int value;
int visited;
int bf;
struct node *right;
struct node *left;
}mynode;

mynode *root;

mynode *add_node(int value);
void levelOrderTraversal(mynode *root);
int setbf(mynode *p);


// The main function
int main(int argc, char* argv[])
{
root = NULL;

// Construct the tree..
add_node(5);
add_node(1);
add_node(-20);
add_node(100);
add_node(23);
add_node(67);
add_node(13);

// Set the balance factors
setbf(root);

printf("\n\n\nLEVEL ORDER TRAVERSAL\n\n");
levelOrderTraversal(root);
getch();
}

// Function to add a new node to the tree...
mynode *add_node(int value)
{
mynode *prev, *cur, *temp;

temp = (mynode *) malloc(sizeof(mynode));
temp->value = value;
temp->visited = 0;
temp->bf = 0;
temp->right = NULL;
temp->left = NULL;

if(root==NULL)
{
//printf("\nCreating the root..\n");
root = temp;
return;
}

prev=NULL;
cur=root;

while(cur!=NULL)
{
prev=cur;
cur=(valuevalue)?cur->left:cur->right;
}

if(value <>value)
prev->left=temp;
else
prev->right=temp;

return(temp);

}


// Recursive function to set the balancing factor
// of each node starting from the root!
int setbf(mynode *p)
{
int templ, tempr;
int count;
count = 1;

if(p == NULL)
{
return(0);
}
else
{
templ = setbf(p->left);
tempr = setbf(p->right);

if(templ < tempr)
count = count + tempr;
else
count = count + templ;
}

// Set the nodes balancing factor.
printf("\nNode = [%3d], Left sub-tree height = [%1d], Right sub-tree height = [%1d], BF = [%1d]\n",
p->value, templ, tempr, (tempr - templ));
p->bf = tempr - templ;
return(count);
}



// Level order traversal..
void levelOrderTraversal(mynode *root)
{
mynode *queue[100] = {(mynode *)0};
int size = 0;
int queue_pointer = 0;

while(root)
{
printf("\n[%3d] (BF : %3d) ", root->value, root->bf);

if(root->left)
{
queue[size++] = root->left;
}

if(root->right)
{
queue[size++] = root->right;
}

root = queue[queue_pointer++];
}
}


And here is the output...


Node = [-20], Left sub-tree height = [0], Right sub-tree height = [0], BF = [0]
Node = [ 1], Left sub-tree height = [1], Right sub-tree height = [0], BF = [-1]
Node = [ 13], Left sub-tree height = [0], Right sub-tree height = [0], BF = [0]
Node = [ 67], Left sub-tree height = [0], Right sub-tree height = [0], BF = [0]
Node = [ 23], Left sub-tree height = [1], Right sub-tree height = [1], BF = [0]
Node = [100], Left sub-tree height = [2], Right sub-tree height = [0], BF = [-2]
Node = [ 5], Left sub-tree height = [2], Right sub-tree height = [3], BF = [1]


LEVEL ORDER TRAVERSAL

[ 5] (BF : 1)
[ 1] (BF : -1)
[100] (BF : -2)
[-20] (BF : 0)
[ 23] (BF : 0)
[ 13] (BF : 0)
[ 67] (BF : 0)




Here is the tree which we were dealing with above


5
1 100
-20 23
13 67




After insertion, the tree might have to be readjusted as needed in order to maintain it as an AVL tree. A node with balance factor -2 or 2 is considered unbalanced and requires rebalancing the tree. The balance factor is either stored directly at each node or computed from the heights of the subtrees, possibly stored at nodes. If, due to an instertion or deletion, the tree becomes unbalanced, a corresponding left rotation or a right rotation is performed on that tree at a particular node. A balance factor > 1 requires a left rotation (i.e. the right subtree is heavier than the left subtree) and a balance factor < -1 requires a right rotation (i.e. the left subtree is heavier than the right subtree).


Here is some pseudo code to demonstrate the two types of rotations...


Left rotation


BEFORE

0 (par)

0 0 (p)

0 0 (tmp)

0 0 0 0
(a) (b)



Here we left rotate the tree around node p



tmp = p->right;
p->right = tmp->left;
tmp->left = p;

if(par)
{
if(p is the left child of par)
{
par->left=tmp;
}
else
{
par->right=tmp;
}
}
else
{
root=tmp;
}

// Reclaculate the balance factors
setbf(root);




AFTER
0 (par)

0 0
(tmp)

0 0
(p) (b)

0 0
(a)

0 0






Right rotation


BEFORE

0 (par)

0 0 (p)

0 (tmp) 0

0 0 0 0
(a) (b)



Here we right rotate the tree around node p


tmp = p->left;
p->left = tmp->right;
tmp->right = p;

if(par)
{
if(p is the left child of par)
{
par->left=tmp;
}
else
{
par->right=tmp;
}
}
else
{
root=tmp;
}

// Recalculate the balancing factors...
setbf(root);




AFTER

0 (par)

0 0 (tmp)

0 0
(a) (p)

0 0
(b)

0 0




**

Continue

Write a C program to free the nodes of a linked list

Before looking at the answer, try writing a simple C program (with a for loop) to do this. Quite a few people get this wrong.


This is the wrong way to do it


struct list *listptr, *nextptr;
for(listptr = head; listptr != NULL; listptr = listptr->next)
{
free(listptr);
}


If you are thinking why the above piece of code is wrong, note that once you free the listptr node, you cannot do something like listptr = listptr->next!. Since listptr is already freed, using it to get listptr->next is illegal and can cause unpredictable results!



This is the right way to do it


struct list *listptr, *nextptr;
for(listptr = head; listptr != NULL; listptr = nextptr)
{
nextptr = listptr->next;
free(listptr);
}
head = NULL;


After doing this, make sure you also set the head pointer to NULL!

Continue

How do you reverse a linked list without using any C pointers?

One way is to reverse the data in the nodes without changing the pointers themselves. One can also create a new linked list which is the reverse of the original linked list. A simple C program can do that for you. Please note that you would still use the "next" pointer fields to traverse through the linked list (So in effect, you are using the pointers, but you are not changing them when reversing the linked list).

Continue

25 Horses.

You have 25 horses. You have 5 tracks to race on. We need to find 3 fastest horses. How many minimum races required to find that ? We have no stop-watch. Horses run at same speed.

Now this puzzle is deceptive if you are not careful enough.

Solution :

Divide the set of 25 horses into 5 non-overlapping sets of 5 horses each.
Have a race each for all the horses in eachset.
This makes it a total of 5 races, one for each set.

Now, have a race for the winners of each of the previous 5 races.
This makes it a total of 6 races.
But this step is tricky. We need to use the following logic
to identify horses for this race.

Observe the position of each horse in the 6th race and correspondingly
number the sets. i.e. the set of the winner of 6th race will be said to be set no. 1
while the set of the loser of the 6th race will be said to be set no. 5.

Now, possible candidates for the first three positions :
1. No horse from set 4 or set 5.
2. No horse from set 3, except for 1st Rank from this group.
3. No horse from set 2, except for 1st and 2nd Rank from this group
4. No horse from set 1, except for 1st, 2nd and 3rd Rank from this group

So now we have 6 candidates for top 3 positions. However, we know that the winner
of set 1 is the fastest horse in the whole group of 25 sets.

So now we have 5 candidates for the second and third position.
What better way to find out who’s who than to have a race of these 5 horses. Race them and this will solve our
problem in just 7 races.

Continue

Find two numbers in an array whose sum =X

Find if the sum of two elements in an array sum up to b (a number) with complexity of O(n)?

Input – Array : 1,2,3,4,5,6,7,8 and the sum is : 6

Output would be : {1,5} {2,4}

Solution : Here is the idea is to start from the first element of the array and keep a hashtable to store the potential pairs. We will check if sum – (a[i]) already exists in the Hashtable. If yes, we have a pair (a[i], value from hashtable) as the pair with the sum. If no, we store a[i] in the hashtable.

Here is a little dry run of array a= {1,2,3,4,5,6,7,8} and sum = 6.

6 – 1 = 5 — found in Hashtable H ? No – store it in H. H will contain (1)

6 –2 = 4 – found in Hashtable H ? No – store it in H. H will contain (1, 2)

6 –3 = 4 – found in Hashtable H ? No – store it in H. H will contain (1, 2, 3)

6 –4 = 2 – found in Hashtable H ? Yes – now we have a pair (a[i] , found in H) – (4,2)

6 –5 = 1 – found in Hashtable H ? Yes – now we have a pair (a[i] , found in H) – (5,1)

Why Hashtable ? because the lookup is always O(1) in a hashtable.

Continue

Find Duplicates from m + n elements in an array

Given an array of m+n elements in the range 1 to n ie(m elements are repeated). Find the duplicate elements.
Time Complexity: O(m+n)
Space Complexity: O(m)

Solution :

Since we know there are 1 to n elements, we can sort the array in O(n).
The first n elements will be the unique values and n to m will be the duplicates.
This is O(n+m) && no extra space required.

for (int i = 0; i < array.Length; i++)
{
if (array[i] != i + 1)
{
int t = array[array[i]-1];
array[array[i]-1] = array[i];
array[i] = t;
}
}

Continue

Small Algo

Write an algorithm to find whether a given number is a multiple of 3 or not without using modulo or division operation.

Ans: Convert the number to a string, thereby getting the decimal digits separately. Read those digits once by one and add all of them. If the sum is more than 10, repeat the procedure. Once the sum is less than 10, if it is 0, 3, 6 or 9, then the original number is divisible by 3.

Continue

Array Question

In an integer array all numbers occur exactly twice except for a single number which occurs exactly once..give an O(n) algorithm to find the number occurring only once.

Ans: Do bitwise XOR of all numbers. The result will be the number that occurs only once. The result in each position is the different number if the two bits are different, and 0 if they are the same.

public class Xor
{
public static void main(String args[])
{
int[] arr= {1,1,2,2,3,4,4,5,5};
int xOR = arr[0] ;
for(int i =1 ;i< arr.length; i++)
{
xOR = xOR ^ arr[i];
System.out.println( arr[i] + " —- " + xOR);
}
System.out.println(xOR);
}
}

Continue

Find an element in a sorted 2D Array.

You have a [n * n] array which is sorted both row wise and column wise. How do you find an element in this array in O(n) time ?

Solution: 1

1. Start from left bottom most cell.
2. If query is larger move right .
3. If query is smaller move up.
4. If you can’t move right or up and haven’t found the query yet, it means that the query does not exist.

Applying binary search for Rows and column may furthur reduce the complexity,,,

Continue

Maximum sub-sequence…

Question : Given an array all of whose elements are positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array.
Eg.
i) 3 2 7 10 should return 13 (sum of 3 and 10)
ii) 3 2 5 10 7 should return 15 (sum of 3, 5 and 7)

The idea is to use Dynamic Programming and store the intermediate “good” sums in an auxiliary array. The right way is to define an array B[n] whose j-th element B[j] represents the best sum that has A[j] as the last element.

A simplistic java code looks like this :

public class maxSkip
{
public static void main(String args[])
{
.... int[] a = {3,2,5,10,7};
.... int j,mx=0;
.... int len = a.length;
.... int[] b = new int[len];

....b[0] = a[0]; if(len==1) mx = b[0];
....b[1] = a[1]; if(len==2) mx = max(b[0],b[1]);
....b[2] = a[2]+b[0]; if(len==3) mx = max(b[1],b[2]);

.... for(j = 3 ; j< len; j++)
.... {
........ b[j] = max(a[j]+b[j-2] , a[j] + b[j-3]);
.... }
.... mx= max(b[j-2], b[j-1]);
.... System.out.println("Max subsequence : " + mx);
}
public static int max(int a, int b)
{
......return(a>b?a:b);
}
}

Continue

Max contiguous sub-sequence.

This problem is called Maximum contiguous sub sequence sum problem.
Given an array which can contain both positive and negative numbers, find the maximum contiguous sub sequence sum.
For example in an array = {2, -3, 4, -5, 6, -3, 8}, it should return 11.

Algo :

Take the array, {2, -3, 4, -5, 6, -3, 8}
Compute the partial sums up to place i for all i, {2, -1, 3, -2, 4, 1, 9}
Subtract from each element the minimum that occurs earlier (or 0), {2, -1, 4, -1, 6, 3, 11}
Take the maximum, 11

Code:

public class maxSubSeq
{
public static void main(String args[])
{
....int[] a = {2,-3,4,-5,6,-3,8};
....int[] p = new int[a.length];
....//Compute partial sums
....for(int i = 0; i ....{
....if(i==0)
.......p[i] = a[i] ;
....else
.......p[i] = a[i] + p[i-1];
....}
....//Substract from each element in p, the minimum that occur
....//earlier (or 0)
....int min=0;
....for(int i=0; i< p.length; i++)
....{
....if(i==0)
....{
....if(p[i] > 0)
........min = 0;
....else
........min = p[i];

..... p[i] = p[i] - min;
...}
....else
... {
....if(p[i] < min)
.......min = p[i];
....... p[i] = p[i] - min;
}
}

//Maximum of the resulting p would be the maximum subsequence
java.util.Arrays.sort(p);
System.out.println("The maximum subsequence - " + p[p.length-1]);
}

}

Continue

N stack 1 Array

Implement N stacks using constant sized array(space). Until the array is completely filled, I should be able to push elements to any one of the N stacks.(i.e.)Do not reserve space for the stacks. And I should also be able to pop elements from any stack.

Sounds very tricky. The idea is :

Keep an array S of N pointer, where each S_i.top will point to the top of the corresponding stack. And one global pointer gptr, which points to the next free location in the array. Now follow the steps:

Now implement Push(stackToPush) and pop(StackToPop) as follows :

Push(x, Si) //pushing x in Stack Si.
{
if(gptr > sizeof(Arr))
{
// To Be Added -- explained below
}
Arr[gptr].data = x;
Arr[gprt].prev = Si.top;
Si.top = gptr;
gptr++;
}


Pop(Si)
{
T data = Arr[Si.top].data; //T is data type
Si.top = Arr[Si.top].prev;
return data;
}

I would suggest that you try a very detailed dry-run with a little visual aid for this.

Continue

Inorder successor ?

This is one of the nasty ones, if you don’t fully understand what “Inorder successor” is. The inorder successor is the next value in an inorder traversal of a binary search tree. So how do you find the inorder successor for the node U ?

Algorithm : If node U has a right sub-tree, then the successor is the left most descendent of the right sub-tree. Otherwise, find the first ancestor that has node U in the left sub-tree.

Pseudocode :

if(node->right)
if( ! node->right->left)
return node->right;
else
{
tmp = node->right->left;
while(tmp->left)
tmp = tmp->left;
return tmp;
}

Continue

Reverse a Singly Linked List.

Reverse a singly linked list :

public void reverse()
{
Node current = head;
head = null ; //set head to null
while(current != null)
{
Node save = current;
//Interchange the pointers
current = current.next;
save.next = head;
head = save;
}
}

Continue

Chasing Dogs.

There are four dogs, each at a corner of a large square.
Each of the dogs begins chasing the dog clockwise from it.
All of the dogs run at the same speed. All continuously
adjust their direction so that they are always heading
straight toward their clockwise neighbor. How long does it
take for the dogs to catch each other? Where does this
happen?

Solution :

To make things easy, let’s say the square is 1 mile on each
side, and the dogs are genetically enhanced greyhounds that
run exactly 1 mile per minute. Pretend you’re a flea riding on
the back of Dog 1. You’ve got a tiny radar gun that tells you how
fast things are moving, relative to your own frame of reference
(which is to say, Dog l’s frame of reference, since you’re holding
tight to Dog l’s back with five of your legs and pointing the
radar gun with the sixth). Dog 1 is chasing Dog 2, who is
chasing Dog 3, who is chasing Dog 4, who in turn is chasing
Dog 1. At the start of the chase, you aim the radar gun at Dog
4 (who’s chasing you). It informs you that Dog 4 is
approaching at a speed of 1 mile per minute.
A little while later, you try the radar gun again. What
does the gun read now? By this point, all the dogs have
moved a little, all are a bit closer to each other, and all have
shifted direction just slightly in order to be tracking their
respective target dogs. The four dogs still form a perfect
square. Each dog is still chasing its target dog at 1 mile per
minute, and each target dog is still moving at right angles to
the chaser. Because the target dog’s motion is still at right
angles, each chasing dog gains on its target dog at the full
running speed. That means your radar gun must say that Dog
4 is still gaining on you at 1 mile per minute.
Your radar gun will report that Dog 4 is approaching at
that speed throughout the chase. This talk of fleas and radar
guns is just a colorful way of illustrating what the puzzle
specifies, that the dogs perpetually gain on their targets at
constant speed.
It makes no difference that your frame of reference
(read: dog) is itself moving relative to the other dogs or the
ground. One frame of reference is as good as any other. (If
they give you a hard time about that, tell ‘em Einstein said
so.) The only thing that matters is that Dog 4 approaches you
at constant speed. Since Dog 4 is a mile away from you at the
outset and approaches at an unvarying 1 mile per minute,
Dog 4 will necessarily smack into you at the end of a minute.
Fleas riding on the other dogs’ backs will come to similar
conclusions. All the dogs will plow into each other one
minute after the start.
Where does this happen? The dogs’ motions are
entirely symmetrical. It would be strange if the dogs ended
up two counties to the west. Nothing is "pulling" them to
the west. Whatever happens must preserve the symmetry of
the original situation. Given that the dogs meet, the collision
has to be right in the middle of the square.

Continue

Sorting Array of 0’s and 1’s

You are given an Array of N size. It contains 0 and 1 only. You have to arrange all 0s before all 1s (In the program you can’t travel more than once. Minimum complexity desired).

Idea : Move a pointer left, from the front, until it encounters a 1
Move a pointer right, from the end, until it encounters a 0
Swap the elements at the two pointers (if they haven’t crossed)
Repeat this for entire array – this is inplace and single pass.

Code :

public class swap01
{
public static void main(String arg[])
{
int[] a = {0,1,1,0,0,1,1,1,0};
int l =0;
int r= a.length-1;
while(l {
if(a[l] == 0)
{
l++;
}
else if(a[r] == 1)
{
r–;
}
else {
swap(a,l,r);
l++;
r–;
}
}
for(int i=0;i System.out.print(a[i] + ",");
}
private static void swap(int[] a, int l, int r)
{
int tmp = a[l];
a[l] = a[r];
a[r]=tmp;
}
}

Continue

Remove Duplicates from a String.

Given a string of ASCII characters, write the write a program to remove the duplicate elements present in them. For example, if the given string is "Potato", then, the output has to be "Pota". Additional constraint is, the algorithm has to be in-place( no extra data structures allowed)

Idea for an O(n) solution :

Let’s start with ['a','b','a','c','a','a','d','b','c']
[i:j:'a','b','a','c','a','a','d','b','c'] – [0,0,0,0] (character map for a,b,c,d)
1st charcter is an ‘a’, it’s not in the map, so we add it and increment i&j
['a',i:j:'b','a','c','a','a','d','b','c'] – [1,0,0,0]
2nd character is ‘b’, same procedure as before
['a','b',i:j:'a','c','a','a','d','b','c'] – [1,1,0,0]
third character is an ‘a’, this is already in the map, so we clear the spot, and increment only i
['a','b',j:0,i:'c','a','a','d','b','c'] – [1,1,0,0]
fourth character is ‘c’, which is not in the map; since i and j are different we add ‘c’ to the map, move it to position j, clear position i and increment i and j.
['a','b','c',j:0,i:'a','a','d','b','c'] – [1,1,1,0]
fifth and sixth character are handled like the third
['a','b','c',j:0,0,0,i:'d','b','c'] – [1,1,1,0]
seventh character is ‘d’, which is not in the map, so we handle it like the fourth one.
['a','b','c','d',j:0,0,0,i:'b','c'] – [1,1,1,1]
last two are like third case.
['a','b','c','d',j:0,0,0,0,0]:i – [1,1,1,1]
i has incremented beyond the range of the array so we’re done. We have j unique characters starting from position 0.
Code :

public static void main(String[] args) {
char[] a = {‘a’,'b’,'a’,'c’,'a’,'a’,'d’,'b’,'c’};
boolean[] ascii = new boolean[256];
int j=0;
for(int i=0;i<255;i++){
ascii[i] = false;
}
for(int i=0; i {
if(ascii[a[i]] == false)
{
ascii[a[i]] = true;
a[j] = a[i];
if (i != j)
{
a[i] = ‘0′;
}
j++;
i++;
}
else if (ascii[a[i]] == true)
{
a[j]=’0′;
a[i]=’0′;
i++;
}
}

Continue

Loop in Singly Linked List.

I am sure you must know answer to this by now. Nevertheless, its very easy to miss the most valid answers to this which is the lesser known “Tortoise and Hare Algorithm”

Solution with – O(n) time complexity

Simultaneously go through the list by ones (slow iterator) and by twos (fast iterator). If there is a loop the fast iterator will go around that loop twice as fast as the slow iterator. The fast iterator will lap the slow iterator within a single pass through the cycle. Detecting a loop is then just detecting that the slow iterator has been lapped by the fast iterator.

This solution is "Floyd’s Cycle-Finding Algorithm" as published in "Non-deterministic Algorithms" by Robert W. Floyd in 1967. It is also called "The Tortoise and the Hare Algorithm".

function boolean hasLoop(Node startNode){
Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
if (slowNode == fastNode1 || slowNode == fastNode2) return true;
slowNode = slowNode.next();
}
return false;
}

Continue

Lowest Common Ancestor in a Binary Search Tree.

Given the values of two nodes in a binary search tree, we need to find the lowest common ancestor. You may assume that both values already exist in the tree.

I/P : 4 and 14

O/P : 8 (Here the common ancestors of 4 and 14, are {8,20}. Of {8,20}, the lowest one is 8).

Algorithm:
The main idea of the solution is — While traversing Binary Search Tree from top to bottom, the first node n we encounter with value between n1 and n2, i.e., n1 <>

    private static int LCA(Node root, int x, int y){

       /* If we have reached a leaf node then LCA doesn't exist

          If root->data is equal to any of the inputs then input is

          not valid. For example 20, 22 in the given figure */

       if(root==null || root.data==x || root.data==y){

           return -1;

       }

       /* If any of the input nodes is child of the current node

       we have reached the LCA. For example, in the above figure

       if we want to calculate LCA of 12 and 14, recursion should

       terminate when we reach 8*/

       if(root.right != null && (root.right.data==x || root.right.data ==y)){

           return root.data;

       }

       if(root.left != null && (root.left.data==x || root.left.data ==y)){

           return root.data;

       }



       if(root.data > x && root.data < y){

           return root.data;

       }

       if(root.data > x && root.data > y)

       {

           return LCA(root.left, x,y);

       }

       if(root.data < x && root.data < y){

           return LCA(root.right,x,y);

       }

       return -1;

   }

Continue

Merge Two Sorted Arrays.

Problem : There are two sorted arrays A1 and A2. Array A1 is full where as array A2 is partially empty and number of empty slots are just enough to accommodate all elements of A1. Write a program to merge the two sorted arrays to fill the array A2. You cannot use any additional memory and expected run time is O(n).

Solution: The trick to solving this problem is to start filling the destination array from the back with the largest elements. You will end up with a merged and sorted destination array.

Code:

public class MergeSortedArrays {

   public static void main(String[] args) {

       int[] a = new int[] {3,6,10,12,56};

       int[] b = new int[8] ;

       b[0] = 9;

       b[1] =11;

       b[2] =36;

       //after this b looks like {9,11,36,0,0,0,0,0}

       // with enough space to accommodate 'a'

       //0 indicating a free space.

       int i = a.length-1; //a's length

       int k = b.length-1; //b's length

       //Starting point to the empty slots.

       int j = findCount(b) - 1;

       for(; k>0; k--) {

           if(j<0)

               break;



           if(a[i] > b[j])

           {

               b[k] = a[i];

               i--;

           }

           else

           {

               b[k] = b[j];

               j--;

           }

           print(b);

       }

       //Copy the leftovers which are already sorted.

       while(k>=0){

               b[k--] = a[i--];



       }

      print(b); //Final array is printed.

   }

   //Purely a debug method

   private static void print(int[] b){

       for(int x=0;x           System.out.print(b[x] + ", ");



       System.out.println("");

   }

   private static int findCount(int[] b)

   {   int i=0;

       while (b[i] != 0){

          i++;

       }

       return i;

   }

}

Continue

Merge Sorted Linked Lists.

Given two sorted Linked Lists, we need to merge them into the third list in sorted order. Complexity – O(n)

Solution :

   public Node mergeList(Node a, Node b){
       Node result = null;
       if(a==null)
           return b;
       if(b==null)
           return a;

       if(a.data <= b.data){
           result =a;
           result.next = mergeList(a.next,b);
       }
       else
       {
           result =b;
           result.next = mergeList(b.next,a);
       }
       return result;
   }

Continue

MaxHeap and MinHeap Implementations in Java

Sometimes a code-segment is worth a thousand words. Understanding the MaxHeap and MinHeaps using Java code is very easy. Here is an implementation of both.

MaxHeap :

package bst;

import java.util.ArrayList;

import java.util.List;

public class BinaryHeap {

   //ArrayList to hold the heap

    List h = new ArrayList();

   public BinaryHeap(){



   }

   //Constructs the heap - heapify

    public BinaryHeap(int[] e) {

       for(int i=0; i<e.length;i++)

       {

           add(e[i]);

       }

   }

   private int intGet(int key){

       return new Integer(h.get(key).toString()).intValue();

   }

   public void add(int key){

       h.add(null);

       int k = h.size()-1;

       while (k>0){

           int parent = (k-1)/2;

           int parentValue = new Integer(h.get(parent).toString()).intValue();

           //MaxHeap -

           //for minheap - if(key > parentValue)

            if(key <= parentValue){

               break;

           }

           h.set(k,parentValue);

           k=parent;

       }

       h.set(k,key);

   }

   public int getMax()

   {

       return new Integer(h.get(0).toString()).intValue();

   }

   public void percolateUp(int k, int key){

       if(h.isEmpty())

           return ;



       while(k < h.size() /2){

           int child = 2*k + 1; //left child

            if(child < h.size() -1 &&

              (new Integer(h.get(child).toString()).intValue() <

               new Integer(h.get(child+1).toString()).intValue()    )){

               child++;

           }

           if(key >= new Integer(h.get(child).toString()).intValue()){

               break;

           }

           h.set(k,new Integer(h.get(child).toString()).intValue());

           k=child;

       }

       h.set(k,key);

   }

   public int remove()

   {

       int removeNode = new Integer(h.get(0).toString()).intValue();

       int lastNode = new Integer(h.remove(h.size()-1).toString()).intValue();

       percolateUp(0,lastNode);

       return removeNode;

   }

   public boolean isEmpty()

   {

       return h.isEmpty();

   }



   public static void main(String[] args) {

       BinaryHeap heap = new BinaryHeap(new int[] {2,5,1});

       while(!heap.isEmpty()){

           System.out.println(heap.remove());

       }



   }

}

MinHeap :

package bst;

import java.util.*;



public class MinHeap<E extends Comparable<E>> {

 List<E> h = new ArrayList<E>();



 public MinHeap() {

 }



 public MinHeap(E[] keys) {

   for (E key : keys) {

     h.add(key);

   }

   for (int k = h.size() / 2 - 1; k >= 0; k--) {

     percolateDown(k, h.get(k));

   }

 }



 public void add(E node) {

   h.add(null);

   int k = h.size() - 1;

   while (k > 0) {

     int parent = (k - 1) / 2;

     E p = h.get(parent);

     if (node.compareTo(p) >= 0) {

       break;

     }

     h.set(k, p);

     k = parent;

   }

   h.set(k, node);

 }



 public E remove() {

   E removedNode = h.get(0);

   E lastNode = h.remove(h.size() - 1);

   percolateDown(0, lastNode);

   return removedNode;

 }



 public E min() {

   return h.get(0);

 }



 public boolean isEmpty() {

   return h.isEmpty();

 }



 void percolateDown(int k, E node) {

   if (h.isEmpty()) {

     return;

   }

   while (k < h.size() / 2) {

     int child = 2 * k + 1;

     if (child < h.size() - 1 && h.get(child).compareTo(h.get(child + 1)) > 0) {

       child++;

     }

     if (node.compareTo(h.get(child)) <= 0) {

       break;

     }

     h.set(k, h.get(child));

     k = child;

   }

   h.set(k, node);

 }



 // Usage example

  public static void main(String[] args) {

   MinHeap<Integer> heap = new MinHeap<Integer>(new Integer[] { 2, 5, 1, 3 });

   // print keys in sorted order

    while (!heap.isEmpty()) {

     System.out.println(heap.remove());

   }

 }

}

Continue

LCA of two nodes in a Binary Tree

Ah, this question has bugged me a lot. Finally I have found an answer to this. Actually there are two standard ways of doing this :

a. Do a Euler Walk on the tree and get the RMQ algorithm to calculate the LCA – cool, but for Ph,D. Students.

b. Create two array/linked list/queue and store DFS path to both the nodes and store them in these arrays. The last match in these arrays will be LCA. This solution is more practical than the first one. But the problem is how to get the DFS paths efficiently in a non BST binary tree ? If you know how to do that, please let me know in the comments.

After some research, I found a way which is smart and easier to understand.

Lets take the following tree.

We want to find the LCA for nodes – 4 and 7. LCA would be 6.

Algorithm :

We want to find the LCA of two nodes a and b.

1. Call the method LCA recursively on the left and right sub-tree. If both calls return ‘1’, it means that the current node has the parent of the left and right child and hence current node is the LCA.

2. The node that gets a ‘1’ from either left or right sub-tree returns back 1 to the parent. This node is not the parent yet but he is in the right path.

3. We need to take care of a special care where a is the parent of b or vice versa. In this case, we return 2 from one side and 0 from the other.

Code :

public static int findAncestor(Node node, int a, int b){
       if(node==null){
           return 0;
       }
       //Recursive calls to left and right sub-trees
        int l = findAncestor(node.left, a,b);
       int r = findAncestor(node.right, a,b);
       if(l==1 && r==1) //We found the LCA
        {
           System.out.println("LCA - " + node.data);
       }
       if((l==1 && r==0) || (l==0 && r==1)){
           //We found one of the element under this parent
            return 1;
       }
       if((l==2 && r==0) || (l==0 && r==2)){
           return 2;
       }
       else  //when l==0 and r==0
        {
           int matchRoot = (node.data ==a || node.data ==b) ? 1 : 0 ;
           return (l + r + matchRoot);
       }
   }

Continue

Zero-One Array Shuffle

You are given a number (either 32 or 64 bit)containing some bit pattern (or numeric value). You have to place all the 0s in even position and 1s in odd position and if suppose number of 0s exceed the number of 1s or vice versa then keep them untouched. Generalize your solution for an N bit number.
It has to be done in O(n) time, without several single loops (only one pass) and O(1)space.
For e.g.
Input Number: 0 1 1 0 1 0 1 0 1 1 1 0 0 1 0 1 1
output number: 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1

Logic : We need to maintain two pointers – oddPtr which moves along the odd positions in the array and evenPtr which moves along the even positions. When we find an incorrect position, we swap this pointers and move along.

One interesting case is when one of the pointer moves past the last element, in that case, we have no way to compare the other pointer with. In this case, we simply swap one pointer with the other position.

public class ZeroOneArray {

      public static void main(String args[]){

          int[] a = {0 ,1 ,1 ,0 ,1 ,0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1};

          int oddPtr = 1;

          int evenPtr= 0;

          while(true){

              if((oddPtr > 0 && oddPtr < a.length-1)

                  && (evenPtr>=0 && evenPtr<a.length-1)){

                  //Incorrect position found for both odd and even pointers

                   if(a[oddPtr]!=1 && a[evenPtr] !=0)

                  {

                      //Swap the incorrect positions 

                       swap(a, evenPtr, oddPtr);

                      //Move both the pointers to two places.

                       oddPtr+=2; evenPtr+=2;

                  }

                  else

                  {

                      //Correct values at correct positions

                      //Just increment pointers

                       if(a[oddPtr] ==1)

                          oddPtr+=2;

                      if(a[evenPtr] ==0)

                          evenPtr+=2;

                  }

              }

              //This is the case where one of the pointers has reached the end

              //so there is no way to find a mismatch pointer

              //In that case, we simply swap odd with even and vice versa

               else if ((evenPtr>a.length-1) && (oddPtr+2 < a.length-1)) {swap(a, oddPtr, oddPtr+2); oddPtr+=2;}

              else if ((oddPtr>a.length-1) && (evenPtr+2 < a.length-1)) {swap(a, evenPtr, evenPtr+2); evenPtr+=2;}

              else{break;}

          }



          for(int i=0;i<=a.length-1;i++){

              System.out.print(","+a[i]);

          }



      }

      private static void swap(int[] a, int even, int odd){

          int tmp = a[even];

          a[even] = a[odd];

          a[odd] = tmp;

      }

}

Continue

Intersection of Two Linked Lists.

We have two linked lists which are merged at some point. We need to find the intersection.

This shape is popularly known as Y-Shape intersection also.

Finding of intersection can be done by several methods. Some of them are listed in this excellent article.

We will discuss a simpler approach which works by getting the difference of the counts of elements in two lists and performs at O(m+n) with O(1) complexity.

Algorithm:

1) Get count of the nodes in first list, let count be c1.
2) Get count of the nodes in second list, let count be c2.
3) Get the difference of counts d = abs(c1 – c2)
4) Now traverse the bigger list from the first node till d nodes so that from here onwards both the lists have equal no of nodes.
5) Then we can traverse both the lists in parallel till we come across a common node. (Note that getting a common node is done by comparing the address of the nodes)

It is simple to code this if this concept is understood. Give it a try.

Continue

Check If the Singly Linked List is a Palindrome.

The list shows above is a palindrome and we need to check if it is indeed a palindrome. Among several approaches, the following is a simple and easy to understand method.

Algorithm:
1. Get the middle of the linked list.
2. Reverse the second half of the linked list.
3. Compare the first half and second half.
4. Construct the original linked list by reversing the
second half again and attaching it back to the first half

Time Complexity O(n)
Space Complexity O(1)

Continue

Check If the Singly Linked List has a Loop

The list shown above contains a loop – from 5 its connected to 2. There are several incorrect and inefficient methods of finding a loop. The most efficient method is discussed here.

Simultaneously go through the list by ones (slow iterator) and by twos (fast iterator). If there is a loop the fast iterator will go around that loop twice as fast as the slow iterator. The fast iterator will lap the slow iterator within a single pass through the cycle. Detecting a loop is then just detecting that the slow iterator has been lapped by the fast iterator.
This solution is "Floyd’s Cycle-Finding Algorithm" as published in "Non-deterministic Algorithms" by Robert W. Floyd in 1967. It is also called "The Tortoise and the Hare Algorithm". Further Reading on various approaches.
This algorithm has – O(n) time complexity

// Best solution
function boolean hasLoop(Node startNode){
Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
 if (slowNode == fastNode1 || slowNode == fastNode2) return true;
 slowNode = slowNode.next();
}
return false;
}

Continue

Check If Strings are Rotations of Each Other

Given a string s1 and a string s2, write a snippet to say whether s2 is a rotation of s1 Algorithm:

1. Create a temp string and store concatenation of str1 to
str1 in temp.
temp = str1+str1
2. If str2 is a substring of temp then str1 and str2 are
rotations of each other.

Example:
str1 = "ABACD"
str2 = "CDABA"

temp = str1.str1 = "ABACDABACD"
Since str2 is a substring of temp, str1 and str2 are
rotations of each other.

Continue

Measure 45 Minutes Using 2 Candles

A very famous Microsoft Interview question : You have two candles. Each burn for 60 minutes. How can you measure 45 minutes using this ?

Solution :

lay both the candles together on a horizontal surface, next to each other, but both pointing in opposite direction as shown….
<=======
=======>
now light both the candles….
when both the flames on both candles meet , exactly half an hour would hav passed…
now the candles should look like…
…..…|<===
===>|………
now rearrange the candles…
===>
<===
now wait until the flames meet…..
so that the total time elapsed will be 30 + 15 = 45 mins…
the above solution is assuming that the rate at which the candles burn doesnt change
with respect to its orientation – horizontal or vertical

OR
1.Light the first candle from both the sides and 2nd candle from one side.
2.1st canlel will finish in 30 min. while 2nd candle will be burnt half way.
3.Now light 2nd candle from both the sides. It will finish in next 15 min.
So we have calculated 45 minutes in all.

Continue