The Algo Blog: November 2008

The Fork in the Road

A logician vacationing in the South Seas finds himself on an island inhabited by two proverbial tribes of liars and truth-tellers. Members of one tribe always tell the truth, members of the other always lie. He comes to a fork in a road and has to ask a native bystander which branch he should take to reach a village. He has no way of telling whether the native is a truth-teller or a liar. The logician thinks a moment, then asks one question only. From the reply he knows which road to take. What question does he ask?
(source: My Best Mathematical and Logic Puzzles By Martin Gardner)

Solution:

If we require that the question be answerable by "yes" or "no" there are several solutions, all exploiting the same basic gimmick. For ex, the logician points to one of the roads and says to the native,
1. "If I were to ask you if this road leads to the village, would you say 'yes'?" The native is forced to give the right answer, even if he is a liar! If the road does lead to the village, the liar would say "no" to the direct question, but as the question is put, he lies and says he would respond "yes." Thus the logician can be certain that the road does lead to the village, whether the respondent is a truth-teller or a liar. On the other hand, if the road actually does not go to the village, the liar is forced in the same way to reply "no" to the inquirer's question.

2. "Of the two statements, 'You are a liar' and 'This road leads to the village,' is one and only one of them true?" Here again, a "yes" answer indicates it is the road, a "no" answer that it isn't regardless of whether the native lies or tells the truth.

Twist: Suppose logician knows that 'pish' and 'tush' are the native words for 'yes' and 'no' but has forgotten which is which, though otherwise he can speak the native language, He can still determine which road leads to the village:
He points to one of the roads and asks, 'If I asked you whether the road I am pointing to is the road to the village would you say pish?'

The Fork in the Road

The Returning Explorer

An old riddle runs as follows. An explorer walks one mile due south, turns and walks one mile due east, turns again and walks one mile due north. He find himself back where he started. He shoots a bear. What color is the bear? The time-honoured answer is: "White," because the explorer must have started at the North Pole. But not long ago someone made the discovery that the North pole is not the only starting point that satisfies the given conditions! Can you think of any other spot on the globe from which one could walk a mil south, a mile east, a mile north and find himself back at his original location?(source: My Best Mathematical and Logic Puzzles By Martin Gardner)

Solution:

Us there any other point on the globe, besides the North Pole, from which you could walk a mile south, a mile east, and a mile north and find yourself back at the starting point? Yes indeed; not just one point but an infinite number of them! You could start from any point on a circle drawn around the south pole at a distance slightly more than 1 + 1/2Pi miles ( 1.16 miles ) from the Pole, the distance is "slightly more" to take into account the curvature of the earth. After walking a mile south, your next walk of one mile east will take you on a complete circle around the Pole, and the walk one mile north from there will then return you to the starting point. Thus your starting point could be any one of the infinite points on the circle with a radius of about 1.16 miles from south pole. You could also start at points close to the Pole, so that the walk east woule carry you just twice around the Pole, or three time, and so on.

How many smokes?

Mr. Puffem, a heavy smoker for many years, finally decided to stop smoking altogether. "I'll finish the twenty-seven cigaretees I have left," she said to herself, "and never smoke another one."
It was Mrs. Puffem's practice to smoke exactly two-thirds of each cigarette. It did not take her long to discover that with the adi of some cellophane tape she could stick three butts together to make a new cigarette. With 27 cigarettes on hand, how many cigarettes can she smoke before she gives up the weed forever?

Solution:


After smoking 27 cigarettes, she patched together the butts to make 9 more, and after smoking these, she had enough butts for 3 more smokes; then with the final 3 butts she made one final cigarette, total : 40 cigarettes

The Colored Socks

Ten Red socks and ten blue socks are all mixed up in a dresser drawer. The twenty socks are exactly alike except for their color. The room in in pitch darkness and you want two matching socks. What is the smallest number of socks you must take out of the drawer in order to be certain that you have a pair that match? (source: Entertaining Mathematical Puzzles By Martin Gardner, Anthony Ravielli)

Answer:

Many people (including me) initially (and incorrectly )solved this puzzle as follows:
* Initially I pull out a sock, and this could be Red / Blue.
* Then to match the color of the first sock, we pull out (10 + 1) socks.

But if we read the question carefully, it simply says, "pair that match" and nothing about the
color, so all we need is to pull out just three socks.

Transportation of Bananas

There are 2 cities A and B, dist. between them is 1000 Km
we have 3000 bananas in city A and a elephant can carry max 1000 bananas at
any given time and it needs to eat a banana every 1 Km.

How Many Max. No. of bananas one can transfer to city B?

Note : the elephant cannot go without bananas to eat.



One possible solution is to transport the banana in stages or intervals


for 200 kms we have,
A   200  B  200   C  200   D  200   E   200  F
|--------|--------|--------|--------|--------|

A to B
------
-> 2000, 800
<- 2000, 600
-> 1000, 1400
<- 1000, 1200
-> 0   , 2000

distance left = 800

B to C
--------
-> 1000, 800
<- 1000, 600
-> 0,    1400

distance left = 600

C to D
-------
-> 400, 800
<- 400, 600
-> 0,   800

distance left = 400

Move from D to F , leaving 400 bananas.


for, 250 kms we have,
A  250   B   250  C  250   D  250   E
|--------|--------|--------|--------|

A to B
------
-> 2000, 750
<- 2000, 500
-> 1000, 1250
<- 1000, 1000
-> 0   , 1750

distance left = 750

B to C
------
-> 750 , 750
<- 750 , 500
-> 0   , 1000

distance left = 500

Go directly from C to E (500 kms) leaving 500 bananas

for, 300, we have
A   300  B  300   C  300   D  100   E
|--------|--------|--------|--------|

A to B
-------
-> 2000, 700
<- 2000, 400
-> 1000, 1100
<- 1000, 800
-> 0,    1500

distance left = 700

B to C
------
-> 500, 700
<- 500, 400
-> 0  , 600

distance left = 400

travel C to E, leaving only 200 bananas

Using the above scheme, we can transport a max of 500 bananas for intervals of 250, 
this is probably not the best solution, and using dynamic programming we can find the
best solution.

Solders and dog

There is a column of soldiers fifty feet long. At the end of the line
there is a dog. The dog begins to run forward at exactly the same time
that the column begins to march forward. The dog runs to the head of the
column and then, without loosing any time he turns back and and runs
towards the rear of the column. He gets to the end of the line of
soldiers just as the column advances 50 feet. What is the distance
covered by the dog? (Assume that both the dog and the soldiers travel at
constant speeds.)

Answer:


when the dog ran on one way, the solders had marced 25 feet, and dog travelled 75 feet,
and by the time it could com back, the solders had marched another 25 feet, and dog travelled 25 feet.
so in total 100 feet

sum of digits puzzle

Let the letters: A, B, C, D, E, F, G, H, and I be representative of the
numbers 1, 2, 3, 4, 5, 6, 7, 8, 9 in no particular order. If we let
A+B+C=C+D+E=E+F+G=G+H+I=13, then what must E be?

Answer:


start from the maximum value = 9
and it can only be combined with 1, 3
so we have,
(1, 3, 9)

take the second maximum value = 8
possible tuples,
(1, 4, 8)
(2, 3, 8)

take the third max value = 7
(1, 5, 7)
(2, 4, 7)

take the third max value = 6
( 2, 5, 6 )
( 3, 4, 6 )

now, only C, E, F are common,
so,

Option I:

9 + 3 + 1
        +
        8
        +
        4 + 7 + 2
                +
                5
                +
                6

This is a perfectly valid arrangement

Option II:

9 + 1 +[3]
        +
        8
        +
        2 + 7 + 4
                +
                6
                +
               [3]

which is an invalid arrangement

So the required answer is 4.

Robots and Beacon

Two robots are each standing on a beacon, on a line of infinite length.
They both execute the same code. Write the code to have them collide.
Only use these commands:
SKIPNB - skip the next line of code if not on a beacon
MVR - move right one step
MVL - movel eft one step
JMP - goto label in the code
hint: have both robots move to the right in a loop. if a robot passes a
beacon, double its speed.



Three cases:

|--B--------R--------R-----|

|--R--------R--------B-----|

|--R--------B--------R-----|

Make the robots osciallate ( left to right ) so that the step 
increases in each pass.

Hens, eggs, days

If a hen and a half lay an egg and a half in a day and a half then how many hens will it take to lay six eggs in six days?


no of hens directly propotional to eggs and inversely propotional to days

 x     1.5       6
--- = -----  x  ----
1.5     6        1.5
       ^^^       ^^^
       days      eggs

x = 1.5

Deck of 52 cards, two players

The rules of a card game (having 52 cards) played between two peole are:- they will turn over two cards at a time. If both the cards are Black they will go the first player's pile and if both are Red they they will go to the second player's pile. If one is Red and one Black then both the cards will simply be discarded.

The process of turning over two cards at a time is repeated till all the 52 cards are exhausted. Whoever is having more number of cards in their pile wins the game. In case of tie the first player is declared winner. What's the chance of second player winning the game?

Answer:

case I : 26B, 26R => tie, first player wins
case II : 26 Red, 26 Black => tie, first player wins
case III: The order of Red and Black cards are jumbled.
so we cards will cancel out each other and go into no man's pile and
the remaining cards will get equally distributed between the players,
resulting in a tie, and again the first player wins.

So the probability of the second player winning is zero

Chameleons and Changing Colors

There are 13 Red, 15 Green, and 17 Blue Chameleons at some point of time. Whenever two Chameleons of the different colors meet both of them change their color to the third color. Is it ever possible for all Chameleons to become of the same color? Why?


The difference in the numbers make it impossible.

Trailing zeros in 100!

What is the trailing number of zeros in 100!


Just compute zeros in , n * 8 * 10
we choose 8 because that is the max even num, 
that produces the max num of zeros.
----------------------
                Zeros
----------------------
(5  * 8  * 10)  = 2
(15 * 18 * 20)  = 2
(25 * 28 * 30 ) = 3
(35 * 38 * 40)  = 2
(45 * 48 * 50 ) = 3
(55 * 58 * 60 ) = 2
(65 * 68 * 70)  = 2
(75 * 78 * 80 ) = 3
(85 * 88 * 90)  = 2
(95 * 98 * 100) = 3

crystal balls and the floor from which they break

There are two identical crystal balls and one needs to find out which is the maximum floor in a 100 storey building from where the balls can fall before they break. In the most efficient way, what will be the maximum number of drops required to find the right floor in any possible scenario? The balls are allowed to be broken (if required) while finding the right floor.

Solution 1 (Constant interval, not optimal):


import sys

min_drops = 100
min_interval = 1
for interval in range(1,50):
    drops = 100/interval + max(100%interval, interval-1)
    print "interval " , interval , " drops " , drops
    if drops < min_drops:
        min_drops = drops
        min_interval = interval

print "min_interval ", min_interval, " min_drops ", min_drops

Solution 2 (increasing interval, not optimal):
seq = (1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 100)
count(seq) = 14.
worst case = 14 + 8 = 22

Solution 3 (decreasing interval, optimal, best solution):
14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 100

The advantage with decreasing interval is that, when the crystal ball breaks
the number of trails required to determine the floor at which it breaks gets
smaller everytime.,

One method to decrease the interval is to find a number n, such that
∑n >= no_of_floors,
and then start from interval n, n+n-1, n+n-2 , .... 100
so when the ball breaks at 100, the number of trails required is the difference
b/w previous floor and current floor.

we have ∑n = n(n+1)/2 >= 100
solving the above equation gives, n = 14
so we will test from:
#14, #(14 + 14 - 1 = 27), #(27 + 14 - 2 = 39), #(39 + 14 - 3 = 50), #(50 + 14 - 4 = 60), #(60 + 14 - 5 = 69), #(69 + 14 - 6 = 77), #(77 + 14 - 7 = 84), #(84 + 14 - 8 = 90), #(90 + 14 - 9 = 95), #(95 + 14 - 10 = 99), and finally from #100.

probability of taking the correct seat

100 passengers are waiting to board a flight having 100 seats. Each of them is having a ticket with a particular seat number which is same as their number in the queue. Unfortunately the first person in the queue is little crazy and he can occupy any random seat. Now, all other passengers will see if their seat is occupied by that crazy guy or not? If not, then they will be seated on their own seat numbers otherwise they will also look for a free random seat to sit on. This continues. What's the probability that the 100th person gets his own seat to sit on?

Answer:

1. Probability of the first person taking his seat = 1/2 (no its not 1/100, since there are only two chances , either he may sit in the correct place or he may not)
2. Probability of the second person taking this correct seat = 1/2
....
so even for the 100th person, it will be 1/2

Average salary without disclosing salary

Three coworkers would like to know their average salary. how can they do it, without disclosing their own salaries?

Solution:

Let's say the three co-workers are A, B, and C and their individual salaries are Sa, Sb, and Sc respectively. For knowing the average of their salaries without disclosing their own salaries to each other, they follow these steps:-

* A adds a random amount, say Ra to his own salary and gives that to B (B won't be able to know A's salary as he has added a random amount known to him only). In this case, B will receive the figure (Sa + Ra) from A.
* B does the same and gives the final amount to C (without showing that to A). Now C will get the figure (Sa + Ra + Sb + Rb).
* C does the same and gives the final figure to A (without showing it to B). Now, A will receive the figure (Sa + Ra + Sb + Rb + Sc + Rc).
* Now A subtracts his random amount and gives the final figure to B (without showing that to C). B will now receive the figure (Sa + Sb + Rb + Sc + Rc).
* B subtracts his random amount and gives the final figure to C (without showing it to A). C will receive the figure (Sa + Sb + Sc + Rc).
* C subtracts his random amount and then the figure becomes (Sa + Sb + Sc). It's shown to everyone and by they get to know the average simply by dividing this figure by 3.

Very good puzzle

shaking hands with a pair of gloves

Bill Gates is about to give 3 distinct awards, 1 each, to 3 different
distinguished developers. He needs to hand 1 award to each developer and
then shake the developer's hand. However, all 4 people involved in this
ceremony have a separate disease. If Bill shakes Developer 1's hand
(without protection), Bill will contract Developer 1's disease and
Developer 1 will contract Bill's disease (and so on for all of the
others). The only protection Bill has available at this ceremony is a
pair of normal, plain gloves. The ceremony cannot be delayed and Bill
must think of a quick solution before he embarrasses himself. Given this
information, how can Bill proceed?

Answer:

1. Wear one glove on another, and shake hand with first developer.
2. Remove the first glove and shake hand with the second developer.
3. Now, reverse the first glove and wear it on the second glove, and shake hand.

Hats puzzle

There are 3 black hats and 2 white hats in a box. Three men (we will
call them A, B & C) each reach into the box and place one of the hats
on his own head. They cannot see what color hat they have chosen. The
men are situated in a way that A can see the hats on B & C's heads, B
can only see the hat on C's head and C cannot see any hats. When A is
asked if he knows the color of the hat he is wearing, he says no. When B
is asked if he knows the color of the hat he is wearing he says no. When
C is asked if he knows the color of the hat he is wearing he says yes
and he is correct. What color hat and how can this be? There is no play
on words and there are no tricks.

Answer:



A will know only if, B and C are wearing White hats.
i.e B W W
and since A does not know, B and C are wearing either of,
B B
W B
B W

Now B would know what he is wearing if it C was wearing W. (last option)
Since B does not know, C knows for sure that he is wearing W

Bridge crossing problem

There are four men who would all like to cross a rickety old bridge.
(Perhaps it is more accurate to say that they'd like to get to the
other side.) The old bridge will only support 2 men at a time, and it is
night time, so every crossing must use the one flashlight that they all
share. The four men each have different walking speeds; the fastest each
of them can cross is 1 minute, 2 minutes, 5, minutes, and 10 minutes. If
they pair up, since they must share the flashlight, they can only cross
in the time that it would take the slower of the two. Given that the
shortest time to get them all across is 17 minutes total, how should
they all cross?



1, 2 go together, drops 2 and comes back, taking 3 minutes
(1,2)-------> 2
     <------  

5,10 go together, taking 10 minutes
(5,10)------> 2, 5, 10

Now, 2 comes back with the light
and takes 1 to the other side, taking 4 minutes

Note, its efficient to club 5,10.

Winners in a game

There is a new game in which 3 person play each other and only one wins. If 81 person participated in the tournament give a quick reply that how many matches will be played to decide the winner.
Answer:


Its logarithmic, 
   27   27  27  
   |    |   |   
   9    9   9 = 27   
   |    |   | +  
   3    3   3 = 9  
   |    |   | +
   1    1   1 = 3
              +
                1
-------------------
i=3
∑ i         = 81
i=0
-------------------

   

    \   /    \  /
      9       9
       \     /

Triangles with matches

How can you form 4 triangles with only 6 matches? You cannot light,
bend, break, mutilate, etc... the matches. Nor can you overlap the matches.
(Clue : Think 3d!)
Answer:

Make a pyramid like structure.

Time measurement with hour glasses

You have two hourglasses--a 4-minute glass and a 7-minute glass. You
want to measure 9 minutes. How do you do it?
Answer:


4:0 - 7:0
0:4 - 3:4
3:1 - 6:1 << start measurement now, 3 + 6

Hour hand and minute hand

Part I: what is the angle between the minute hand and the hour hand at 3:15 on an analog clock? no, its not 0

Part II: how often does the minute hand pass the hour hand on an analog clock?

Answer:


Part I:
Every 60 mins, hour hand covers, 30 degrees
so for 15 mins, hour hand 7.5 degrees. which is the difference.

Part II:
consider the example of 1 past x at which they meet.
Let they meet at x degrees,
The minute hand covers  6 degrees every minute.
The hour hand covers 1/2 degree every minute.
6x-30 = x/2
11x = 60
x = 5 (5/11),
so they meet every 60 + 5.55555 minutes

Odd ball out

You are given 10 baskets. 9 of the baskets each have 10 balls weighing
10kg per ball, however one basket has 10 balls weighing 9kg each. All
the balls and baskets are identical in appearance. You are asked to
determine which basket contains the 9kg balls. You have a suitable
scale, but may only take a single measurement. No other measurements may
be taken (like trying to determine by hand). You may remove balls from
the baskets but may still only take one measurement.
1. How do you do it?
2.Now if two balls are defective, how do you do it in only one weighing?

Answer:

1. use, ∑n principle , i.e (∑10 - actual wieight)^th basket has defective balls.
2. (Possible answer) Use ∑n² principle and (∑n² - actual weight)=diff should be divided into two variables a, b such that , a²+b² = diff, and a^th and b^th baskets are defective.

Fork in the road

You are ill and travelling down a road to the hospital. You reach a fork
in the road and find a pair of identical twin boys standing there. One
of the twins always tells the truth and the other twin always lies. You
are allowed to direct only one question to one of the twins, and as such
you will be assured of the correct road to the hospital. What is your
question and to whom?

Ask the question,

What will the other person say if this this road goes to the hospital?


Person |On Road|  Answer
------------------------
True   |  yes |  False
       |  no  |  True
False  |  yes |  False
       |  no  |  True


Explanation, treat the two persons as Functions:

T(a) = a
F(a) = !a
so we make use of the following property,
T(F(a)) = F(a) = !a
F(T(a)) = F(a) = !a

bit function

Let f(k) = y where k is the y-th number in the increasing sequence of non-negative integers with the same number of ones in its binary representation as y, e.g. f(0) = 1, f(1) = 1, f(2) = 2, f(3) = 1, f(4) = 3, f(5) = 2, f(6) = 3 and so on. Given k >= 0, compute f(k).

Analysis:

Ex:
// series with 2 bits
00000011 1
00000101 2
00000110 3
00001001 4
00001010 5
00001100 6
00010001 7

// series with 3 bits
00000111 1
00001011 2
00001101 3
00001110 4
00010011 5



//------------- PROBABLY NOT SO OPTIMAL ---------------
#include "stdio.h"
#include "stdlib.h"

/**
 * O(n) algorithm, where n is the number of bits set
 * This algorithm works on the fact that when 1 is subtracted,
 * there exists a bit k, below which all the bit places get changed
 * so, num & num-1 will clear all the bits below the bit k.
 * ( to see this enable PrintBinary() function below )
 * */
size_t CountBits(size_t num)
{
    size_t count = 0;
    while (num)
    {
        //PrintBinary(num);
        num &= num-1;
        ++count;
    }
    return count;
}
/**
 * This is O(1) algorithm, but uses a lookup table.
 * Initially fill the lookup table with the bit count
 * then look into it :)
 * we can bring down the memory even further by using a lookup
 * table of size 16 (4 bits instead of 8 )
 * */
size_t lookup[256] = {};
void InitLookup()
{
    for( int i = 0; i <= 0xFF; ++i)
        lookup[i] = CountBits(i);
}

size_t CountBits_O1(size_t num)
{
    size_t count = lookup[num&0xFF] +
        lookup[ (num >> 8) & 0xFF ] +
        lookup[ (num >> 16) & 0xFF ] +
        lookup[ (num >> 24) & 0xFF ];

    return count;
}

void FindInSeries(size_t k)
{
    const size_t bit_count = CountBits_O1(k);
    size_t seq_pos = 0;
    // This is the start of the series
    size_t start = ( 1 << bit_count ) - 1;

    printf(" start %d, bit_count %d \n", start, bit_count );

    for ( size_t i=start; i != k; ++i)
    {
        if ( CountBits_O1(i) == bit_count )
        {
            ++seq_pos;
            printf("%d ", i);
        }
    }

    ++seq_pos;

    printf("\n f(%d) = %d \n", k, seq_pos);
}

int main (int argc, char* argv[])
{
    size_t num = atoi( argv[1] );
    InitLookup();
    FindInSeries(num);
    return 0;
}

probability of seeing a car

If the probability of observing a car in 30 minutes on a highway is 0.95, what is the probability of observing a car in 10 minutes


P(A intersection B) = P(A)*P(B)
so probability of observing a car in 10 mins = ³√0.95

River Crossing

A man has to get a fox, a chicken, and a sack of corn across a river. He
has a rowboat, and it can only carry him and one other thing. If the fox
and the chicken are left together, the fox will eat the chicken. If the
chicken and the corn is left together, the chicken will eat the corn.
How does the man do it?



Boat(Man, Chicken) ---------->
                   <---------- Chicken

//Leave the fox and carry back the chicken

Boat(Man, Fox)     ----------->
     (man, chiken)<------------ Fox

// Leave the chicken, and take the corn
(Man, Corn)    --------------->
               <--------------- Fox, Corn

// Now Take the chicken to the other side.
(Man, Chicken) ------------>

travel, time problem

Every day, Joe arrives at the train station from work at 6pm. His wife leaves home in her car to meet him there at exactly 6pm, and drives him home. One day, Joe gets to the station an hour early, and starts walking home, until his wife meets him on the road. They get home 20 minutes earlier than usual. How long was he walking? Distances are unspecified. Speeds are unspecified, but constant.



 [House] --------------------------- [Station]
         -------------------->|  x
         <--------------------|
                        {They meet here}

Let x be the distance from station at which they meet.
now , 2x distance saved 20 mins, (because the car should go back and forth)
2x = 20 minutes, i.e x = 10 minutes => Husband was walking for 50 minutes.

Steps and elevator.

Two brothers were running up an escalator which is moving up as well.
The older brother ran three times as quickly as his younger brother. The
older brother counted 75 step as he ran up while his brother counted 50
step. How many steps in the visible part of the escalator?


3x = 75, and 2x = 50, => x = 25 steps are visible.

Merging of Companies

Suppose we have N companies, and we want to eventually merge them into
one big company. How many ways are there to merge?


Select any two companies and merge them, now we are left with n-1 ... and so on.
nC2 + n-1C2 + n-2C2 + ... + 2C2

Missing Money

It is a dark and stormy night when three travelers must stop in hotel.
They approach the front desk, where the front desk clerk informs them of
the rate of $30 for three men in one room. The men each hand over a $10
bill for a total of $30. They are given a key and go to their room.
Moments later, the manager is informed of the transaction and reprimands
the clerk, reminding him of the 3 men/1 room special of $25 a night. The
manager asks the clerk to refund the $5 to the men. Taking five $1 bills
from the register, he goes to the men's room and knocks on the door.
While he waits for the men to come to the door, he realizes a problem.
How can he divide the 5 $1 bills evenly among the men? When they answer
the door, he tells them that there was a special that night and that the
total bill only came to $27. He gave them each $1 as a refund, and the
sneaky clerk made off with $2 for himself. Though it seems everyone came
out a winner, a problem occurs. In the beginning, $30 was paid. In the
end, however, the man had paid a collective $27, and the clerk had $2.
$27 + $2 =$29, not $30. The question is: where is the extra dollar?

Possible answer:


The Question itself is probably wrong, another way to look at it is,
The rent of the room is 25$, each three men contributed 9$, and 2$ was tips.

Pythagorean triplets in an array

Given an array print all the pythagorean triplets.

Answer:

See also : http://en.wikipedia.org/wiki/Pythagorean_triples#Elementary_properties_of_primitive_Pythagorean_triples


#include <vector>
#include <iterator>
#include <algorithm>
#include <stdio.h>
#include <iostream>
using namespace std;


/**
 * See 
 * we can make use of the properties to check that a pythagorean triplet is possible
 * */
bool IsPyTripletPossible(size_t a, size_t b, size_t c)
{
    bool flag = false;
    /*
     * # Exactly one of a, b is odd; c is odd.
     * */
    flag =  (a % 2) + (b % 2) ;
    if (!flag) return flag;
    flag = ((c%2) == 1);
    if (!flag) return flag;
    /*
        # Exactly one of a, b is divisible by 3.
        # Exactly one of a, b is divisible by 4.
        # Exactly one of a, b, c is divisible by 5.
    */
    if ( !(
             ( !(a%3) && (b%3) ) ||
             ( (a%3) && !(b%3) )
            )
       )
        return false;
    if ( !(
             ( !(a%4) && (b%4) ) ||
             ( (a%4) && !(b%4) )
            )
       )
        return false;
    // other tests ignored.
    return true;
}

void PrintPythagorousTriplets(vector &a)
{
    size_t i = 0, j = 1, k = 2;
    size_t lower_bound = 0;
    sort( a.begin(), a.end() );
    while ( k < a.size() )
    {
        if ( (a[k]%2) == 0  )
        {
            // RULE:
            // the hypotenuse cannot be a even number
            ++k;
        }
        else
        {
            size_t k_sq = a[k] * a[k];
            i = lower_bound;
            j = k - 1;
            bool found = false;
            while ( i < j )
            {
                size_t sq = a[i]*a[i] + a[j]*a[j];
                if ( sq == k_sq )
                {
                    printf(" %d, %d, %d \n", a[i], a[j], a[k]);
                    found = true;
                    break;
                    // break, because there can be one and only one
                    // py triplet, (because there is only one way to draw
                    // a triangle)
                }
                else if ( sq < k_sq )
                    ++i;
                else if ( sq > k_sq )
                    --j;
            }
            if ( found )
            {
                // RULE :
                // There are no Pythagorean triplets in which the hypotenuse and 
                // one leg are the legs of another Pythagorean triple.
                // so the next search can start from the hypotenuse of the current 
                // triplet
                lower_bound = i;
            }
            ++k;
        }
    }
}

int main( int argc, char* argv[] )
{
    if ( argc == 1 ) return 0;
    else
    {
        vector a(argc-1);
        for ( int i = 1; i <= argc-1; ++i)
            a[i-1] = atoi(argv[i]);
        cout << "Input :" << endl;
        copy ( a.begin(), a.end(), ostream_iterator(cout, " "));
        cout << endl;
        PrintPythagorousTriplets(a);

    }
    return 0xabcdef;

}

Drawing a circle without floating point ops.

Write a routine to draw a circle given a center coordiante (x,y) and a radius (r) without making use of any floating point computations


              |
         x    |
         |\   |
         | \r |
        j|  \ |
         |   \|
    ----------\---------
           i  |
              |
              |
              |
              |


// make use of pythoragus theorm

DrawCircle( Point origin, size_t radius )
{
    for ( int x = (origin.x - radius) ; x <= (origin.x) ; x++ )
        for ( int y = (origin.y - radius) ; y <= (origin.y) ; y++ )
            if ( pow(i,2) + pow (j,2) == pow{r,2) )
            {
                // Set the pixels symmetrically.
                SetPixel(i,j);
                SetPixel(origin.x + i, j);
                SetPixel(i,origin.y + j);
                SetPixel(origin.x + i, origin.y + j);
            }
}

chicken egg problem

I. The chicken came first.
II. The egg came first.
III. Statement I is false and Statement II is true.

If two of the above statements are false, what chance is there that the egg
came first?


T F F -> 1
F T F -> 0
F F T -> 0

so Chicken came first

water measurement

If you had an infinite supply of water and a 5 quart and 3 quart pail,
how would you measure exactly 4 quarts?


[5] - [3]
---------
 5 - 0
 2 - 3
 2 - 0
 0 - 2
 5 - 2
 4 - 3

distance problem

A turnpike consists of n-1 stretches of road between n toll stations; Each stretch has an associated cost of travel. It is trivial to tell the cost of going between any 2 stations in O(n) time using only an array of the costs, or in constant time using a table of O(n^2) entries. Describe a data structure that requires O(n) space but allows the cost of any route to be computed in constant time.

Answer:


|------|-----|-----|-----|--------|
   a      b     c     d       e

An entry i in an array stores the sum of distance from the start of all stations <=i

i.e
distance[1] = a;
distance[2] = a+b;
distance[3] = a+b+c; 
and so on,

So distance between any two given stations i and j, distance[j] - distance[i]

Switches and bulbs

In your cellar there are three light switches in the OFF position. Each
switch controls 1 of 3 light bulbs on floor above. You may move any of
the switches but you may only go upstairs to inspect the bulbs one time.
How can you determine the switch for each bulb with one inspection?

Answer:

Weird Lateral thinking solution:
1. Turn on one bulb for some time.
2. Turn off the previous bulb, an turn on a different bulb
3. Go upstairs, and check which bulb is hot (first switch), the bulb which is on corresponds to second switch..

Function Object

What is a function object?
Answer:


A class with overloaded operator(), see STL

Copy Constructor Question

Why do you have to provide your own copy constructor and assignment operator for classes with fields dynamically allocated memory?

Answer:


To prevent ptr aliasing, and when one class is destroyed, the ptr belonging to another can be distroyed., or use auto_ptr.

Common characters

Write a function f(a, b) which takes two string arguments and returns a
string containing only the characters found in both strings in the order
of O(n)

Answer:


//Use a lookup table, this can be 
size_t lookup[26];
// or just a unsigned int, in which the first 26 bits 
// is used to mark the presence of a character.
size_t lookup;

Scan the first string and mark the characters in the lookup

Scan the second string, if the character is found in lookup,
then copy it to output string.

Time Measurement

There are two long wooden rods of arbitrary lengths. Each takes an hour
to burn and each burns at its constant rate. Without measuring the
length of the rods, how would you clock exact 45 min provided that you
are given as many matchsticks as you need to burn the wood

Answer:


Light the first log and when it completely burns (30 mins) , burn the second log with both the ends (15 mins)

C++ = operator

Suppose that objects A, B, and C are instances of class Foo. How should you design an assignment operator so that the "A=B=C;" statement would be allowed by a compiler but "(A=B)=C;" would not be allowed by a compiler?

Answer:



class Foo
{
    private:
        int a;
    public:
        const Foo& operator=(const Foo& other)
        {
            this->a = other.a;
            return *this;
        }
};

int main()
{
    Foo a,b,c;
    a = b = c;
    (a = b) = c;
}

Intersection of Linked Lists

Given two sorted linked lists, L1 and L2, write a C program to compute L1 /\ L2 (L1 intersection L2).

Train puzzle

Two boys walking in the woods decide to take a shortcut through a railroad tunel. When they had walked 2/3 of the way, their worst fears were realized. A train was coming in the opposite direction, nearing the tunnel entrance. They boys panicked and each ran for a different end of the tunnel. Both boys ran at the same speed, 10 miles per hour Each boy escaped from the tunnel just at the instant the train would have squashed him. Assuming the train's speed was constant, and both boys were capable of instantaneous reaction and acceleration, how fast was the train going?

Answer:


When the first boy just escapes at the end of tunnel, the second boy is 1/3rd away from entrance, and when the train reaches the entrance, the second boy just escapes, so when second boy travells x, the train travells 3x, i.e speed is 10 mph

Calendar Cubes

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?

Answer:

Note, that we must use both cubes.

Cube 1: 1 2 3 6 7 8
Cube 2: 0 1 2 3 4 5

Here the trick is to reuse 6 for 9.

Product Array

There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. Solve it without division operator and in O(n).


#include "vector"
#include "iterator"
#include "algorithm"
#include "iostream"
#include "stdlib.h"
using namespace std;

/*
 * Pass 1
   --->
   1 2 3 4 5
       ^
   Pass 2
         <--
   1 2 3 4 5
       ^
*/

void ArrayProduct(vector& array)
{
    const int n = array.size();
    vector product(n);
    int prod = 1;
    for ( int i=0; i    {
        product[i] = prod;
        prod *= array[i];
    }
    prod = 1;
    for ( int i=n-1; i>=0; --i)
    {
        product[i] *= prod;
        prod *= array[i];
    }

    copy ( product.begin(), product.end(),
            ostream_iterator(cout, " ")
         );
}

int main ( int argc, char* argv[])
{
    const int n = atoi(argv[1]);
    vector array(n);
    for ( int i = 1; i<= n; ++i )
        array[i-1] = i;
    ArrayProduct(array);
    return 0;
}

Add numbers in base n

Give an approach/code to add numbers in base n.

Answer:


After adding each digit, the sum%n will appear in the sum, and sum/n will be carried forward.

Palindrome Bit Representation

Check if binary representation of an int is a palindrome or not.
Answer:


Approach I:
Reverse the first word of the number and compare with the second word.

Apporach II:
Use a lookup table which contains the reverse of numbers from [0,0xFF]
#define IS_PALINDROME(num) ( (num & 0xFF) == lookup[num>>24] ) && (num>>8 & 0xFF) == lookup[num>>16] )

Mulitply by 7

Give a fast way to multiply a number by 7.

Answer:


#define MULTIPLY_BY_7(num) (num << 3) - num

Bit changes required to convert one int to another

Given two integers A & B. Determine how many bits required to convert A to B.

Answer:

 CountBits(A^B);

bit pattern check

I want to see if all the ones in a number appear on the right side of the number and all zeros appear on the left, how can I do this most efficiently? (i.e. 00000111 is true but 100010 is false)

Answer: Check if num+1 is a power of 2

Power of 2

Give a one-line C expression to test whether a number is a power of 2.

Anwer:


#define IS_POW_OF_2(n) !(n & (num-1))

Reverse the bits of an unsigned integer.

Reverse the bits of an unsigned integer.

Anwer:

Solution 1: The normal loop technique.
Solution 2: Use the lookup table, as used in counting the bits of a unsigned integer.¹

Bits set in a number

Write Program to count the number of bits set in a number.

Answer:


/**
 * Program to count the number of bits in a program
 * */

#include "stdio.h"
#include "stdlib.h"

void PrintBinary(size_t num)
{
    for( int i = 31; i >=0; --i )
        if ( num & ( 1 << i) )
            printf("1");
        else
            printf("0");
    printf("\n");
}

/**
 * O(n) algorithm, where n is the number of bits set
 * This algorithm works on the fact that when 1 is subtracted,
 * there exists a bit k, below which all the bit places get changed
 * so, num & num-1 will clear all the bits below the bit k.
 * ( to see this enable PrintBinary() function below )
 * */
size_t CountBits(size_t num)
{
    size_t count = 0;
    while (num)
    {
        //PrintBinary(num);
        num &= num-1;
        ++count;
    }
    return count;
}

/**
 * This is O(1) algorithm, but uses a lookup table.
 * Initially fill the lookup table with the bit count
 * then look into it :)
 * we can bring down the memory even further by using a lookup
 * table of size 16 (4 bits instead of 8 )
 * */
size_t lookup[256] = {};
void InitLookup()
{
    for( int i = 0; i <= 0xFF; ++i)
        lookup[i] = CountBits(i);
}

size_t CountBits_O1(size_t num)
{
    size_t count = lookup[num&0xFF] +
        lookup[ (num >> 8) & 0xFF ] +
        lookup[ (num >> 16) & 0xFF ] +
        lookup[ (num >> 24) & 0xFF ];

    return count;
}

int main (int argc, char* argv[])
{
    size_t num = atoi( argv[1] );
    printf("Bit count O(n) %d \n", CountBits(num) );
    InitLookup();
    printf("Bit count O(1) %d \n", CountBits_O1(num) );
    return 0;
}

Divisible by 3?

Give a method if a number is divisible by 3 without using the modulo operator.

Answer:

Sum the digits recursively until we are left with 3 or 6 or 9


bool IsDivisible(int num)
{
    int sum_of_digits = 0;
    if ( num < 10 )
    {
        if ( num == 3 || num == 6 || num == 9 )
            return true;
        else
            return false;
    }
    while(num)
    {
        sum_of_digits += num % 10;
        num = num / 10;
    }
    return IsDivisible(sum_of_digits);
}

BST with child count

You are given a special binary search tree where each node contains the
number of nodes in its child-trees in addition to the key.

Example:



                (50,4)
             /           \
          (30,4)        (70,2)
         /      \       /     \
      (20,2)  (40,0) (60,0)  (80,0)
      /    \
    (10,0) (25,0)


Given, 10, 40, the required value is 3, since we have 20, 25, 30

Answer:


int FindCount(TreeNode* n, int min_val, int max_val)
{
    if (n)
    {
        if ( n->val is between min_val and max_val )
            return n->child_count - 2;
        else if ( n->val < min_val )
            return FindCount(n->right, min_val, max_val);
        else
            return FindCount(n->left, min_val, max_val);
    }
    return 0;
}

Merging two Binary Search Trees

Describe a method to merge two BSTs.


             50
           /    \
          30     70
         /  \   /  \
        20  40 60   80
       /  \           \
      10   25         90


               30
              /   \
            15    45
              \
              20

Answer:

Probably the most efficient:
1. Create two array from the two trees by traversing in inorder: O(n+m) space + O(n+m) time
2. Merge the two arrays: O(n+m) time, O(n+m) space.
3. Create a balanced binary tree from this sorted array ¹, O(n+m) time (see related solution)

Valid Binary Search Tree

Given a BST, give an approach to verify if it is a 'valid' BST. Code it.

Answer:

Solution I:


bool IsValidBST(TreeNode* n)
{
    if(n)
    {
        bool isLeftValid = true;
        bool isRightValid = true;
        if( n->left )
        {
            if (n->left->val > n->val)
                return false;
            isLeftValid = isValidBST(n->left);

        }
        if( n->right)
        {
            if (n->right->val <= n->val)
                return false;
            isRightValid = isValidBST(n->right);
        }
        return isLeftValid && isRightValid;
    }
    return true;
}

Addition of Linked Lists

The numbers are represented in linked-list with each node representing a
digit of the number as follows:

1→2→3→ø
9→9→9→ø

Write a C program to add two numbers.


9→9→9→ø
    1→ø
—————————
1→0→0→0→ø

Answer:


struct Node
{
    Node* next;
    int val; 
};

Solution I:


/* Recursive solution */
Node* AddLinkedLists(Node* A, Node* B, size_t *carry)
{
    Node *next_node = NULL;
    if ( A->next )
         A = A->next;
    if ( B->next )
        B = B->next;
    if( (A->next) && (B->next) )
    {
        next_node = AddLinkedList(A,B);
    }
    Node* new_node = new Node();
    int sum = A->val + B->val + *carry
    new_node->val = sum%10 ;
    *carry = sum/10;
    new_node->next = next_node;
    return new_node;
}

Complexity: Space : O(n) , Time : O(n)

Solution II:

1. Reverse the lists O(n)
2. Add the lists
3. Reverse the lists O(n)

Better solution, time : O(n), space : O(1)

merging sorted streams

Given k sorted streams where each stream could possibly be infinite in length, describe an efficient algorithm to merge the k streams into a new stream (also in sorted order).

Answer:

Solution I (Divide and Conquer) :


                             list1
                      listA /
                     /  .   \
                    /   .    list2
                   /    .      .
         Merged   /     .      .
         List     \     .      .
                   \
                    \   .    listk-1
                      listC /
                            \
                             listk

This solution is not efficient, Complexity is 2^k-1 - 1

Solution II (Using buckets)

Use technique similar to Bucket sort, maximum complexity = O(N²)

Solution III (Using Heap)

(credit : The Great Khali)

Step1: Take first element of all k streams and build a min heap of them. => O(k)
Step2: Remove the min element (elem at top of heap) from the heap and put in the new stream. => O(log k)
Step3: Put new element in heap from the stream to which the prev elem belongs (which was at heap min). => O(log k)
Step4: continue above steps till we exhaust all the streams. If all streams in combination have n elements then order is O(n log(k))

Path in a directed graph

Write an algorithm to find if a path exists between two nodes in a directed graph.


1 ————> 2 ————> 3
        ↑       |
        |       |
        |       ↓
        4 ————> 5 ————> 6

Answer:


#include "stdio.h"
#include "stdlib.h"
#include "assert.h"

#define IS_CONNECTED(from,to) graph[(from-1)][(to-1)]

int graph[6][6]= {
                {0, 1, 0, 0, 0, 0},
                {0, 0, 1, 0, 0, 0},
                {0, 0, 0, 0, 1, 0},
                {0, 1, 0, 0, 1, 0},
                {0, 0, 0, 0, 0, 1},
                {0, 0, 0, 0, 0, 0}
               };

bool isReachable(size_t from, size_t to)
{
    const int n = 6;
    printf("\n isReachable %d -> %d \n", from, to );
    if ( from == to )
        return true;
    if(IS_CONNECTED(from, to))
        return true;
    else
    {
        for( size_t i =1; i <= n; ++i )
        {
            if( IS_CONNECTED(i,to) )
            {
                if (isReachable( from, i))
                    return true;
                continue;
            }
        }
        return false;
    }
}

int main(int argc, char* argv[])
{
    size_t from = atoi(argv[1]);
    size_t to = atoi(argv[2]);
    assert( (from <= 6) && (from >=1) );
    assert( (to <= 6) && (to >=1) );
    return printf("\n Is Reachable(%d -> %d) %d\n", from, to, isReachable(from, to ));
}

Find the non duplicate element

There is an array in which except one element, all other elements have duplicates, find that non duplicate element.

Answer:


/**
 * An array in which all elements except one are duplicate.,
 * find that element
 * */
#include "vector"
#include "algorithm"
#include "stdio.h"
using namespace std;

/** SOLUTION I 
 * Sort the array - O(n log(n))
 * Find the duplicate - O(n) (single pass)
 * */
void SortAndFind(vector &vec)
{
    // O(n log(n))
    sort(vec.begin(), vec.end() );
    int i = 0;
    int j = i + 1;
    int n = vec.size();
    // O(n)
    for ( i = 0, j = i+1; j < n ; ++j)
    {
        if ( vec[j] != vec[i] )
        {
            if ( (j-i) == 1 )
            {
                /* non duplicate found at j */
                printf("\n Non Duplicate (%s) %d \n", __func__, vec[i]);
                return;
            }
            else
            {
                i=j;
            }
        }
    }
    // the last element is the duplicate
    printf("\n Non Duplicate (%s) %d \n", __func__, vec[n-1]);
}

/** SOLUTION II , better than first solution.
 * Heapify the array - O(n)
 * Remove one element at a time and find the duplicate - O(log(n))
 * This approach is better because there is no need to sort the entire array
 * */
void HeapifyAndFind(vector &vec)
{
    // Create the heap O(n)
    make_heap(vec.begin(), vec.end() );
    // Find the duplicate, by removing one element at a
    // time.
    //
    int i = 0;
    int n = vec.size();
    for ( int j = i+1; j < n; ++j)
    {
        // vec[j-1] is the min element
        make_heap( vec.begin() + i , vec.end() );
        if ( vec[i] != vec[j] )
        {
            if ( (j-i) == 1 )
            {
                /* non duplicate found at j */
                printf("\n Non Duplicate (%s) %d \n", __func__, vec[i]);
                return;
            }
            else
            {
                i=j;
            }
        }

    }
    // the last element is the duplicate
    printf("\n Non Duplicate (%s) %d \n", __func__, vec[n-1]);

}

int main(int argc, char *argv[])
{
    if ( argc > 1 )
    {
        vector vec1(argc-1);
        vector vec2(argc-1);

        for (int i = 1; i <= argc-1; ++i)
        {
            vec1[i-1] = atoi(argv[i]);
            vec2[i-1] = atoi(argv[i]);
        }

        SortAndFind( vec1 );
        HeapifyAndFind( vec2 );
    }
    return 0;
}

Circular linked list or Corrupt linked list

Write an algorithm to detect a corrupt node in a linked list, i.e
There is a linked list. The last node could point back to any node in
the list (including the head). Find the node in the list to which the
last node points. Or in other words at which node does the circular
linked list start.

Answer:

Solution 1 : O(n) solution, ( This is the most expected solution )


#include "iostream"
#include "stdio.h"

using namespace std;

struct Node
{
    int val;
    Node *next;
    Node(int _val, Node* _next=0):val(_val),next(_next){}
};

Node* createLinkedListWithLoop(size_t n)
{
    Node *head = 0;
    Node *prev = 0;
    Node *last = 0;
    printf("\n ---- \n");
    for ( int i = 0; i < n; ++i)
    {
        head = new Node(0,prev);
        printf("\n New Node %#x \n", head);
        prev = head;
        if ( !last ) last = head;
    }
    head = prev;
    // create the loop
    last->next = head->next->next->next->next;
    printf("\n The last node points to %#x \n", last->next);
    return head;
}

size_t countElements(Node* list, const Node* delim_node)
{
    size_t count = 0;
    while(list != delim_node)
    {
        ++count;
        list = list->next;
    }
    return count;
}

void findLoop(Node* list)
{
    // step 1 : Find a node that occurs in the loop
    // this is done by taking two pointers and traversing
    // the linked list such that :
    // PtrA moves at steps of 1
    // PtrB moves at steps of 2,
    // so that they will intersect each other in the loop.
    Node * listA = list;
    Node * listB = list;
    do
    {
        if ( listA )
            listA = listA->next;
        // increment twice
        if ( listB )
            listB = listB->next->next;
    }while(listA != listB);


    // now treat list to listA as one list
    // and treat listB->next to listA as another list
    // i.e. find the point of intersection of these two lists
    // and during the traversal, the second node pointing to this 
    // intersection is the corrupt node.

    // the point of intersection
    const Node* delim_node = listA;
    // the first sub linked list
    listA = list;
    // the second sub linked list
    listB = listB->next;

    // step 2 : count the elements
    size_t countA = countElements(listA, delim_node);
    size_t countB = countElements(listB, delim_node);

    // step 3 : align the ptrs so that they are
    // at the same distance from the end
    while (countA != countB)
    {
        if( countA > countB )
        {
            --countA;
            listA = listA->next;
        }
        else
        {
            --countB;
            listB = listB->next;
        }
    }
    // step 4 : move both the ptrs one at a time, and check if they
    // both point to same node.
    Node *corrupt_node = 0;
    while( listA != listB )
    {
        listA = listA->next;
        corrupt_node = listB;
        listB = listB->next;
    }
    // we have found the intersection now,
    printf("\n Intersection at %#x, corrupt node %#x \n",
            listA, corrupt_node);
}

int main()
{
    Node* list = createLinkedListWithLoop(16);
    findLoop(list );
    return 0;
}

Solution 2 : O(n) time, O(n) space solution, but single pass.

Take a hash_map, as we traverse the linked list,
if ( node ) is absent in hash_map, add it
else if the node is present, then we have found a loop.

Intersection of linked lists

Write an algorithm to find the intersection of linked lists.

Answer:

Solution 1 :
O(n) solution, constant space. (this is what expected most of times)


#include 
#include 

using namespace std;

struct Node
{
    int val;
    Node *next;
    Node(int _val, Node* _next=0):val(_val),next(_next){}
};

Node* createLinkedList(size_t n)
{
    Node *head = 0;
    Node *prev = 0;
    printf("\n ---- \n");
    for ( int i = 0; i < n; ++i)
    {
        head = new Node(0,prev);
        printf("\n New Node %#x \n", head);
        prev = head;
    }
    head = prev;
    return head;
}

void createIntersection(Node* listA, Node* listB)
{
    while(listB->next) listB = listB->next;
    listB->next = listA->next->next->next->next;
}

size_t countElements(Node* list)
{
    size_t count = 0;
    while(list)
    {
        ++count;
        list = list->next;
    }
    return count;
}

void findIntersection(Node* listA, Node* listB)
{
    // step 1 : count the elements
    size_t countA = countElements(listA);
    size_t countB = countElements(listB);

    // step 2 : align the ptrs so that they are
    // at the same distance from the end
    while (countA != countB)
    {
        if( countA > countB )
        {
            --countA;
            listA = listA->next;
        }
        else
        {
            --countB;
            listB = listB->next;
        }
    }
    // step 3 : move both the ptrs one at a time, and check if they
    // both point to same node.
    while( listA != listB )
    {
        listA = listA->next;
        listB = listB->next;
    }
    // we have found the intersection now,
    printf("Intersection at %#x \n", listA);
}

int main()
{
    Node* listA = createLinkedList(10);
    Node* listB = createLinkedList(3);
    createIntersection(listA, listB);
    findIntersection(listA, listB);
    return 0;
}

Solution 2:
O(n) space, O(n) time solution,
Use a lookup table. ( not expected most of the times )

7 segment display

Seven segment displays provide an inexpensive display of the 10 decimel digits(0,1,2,3,4,5,6,7,8,9). The seven segments are usually numbered as


---2---
|     |
3     4
|     |
---1---
|     |
5     6
|     |
---0---

Answer:

Use lookup tables with bit pattern for each digit, for ex: this techinque is used in counting the number of bits set, reversing the bits of a number.

Sequence Conversion

Given the sequence S1 = {a,b,c,d,...,x,y,z,aa,ab,ac.... } and given that this sequence corresponds (term for term) to the sequence S2 = {1,2,3,4,....}
Write code to convert an element of S1 to the corresponding element of S2. Write code to convert an element of S2 to the corresponding element of S1.

n-ary trees

How do you represent an n-ary tree? Write a program to print the nodes
of such a tree in breadth first order.

Answer: using array of nodes, and use Q

linked list flattening

You are given a singly link-list such that each node of this list is also a
head of another link list of the same type. So, how does one flatten the
linked-list

struct node {
void *data; /* could be anything */
struct node *next;
struct node *down;
};

Second minimum element in a array

Given an array of n numbers a[1], a[2],..., a[n], find the second minimum number in n + log n comparisons.

Answer:

Initially it seems that this can be done in a single pass,
like finding the min element, but dont be tricked, this is not possible.
For example, if the second min happens first and the min element happens later,
then its not possible, ex: {10, 6, 9, 7, 8, 5}

The answer is in fact is in the question itself,
Build a Min Heap - O(n) time
Remove the Root - O(log(n)) time
Remove the Root again, which happens to be the second min element - O(log(n))

So the total time = n + log(n)

See also:
*Selection Sort technique

mth to last element in a linked list

Given a singly linked list, devise an algo to find the m-th to last
element of the list. Code it.(Ex. when m=0 the last element of the LL is
returned).

Answer:



[2] -> [3] -> [4] -> [5] -> ..... [100]
 ^                    ^
mThToLast            last --->
|----------------------|
     distance = m


Node *mThToLast = head;
Node* last = head;
while ( m )
{
    last = last->next;
    --m;
}
while(  last->next )
{
    mThToLast= mThToLast->next;
    last = last->next;
}

Sort an Array of 0s and 1s

How would you sort an array that consists of only zeros and ones in only one pass?
Answer:


Use Quick Sort :

0 1 1 1 0 0 1 0 0 1
^       ^         ^
up     pivot      down

Quick sort will do this in one pass.

Count Sort will do this in two passes.

Find median of numbers held in servers

Given N computers networked together, with each computer storing N integers, describe a procedure for finding the median of all of the numbers. Assume that a computer can only hold O(N) integers (i.e. no computer can store all N² integers). Also assume that there exists a computer on the network without integers, that we can use to interface with the computers storing the integers.

Probable Answer:


Median = Sum / Count
Find the sum, count requires O(1) memory,
[1 2 3] [4 5 6] [7 8 9]
   |       |       |
  [2]     [5]     [9] (The machine with free memory)
   |       |       |
   ^^^^^^^^^^^^^^^^^
          [5]

Distributing 0s and 1s in even and odd positions

Given an array of 0s and 1s, write an algo such that,
- the 0s will occupy the even positions.
- the 1s will occupy the odd positions.
- any extra 0s or 1s should be placed at the end of array
Complexity: linear, in a single pass

Answer:


#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream>
using namespace std;

//
//  1 0 1 0 1 1 1
//  i j --> move by step of 2
void Distribute0s1s(vector& a, size_t n)
{
    size_t i = 0, // i will point to the even indices
           j = i+1; // j will point to the odd indices
    for ( ; (i < n) && (j < n) ; )
    {
        // already 0 in even position, move ahead
        if ( a[i] == 0 )
        {
            i += 2;
        }

        // already 1 in odd position, move ahead
        if ( a[j] == 1 )
        {
            j += 2;
        }

        if ( i >=n ) break;
        if ( j >=n ) break;

        // 1 in even pos, 0 in odd pos, swap
        if ( a[i] && !a[j] )
        {
            swap( a[i], a[j] );
            i += 2;
            j += 2;
        }
    }

    if ( i < n )
    {
        // At this point, all the odd positions are enused with 
        // 1s
        j = i + 2;
    }
    else if ( j < n )
    {
        // At this point, all the even positions are enused with 
        // 0s
        i = j;
        j = i + 2;
    }

    // handle the remaining numbers
    while ( j < n )
    {
        if (
                (  ( i % 2 == 0 ) &&  ( a[j] < a[i] )  ) ||
                (  ( i % 2 == 1 ) &&  ( a[j] > a[i] )  )
           )
        {
            swap( a[j], a[i] );
            i += 2;
        }
        j += 2;
    }
}

int main( int argc, char* argv[] )
{
    if ( argc == 1 ) return 0;
    else
    {
        vector a(argc-1);
        for ( int i = 1; i <= argc-1; ++i)
            a[i-1] = atoi(argv[i]);
        cout << "Input :" << endl;
        copy ( a.begin(), a.end(), ostream_iterator(cout, " "));
        cout << endl << "Output :" << endl;
        Distribute0s1s(a, a.size() );
        copy ( a.begin(), a.end(), ostream_iterator(cout, " "));
    }
    return 0xabcdef;

}

Locker door state puzzle

Lockers numbered 1 to 100 stand in a row at the school gym. When the first student arrives, she opens all the lockers. The second student then goes through and recloses all the even-numbered lockers; the third student changes the state of every locker whose number is a multipls of 3.

This continues until 100 students have passed through. Which lockers are now open?

Answer:

Let us trace the first few doors as they are operated by the students:
1 -> 1 (open)
2 -> 1, 2 (close)
3 -> 1, 3 (close)
4 -> 1, 2, 4 (open)
5 -> 1, 5 (close)
6 -> 1, 2, 3, 6 (close)
7-> close
8->1, 2, 4, 8(close)
9-> 1, 3, 9 (open)
10-> 1, 2, 5, 10(close)
11->1, 11(close)
12 -> 1, 2, 3, 4, 6, 12(close)
13 -> close
14 -> 1, 2, 7, 14 (close)
15 -> 1, 3, 5, 15 (close)
16 -> 1, 2, 4, 8, 16 (open)
17 -> (close)
18 -> 1, 2, 3, 6, 9, 18 (close)

What can be infered is that, a state of the door depends on the
number of divisors:
Even : then door is closed
Odd : Open

Now the multiples of a number ususally occur in pairs, i.e j*k = n
( exception is for 1)
for example for 10 we have 1 * 10, 2 * 5
i.e effects of (1,10) (2,5) is nullified, i.e a pair nullifies the effect.
the door is in its original state.

But for perfect squares, we have something like j*j = n, and since j happens only once there is no nullifying effect, so the perfect squares will be open. for ex take 16 : we have the pairs, (1*16) (2*8) (4*4), and the last pair does not nullify each other.

So, the perfect squares, 1, 4, 16, 25, 36, 49, 64, 81, 100 will be open

Tree permutations

Write a program to calculate the different number of tree structures possible,
given n identical values.
For Example:


    For one node, the tree is a trivial one node tree.
    For two nodes, two combinations are possible:
    O               O
     \      and    /
      O           O

    For three nodes :
      O      O      O      O        O
     /      /      / \      \        \
    O      O      O   O      O        O
   /        \                 \      /
  O          O                 O    O

Answer:


/*
For the above diagrams, we can see the recursive property,
i.e, 
For given N nodes:
* One node becomes the root
* Divide the remaining N-1 nodes between left and right subtrees, and this can be
  done as follows:
  Left Subtree              Right Subtree
      0                         N-1
      1                         N-2
      2                         N-3
      ...                       ...
     N-1                         0

  Summing up the above combinations, to get the value of N, 
  The solution can be recursively defined as following:

            { 1 if n == 1  }
  F(n) =    { sigma( F(i) * F(n-i-1 ) where i = 0 to n-1 }

  note that its F(i) * F(n-i-1) , product, not a sum because its a combinatorics problem,
  If event A can be in m ways, and another event B can be done in n ways, then the total
  possible events are (m x n)

  Note that optimization can be achived by caching the results in the recursive call.


*/


#include <stdio.h>
#include <stdlib.h>
#include <vector>
using namespace std;
// the cache used to "cache the results in a recursive call"
vector cache;
size_t TreeCombinations(size_t n)
{
    if ( (n == 1) || (n == 0) )
        return cache[n];
    // Check if the result was already computed
    if ( cache[n] != 0 )
        return cache[n];
    else
    {
        int i = 0;
        size_t combinations = 0;
        //printf("{ %d \n", n);
        for ( i =0 ; i <= n-1; ++i)
        {
            size_t tmp = TreeCombinations(i) * TreeCombinations(n-i-1);
            //printf(" f(%d) * f(%d) = %d \n", i, n-i-1, tmp );
            combinations += tmp;
        }
        //printf("}\n");
        cache[n] = combinations;
    }

    return cache[n];
}

int main(int argc, char* argv[])
{
    size_t n = atoi(argv[1]);
    // initialize the cache
    cache.reserve(n+1);
    for ( int i = 0; i <= n; ++i )
    {
        cache[i] = 0;
    }
    cache[0] = 1;
    cache[1] = 1;
    // ----
    return printf("Tree combinations for %d nodes = %d \n", n, TreeCombinations(n) );
}

Clumps in a Binary Tree

Assume that each node in a binary tree represents a color. A clump is defined as 3 or more adjacent nodes with same color.
Write an algorithm to determine the number of clumps.
For example:


                R
              /   \
             R     R
            / \   /  \
           B   B  R   G
              / \    / \
             B   B  G   G
                         \
                          G
The Above tree has 3 clumps:
4 Adjacent Reds starting at the root.
4 adjacent Greens in the right subtree.
3 adjacent Blues in the left subtree.

Answer:

Here is the solution in C++:


#include 
using namespace std;
// The colors of the tree
enum Color
{
    Unknown,
    Red,
    Green,
    Blue
};

struct TreeNode
{
    Color color;
    TreeNode* left;
    TreeNode* right;

    TreeNode(Color c, TreeNode* _left=0, TreeNode* _right=0):
        color(c), left(_left), right(_right){}
};

void CountClumps(TreeNode* node, Color parentColor, size_t &curCount, size_t &clumpCount)
{
    if( node )
    {
        if (node->color != parentColor)
        {
            /* The color of the current node is not equal to the 
             * parent node's color, then we dont increase the curCount, but start a new
             * clumpCount */
            size_t _curCount = 1; // 1 because of the current node color
            CountClumps(node->left, node->color, _curCount, clumpCount);
            CountClumps(node->right, node->color, _curCount, clumpCount);
            if ( _curCount >= 3 )
                ++clumpCount;
        }
        else
        {
            /* increase the curCount ( which signifies the nodes with same color )
             * and let the parent decide about the clump, and traverse the left and
             * right subtrees
             * */
            ++curCount;
            CountClumps(node->left, node->color, curCount, clumpCount);
            CountClumps(node->right, node->color, curCount, clumpCount);
        }
    }
}

int main(int argc, char* argv[])
{
    // The left subtree
    TreeNode *n1 = new TreeNode(Green,0,0);
    TreeNode *n2 = new TreeNode(Green,0,n1);
    TreeNode *n3 = new TreeNode(Green,0,0);
    TreeNode *n4 = new TreeNode(Green,n3,n2);

    TreeNode *n5 = new TreeNode(Red,0,0);
    TreeNode *n6 = new TreeNode(Red,n5,n4);

    // The right subtree
    TreeNode *n7 = new TreeNode(Blue, 0,0);
    TreeNode *n8 = new TreeNode(Blue, 0,0);
    TreeNode *n9 = new TreeNode(Blue, n7,n8);
    TreeNode *n10 = new TreeNode(Blue, 0, 0);
    TreeNode *n11 = new TreeNode(Blue, n10, n9);

    // The Root
    TreeNode *root = new TreeNode(Red, n11, n6);

    size_t curCount = 0;
    size_t clumpCount = 0;

    CountClumps( root, Unknown, curCount, clumpCount );

    cout << "Clumps " << clumpCount << endl;

    // set the left subtree to null
    curCount = 0;
    clumpCount = 0;
    root->left = 0;
    CountClumps( root, Unknown, curCount, clumpCount );

    cout << "Clumps " << clumpCount << endl;

    // set the right subtree to null
    curCount = 0;
    clumpCount = 0;
    root->right= 0;
    root->left = n11;
    CountClumps( root, Unknown, curCount, clumpCount );

    cout << "Clumps " << clumpCount << endl;

    // Sorry forgot to release the memory of the TreeNode :D
    return clumpCount;
}

Matrix Multiplication

Write code for matrix multiplication.

Answer:



(M x N) * (N x P) = (M x P) matrix
     ^^^^^^^

  N
---->
1 2 3   x 1 4 |
4 5 6     2 5 | N
          3 6 \/

From the above diagram, it can be infered that
M and P will form the outer loops and N will be the
innermost loop.

for ( i = 0 to M )
  for ( j = 0 to P )
  {
    a[i][j] = 0;
    for ( k = 0 to N )
    {
       a[i][j] += a[i][k] * a[k][j];     
         
    }
  }

Exchange the bits at even and odd positions

Write code to exchange the bits at even and odd positions in a number.

Answer:


/**
 * Program to exchange the bits at even and odd positions
 * */
#include "stdio.h"
#include "stdlib.h"

void PrintBinary(size_t num)
{
    for( int i = 31; i >=0; --i )
        if ( num & ( 1 << i) )
            printf("1");
        else
            printf("0");
    printf("\n");
}

size_t SwapBits(size_t num)
{
    /* Program to reverse the bits of a number */

    return ( (num << 1) & 0xAAAAAAAA ) |
        ( (num >> 1 & 0x55555555) );
}

int main(int argc, char* argv[])
{
    for ( int i = 1; i <= argc-1; ++i )
    {
        size_t num = atoi(argv[i]);
        PrintBinary(num);
        PrintBinary(SwapBits(num));
    }
    return 0;

}

N-Queens problem

Write the algorithm for N-Queens problem.

Answer:


Board[n] = {}


bool isColliding(int row, int col)
{
    for ( i = 1; i < row; ++i)
    {
        /* diagonal collision */
        if ( abs(row -i) == abs(col - Board[i] ) )
            return false;
        /* columnar collision */
        if ( Board[i] == col )
            return false;
    }
    return true;
}

void placeQueen(int row, int col)
{
    Board[row] = col;
}

void Iterative_NQueens()
{
    for (row=1; row <= n; ++row)
    {
        for(col=1; col <= n; ++col )
        {
            if ( isColliding(row,col) )
                continue;
            else
            {
                placeQueen(row,col);
                if ( row == n )
                {
                    /* print the solution */
                }
                break; // continue with next row
            }
        }
    }
}

void Recursive_NQueens(int _row)
{
    for (row = _row; row <= n; ++row)
    {
        for(col=1; col <= n; ++col )
        {
            if ( isColliding(row,col) )
                continue;
            else
            {
                placeQueen(row,col);
                if ( row == n )
                {
                    /* print the solution */
                    return;
                }
                else
                    /* next row */
                    Recursive_NQueens(_row + 1);
            }
        }
    }
}

Generation of Prime Numbers

Write an algorithm to generate the prime numbers.

Answer:

Several solutions exist, the basic solution is to use the sieve technique.
Basic Solution:


prime_nos = [1,2]
bas
for ( i = 3 to n )
{
    if (i is divisible by any number < sqrt(i))
    {
        then i is not prime
        i += 2; // increment by two, optimization, since even numbers
                // cannot be prime.
    }
    else
    {
        add i to the prime_nos list.
    }

}

Well known algorithms:
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
http://en.wikipedia.org/wiki/Sieve_of_Atkin

Also as per wikipedia:

One method for determining whether a number is prime is to divide by all primes less than or equal to the square root of that number. If any of the divisions come out as an integer, then the original number is not a prime. Otherwise, it is a prime. One need not actually calculate the square root; once one sees that the quotient is less than the divisor, one can stop.