Brain Teaser 5+ Important Questions
1} 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).
2} 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.</p>
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.
even if the candidate doesn’t know the solution, they could come up with some interesting thoughts. if they just stare at you and shrug “i dunno” then thank them for their time and don’t give them a fogcreek pen.
Also Read more: Interview Question
3} Palindromes
Problem: this year on October 2, 2001, the date in MMDDYYYY format will be a palindrome (same forwards as backwards).
10/02/2001
when was the last date that this occurred on? (see if you can do it in your head!)
Solution
solution: 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 what's 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.
palindromes also offer another great string question.
write a function that tests for palindromes
bool isPalindrome( char* pStr )
if you start a pointer at the beginning and the end of the string and keep comparing characters while moving the pointers closer together, you can test if the string is the same forwards and backward. notice that the pointers only have to travel to the middle, not all the way to the other end (to reduce redundancy).
bool isPalindrome( char* pStr )
{
if ( pStr == NULL )
return false;
char* pEnd = pStr;
while ( *pEnd != ‘’ )
pEnd++;
pEnd — ;
while(pEnd > pStr)
{
if ( *pEnd != *pStr )
return false;
pEnd — ;
pStr++;
}
return true;
}
4} 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?)
Solution
as a programmer, my first answer to this problem would make a bit vector of size n, and every time you see the number, set its corresponding 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. it's good because it makes sense if you draw it for someone, whether they are a programmer, mathematician, or just your grandpa. it's 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.
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² + 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² + b²
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.
5} Pirates
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).
Solution
(to be clear on what 50% means, 3 pirates must vote for the proposal when there are 5 for it to pass. 2 if there are 4. 2 if there are 3. etc… )
solution: 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 — — -
1.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).
6} Fog Creek Programmers
100 fogcreek programmers are lined up in a row by an assassin. the assassin puts red and blue hats on them. they can’t see their own hats, but they can see the hats of the people in front of them. the assassin starts in the back and says “what color is your hat?” the fogcreek programmer can only answer “red” or “blue.” the programmer is killed if he gives the wrong answer; then the assassin moves on to the next programmer. the programmers in front get to hear the answers of the programmers behind them, but not whether they live or die. they can consult and agree on a strategy before being lined up, but after being lined up and having the hats put on, they can’t communicate in any way other than those already specified. what strategy should they choose to maximize the number of programmers who are guaranteed to be saved?
Solution
this is a very difficult problem to solve during an interview (especially if you’ve already taxed the candidate’s brain). look for obvious solutions first, and the reasoning behind them and then try to lead them to the ultimate solution.
a logical answer could be all the programmers would just say “red” and that way about half of them would survive on average, assuming the hats were distributed randomly.
this is a good start and should naturally lead to having every other programmer say the color of the hat in front of them. the first programmer would say the color of the hat in front of him, then the next programmer would just say that color that was just said. so we can guarantee that half survive — the even numbered programmers (since the person behind them told them the answer). and potentially if the hats were distributed randomly some of the programmers would get lucky and the hat in front of them would be the same color as their own. so this strategy should save more than half, and on average 75% of them would live.
at this point, if the solution is not clear, the candidate may give answers like, “they could agree that if they said their hat color in a soft voice, it means the hat in front of them is the same color, and if they say it in a loud voice, it means the hat in front is a different color”. this is definitely good and on the correct track. another option is they could say “reeeeeeeeeeed” for x number of seconds, where x represented the distribution of hats where a hat was a bit in a binary number, (red = 1, blue = 0). another interesting answer. there are many others like these that “bend” the rules and come to a solution.
but the real solution acknowledges that the programmers can only say “red” or “blue” and cannot alter their voice in such a convincing way as to signal any information other than the word they said. a good way to get this point across, is simply to change the problem slightly by saying “the assassin gets to hear their plan before she puts the hats on, and so will try to thwart the plan however she can.”
so if they decide to all say “red”, she’ll put blue hats on all of them. if they decide to all say the color of the hat in front of them, she’ll alternate the hats on every head, guaranteeing half will die. even with the assassin hearing their plan, there is still a way to save almost everyone.
we know that the first person is never going to have any information about the color of their hat, so they cannot be guaranteed to survive. but, i’ll give you a hint to the solution: i can save every other person for sure.
solution: they agree that if the number of red hats that the back person can see is even, that programmer will say “red”. if they add up to an odd number, they will say “blue”. this way number 99 can look ahead and count the red hats. if they add up to an even number and number 100 said “red”, then 99 must be wearing a blue hat. if they add up to an even number and number 100 said “blue”, signalling an odd number of red hats, number 99 must also be wearing a red hat. number 98 knows that 99 said the correct hat, and so uses that information along with the 97 hats in front to figure out what color hat is on 98’s head.
sample:
100 99 98 97 96 95 94 … facing ->
R B B R B R B … -> 45 R and 48 B
this shows #100 wearing a red hat, 99 a blue, 98 a blue, 97 a red, 96 a blue, 95 a red, 94 a blue and 45 red hats — 48 blue hats on the people in front of them.
100 counts up the red hats: 47 total. so 100 says “blue”. the assassin kills 100. 99 counts up the red hats in front: 47. 100 said blue, so 100 saw an odd number. 99 sees an odd number, so 99 says “blue” and lives. 98 had counted 47 red hats, and 99 didn’t say “red” so thats still the total. 98 says “blue”. 97 counts up and finds 46 red hats. 99 and 98 didn’t say “red”, so his count is missing a red hat (its on his head, he realizes). he says “red”. 96 heard the “red” and now knows that there are an even number of “red” hats in front of 95. 96 sees 46, so he knows he has a “blue” hat. etc…
even if the assassin knows the plan, she can’t thwart it. she hears the plan, but she still has to put the hats on their heads. the plan doesn’t rely on any ordering of the hats, so the worst the assassin can do is to make sure #100 gets killed and thats the worst damage she can do.
