• #1.Write an efficient C program to count the number of bits set in an unsigned integer.

i/p         o/p
====      ===
0(00)         0
1(01)         1
2(10)         1
3(11)         2
…..           …

• #2.Given a string s1 and a string s2, write  a snippet to say whether s2 is a rotation of s1 using only one call to strstr routine?
(eg given s1 = ABCD and s2 = CDAB, return  true,
given s1 = ABCD, and s2 = ACBD , return false)

• #3.What's the <condition> so that the following code snippet  prints both HelloWorld
 ```1 2 3 4 ``` `if()           ` `          printf ("Hello");` `else` `          printf("World");`

• #4.Change/add only one character so that the following program prints * exactly 20 times. (There are atleast 3 solutions to this problem.)

 ```1 2 3 4 5 6 7 ``` `int main()` `    {` `         int i, n = 20;` `         for (i = 0; i < n; i--)` `         printf("*");` `         return 0;` `    }`
• #5.Describe an algorithm for reversing the words in a string; for example ”My

name is Amit Agarwal” becomes ”Agarwal Amit is name My”.

• #6.There is a 100-story building and you are given two eggs. The eggs have an interesting property that if you throw the egg from a floor number < x, it will not break,and it will always break if the floor number is ≥ x. Assuming that you can reuse the eggs which didn’t break, give an algorithm to find x in minimal number of throws.

• #7.In C, copying of array as follows is not possible:

 ```1 2 3 ``` `int a,b;` `    a = b;` `    a = GetAnArrayOfTenElements();`

Can you think of a simple hack, which would enable you to get this effect?

• #8.The distance between cities A and B is 1000 km. We have 3000 bananas in city A, and an elephant that can carry at most 1000 bananas at once. The elephant must eat a banana every 1km; it cannot go furhter if it runs out of the banana supply. What is the maximum number of bananas that can be transferred to the city B?

• #9.Given an 8×8 chessboard, calculate:

• The number of subsquares in the board.
• The number of subrectangles in the board.
Note that rectangles are restricted to having different width and height.

• #10.A man has two cubes on his desk. Every day he arranges both cubes so that the front faces show the current day of the month. What numbers are on the faces of the cubes to allow this?

• #11.Given 6 match-sticks of equal length, you are asked to form 4 equilateral triangles. You are not allowed to break, split or bend the sticks.

• #12.Given 13 balls, how would you arrange them in 9 lines, such that there are 4 balls in each line? You can assume that the lines are arranged in 2-D space and that a ball cannot be placed on top of another ball.
Bonus: if you find that too easy, and have loads of time to kill, then how about arranging 22 balls in 21 lines of 4?

• #13.A skier must decide every day she goes skiing whether to rent or buy skis, unless or until she decides to buy them. The skier does not know how many days she will go on skiing before she gets tired of this hobby. Suggest a strategy for the skier minimizing her cost, given the cost of rent is 1 unit, and the cost to buy the skis is B units where B>>1.

• #14.If two of the below statements are false, what chance is there that the egg came first?

1. The chicken came first.
2. The egg came first.
3. Statement I is false and Statement II is true.

• #15.You are travelling in the jungles of Africa, when you are caught by a tribe of barbarians. They allow you to choose between death or solving their great challenge:
You are blindfolded and taken to a room, where you are asked to kneel. You feel hundreds of circular discs lying in front of you. You are told that one side of each disc is painted red, and the other, green. There are exactly 129 discs that currently are red side up. You have to divide the discs into two groups, such that each group has the same number of discs showing the red colour. Obviously, no peeking allowed.

• #16.The expected output of the following C program is to print the elements in the array. But when actually run, it doesn't do so.

 ``` 1 2 3 4 5 6 7 8 9 10 ``` `#include` `#define TOTAL_ELEMENTS (sizeof(array) / sizeof(array))` `int array[] = {23,34,12,17,204,99,16};` `int main()` `{` `     int d;` `     for(d=-1;d <= (TOTAL_ELEMENTS-2);d++)` `     printf("%d\n",array[d+1]);` `     return 0;` `}`

Find out what's going wrong.

• #17.I thought the following program was a perfect C program. But on compiling, I found a silly mistake. Can you find it out (without compiling the program ?

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 ``` `#include` `void OS_Solaris_print()` `{` `        printf("Solaris - Sun Microsystems\n");` `}` `void OS_Windows_print()` `{` `        printf("Windows - Microsoft\n");` `}` `void OS_HP-UX_print()` `{` `        printf("HP-UX - Hewlett Packard\n");` `}` `int main()` `{` `     int num;` `     printf("Enter the number (1-3):\n");` `     scanf("%d",&num);` `     switch(num)` `     {` `           case 1:` `                        OS_Solaris_print();` `                        break;` `           case 2:` `                        OS_Windows_print();` `                        break;` `           case 3:` `                        OS_HP-UX_print();` `                        break;` `          default:` `                        printf("Hmm! only 1-3 :-)\n");` `                        break;` `     }` `return 0;` `}`

————————-————————-————————-————————-—————
UPDATE-PART 2
————————-————————-————————-————————-—————

• #18.There are 4 buckets of 9 coins each. Real coins weigh one gram each, and fake coins weigh 2 grams each. Each bucket is either fake (contains only fake coins) or real (contains only real coins). Given a weighing machine, how can you determine all the buckets that are fake with just one weighing?

• #19.How do you efficiently find the largest repeating string and the number of times it repeats in a given string? For example, given string "abc fghi bc kl abcd lkm abcdefg", the function should return string "abcd" and the count of 2.

• #20.Write a program that will display a ”spiral” of n × n numbers, using constant space (no arrays allowed). For example, here’s what the spiral looks like for n = 10:

99   98   97   96   95   94   93   92   91   90
64   63   62   61   60   59   58   57   56   89
65   36   35   34   33   32   31   30   55   88
66   37   16   15   14   13   12   29   54   87
67   38   17   4     3     2    11   28   53   86
68   39   18   5     0     1    10   27   52   85
69   40   19   6     7     8     9    26   51   84
70   41   20   21   22   23   24   25   50   83
71   42   43   44   45   46   47   48   49   82
72   73   74   75   76   77   78   79   80   81

• #21.The following program, when run,

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ``` `#include` `void main()` `{` `    int a,b,c;` `    for (b=c=10;a="- FIGURE?, UMKC,XYZHello Folks,\` `    TFy!QJu ROo TNn(ROo)SLq SLq ULo+\` `    UHs UJq TNn*RPn/QPbEWS_JSWQAIJO^\` `    NBELPeHBFHT}TnALVlBLOFAkHFOuFETp\` `    HCStHAUFAgcEAelclcn^r^r\\tZvYxXy\` `    T|S~Pn SPm SOn TNn ULo0ULo#ULo-W\` `    Hq!WFs XDt!" [b+++21]; )` `    {` `        for(; a-- > 64 ; )` `        {` `            putchar ( ++c=='Z' ? c = c/ 9:33^b&1);` `        }` `    }` `}`

Gives as output, What is the logic used here?

• #22.Write a recursive function which generates the power set of a given set. The set is passed to the function as a string, and the function should print the subsets as strings.
Example: given "abc", the function should print  (the empty string, encode it somehow), a, b, ab, c, ac, bc, abc.

• #23.What's the expected output for the following program and why?

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 ``` `enum {false,true};` `int main()` `{` `      int i=1;` `      do` `        {` `                printf("%d\n",i);` `                i++;` `                if(i < 15)` `                   continue;` `        }while(false);` `      return 0;` `}`

• #24.The following program doesn't "seem" to print "hello-out". (Try executing it)

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 ``` `#include ` `#include ` `int main()` `  {` `     while(1)` `     {` `          fprintf(stdout,"hello-out");` `          fprintf(stderr,"hello-err");` `          sleep(1);` `     }` `     return 0;` `  }`

What could be the reason?

• #25.The following C program segfaults of IA-64, but works fine on IA-32.

 ```1 2 3 4 5 6 7 ``` `int main()` `  {` `     int* p;` `     p = (int*)malloc(sizeof(int));` `     *p = 10;` `     return 0;` `  }`

Why does it happen so?

• #26.Here is a small piece of program(again just 14 lines of program) which counts the number of bits set in a number.
Input          Output
0             0(0000000)
5             2(0000101)
7             3(0000111)

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ``` `int CountBits (unsigned int x )` `  {` `     static unsigned int mask[] = { 0x55555555,` `             0x33333333,` `             0x0F0F0F0F,` `             0x00FF00FF,` `             0x0000FFFF` `          } ;` `     int i ;` `     int shift ; /* Number of positions to shift to right*/` `     for ( i =0, shift =1; i < 5; i ++, shift *= 2)` `          x = (x & mask[i ])+ ( ( x >> shift) & mask[i]);` `     return x;` `  }`

Find out the logic used in the above program.

————————-————————-————————-————————-———-
Update-Part 3
————————-————————-————————-————————-———-
#27 Write a program to count the number of 1's which occur in the page number of a book of n pages.
Bonus: Generalize this for numbers other than 1.

What are some interesting puzzles asked in computer science programming technical interviews?