Daughters’ 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

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”.

(caveat: an astute reader pointed out that it is possible for two siblings to have the same age but not be twins, for instance one is born in january, and the next is conceived right away and delivered in october. next october both siblings will be one year old. if a candidate points this out, extra credit points to him/her.)

this question is pretty neat, although there is certainly a bit of an aha factor to it. the clues are given in such a way that you think you are missing information (the building number), but whats important isn’t the building number, but the fact that the first man thought that it was enough information, but actually wasn’t.

int atoi( char* pStr )

Problem: write the definition for this function without using any built-in functions. if pStr is null, return 0. if pStr contains non-numeric characters, either return 0 (ok) or return the number derived so far (better) (e.g. if its “123A”, then return 123). assume all numbers are positive. plus or minus signs can be considered non-numeric characters. in order to solve this program, the programmer must understand the difference between the integer 0 and the character ‘0’, and how converting ‘0’ to an int, will not result in 0. in other words, they have to understand what ascii is all about.


Solution

string manipulation functions are great programming questions. they test whether the user can understand and translate into code simple algorithms. string functions test pointer arithmetic which usually shows a knowledgeable programmer. also there are usually multiple solutions, some more efficient than others. plus people use them all the time so they should understand how they work. my favorite is atoi and i start the problem like this:

int atoi( char* pStr )

write the definition for this function without using any built-in functions. if pStr is null, return 0. if pStr contains non-numeric characters, either return 0 (ok) or return the number derived so far (better) (e.g. if its “123A”, then return 123). assume all numbers are positive. plus or minus signs can be considered non-numeric characters. in order to solve this program, the programmer must understand the difference between the integer 0 and the character ‘0’, and how converting ‘0’ to an int, will not result in 0. in other words, they have to understand what ascii is all about. if they are stuck solving this problem, just ask them first to write:

charToInt(char c)

if they can’t do that then they basically missed half the problem. any moderately talented programmer who has a CS degree knows how to convert a char to an int. (note i said convert, not cast. charToInt('9') should return 9.)

when they start to solve the problem you will notice that they must make a choice in how they will process the string - from left to right or right to left. i will discuss both methods and the difficulties encountered in each.

“right to left” - this method starts at the right hand letter of the string and converts that character to an int. it then stores this value after promoting it to its correct “tens” place.
int atoi( char* pStr )
{
  int iRetVal = 0;
  int iTens = 1;

  if ( pStr )
  {
    char* pCur = pStr;
    while (*pCur)
      pCur++;

    pCur--;

    while ( pCur >= pStr && *pCur <= '9' && *pCur >= '0' )
    {
      iRetVal += ((*pCur - '0') * iTens);
      pCur--;
      iTens *= 10;
    }
  }
  return iRetVal;
}

“left to right” - this method keeps adding the number and multiplying the result by ten before continuing to the next number. e.g. if you had “6234” and you processed from left to right you’d have 6, then if you kept reading you’d multiply your result by 10 (6*10) to add a zero for where the next number would go. 60, and then you’d slide the 2 into the zero place you just made. 62. do it again, 620, slide the next number in, 623.
int atoi( char* pStr )
{
  int iRetVal = 0;

  if ( pStr )
  {
    while ( *pStr && *pStr <= '9' && *pStr >= '0' )
    {
      iRetVal = (iRetVal * 10) + (*pStr - '0');
      pStr++;
    }
  }
  return iRetVal;
}

i think the “left to right” method is a little bit cleaner, or maybe its just cooler. but both are “correct”.

remember that debugging code on paper is somewhat hard. most programmers aren’t used to studying code that much when you can just hit F-7, compile and see if the compiler barfs or not. if you notice an error, just ask them to step through a sample string drawing out what is happening with all the variables and the pointers in every step. they should find their mistake then and fix it (no points deducted).

Bumblebee

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

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

Problem: 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.


Solution

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).

it wasn’t really a good proof, but QED anyway :-P

100 Doors in a Row - Solution

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?
Solution

For example, after the first pass every door is open. on the second pass you only visit the even doors (2,4,6,8…) so now the even doors are closed and the odd ones are opened. the third time through you will close door 3 (opened from the first pass), open door 6 (closed from the second pass), etc..

question: what state are the doors in after the last pass? which are open which are closed?

solution: 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 - Solution

Reverse a String
A typical programming interview question is “reverse a string, in place”. if you understand pointers, the solution is simple. even if you don’t, it can be accomplished using array indices. i usually ask candidates this question first, so they get the algorithm in their head. then i play dirty by asking them to reverse the string word by word, in place. for example if our string is “the house is blue”, the return value would be “blue is house the”. the words are reversed, but the letters are still in order (within the word).
Solution

Solving the initial problem of just reversing a string can either be a huge help or a frustrating hinderance. most likely the first attempt will be to solve it the same way, by swapping letters at the front of the string with letters at the back, and then adding some logic to keep the words in order. this attempt will lead to confusion pretty quickly.

for example, if we start by figuring out that “the” is 3 letters long and then try to put the “t” from “the” where the “l” from “blue” is, we encounter a problem. where do we put the “l” from “blue”? hmm… well we could have also figured out how long “blue” was and that would tell us where to put the “l” at… but the “e” from “blue” needs to go into the space after “the”. argh. its getting quite confusing. in fact, i would be delighted to even see a solution to this problem using this attack method. i don’t think its impossible, but i think it is so complex that it’s not worth pursuing.

here’s a hint. remember before when we just reversed “the house is blue”? what happened?
initial: the house is blue
reverse: eulb si esuoh eht

look at the result for a minute. notice anything? if you still don’t see it, try this.
initial: the house is blue
reverse: eulb si esuoh eht
wanted : blue is house the

the solution can be attained by first reversing the string normally, and then just reversing each word.

The Circular Lake Monster solution

For #1, how about row in a circle a bit smaller 1/4r in size. Since he won't be able to keep up with you, when he is on the opposite shore you can make a brake for it. You have r*3/4 to travel, but 4*3/4 is less then pi, so he won't be able to catch you in time




part 2: Assume x is the monster's speed. Then to get the circle trick to work, you row a circle a little less than 1/x of the radius, leaving you 1 - 1/x to row when he is opposite of you. If the monster can travel pi times the radius faster than you can travel the radius, you're hosed. In the time you travel 1 - 1/x, he'll travel x times that. Set that equal to pi, and you x * (1 - 1/x) = pi, which solves to x = pi + 1.

pi + 1 would be my guess for the speed that impossible to escape from, but I could be making an easy mistake.