Constructing Tree From Inorder and Preorder

ConstructTree(preorder, 0, preOrder.Length-1, inorder, 0, inorder.Length-1);

Node ConstructTree(int[] preorder, int ps, int pe, int[] inorder, int is, int ie)
{
  if(ps < pe || is < ie)
    return NULL;
  Node root = new Node();
  root->data = preorder[ps];
  int mid = is;
  while(inorder[mid] != preorder[ps]) 
    mid++;
  root->left = ConstructTree(preorder, ps+1, ps+mid-is, inorder, is, mid-1);
  root->right = ConstructTree(preorder, ps+mid-is+1, pe, inorder, mid+1, ie);
  return root;
}

Princess, Flowers and Snake With Incorrect Name Plates

There are three rooms, and there are Princess, Flowers and Snake in those rooms. The doors of all the rooms have incorrect nameplates. i.e., the nameplate for the princess' room is not Princess. Similarly, the nameplate for the Flowers' room is not Flowers. You need to find the room of the Princess without going to the room of Snake. How do you find?



Answer:

Go to the room which has the nameplate Snake. That will not have Snake. If the room has princess, you are done. If the room has flowers, then go to the room which has nameplate flowers. Princess would be there in that room. [Since, Princess cannot be there in the room which has nameplate Princess.]

One Person Always Lies, Another always Tells Truth

You have to go to a place and there are two paths. You don't know which path leads to your destination. There are two watchmen at the entrance. One person always tells truth, and another one always tells lies. You can ask only one question to one person. What question would you ask to find the way to your destination?



Answer:
If I ask the other person, the way to the destination, what would he tell?

Whatever he says, that is not the correct path. Take the other path.

Four People crossing the river with different speeds

There is a dark tunnel and four people wants to cross the tunnel. In the tunnel, only two people can travel at a time, and there is only one torch light. Without the torch light, they cannot travel through the tunnel. The four people can travel with different speeds. The first person takes 1 hour to travel through the tunnel. Second person takes 2 hours, third person takes 5 hours, and fourth person takes 10 hours. How can they travel in the least amount of time?



Solution:

1 & 2 cross the tunnel

1 returns

5 & 10 cross the tunnel

2 returns

1 & 2 cross the tunnel

Total Time: 17 hours

Three Cannibals and Three Humans Crossing River

There is a small river. On one side of the river, there are three cannibals, and on another side three humans are there. Boat is with the cannibals. If there are more no.of cannibals than the humans, then the cannibals will eat the humans. If the no.of cannibals is equal or less than the no.of humans, then they cannot do anything. How do the humans move to the other side of the river safely?













Answer:

3 Cannibals - 3 Humans

One Cannibal crosses the river

2 Cannibals - 3 Humans, 1 Cannibal

2 Humans cross the river

2 Cannibals, 2 Humans - 1 Human, 1 Cannibal

1 Human and 1 Cannibal cross the river.

1 Cannibal, 1 Human - 2 Humans, 2 Cannibals

2 Humans cross the river

1 Cannibal, 3 Humans - 2 Cannibals

1 Cannibal crosses the river

3 Humans - 3 Cannibals.

Find the Distance Travelled By the Prince

A Prince is going to a temple in a forest by his horse which travels at a speed of 60 km per hour. When he reached the entrance of the forest, he saw a girl who is going to the temple at a speed of 6 kms per hour. He visits the temple and returns to see the girl immediately. After he sees the girl, he goes again to the temple. He roams between the temple and girl, till the girl reaches the temple after one hour. How much distance the prince travelled by roaming between the girl and the temple?











Answer:

If we try to calculate how many no.of times, the prince has visited the temple or girl etc., the problem becomes complicated. The simple to way to solve the problem is, how long the prince has travelled, and from that calculate the distance. The prince has travelled as long as the girl was walking towards the temple. The girl took one hour to reach the temple. For that one hour, the prince was travelling. So, he travelled total 60 kms.

Finding the Poison Bottle

A king has arranged a celebration with many visitors to his kingdom. In the celebration, they arranged drinks in 1000 bottles. Just one hour before the celebration, he came to know that, one person has included a poison drink of the same color in a bottle of the same shape. If anyone drinks poison, then nothing happens to that person for one hour. After one hour, suddenly that person would die.

The king has few criminals who are going to be hanged the next day. With the help of them, he can find which bottle has poison. How many minimum no.of criminals he needs to find out the poisoned bottle in one hour.









Answer:
He needs 10 criminals.

Every bottle is given a no from 0 to 1000. Convert each number to binary. The binary number would contain 10 bits. For the first criminal, give little drink from all the bottles for which the first bit is 1. Similarly, for the second criminal, give drink from all the bottle for which the second bit is 1. Do the same thing for all the ten criminals.

After one hour, form a binary number with the criminals. If the first criminal dies, then make the first bit 1. If the second criminal does not die, then make the second bit 0. Do the same for all the criminals. Convert the binary number to the corresponding decimal number. That bottle has the poison.

Sending a parcel by unsecured courier

You have a gift item which you want to send by courier from Hyderabad to Chennai. You have only one box. You have a lock and key, and the receiver also has a lock and key. If you send the gift item without locking in the box, then the courier person will take it. How do you send the gift item to the receiver safely?


Answer

Put the gift item in the box and lock it, and keep the key with you. Send that box to the receiver by courier. The receiver puts his/her lock and keeps the key with him/her. He/She returns the box to you by courier, and you will remove your lock, and send the box again by courier to him/her. He/She removes his/her lock and takes the gift item.

Print an Integer by using only putchar

#include<stdio.h>
main(int argc, char **argv)
{
    int i, n, rev, lz = 0;
    if(argc > 1) {
        n = atoi(argv[1]);
    } else {
        printf("Enter the number : ");
        scanf("%d", &n);
    }
    rev = 0;
    lz = 0;
    while(n != 0) {
        if(rev == 0 && n%10 == 0) {
            lz++;
        }
        rev = rev*10 + n%10;
        n = n/10;
    }
    while(rev != 0) {
        putchar(rev%10 + '0');
        rev = rev/10;
    }
    while(lz--) {
        printf("0");
    }
    printf("\n");
}

Find the repeated element

There are n elements in an array, and one element is repeated n/2 times (n is even), and other n/2 numbers are unique. Find the element that is repeated n/2 times.

Simple Solution:

In the array, take the first element and compare with second and third. If it is same as any other, that is the answer. Otherwise, take the second element and compare with the third and fourth elements, and so on. There is only one exception in this. If the no.of elements is 4, and if the input is like a, b, c, a, then this solution will not work. In that case, For the last two elements, we can compare with the first element or first two elements depending on whether it is last but one element or last element.

Optimum Solution:

The following gives the solution in n/2+2 comparisons

int FindRepeatedElement(int a[], int n)
{
 int i;
 for(i=0; i<n-1; i+=2) {
  if(a[i] == a[i+1])
   return a[i];
 }
 if(a[0] == a[2])
  return a[0];
 if(a[0] == a[3])
  return a[0];
 return a[1];
}

Highest Floor to Drop Egg Without Breaking

You have two identical eggs. What is the highest floor of a 36-story building from which you can drop an egg without it breaking? If an egg survives a drop without breaking, it is as good as new. That is, you can then conduct another dropping experiment with it. What is the smallest number of drops that is sure to determine the answer?

Answer:

Take the first egg, and drop it from 6, 12, 18, 24, 30, 36. Let's suppose, if it breaks on 18th floor, take the second egg and drop it from 13th floor till 17th floor. With that, you will come to know the highest floor from which you can drop without breaking.

Generic Solution

If the building has n floors, then take the first egg and drop it from sqrt(n), 2*sqrt(n), 3*sqrt(n) and so on. If it breaks on any floor, take the second egg and start dropping from the next floor to the previous floor where we tried.

The maximum no.of times we drop in this method is 2*sqrt(n).

Even More Generic Solution

If the building has n floors, and if we have m eggs, then take the first egg, and drop it from 1*n^((m-1)/m), 2*n^((m-1)/m), .. , n^(1/m)*n^((m-1)/m).

If it breaks on floor x, then start dropping the egg from x + 1*n^((m-2)/m), x + 2*n^((m-2)/m), ... x + n^(1/m)*n^((m-2)/m) and so on.

The maximum no.of times we drop in this method is m*n^(1/m).

Printing a tree on a console

You are given a tree, and you need to print it on a console. The root node should be at the center of the first row. Left child of the root should be at the center of the first half of the console, and right child of the root should be at the center of the second half of the console. Similarly, the left child of the left child of the root should be at the center of the first quarter of the console, and so on. You have a function printxy(row, column, data) which prints at the give row and column.

Answer:

void print(int row, int startCol, int endCol, Node tree)
{
    if(tree==NULL)
        return;
    printxy(row, (startCol+endCol)/2, tree->data);
    print(row+1, startCol, (startCol+endCol)/2, tree->left);
    print(row+1, (startCol+endCol)/2+1, endCol, tree->right);
}

call print(1, 1, colsInConsole, root);

Finding the Celebrity

In a function, there is one celebrity. Everyone knows the celebrity and celebrity does not know anyone. Among the other people in the function, few people know few others. You can ask only one type of question, "Do you know this person or not?". How do you find the celebrity by asking minimum no.of questions?


Answer:

Ask the first person, whether he/she knows the second person or not. If the first person knows the second person, it means, first person is not a celebrity. We don't know whether the second person is a celebrity or not. If the first person does not know the second person, it means, second person is not a celebrity, and we don't know about the first person. By asking this question, we eliminated one person.

After eliminating one person, we can ask the remaining person, whether he/she knows the third person or not. Again from the answer he/she gives, we can eliminate one of them. If we repeat the same procedure, when we ask (n-1)th question, if the reply is no, then the person whom we asked the question, is the celebrity. Otherwise, the other person is the celebrity.

Given a matrix of relationships, the following program gives the celebrity. In the following program, a[i][j] is 1, if i knows j. It is 0, if i does not know j.

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
main(int argc, char **argv)
{
 int **a;
 int n, i, j, c;
 if(argc >= 3) {
  n = atoi(argv[1]);
  c = atoi(argv[2]);
 } else {
  printf("Enter the no.of people including celebrity \n");
  scanf("%d", &n);
  printf("Enter the index of the celebrity (0 to %d)\n", n-1);
  scanf("%d", &c);
 }
 if(c < 0 || c > n-1) {
  c = n-1;
 }

 if(argc >= 4) {
  srandom(atoi(argv[3]));
 } else {
  time_t time;
  localtime(&time);
  printf("Used the seed %lu\n", time);
  srandom(time);
 }

 a = (int**)calloc(n, sizeof(int*));
 if(a==NULL) {
  printf("Unable to allocate memory\n");
  exit(-5);
 }
 for(i=0; i<n; i++) {
  a[i] = (int*) calloc(n, sizeof(int));
  if(a[i] == NULL) {
   printf("Unable to allocate memory\n");
   exit(-5);
  }
 }
 for(i=0; i<n; i++) {
  for(j=0; j<n; j++) {
   if(i==j) {
    a[i][j]=1;
   } else if(i==c) {
    a[i][j]=0;
   } else if(j==c) {
    a[i][j]=1;
   } else {
    a[i][j]=random()%2;
   }
   printf("%d ", a[i][j]);
  }
  printf("\n");
 }
 printf("Random numbers are generated\n");
 printf("Celbrity is %d\n", findCelebrity(a, n));
}

int findCelebrity(int **a, int n)
{
 int i;
 int p = 0, q = 1;
 for(i=0; i<n-2; i++) {
  if(a[p][q] == 1) {
   // P is not a celebrity
   p = (p>q ? p+1 : q+1);
  } else {
   // Q is not a celebrity
   q = (p>q ? p+1 : q+1);
  }
 }
 if(a[p][q] == 1) 
  return q;
 return p;
}

Speed of train going through a tunnel

There is a tunnel with a train track and two people are at 1/4th distance from one end of the tunnel. They heard the train sound, and both started running in the opposite directions immediately. Both barely missed the train from hitting. Both run at the same speed. What is the speed of the train?

It is not possible to find the speed of the train with just this information. But, if this kind of question is asked in the interviews, it means, we need to find the speed of the train relative to others like the speed of the person, or the distance of the tunnel etc.



In the above diagram, AB is the tunnel, and AC is 1/4th of the tunnel and BC is 3/4th of the tunnel. The train is at D when they heard the train sound.

The train enters the tunnel at point A. If the train enters the tunnel at point B, then both will not miss the train barely. If the train enters the tunnel at point B, By the time the person travels from C to B, the other person can comfortably cross the tunnel. So, the train enters the at point A only.

Since both barely missed the train, it means, both the train and the first person reached point A at the same time. At that time, the second person would be at the middle of the tunnel. The second person also misses the train barely at point B. It means, by the time, the second person reaches from the middle of the tunnel to B, the train reached from point A to B. It means, the train travels twice faster than the person.

By the time, the first person reached from C to A, the train reached from D to A. From the relative speeds of the person and the train, we can conclude that, DA is double to CA, and half of AB.

Finding Maximum Sum of Sub Sequence

Given an array of integers, find the maximum sum of Sub Sequence.

For example, if the array is, 4 5 6 -2 3 4 -10 1 2 3, then the maximum sum is 20, and the range is 0 to 5.

If the array is, 1 2 3 -10 4 5 6 -2 3 4, then the maximum sum is 20, and the range is 4 to 9.

#include<stdio.h>
main()
{
  int i, n;
  int a[100];
  int start=-1, end=-1, sum=0;
  int maxstart=-1, maxend=-1, maxsum=0;
  printf("Enter the count: ");
  scanf("%d", &n);
  printf("Enter the numbers\n");
  for(i=0; i<n; i++) {
    scanf("%d", &a[i]);
  }
  start = 0;
  end = 0;
  for(i=0; i<n; i++) {
    sum += a[i];
    end = i;
    if(sum < 0) {
      start = i+1;
      sum = 0;
    }
    if(sum > maxsum) {
      maxstart = start;
      maxend = end;
      maxsum = sum;
    }
  }
  printf("sum = %d\nstart = %d\nend = %d\n", maxsum, maxstart, maxend);
}

How will you write your own sizeof operator

#define MySizeof(x) (char*)((x*)NULL+1)-(char*)((x*)NULL)

Setting Element to Zero

An array contains two elements. One is 0 and another one is 1. We don't know the position of 0 or 1. If we cannot do anything other than complement, and assignment. Direct assignment of 0 is not allowed.

Answer:
a[a[1]] = a[a[0]]

What is the Radius of the Circle?

Answer is in comments.

Rabbit and the Hunter

A rabbit is in a circular pond and on its edge stands a hunter who wants to catch it.

The hunter can move across the circumference of the pond at 4 times the speed at which the rabbit can swim. However the hunter cannot enter the pond and if the rabbit swims to the surface without the hunter being close by, then the rabbit escapes.

Can the rabbit outwit the hunter and escape?




Answer

The rabbit can escape.

If rabbit is one edge of the pond, and hunter is on the other side, then rabbit can easily come out of the pond and esacape.

Let's assume that, at the beginning, rabbit is at the center, and hunter is on the edge of the circular pond.

Let the radius of the pond be r.

Initially, rabbit moves a distance of r/4 from the center of the pond. If the rabbit rotates circularly, then the rotation speed would be same as the rotation speed of the hunter. Since, perimeter for rabbit path is 2*pi*r/4=pi*r/2. For Hunter, the perimeter is 2*pi*r. Since, hunter can travel 4 times faster than rabbit, both rotate at the same speed.

If rabbit is at a distance of (r/4-delta) (where delta is a very small number), then rabbit can rotate faster than hunter. So, eventually, at some point, rabbit would be at a distance of (r+r/4-delta) from the hunter. At that point, if rabbit moves to the nearest point to the edge of the pond, it has to travel 3*r/4 (ignoring delta, since it is a very small number). To reach that point, hunter has to travel pi*r. But, by the time rabbit travels 3*r/4, hunter can travel only 3*r, whereas the hunter should travel 3.14 * r to catch rabbit. So, rabbit can escape.

Question was originally posted in enagar.com

Area visible outside in a hyper cube

In K-dimensional space, if a hyper cube of size N^k is formed with N^k unit hypercubes, how many hyper cubes are visible from outside?

There is a three dimensional cube of size NxNxN formed with NxNxN cubes. How many cubes are visible from outside?

For example,
In one dimensional space (i.e., in a line), there are two visible points.

In two dimensional space, for 3x3 square, there are 8 squares visible from outside.

In three dimensional space, for 3x3x3 cube, there are 26 cubes visible from outside.

If it is in k-dimensional space, how many hyper cubes are visible?




Answer

The hypercube is in K-Dimensional space. There are two visible sides in each dimension. The length of one side is N. If we remove the two visible cubes that are visible from outside, the remaining length is N-2. If we do the same in all the dimensions, then in all the dimensions, the length would be reduced to N-2. The volume of the remaining is (N-2)^k, and this is not visible. The original volume is N^k. So, the no.of hyper cubes that are visible is N^k - (N-2)^k.