Sunday, September 20, 2009

3n+1 problem

The Problem

Consider the following algorithm:
1. input n 2. print n
3. if n = 1 then STOP
4. if n is odd then  n = 3*n+1
5. else    n = n/2
6. GOTO 2

Given the input 22, the following sequence of numbers will be printed 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

It is conjectured that the algorithm above will terminate (when a 1 is printed) for any integral input value. Despite the simplicity of the algorithm, it is unknown whether this conjecture is true. It has been verified, however, for all integers n such that 0 < n < 1,000,000 (and, in fact, for many more numbers than this.)
Given an input n, it is possible to determine the number of numbers printed (including the 1). For a given n this is called the cycle-length of n. In the example above, the cycle length of 22 is 16.

For any two numbers i and j you are to determine the maximum cycle length over all numbers between i and j
Normal non recursive method
using namespace std;
int main() {
    unsigned int i, j;     int count, cmax;       int process(int x);     cout<<"Enter range:\nFrom:";     cin>>i;     cout<<"\nTo: ";     cin>>j;     cout<<<" "<
    for(;i<=j;i++)    {                               count=process(i); 
                  if(count>cmax)                   cmax=count;               }     cout<<" "<       return 0; } int process(int x) {      int count;  
     for(count=1;x!=1;++count)      {                                               if(x%2==0)                                  x/=2;                             else                                x=3*x+1;    }      return count; }
Recursive Solution
#include <stdio.h>
#define SIZE 1000001

static unsigned short table[SIZE];

unsigned short calcCycleLength(register unsigned long n )
 if(n < SIZE && table[n])
  return table[n];
 if(n & 1){ /* if n is odd */
  if( n < SIZE) {
   table[n] = 2 + calcCycleLength( (3*n+1) >> 1 ); /* calc two steps at one */
   return table[n];
   return 2 + calcCycleLength( (3*n+1) >> 1 );

 else {
  if( n < SIZE) {
   table[n] = 1 + calcCycleLength( n >> 1 ); /* n/2 */
   return table[n];
   return 1 + calcCycleLength( n >> 1 );

int main()
 unsigned long i, fstIn, sndIn;
 short out = 0, temp;

 table[1] = 1;

 while ( scanf("%lu %lu", &fstIn, &sndIn ) != EOF  )
  if( fstIn > sndIn) {
   for( i = sndIn; i <= fstIn; ++i )
    temp = calcCycleLength( i );
    if( temp > out)
     out = temp;
  else {
   for( i = fstIn; i <= sndIn; ++i )
    temp = calcCycleLength( i );
    if( temp > out)
     out = temp;
  printf("%lu %lu %hdn", fstIn, sndIn, out);
  out = 0;
 return 0;

Friday, September 18, 2009

jelly beans

you have three jars that are all mislabeled. one contains peanut butter jelly beans, another grape jelly jelly beans, and the third has a mix of both (not necessarily a 50/50 mix, could be a 1/99 mix or a 399/22 mix). how many jelly beans would you have to pull out, and out of which jars, to find out how to fix the labels on the jars?

|     |        |     |          |     |
|jar 1|        |jar 2|          |jar 3|
|     |        |     |          |     |
=======        =======          =======
  p.b.          grape          p.b./grape


solution: 1 jelly bean from the p.b./grape jar will do the trick.
the trick here is to realize that every jar is mislabeled. therefore you know that the peanut butter jelly bean jar is not the penut butter jelly bean jar, and the same goes for the rest.
you also need to realize that it is the jar labeled p.b./grape, labelled as the mix jar, that is your best hope. if you choose a jelly bean out of there, then you will know whether that jar is peanut butter or grape jelly jelly beans. it can't be the mix jar because i already said that every jar is mislabeled.
once you know that jar 3 is either peanut butter, or grape jelly, then you know the other jars also. if it is peanut butter, then jar 2 must be mixed because it can't be grape (as its labelled) and it can't be peanut butter (that's jar 3). hence jar 1 is grape.
if jar 3 is grape, then you know jar 1 must be the mix because it can't be p.b. (as its labelled) and it can't be grape (that's jar 3). hence jar 2 is peanut butter.
if you pick jelly beans from jar 1 or jar 2, then you would have to pick out all of the jelly beans before you knew what that jar was. this is because jar 1 and 2 could be the mix, so in order to disprove that they were the mix, you would have to pull out every jelly bean just to make sure (since there could just be one bean of the opposite flavor in there).

Bad king

a bad king has a cellar of 1000 bottles of delightful and very expensive wine. a neighbouring queen plots to kill the bad king and sends a servant to poison the wine. (un)fortunately the bad king's guards catch the servant after he has only poisoned one bottle. alas, the guards don't know which bottle but know that the poison is so strong that even if diluted 1,000,000 times it would still kill the king. furthermore, it takes one month to have an effect. the bad king decides he will get some of the prisoners in his vast dungeons to drink the wine. being a clever bad king he knows he needs to murder no more than 10 prisoners - believing he can fob off such a low death rate - and will still be able to drink the rest of the wine at his anniversary party in 5 weeks time.

i'll give you a hint. 1000 is less than 1024. if there were 1024 or more bottles of wine it would take more than 10 prisoners.
number the bottles 1 to 1000, and write the number in binary format.
bottle 1 = 0000000001
bottle 250 = 0011111010
bottle 1000 = 1111101000
now take your prisoner's 1 through 10 and let prisoner 1 take a sip from every bottle that has a 1 in its least significant bit. let prisoner 10 take a sip from every bottle with a 1 in its most significant bit. etc.
prisoner 10 9 8 7 6 5 4 3 2 1
bottle 924 1 1 1 0 0 1 1 1 0 0
for instance, bottle #924 would be sipped by 10,9,8,5,4 and 3. that way if bottle #924 was the poisoned one, only those prisoners would die.
after four weeks, line the prisoners up in their bit order and read each living prisoner as a 0 bit and each dead prisoner as a 1 bit. the number that you get is the bottle of wine that was poisoned.
additional question: to increase your chance of living, which prisoner would you want to be?
if there were 1023 bottles, it wouldn't matter since everyone would have to take 512 sips. but there are 23 bottles less, so the people whose bits would have been on from 1001 to 1023 won't have to take a sip. 1001 is [11111 01001] in binary and 1023 is [11111 11111]. the most five significant bits are the most interesting because they would always be on from 1001 to 1023, so all those people are missing out on 23 bottles of wine that they otherwise would have had to drink. so in order to increase your chance of living, you'd probably want to be prisoner 6 to 10. (but depending on how the king determines who is least significant and who is most significant you could get shafted.)
note that if the king was really trying to kill the least number of prisoners, he should have let 999 prisoners each take a sip from their respective bottle numerically (if he had that many prisoners at his disposal). that way only one prisoner would die, and there's a chance of 1/1000 that no one would die, but then the puzzle isn't very fun.


five pirates have 100 gold coins. they have to divide up the loot. in order of seniority (suppose pirate 5 is most senior, pirate 1 is least senior), the most senior pirate proposes a distribution of the loot. they vote and if at least 50% accept the proposal, the loot is divided as proposed. otherwise the most senior pirate is executed, and they start over again with the next senior pirate. what solution does the most senior pirate propose? assume they are very intelligent and extremely greedy (and that they would prefer not to die).

Most of the time i get people who give answers like "the most senior pirate takes half and divides the rest up among the least senior pirates." um, you missed the whole point to begin with. sorry. any answer without a specific logic behind it is invalid. if i ask you why pirate 5 gave x coins to pirate 1, please don't say "because he's nice".

Now for the real solution. pirate 5 being the most senior knows that he needs to get 2 other people to vote for his solution in order for him not to be executed. so who can he get to vote for him, and why would they choose to vote for him? if you start thinking that pirate 4 will never vote for him, because he would rather have 5 die and then be in charge and take it all for himself, you are on the right track. but it gets more complicated.

Lets consider if there were only 1 pirate. obviously he would take it all for himself and no one would complain.
If there were 2 pirates, pirate 2 being the most senior, he would just vote for himself and that would be 50% of the vote, so he's obviously going to keep all the money for himself.

If there were 3 pirates, pirate 3 has to convince at least one other person to join in his plan. so who can he convince and how? Here is the leap that needs to be made to solve this problem. pirate 3 realizes that if his plan is not adopted he will be executed and they will be left with 2 pirates. he already knows what happens when there are 2 pirates as we just figured out. pirate 2 takes all the money himself and gives nothing to pirate 1. so pirate 3 proposes that he will take 99 gold coins and give 1 coin to pirate 1. pirate 1 says, well, 1 is better than none, and since i know if i don't vote for pirate 3, i get nothing, i should vote for this plan.

Now we know what happens when there are 3 pirates. so what happens with 4? well pirate 4 has to convince 1 other person to join in his plan. he knows if he walks the plank then pirate 3 will get 99 coins and pirate 1 will get 1 coin. pirate 4 could propose giving pirate 1 two coins, and surely pirate 1 would vote for him, since 2 is better than 1. but as greedy as he is, pirate 4 would rather not part with 2 whole coins. he realizes that if he gets executed, then pirate 3's scenario happens and pirate 2 gets the shaft in that scenario (he gets zero coins). so pirate 4 proposes that he will give 1 coin to pirate 2, and pirate 2 seeing that 1 is better than 0 will obviously vote for this plan.

A common objection is that pirate 2 is not guaranteed to vote for this plan since he might hope for the case when there are only 2 pirates and then he gets all the booty. but that is why i said that the pirates are extremely intelligent. pirate 2 realizes that pirate 3 is smart enough to make the optimal proposal, so he realizes that there will never be 2 pirates left, because 3 doesn't want to die and we just showed that 3 has a winning proposal.
so lets sum up at this point
Pirate 1 2 3 4 5
5. ? ? ? ? ?
4. 0 1 0 99 -
3. 1 0 99 - -
2. 0 100 - - -
once you see the pattern it becomes very clear. you have to realize that when a pirate's plan does not succeed then that means you are in the same situation with one less pirate.
1. pirate 1 needs 0 other people to vote for him. so he votes for himself and takes all the money. 2. pirate 2 needs 0 other people to vote for him. so he votes for himself and takes all the money. pirate 1 gets 0. 3. pirate 3 needs 1 other person to vote for him. he gives 1 coin to pirate 1 for his vote - if we are reduced to 2 pirates, pirate 1 gets 0 so pirate 1 knows 1 is better than none. pirate 3 takes 99. pirate 2 gets 0. 4. pirate 4 needs 1 other person to vote for him. he gives 1 coin to pirate 2 - if we reduce to 3 pirates, pirate 2 gets 0 so pirate 2 knows 1 is better than none. pirate 4 takes 99. pirate 3 gets 0. pirate 1 gets 0. 5. pirate 5 needs 2 other people to vote for him. its clear now that the 2 people he needs to convince are the 2 who get shafted in the 4 pirate scenario - pirate 3 and pirate 1. so he can give them each 1 coin (which is better than 0 - what they would get otherwise) and keep 98 for himself.
Pirate 1 2 3 4 5
5.        1 0 1 0 98
what happens if there are 15 pirates? pirate 15 needs 7 other people to vote for him, so he recruits pirates 13,11,9,7,5,3, and 1 with 1 coin each and keeps 93 coins himself. those pirates will all vote for him because they know that they get 0 coins if he dies and pirate 14 is in charge.
hope you enjoyed this one. its my favorite interview question of all. it really allows the candidate to ask a lot of interesting questions and its really amazing when they reach the solution all by themselves (as all fogcreek employees have done so far)

sum it up

Problem: you are given a sequence of numbers from 1 to n-1 with one of the numbers repeating only once. (example: 1 2 3 3 4 5). how can you find the repeating number? what if i give you the constraint that you can't use a dynamic amount of memory (i.e. the amount of memory you use can't be related to n)?
what if there are two repeating numbers (and the same memory constraint?)

As a programmer, my first answer to this problem would be make a bit vector of size n, and every time you see the number, set its correspond index bit to 1. if the bit is already set, then that's the repeater. since there were no constraints in the question, this is an ok answer. its good because it makes sense if you draw it for someone, whether they are a programmer, mathematician, or just your grandpa. its not the most efficient answer though.

Now, if i add the constraint that you can only use a fixed amount of memory (i.e. not determined by n) and it must run in O(n) time... how do we solve it. adding all the numbers up from 1 to n-1 would give us a distinct sum. subtracting the total sum of all the numbers from the sum of n to n-1 ( which is (n)(n-1)/2 ) would give us the secret extra number. 

what if you can only use a fixed amount of memory, and two of the numbers are repeated? we know that the numbers have a distinct sum, and the difference would be equal to the sum of our unknowns
c = a + b
where c is the sum and a and b are the unknowns - c is a constant
If we had another similar formula we could solve the two unknown equations. my first thought was that the numbers would have a distinct product - (n-1)!
If we divide the total product by the (n-1)! product, we would get another equation
c2 = ab
we could then solve the two equations to get them into quadratic formula notation
0 = ax^2 + bx + c
and solve for the two values of x. this answer is correct but factorial grows really fast.
some sort of sum would be better. the sum of the squares from n-1 to 1 would work. that would yield a function of the form
c2 = a^2 + b^2
which could also be solved by using the quadratic equation.
i think its fine to remind someone of the quadratic equation... (maybe only because i myself had to look it up to solve the problem) i mean really though, the last time i used it was probably in 10th grade. as long as they get the idea that given two unknowns and two equations you can solve for the unknowns - thats the point.

Palindrome years


This year on October 2, 2001, the date in MMDDYYYY format will be a palindrome (same forwards as backwards).


when was the last date that this occurred on? (see if you can do it in your head!)

we know the year has to be less than 2001 since we already have the palindrome for 10/02. it can't be any year in 1900 because that would result in a day of 91. same for 1800 down to 1400. it could be a year in 1300 because that would be the 31st day. so whats the latest year in 1300 that would make a month? at first i thought it would be 1321, since that would give us the 12th month, but we have to remember that we want the maximum year in the 1300 century with a valid month, which would actually be 1390, since 09/31 is a valid date.

but of course, a question like this wouldn't be complete without an aha factor. and of course, there are not 31 days in september, only 30. so we have to go back to august 08 which means the correct date would be 08/31/1380.

daughter's ages

Two MIT math grads bump into each other at Fairway on the upper west side. they haven't seen each other in over 20 years.
the first grad says to the second: "how have you been?"
second: "great! i got married and i have three daughters now"
first: "really? how old are they?"
second: "well, the product of their ages is 72, and the sum of their ages is the same as the number on that building over there.."
first: "right, ok.. oh wait.. hmm, i still don't know"
second: "oh sorry, the oldest one just started to play the piano"
first: "wonderful! my oldest is the same age!"
problem: how old are the daughters?

Solution: Start with what you know. you know there are 3 daughters whose ages multiply to 72. let's look at the possibilities...

Ages:            Sum of ages:
1 1 72            74
1 2 36            39
1 3 24            28
1 4 18            23
1 6 12            19
1 8 9             18
2 2 18            22
2 3 12            17
2 4 9             15
2 6 6             14
3 3 8             14
3 4 6             13
after looking at the building number the man still can't figure out what their ages are (we're assuming since he's an MIT math grad, he can factor 72 and add up the sums), so the building number must be 14, since that is the only sum that has more than one possibility.
finally the man discovers that there is an oldest daughter. that rules out the "2 6 6" possibility since the two oldest would be twins. therefore, the daughters ages must be "3 3 8".


Problem: two trains enter a tunnel 200 miles long (yeah, its a big tunnel) travelling at 100 mph at the same time from opposite directions. as soon as they enter the tunnel a supersonic bee flying at 1000 mph starts from one train and heads toward the other one. as soon as it reaches the other one it turns around and heads back toward the first, going back and forth between the trains until the trains collide in a fiery explosion in the middle of the tunnel (the bee survives). how far did the bee travel?

Solution: this puzzle falls pretty high on my aha scale. my first inclination when i heard it was to think "ok, so i just need to sum up the distances that the bee travels..." but then you quickly realize that its a difficult (not impossible) summation which the interviewer could hardly expect you to answer (unless i guess if you are looking for a job as a quant). "there must be a trick" you say. eh, sort of i guess, enough to say that this question is a stupid interview question.
the tunnel is 200 miles long. the trains meet in the middle travelling at 100 mph, so it takes them an hour to reach the middle. the bee is travelling 1000 mph for an hour (since its flying the whole time the trains are racing toward one another) - so basically the bee goes 1000 miles.
there is no process to explain, so this question can't possibly teach you anything about the person. they either know it or they don't and if they already knew it before you asked, you're not going to be able to tell when they give you the answer. so don't ask this question. and if someone asks you this question, just tell them you've already heard it before.

Red marbles, blue marbles

You have two jars, 50 red marbles, 50 blue marbles. you need to place all the marbles into the jars such that when you blindly pick one marble out of one jar, you maximize the chances that it will be red. (when picking, you'll first randomly pick a jar, and then randomly pick a marble out of that jar) you can arrange the marbles however you like, but each marble must be in a jar.  

Chance! chance is easy if you know how to do the formula. we know that we have two choices to make. first we'll pick a jar, and each jar will have a 1/2 chance of being picked. then we'll pick a marble, and depending how we stack the marbles, we'll have a (# of red marbles in jar)/(# of total marbles in jar) chance of getting a red one.

for example, say we put all the red marbles into jar A and all the blue ones into jar B. then our chances for picking a red one are:

1/2 chance we pick jar A * 50/50 chance we pick a red marble
1/2 chance we pick jar B * 0/50 chance we pick a red marble

do the math and you get 1/2 chance for a red marble from jar A and a 0/2 chance for a red marble from jar B. add 'em up and you get the result = 1/2 chance for picking a red marble.

Think about it for awhile and see if you can figure out the right combination. we had a 50/50 (guaranteed) chance in picking a red marble from jar A, but we didn't have to have 50 red marbles in there to guarantee those fantastic odds, did we? we could've just left 1 red marble in there and the odds are still 1/1. then we can take all those other marbles and throw them in jar B to help the odds out there.

let's look at those chances:
1/2 we pick jar A * 1/1 we pick a red marble
1/2 we pick jar B * 49/99 we pick a red marble
do the math and add them up to get 1/2 + 49/198 = 148/198, which is almost 3/4. 

We can prove these are the best odds in a somewhat non-formal way as follows. Our goal is to maximize the odds of picking a red marble. therefore we can subdivide this goal into maximizing the odds of picking a red marble in jar A and maximizing the odds of picking a red marble in jar B. if we do that, then we will have achieved our goal. it is true that by placing more red marbles into a jar we will increase the chances of picking a red marble. it is also true that by reducing the number of blue marbles in a jar we will increase the odds also. we've maximized the odds in jar A since 1/1 is the maximum odds by reducing the number of blue marbles to 0 (the minimum). we've also maximized the number of red marbles in jar B. if we added any more red marbles to jar B we would have to take them out of jar A which reduce the odds there to 0 (very bad). if we took any more blue ones out of jar B we would have to put them in jar A which reduce the odds there by 50% (very bad).

100 doors in a row

Problem: you have 100 doors in a row that are all initially closed. you make 100 passes by the doors starting with the first door every time. the first time through you visit every door and toggle the door (if the door is closed, you open it, if its open, you close it). the second time you only visit every 2nd door (door #2, #4, #6). the third time, every 3rd door (door #3, #6, #9), etc, until you only visit the 100th door.
question: what state are the doors in after the last pass? which are open which are closed?

You can figure out that for any given door, say door #42, you will visit it for every divisor it has. so 42 has 1 & 42, 2 & 21, 3 & 14, 6 & 7. so on pass 1 i will open the door, pass 2 i will close it, pass 3 open, pass 6 close, pass 7 open, pass 14 close, pass 21 open, pass 42 close. for every pair of divisors the door will just end up back in its initial state. so you might think that every door will end up closed? well what about door #9. 9 has the divisors 1 & 9, 3 & 3. but 3 is repeated because 9 is a perfect square, so you will only visit door #9, on pass 1, 3, and 9... leaving it open at the end. only perfect square doors will be open at the end.

Reverse a string - word by word

Problem: Reverse "the house is blue", the answer should be "blue is house the". the words are reversed, but the letters are still in order (within the word).


The solution can be attained by first reversing the string normally, and then just reversing each word.
initial: the house is blue
reverse: eulb si esuoh eht

Now reverse the word at its place
initial: the house is blue
reverse: eulb si esuoh eht
wanted : blue is house the

Thursday, September 17, 2009

17 September Solutions

1) b
2) c
3) b
4) a
5) d
6) d
Number of ordered pairs =  1;
because D=5, G=1
Step 1.

a + b + c + d = d + e + f + g = g + h + i = 17

Means, ( a + b + c + d )+ (d +e + f + g )+ (g +h + i ) = 17 +17+17 = 17 x 3 = 51

a + b + c + d + e + f + g + h + i +( d + g ) = 51

Step 2.

But 'a' to ' i ' takes values only from 1 to 9

So a + b + c + d + e + f + g + h + i = sum of the numbers from 1 to 9 = 45

Step 3.

From step 1 and step 2

d + g = 51 - 45 = 6

possible values of d & g are (1, 5), ( 5,1 ), (2,4) & (4, 2 )

( 2, 4 ) & ( 4 , 2 ) are not possible as "a = 4 "

We have to try with other values (1, 5 ) & ( 5 , 1 )

Step 4.
Case1:  When d = 1 and g = 5

1. a + b + c + d = 4 + b +c + 1 = 17

b + c = 12 ; only possible values of b & c are ( 9, 3 ) or ( 3, 9 )

2. d + e + f + g = 1 + e + f + 5 = 17

e + f = 17 - 6 = 11

possible combinations for 11 are ( 2,9 ) ; ( 3,8 ) ; (4,7 ) & ( 5,6 )

Out of the above four combinations nothing is possible beacuse

b & c takes values 3 & 9 g = 5 (assumed) and a = 4 (given).

So, d = 1 & g = 5 is not the solution.

Case 2. When d = 5 and g = 1

1. a + b + c + d = 4 + b + c + 5 = 17

b + c = 17 - 9 = 8

only possible combination is 2 & 6

a + b + c + d = 4 + ( 2 + 6 ) + 5 = 17

2. d + e + f + g = 5 + e + f + 1 = 17

e + f = 17 - 6 = 11

The only possible value is 3 & 8

d + e + f + g = 5 + ( 3 + 8 ) + 1 = 17

g + h + i = 1 + h + i = 17

h + i = 17 - 1 = 16

The only possible value for h & i are 7 & 9

g + ( h+ i ) = 1 + ( 7 + 9 ) + 17

So the values of d = 5 & g = 1
2) Let us write number in base of 3.
hence T50= (110010)3=327
(10)3 >= 10 in base 3;(10)3= (3+0)10 ie 3 in base 10
now (10)2=2,(11)2=3,(100)2=4 are the respective term numbers
so the 50th term would be (110010)3 as (110010)2=50

3)g(h(g(x)))=2g(x)^2 + 3g(x)
to calculate g(-4) we have to find out x such that h(g(x))=-4
i.e. x^2 + 4x=0 i.e. x=-4
hence we get g(-4)= 2g(-4)^2+ 3g(-4)
hence g(-4)=-1 
as the problem says ‘includes all numbers that are a sum of one or more distinct powers of 3′ so

4) 2x-1=ax^3 + bxy^2 – 1; 2y-1= ayx^2 + by^3 – 1
(2x-1)(2y-1)=(ax^3 + byx^2 – 1)(ayx^2 + by^3 – 1)
after multiplying ,rearranging the terms and using the other conditions given in the problem we can easily get the ans as 4

5)If k1 is the first then k2 will be the (n+2)th toffee k3 will be (2n+3)th toffee. let us assume that in one complete circle there are k consecutive toffees, as there should be no overlap hence the (k+1)toffee shouldnot overlap onto the 1st toffee.
as there are 30 toffees each toffee will be placed at 12degrees
so (k+1)(n+1)12 shouldnt be equal to 360
ie (k+1)(n+1) =! 30
out of the options only for n=12 we cannot have any value of k satisfying (k+1)(n+1)=30
hence there should be 12 toffees in between!!!

Saturday, September 12, 2009

Create a copy of a tree

Node *copy(mynode *root)
Node *temp;


temp = (mynode *) malloc(sizeof(mynode));
temp->value = root->value;

temp->left = copy(root->left);
temp->right = copy(root->right);