Friday, September 10, 2010

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.

Sunday, August 29, 2010

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 any floor, and let's say floor x is the previous floor from where it has not been broken, 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).

Explanation:

If there is only one egg, then one has to go linearly one by one from the first floor.

If there are two eggs, then to utilize both the eggs efficiently, first egg should find set of floors, which contains our floor, and second egg should find our floor exactly. If we take square root of the no.of floors, then this will give the optimum value. If there are 100 floors, then the first egg is going to find 10 floors which contains our final floor, by dropping from 10, 20, .. and so on. Once first egg is broken, second egg is used to find in the remaining.

If there are m eggs, then dropping egg n^(1/m) times in each iteration would give the best result. In the first iteration, if we have to drop the egg n^(1/m) times, we have to split the floors by n^((m-1)/m). So, the floors that we try would be, 1*n^((m-1)/m), 2*n^((m-1)/m), ... and so on.

Once the egg is broken in a floor, we have to take that floor and the previous floor where we tried, as the floors that we have, and one less egg than the previous.

now, we have m-1 eggs, and the total no.of floors is n^(m-1)/m (since in the previous iteration, the floors that we used are n^((m-1)/m) floors apart.)

If we apply the same formula as before, the floors would be (n^((m-1)/m))^((m-2)/(m-1)) apart.

n^((m-1)/m) is the no.of floors.
Previously, we used (m-1)/m as the power, when there are m eggs. Now, there are m-1 eggs. So, the power is (m-2)/(m-1).

If we simplify that, it would become n^((m-2)/m). We will use the egg n^(1/m) times in this iteration also. So, the floors would be x + 1*n^((m-2)/m), x + 2*n^((m-2)/m), ... x + n^(1/m)*n^((m-2)/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.

Sunday, August 22, 2010

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]]