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.

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.

Find whether a number is divisible by 3 or not

Given an array of bits, find out whether the number represented by the binary number is divisible by 3 or not.

If the difference of the no.of 1's in even position and odd position is divisible by 3, then the no.is divisible by 3.

For example, for 18, the binary number is 10010. We can count either from left or right. That will not make any difference. If we count from left, there is one 1 in odd position, and one 1 in even position. The difference is Zero, which is divisible by 3. So, the number 10010 is divisible by 3.

If we take the number 37, the binary number is 100101. The number of 1's in odd position is 1, and the no.of 1's in even position is 2. The difference is 1, and it is not divisible by 3. So, 37 is not divisible by 3.

// Returns non-zero number, if it is divisible. Zero, otherwise. 
int divisible(int array[], int n)
{
   int i, even=0, odd=0;
   for(int i=0; i < n; i++) {
      if(array[i]==1) {
          if(i%2==0)
               even++;
          else 
               odd++;
      }
   }
   return ((even-odd)%3==0);
}

Find the count of the characters in a string

void findChars(char s[])
{
   int count[128];
   int l=strlen(s);
   for(int i=0; i<128; i++)
      count[i]=0;
   for(int i=0; i<l; i++)
      count[s[i]]++;
   for(int i=0; i<128; i++) {
      if(count[i]!=0) 
         printf("%c - %d\n", i, count[i]);
   }
}

River crossing by 3 cannibals and 3 humans

There are three cannibals and three humans need to cross the river, and there is only one boat. There can be only two people at a time while crossing the river. If the number of cannibals become more than number of humans in the bank of the river then they will eat the human. How should they cross the river?

Side 1	Side 2
CCCHHH
CCHH	CH
CCHHH	C
HHH	CCC
HHHC	CC
HC	HHCC
HHCC	HC
CC	HHHC
CCC	HHH
C	HHHCC
CC	HHHC
	HHHCC

Findout the switches for the bulbs

There are three bulbs inside a house of one floor and switches are there in different floor. How will you conclude which switches is for which bulb?

Solution
Switch on one bulb; keep the switch off for another bulb. This way you can detect two bulb’s switch. To find the third one is the trick. Keep the third switch on for some times and then switch it off so that the temperature gets increased for the third bulb and you can detect the switch.

Crossing the bridge by four people

Four people need to cross the bridge in the night time with a single flashlight. The bridge can accommodate two people at a time.
The speed of all the people is different.
A can cross in 1 min
B can cross in 2 min
C can cross in 5 min
D can cross in 10 min
What is the minimum time to cross the bridge?



Solution
A & B cross (2min)
B comes back (2min)
C & D cross (10min)
A comes back (1min)
A & B cross (2min)
Total time=2+2+10+1+2=17min

Let me know if you have better solution.

Increase the probability of picking red and blue balls

You have two bags, 50 red balls and 50 blue balls. How will you arrange the balls in two bags such that probability of picking up red ball is maximum?

There are different ways to keep the balls. If you mix the balls equally then probability would be same for both the balls from both the bags. If you keep different balls in different bag then also probability becomes 50-50 as one bag has 100% chances whereas another has 0% chance.

So in order to increase the probability of picking up red ball, put only one red ball in one bag and rest of the red and blue ball in another bag. So here the probability of picking up a red ball becomes 100% for one bag and approximately 49% for second bag. So the 100%-49% probability is better than other solution of 50%-50% and 100%-0%.
Let me know if you have more optimize solution.

Sudoku Solver

#include <stdio.h>

int row[9],col[9],box[3][3];
int g[9][9];
bool test(int & x,int j) { return (x & (1<<j)) >0 ;}
void set(int & x,int j) { x |= (1<<j) ;}
void unset(int & x,int j) { x &= (~(1<<j)); }
bool doit(int x,int y)
{
 if(x==9) return true;
 if(g[x][y]) return doit(x+(y==8),(y+1)%9);
 for(int i=0; i<9; i++) {
  if(!test(row[x],i) && !test(col[y],i) && !test(box[x/3][y/3],i)){
   set(row[x],i);
   set(col[y],i);
   set(box[x/3][y/3],i);
   if(doit(x+(y==8),(y+1)%9)) {
    g[x][y] = i+1;
    return true;
   }
   unset(row[x],i); unset(col[y],i); unset(box[x/3][y/3],i);
  }
 }
 return false;
}
main()
{
 for(int i=0; i<9; i++) {
  for(int j=0; j<9; j++){
   int k;
   scanf("%d",&k);
   if(k--){
    g[i][j] = k+1;
    row[i] |= (1<<k);
    col[j] |= (1<<k);
    box[i/3][j/3] |= (1<<k);
   }
  }
 }
 if(doit(0,0)){
  for(int i=0; i<9; i++) {
   for(int j=0; j<9; j++) 
    printf("%d%s", g[i][j], (j==8?"\n":(j%3==2?" | ":" ")));
   if(i != 8 && i%3==2){
    printf("---------------------\n");;
   }
  }
 }
 else{
  printf("No Solution!\n");
 }
}

Thanks to Lakshmi Subrahmanyam for providing the solution.

Reversing an array

Let A[1...n] be an array of n distinct numbers. Write a simple linear time algorithm to reverse the order in which the numbers appear on A[1...n]. Use as little additional space as possible. (For example, do not copy the array.)

void reverse(int a[], int n)
{
   int i, t;
   for(i=0; i < n/2; i++) {
       t = a[0];
       a[0] = a[n-i-1];
       a[n-i-1] = t;
   }
}