Monday, April 28, 2014

Petrol Bunks in Circle

There is a circular road, and there are n petrol bunks at different places on that road. The petrol bunk i has enough fuel by which one can travel f_i distance. The distance from the petrol bunk i to i+1 is d_i.

You have a car with empty fuel tank, and you need to find a place from where you can start and travel by that road and reach the same place.























Solution:

The distance from first bunk to second is D1, and second to third is D2 and so on.
The distance that can be travelled by the fuel in the first bunk is F1, and from the second bunk, it is F2 and so on.

If F1 < D1, then we cannot start from the first bunk.
If F1 + F2 < D1 + D2, then we cannot start from the first or second bunks.
Similarly, if F1 + F2 + F3 < D1 + D2 + D3, then we cannot start from the first, second or third bunks.

Wherever we reach the fuel to be less than the distance, we have to skip all those bunks, and have to move to the next bunk and repeat the same thing.


Code:

#include<<stdio.h>

int findStart(int distance[], int capacity[], int n)
{
 int c=0, d=0, st=0, i;
 for(i=0; i<n; i++) {
  c+=capacity[i];
  d+=distance[i];
  if(c<d) {
   st = i+1;
   c=0;
   d=0;
  }
 }
 if(st != 0) {
  for(i=0; i<st; i++) {
   c+=capacity[i];
   d+=distance[i];
   if(c<d) {
    return -1;
   }
  }  
 }
 return st;
}

main()
{
 int distance[] = {10,20,30,40,50,60};
 int capacity[] = {11,21,10,50,51,71};
 int result = findStart(distance, capacity, 6);
 printf("%d \n", result);
}

Sunday, April 27, 2014

Finding Odd Coin

Simple Problem

There are 12 coins, and one coin has less weight. We have to find the odd coin by measuring only three times.

Complex Problem

There are 12 coins, and one coin is of different weight (more or less). We have to find the odd coin by measuring only three times.
















Solutions

Simple Problem

Put 6 coins on one side and other 6 coins on another side.
Take the 6 coins of less weight, and put 3 coins on one side and another 3 coins on another side.
Take the 3 coins of less weight. Put one coin on one side and another coin on another side.

Whichever is of less weight, that is the odd coin. If both are equal, the third coin is of odd coin.


Complex Problem

Incomplete Solution

Split the 12 coins into three parts, A, B and C, and name them like A1, A2, A3, A4, B1, B2, B3, B4, C1, C2, C3 and C4.
  • Put 4 coins of A and 4 coins of B.
    • If they are equal, put 2 coins of A on one side, and put C1 and C2 on the other side, and measure the weight.
      • If they are not equal, Put A1 and C1 and measure the weight.
        • If they are not equal, C1 is the odd coin. Otherwise, C2 is the odd coin.
      • If they are equal, put 1 coin of A and C3 and measure the weight.
        • If they are equal, C4 is the odd coin. Otherwise, C3 is the odd coin.
    • If they are not equal, remember which one is of less weight. Put C1, C2, C3, C4 on one side and A1, A2, B1, B2 on another side.
      • If they are not equal, check whether AB is of more weight or less weight. If it is more weight, then in the previous step, whichever one has more weight that has the odd coin. Same thing applies, if it is of less weight. Let's say, set A has the odd coin. Measure C1 and A1.
        • If they are equal, A2 is the odd coin. Otherwise, A1 is the odd coin.
      • If they are equal, Cannot find the solution

Complete Solution

Split the 12 coins into three parts, A, B and C, and name them like A1, A2, A3, A4, B1, B2, B3, B4, C1, C2, C3 and C4.
  • Put A1, A2, A3 and A4 on one side and B1, B2, B3 and B4 on the other side.
    • If both are equal, put A1, A2, A3 on one side and C1, C2 and C3 on another side.
      • If both are equal, C4 is the odd coin. By weighing with any other coin, we can find whether it is heavier or lighter.
      • If A is heavier, it means one of C1, C2 and C3 is the lighter odd coin. Weigh C1 and C2. Whichever is of less weight, that is the odd coin. If both are equal, C3 is the lighter odd coin.
      • If C is heavier, it means one of C1, C2 and C3 is the heavier odd coin. Weigh C1 and C2. Whichever is of more weight, that is the odd coin. If both are equal, C3 is the heavier odd coin.
    • If A is heavier, put B1, B2, B3 and A4 on one side and C1, C2, C3 and B4 on another side.
      • If both are equal, One of A1, A2, A3 is heavier. Weigh A1 and A2. Whichever is heavier, that is the odd coin. If both are equal, A3 is the odd coin.
      • If B1, B2, B3 and A4 is still heavier. It means, either A4 is heavier or B4 is lighter. Weigh A4 with any other coin (other than B4). If it is equal, then B4 is the odd coin of less weight. Otherwise, A4 is the odd coin of more weight.
      • If B1, B2, B3 and A4 is lighter, then one of B1, B2 and B3 is the lighter odd coin. Weigh B1 and B2. Whichever is lighter, that is the odd coin. If both are equal, B3 is the lighter odd coin.
    • If B is heavier, do same as above. Put C1, C2, C3 and A4 on one side and A1, A2, A3 and B4 on another side and proceed the same way.

Saturday, April 26, 2014

No Child After a Girl Child

Government introduced a rule saying, once a couple gets a girl child, they should not have any more children. What would be the ratio of boys to girls after n years?




It would be 1:1 only [If we assume, for any birth the ratio of boy to girl is 1:1].

Let's suppose, if there 1000 couples. If we take 1:1 in the births, then 500 would give birth to boys and 500 would give birth to girls.

The couple who gave birth to girls will not conceive anymore. The 500 couple who gave birth to boys would give birth to 250 boys and 250 girls in the next delivery.

The couple who gave birth to 250 girls would stop conceiving, and the remaining 250 couple would try again.

They would give birth to 125 boys and 125 girls.

The same thing is repeated and the ratio would be 1:1 at the end.

Friday, April 25, 2014

Converting a Tree into an Array

Call traverse(root, array, 0);

int traverse(Node root, int[] a, int index)
{
   if(node == NULL)
      return index;
   int x = traverse(root->left, a, index);
   a[x] = root->data;
   x = traverse(root->right, a, x+1);
}

Thursday, April 24, 2014

Copy a Linked List in C

Node Copy(Node first)
{
   if(first == NULL)
      return NULL;
   Node copy = (Node)malloc(sizeof(Node));
   Node temp = copy;

   while(first->next != NULL) {
      temp->data = first->data;
      temp->next = (Node)malloc(sizeof(Node));
      temp = temp->next;
      first = first->next;
   }
   temp->data = first->data;
   return copy; 
}

Wednesday, April 23, 2014

No.of Nodes in a Tree

int Count(Node root)
{
   if(root == NULL)
      return 0;
   return 1 + Count(root->left) + Count(root->right);
}

Tuesday, April 22, 2014

Delete all the nodes in a Tree in C


void Clear(Node root)
{
   if(root == NULL)
      return;
   Clear(root->left);
   Clear(root->right);
   free(root);
}

Monday, April 21, 2014

Find Colored Couples

In an array of colors, we need to find out the no.of colored couples of the same color that are next to each other. If you find a colored couple, then you can remove that couple, and check whether any more couples can be formed by that or not.

Example

R G B B G R Y W Y

In the above, there are two B's next to each other. That is one couple, and we can remove that. After removing both the B's, the colors would be like

R G G R Y W Y

Now, there is another pair of G's in this. After removing that, the colors would be like below.

R R Y W Y

after removing R, it would be like below.

Y W Y.

At this time, there are no colored couples that are next to each other. In this case, there are three couples in the given array.


Answer:

Stack:

Stack is the simplest approach to solve this problem. If we can modify the input array, then we can use the input array itself as stack to solve this problem.

We take the first element, and push it to the stack.

If the stack contains any elements, then we take the top element and take the next element in the input array and compare the elements. If both are same, then we found one couple. We pop the element, and we move forward.

If the elements are not same, then we just push that element to the stack and proceed.

With this, by the time we reach the end, we would find the total no. of paired couples.


Doubly Linked List:

If the input elements is given in the form of Doubly Linked List, and if we can modify the input, then from that also, we can easily find the count.

We will have two pointers. Initially, first pointer would point to first element, and second pointer would point to second element. If both are different, then both pointers would move one step forward. If they are same, then the first pointer would move backward, and second pointer would move forward. We also would clear the two colors, and adjust the pointers in the doubly linked list. We repeat the loop.


Code for Stack:

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
class color
{
 private:
 char *array;
 int length;

 public:

 void init(char *c) 
 {
  array = c;
  length = 0;
 };
 
 void push(char x)
 {
  array[length] = x;
  length++;
 };

 char pop() { return array[--length]; };

 char top() { return array[length-1]; };

 int exists() { return length; };
};

main(int argc, char **argv)
{
 char a[1000];
 int n, i, j, c=0;
 if(argc != 2) {
  printf("Usage: colorpairs colorstring\n");
  return -1;
 }
 strcpy(a, argv[1]);
 n = strlen(a);

 class color clr;
 clr.init(a);
 clr.push(a[0]);
 for(int k=1; k<n; k++) {
  if(clr.exists() && clr.top() == a[k]) {
   clr.pop();
   c++;
  } else {
   clr.push(a[k]);
  }
 }
 printf("Count: %d\n", c);
 return 0;
}

Code for Doubly Linked List:

findCount(Node *head)
{
 if(head == NULL || head->next == NULL)
  return 0;

 Node *first = head;
 Node *second = head->next;
 Node *free1, *free2;
 int count = 0;

 while(second != NULL) {
  if(first->value == second->value) {
   count++;
   free1 = first;
   free2 = second;

   if(second->next == NULL) 
    break;

   if(first->prev == NULL) {
    first = second->next;
    second = second->next->next;
   } else {
    first = first->prev;
    second = second->next;
   }

   first->next = second;
   second->prev = first;   

   free(free1);
   free(free2);
  } else {
   first = first->next;
   second = second->next;
  }
 }
 return count;
}

Sunday, April 20, 2014

Check Whether the tree is Balanced Tree or Not

A tree is a balanced tree, if the heights of the left and right sub trees differ by at max 1 at all the nodes.

The code which checks only at the root level

bool IsTreeBalanced(Node root)
{
  if(root == NULL)
    return true;
  int lh = GetDepth(root -> left);
  int rh = GetDepth(root -> right);
  if(lh - rh > 1 || rh - lh > 1)
     return false;
  return true;
}

int GetDepth(Node root) 
{
   if(root == NULL)
      return 0;
   int lh = GetDepth(root->left);
   int rh = GetDepth(root->right);
   return (lh > rh ? lh + 1 : rh + 1);
}


The code which checks at all the levels, but, not optimized
bool IsTreeBalanced(Node root)
{
  if(root == NULL)
    return true;
  int lh = GetDepth(root -> left);
  int rh = GetDepth(root -> right);
  if(lh - rh > 1 || rh - lh > 1 || ! IsTreeBalanced(root->left) || ! IsTreeBalanced(root->right))
     return false;
  return true;
}

int GetDepth(Node root) 
{
   if(root == NULL)
      return 0;
   int lh = GetDepth(root->left);
   int rh = GetDepth(root->right);
   return (lh > rh ? lh + 1 : rh + 1);
}

The code which checks at all the levels, and optimized little

This code does not give the accurate height. If at few levels itself, if it finds that, it is not balanced, it would just return.

In C#, we can use out parameters. In C, C++, we can use pointers, and in java, we need to have some kind of holder class.

bool IsTreeBalanced(Node root, out int height)
{
  if(root == NULL) {
    height = 0;
    return true;
  }
  int lh, rh;
  if(! IsTreeBalanced(root -> left, out lh)) {
    height = lh + 1;
    return false;
  }
  if(! IsTreeBalanced(root -> right, out rh)) {
    height = (lh > rh ? lh + 1 : rh + 1);
    return false;
  }

  height = (lh > rh ? lh + 1 : rh + 1);

  if(lh - rh > 1 || rh - lh > 1)
     return false;
  return true;
}

Very strict Balanced Tree: (In practice, not advisable)

Where the the path length of the nearest empty child is within one from the path to the farthest empty child.

bool IsTreeBalanced(Node root)
{
  int max = GetMaxMinDepth(root, min);
  if(max - min > 1)
     return false;
  return true;
}

int GetMaxMinDepth(Node root, out int minDepth) 
{
   if(root == NULL) {
      minDepth = 0;
      return 0;
   }
   int lmin, rmin;
   int lmax = GetMaxMinDepth(root->left, out lmin);
   int rmax = GetMaxMinDepth(root->right, out rmin);
   minDepth = lmin < rmin ? lmin + 1 : rmin + 1;
   return (lmax > rmax ? lmax + 1 : rmax + 1);
}

Saturday, April 19, 2014

In Binary Tree, Find Sum of Nodes of Alternate Levels

Given a binary tree, find sum of all the nodes of alternate levels.

Root is at level 0.
All the children of root are at level 1.
All the grand children of root are at level 2.
and so on.

Given a level n, find some of all the nodes that are at alternate levels 0, 2, 4, and so on.

int Sum(Node root, level n)
{
   if(root==NULL)
      return 0;
   int d = (n%2 == 0 ? root->data : 0);
   return d + Sum(root->left, n+1) + Sum(root->right, n+1);
}

Thursday, April 17, 2014

In a Binary Tree, find sum of all the nodes below certain level

Given a binary tree, find sum of all the nodes below certain level.

Root is at level 0.
All the children of root are at level 1.
All the grand children of root are at level 2.
and so on.

Given a level n, find some of all the nodes that are at level n or more.

int Sum(Node root, level n)
{
   if(root==NULL)
      return 0;
   if(n>0)
      return Sum(root->left, n-1) + Sum(root->right, n-1);
   return root->data + Sum(root->left, n-1) + Sum(root->right, n-1);
}

Wednesday, April 16, 2014

In A Binary Tree, Find sum of all nodes upto certain level

Given a binary tree, find sum of all the nodes upto certain level.

Root is at level 0.
All the children of root are at level 1.
All the grand children of root are at level 2.
and so on.

Given a level n, find some of all the nodes that are at level n or less.

int Sum(Node root, level n)
{
   if(root==NULL)
      return 0;
   if(n==0)
      return root->data;
   return root->data + Sum(root->left, n-1) + Sum(root->right, n-1);
}

Tuesday, April 15, 2014

In a Binary Tree, Find Sum of all the nodes

Given a binary tree, find the sum of all the nodes.

int SumOfNodes(Node root)
{
   if(root==NULL)
      return 0;
   return root->data + SumOfNodes(root->left) + SumOfNodes(root->right);
}

Monday, April 14, 2014

Find whether two strings are anagrams of each other or not

Given a two strings, find whether they are anagrams of each other or not.

Anagram means, rearranging of the characters in the string.

Ex:
mary and army are anagrams.
abba and abab are anagrams
abba and abbb are not anagrams



Answer:

Assumption: The characters are ASCII characters

AreAnagrams(char a[], char b[])
{
   int count[128];
   int n=strlen(a);

   if(n!=strlen(b))
      return false;

   for(int i=0; i<127; i++)
      count[i]=0;
   
   for(int i=0; i<n; i++)
      count[a[i]]++;
   for(int i=0; i<n; i++)
      count[b[i]]--;

   for(int i=0; i<127; i++)
      if(count[i]!=0)
         return false;

   return true;
}

Sunday, April 13, 2014

Efficiently Right Shift a String

You are given a string and a number k. You need to right shift the string k times. What is the efficient way to solve this?

Example:
the string is "Democracy".
If k is 2, then the output should be "cyDemocra".
If k is 3, then the output should be "acyDemocr"






Answer 1:

O(nk) time complexity, O(1) space complexity.

where n is the length of the string.

Right shift the string k times.

main()
{
    char s[] = "Some string ....";
    int n = streln(s);

    for(int i=0; i<k; i++)
        rightShift(s, n);
}

rightShift(char s[], int length)
{
   char temp = s[length-1];
   for(int i=length-1; i>0; i--)
       s[i]=s[i-1];
   s[0] = temp;
}

Answer 2:

O(n) time complexity, and O(k) space complexity

char s[] = "Some string ....";
int n = streln(s);
char *exsp = (char*)calloc(k, sizeof(char));

for(int i=0; i<k; i++)
   exsp[i]=s[n-k+i];

for(int i=n-1; i>=k; i--)
   s[i]=s[i-k];

for(int i=0; i<k; i++)
   s[i]=exsp[i];

Answer 3:

O(n) time complexity, O(1) space complexity

Reverse the entire array.
Reverse the array from 0 to k-1, and from k-1 to n-1.

Reverse(char s[], int start, int end)
{
    for(int i=start, j=end; i<j; i++, j--)
    {
        int t=s[i];
        s[i]=s[j];
        s[j]=t;
    }
}

Reverse(s, 0, n-1);
Reverse(s, 0, k-1);
Reverse(s, k, n-1);