Saturday, September 3, 2011

Implement Queue using Stacks


A queue can be implemented using two stacks.
Let queue to be implemented be q and stacks used to implement q be stack1 and stack2. 
q can be implemented in two ways:

Method 1 (By making enQueue operation costly)
This method makes sure that newly entered element is always at the top of stack 1, 
so that deQueue operation just pops from stack1. To put the element at top of stack1, stack2 is used.

enQueue(q, x)
  1) While stack1 is not empty, push everything from satck1 to stack2.
  2) Push x to stack1 (assuming size of stacks is unlimited).
  3) Push everything back to stack1.

deQueue(q)
  1) If stack1 is empty then error
  2) Pop an item from stack1 and return it

Method 2 (By making deQueue operation costly)
In this method, in en-queue operation, the new element is entered at the top of stack1.
In de-queue operation, if stack2 is empty then all the elements are moved to stack2 and finally top of stack2 is returned.

enQueue(q,  x)
  1) Push x to stack1 (assuming size of stacks is unlimited).

deQueue(q)
  1) If both stacks are empty then error.
  2) If stack2 is empty
       While stack1 is not empty, push everything from satck1 to stack2.
  3) Pop the element from stack2 and return it.


Method 2 is definitely better than method 1. Method 1 moves all the elements twice in enQueue operation, 
while method 2 (in deQueue operation) moves the elements once and moves elements only if stack2 empty.

Queue can also be implemented using one user stack and one Function Call Stack. 
Below is modified Method 2 where recursion is used to implement queue using only one user defined stack.

enQueue(x)
  1) Push x to stack1.

deQueue:
  1) If stack1 is empty then error.
  2) If stack1 has only one element then return it.
  3) Recursively pop everything from the stack1, store the popped item
    in a variable res,  push the res back to stack1 and return res

The step 3 makes sure that the last popped item is always returned and since the recursion stops when there is only one item in stack1 (step 2), we get the last element of stack1 in dequeue() and all other items are pushed back in step 3.

Levenshtein Distance

int LevenshteinDistance(char s[1..m], char t[1..n])
{
  // for all i and j, d[i,j] will hold the Levenshtein distance between
  // the first i characters of s and the first j characters of t;
  // note that d has (m+1)x(n+1) values
  declare int d[0..m, 0..n]

  for i from 0 to m
    d[i, 0] := i // the distance of any first string to an empty second string
  for j from 0 to n
    d[0, j] := j // the distance of any second string to an empty first string

  for j from 1 to n
  {
    for i from 1 to m
    {
      if s[i] = t[j] then  
        d[i, j] := d[i-1, j-1]       // no operation required
      else
        d[i, j] := minimum
                   (
                     d[i-1, j] + 1,  // a deletion
                     d[i, j-1] + 1,  // an insertion
                     d[i-1, j-1] + 1 // a substitution
                   )
    }
  }

  return d[m,n]
}
k i t t e n
0 1 2 3 4 5 6
s 1 1 2 3 4 5 6
i 2 2 1 2 3 4 5
t 3 3 2 1 2 3 4
t 4 4 3 2 1 2 3
i 5 5 4 3 2 2 3
n 6 6 5 4 3 3 2
g 7 7 6 5 4 4 3
  
S a t u r d a y
0 1 2 3 4 5 6 7 8
S 1 0 1 2 3 4 5 6 7
u 2 1 1 2 2 3 4 5 6
n 3 2 2 2 3 3 4 5 6
d 4 3 3 3 3 4 3 4 5
a 5 4 3 4 4 4 4 3 4
y 6 5 4 4 5 5 5 4 3

Find the Minimum length Unsorted Subarray, sorting which makes the complete array sorted

Example : 10,12, 20,30, 25,40,32,31,35,50,60

1) Find the candidate unsorted subarray

    a) Scan from left to right and find the first element which is greater than the next element.Let s be the index of such an element. In the above example 1, s is 3 (index of 30).
    b) Scan from right to left and find the first element (first in right to left order) which is smaller than the next element (next in right to left order).Let e be the index of such an element.In the above example 1, e is 7 (index of 31).

2) Check whether sorting the candidate unsorted subarray makes the complete array sorted or not. If not, then include more elements in the subarray.

   a) Find the minimum and maximum values in arr[s..e]. Let minimum and maximum values be min and max. min and max for [30, 25, 40, 32, 31] are 25 and 40 respectively.
   b) Find the first element (if there is any) in arr[0..s-1] which is greater than min, change s to index of this element.There is no such element in above example 1.
   c) Find first element (if there is any) in arr[e+1..n-1] which is smaller than max, change e to index of this element.In the above example 1,e is changed to 8 (index of 35)

3) Print s and e.

Find the pair from an sorted array whose difference is x

Here is an inplace solution with O(n) complexity.

i=0,j=1;
while((i!=n-1) or j!=n)
{

  /*compare difference of a[j] and a[i]*/
  if( (a[j]-[a[i]])>x ) {
    i++;j++;
  }

  else if( (a[j]-a[i]) {
    j++;
  }

  else 
  {
  /*SOLUTION*/
  return;
  }

}

Find 10 maximum integer out of 1 million integers

You Have File of Containing 1 Million Integers You need To Find 10
Maximum Integer Out of Them.How You Will Do That. What is Time &
space Complexity of Algorithm that you will use then optimize the
solution..

Constraints- U can't Store Whole File in memory @ one time e.g. if u
will do that gigabyte of memory may be required so that should be
avoided.

Answer:
Using the first 10 numbers, build a max heap. Then add each
number into the 11th array position (always the 11th position) and
perform the up-heap operation. At the end of the input, discard the
11th number in the heap. The remaining numbers will be the 10 maximum.
O(n log k) where n = the number of items in the list and k = the
number of maximum items you want.

Find whether given tree is a subtree or not


Given two binary trees T1 and T2 which store character data, duplicates allowed. You have to devise an algorithm to decide whether the T2 is a subtree of T1. T1 has millions of nodes and T2 has hundreds of nodes.

 Pseudo code :
check( node t1 , node t2 ) 
{
   if ( t1->data == t2->data)
  {
     return check( t1->left , t2->left ) && check(t1->right, t2->right) ; 
  }
  else
  {
     return check(t1->left , t2) || check(t1->right , t2); 
  }
}

Time complexity :O(n) because each node in T1 needs to be visited once.

Given an array of integers, each element represents the max number of jumps can make forward. What is the minimum number of element selections to reach the end of the array

Given an array of integers, each element represents the max number of jumps can make forward. 
What is the minimum number of element selections to reach the end of the array (starting from the first element) ?

Example: arr = 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9
Here the min # of selections is : 3
with the sequence : 1-> 3 -> 8 ->9
First element is 1, so can only go to 3.
Second element is 3, so can make at most 3 jumps: eg to 5 or 8 or 9.
If an element is 0, then cannot make any jumps

Implementation  : Using Dynamic programming - 

int find_min_steps(int arr[], int n)
{
  // min_steps_dp[i] is an array which 
  // indicate minimum jumps required to reach i. 
  int min_steps_dp[20];
  int i, temp, next_vacant;
  // next_vacant : Is the index in the array whose min_steps needs to be updated
  // in the next iteration.
  next_vacant = 1;
  for(i=0;i= n)
    {
      min_steps_dp[n-1] = min(min_steps_dp[n-1],min_steps_dp[i] +1);
    }
    else
    {
      min_steps_dp[temp] = min(min_steps_dp[temp],min_steps_dp[i]+1);
    }
    if(temp>next_vacant)
    {
      for(;next_vacant<temp;next_vacant++)
      {
      // this loop executes only ONCE for each element in the array, so over the
      // course of execution, is an O(n) loop only. 

        min_steps_dp[next_vacant] =min(min_steps_dp[next_vacant],min_steps_dp[temp]);
      }
    }
  }
  for(i=0;i<n;i++)
  {
    printf("%d ",min_steps_dp[i]);
  }
  return min_steps_dp[n-1];
 
}
main()
{
  int arr[] = {1,3,5,8,9,2,6,7,6,8,9};
  int len;
  len = sizeof(arr)/sizeof(arr[0]);
  printf("\n MIN steps : %d\n",find_min_steps(arr,len));
}