PuzzleGuzzle: Puzzles

Showing posts with label Puzzles. Show all posts

Tuesday, October 19, 2010

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

100 Programmers

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

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, mathemetician, 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.

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

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

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 backwards. 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 != '\0' )

pEnd++;

pEnd--;

while(pEnd > pStr)

{

if ( *pEnd != *pStr )

return false;

pEnd--;

pStr++;

}

return true;

}

thanks to tom for sending me this one! congrats on the wedding…

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.

Wednesday, January 6, 2010

Array of 0 and 1, put 0's at even position and 1's at odd position

you are given an array of integers containing only 0s and 1s. you have to place all the 0s in even position and 1s in odd position and if suppose no if 0s exceed no. of 1s or vice versa then keep them untouched. Do that in ONE PASS and WITHOUT taking EXTRA MEMORY.

input array:
{0 1 1 0 1 0 1 0 1 1 1 0 0 1 0 1 1 }
output array:
{0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1 }

Thursday, May 15, 2008

This is similar to an implementation of partition method of quick sort.

oddInd==0;
evenInd=1;

while(true)
{
while(oddInd
if(oddInd>=strLen) break;
while(evenInd
if(evenInd>=strLen) break;
swap(str[evenInd], str[oddInd]);
}

Well, one more challenging version of this problem is to consider an array containing 0s,1s and 2s and do the same thing. This question was asked in one microsoft internship interview.

jigsaw

Thursday, May 15, 2008

OOPS!!! There was a big mistake in the above code.
This is similar to an implementation of partition method of quick sort.

oddInd==0;
evenInd=1;

while(true)
{
while(oddInd if(oddInd>=strLen) break;
while(evenInd if(evenInd>=strLen) break;
swap(str[evenInd], str[oddInd]);
}

Well, one more challenging version of this problem is to consider an array containing 0s,1s and 2s and do the same thing. This question was asked in one microsoft internship interview.

jigsaw

Thursday, May 15, 2008

Perish the thought that anyone should use extra memory!

BTW, the indexes into the array are extra memory.

Too many of these questions are isomorphic with:
"Oh, so you can type in your code? How about if we tie one arm behind your back? YANK! Still typing? How about if we keep hitting you with this baseball bat? Whack, whack, whack! Still at it, huh? Well, at least we got him down to 2 WPM."

Sincerely,

Gene Wirchenko

Gene Wirchenko

Thursday, May 15, 2008

:) That's funny. BTW when he said extra memory, he meant variable amt of memory i guess.

jigsaw

Friday, May 16, 2008

That seems to be what they mean when they say no extra memory. Heck making a function call allocates a frame on the stack so does that mean no function calls either?

I always took it to mean no building a data structure. Which can be a valid restriction if data is going to be changing often(high rebuild costs) or you have a truly large dataset. It can be hard to get a std::vector to hit 100mb if you already have a number of other 100mb chunks floating around.

soup
Friday, May 16, 2008

soup,

The usual complexity-theoretic definition of "no extra memory" is that the program can use a constant number of registers just large enough to index the input.

d
Friday, May 16, 2008

I tried JigSaw's solution in to java(http://pastebin.com/f41fe39d1). I might have mis-understood the code but the resulting array is
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1

ved

Monday, May 26, 2008

I think there is a problem in jigsaw's solution.His solution says:
oddInd==0;
evenInd=1;

while(true)
{
while(oddInd if(oddInd>=strLen) break;
while(evenInd if(evenInd>=strLen) break;
swap(str[evenInd], str[oddInd]);
}
First of all.it will produce an an arrangement of 10101010 type of string.But that can be solved by using str[oddInd]==0 and str[evenInd]==1. But more serious problem is if the array is such that it has even no. of elements and each even positions are correctly filled with 0s and there are some extra 0s in odd positions because in that case the first inner while loop executes and then the outer while loop terminates by break statement.

sagsriv

Friday, June 13, 2008

@sagsriv

i guess the depend on understanding of "and if suppose no if 0s exceed no. of 1s or vice versa then keep them untouched"

e.g., input array:
{0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 }
output array should be:
a)
{0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 }
since in the question, it states
"if 0s exceed no. of 1s or vice versa then keep them untouched"

or

b)
{0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 }
to move "0s" to the end.which should can be also done in one pass.

which looks better..lol

ray

Monday, July 07, 2008

Add all the numbers in the array to get the sum. The sum equals to number of ONEs in the array? Then prepare the sequence of 0,1,0,1 ... based on the no. of ONEs using a simple for loop.

Monday, December 7, 2009

What is the least number of links you can cut in a chain of 21 links to be able to give someone all possible number of links up to 21

Assume that a chain of length k for every 1<=k<=length(chain)
  must be doable with the open links. Then you can reach

  links  length    dissection

    0      1         1
    1      5         1-(1)-3
    2     13         1-(1)-3-(1)-7
    3     29         1-(1)-3-(1)-7-(1)-15
    4     61         1-(1)-3-(1)-7-(1)-15-(1)-31
    n   2^(n+2)-3

we have taken links as 2^k-1...and hence get such answer.

The question can be modified a bit...

You are having 31kg of rice. You are provided with a 1kg stone for weighing. In how many weights the 31kg of rice can be weighed.

Now we can't have empty selection...so for

n we have 2^(n+1)-3...

so we have 2^(n+1)-3 = 31

n+1 = 6 (because 2^5 < 35 < 2^6 )

n=5

Brain teasers and answers

By moving one of the following digits, make the equation correct. 62 - 63 = 1

2⁶ - 63 = 1 (In other words, 2x2x2x2x2x2, which equals 64)

You have a fox, a chicken and a sack of grain. You must cross a river with only one of them at a time. If you leave the fox with the chicken he will eat it; if you leave the chicken with the grain he will eat it. How can you get all three across safely?

Take the chicken over first. Go back and bring the grain next, but instead of leaving the chicken with the grain, come back with the chicken. Leave the chicken on the first side and take the fox with you. Leave it on the other side with the grain. Finally, go back over and get the chicken and bring it over.

You have 12 black socks and 12 white socks mixed up in a drawer. It's early in the morning and you don't have any light to see the colors. How many socks must you pull out (blindly) to be sure of getting a matching pair?

3 socks. If the first sock is black, the second one could be black, in which case you have a matching pair. If the second sock is white, the third sock will be either black and match the first sock, or white and match the second sock.

What is special about the following sequence of numbers?
8 5 4 9 1 7 6 10 3 2 0

The numbers are in alphabetical order.
(eight, five, four, nine, one, seven, six, ten, three, two, zero)

Three travelers register at a hotel and are told that their rooms will cost $10 each so they pay $30. Later the clerk realizes that he made a mistake and should have only charged them $25. He gives a bellboy $5 to return to them but the bellboy is dishonest and gives them each only $1, keeping $2 for himself. So the men actually spent $27 and the bellboy kept $2 - what happened to the other dollar of the original $30?

Nothing. The 3 travelers paid a total of $27, making $25 for the hotel and $2 for the clerk. There is no missing $1.

You are the bus driver. At your first stop, you pick up 29 people. On your second stop, 18 of those 29 people get off, and at the same time 10 new passengers arrive. At your next stop, 3 of those 10 passengers get off, and 13 new passengers come on. On your fourth stop 4 of the remaining 10 passengers get off, 6 of those new 13 passengers get off as well, then 17 new passengers get on. What is the color of the bus driver's eyes?

The eye color of the reader of this problem. The first sentence is the key: "You are the bus driver"

A rooster lays an egg at the very top of a slanted roof. Which side is the egg going to roll off on?

Neither, roosters don't lay eggs.

U2 has a concert that starts in 17 minutes and they must all cross a bridge to get there. All four men begin on the same side of the bridge. You must help them across to the other side. It is night. There is one flashlight. A maximum of two people can cross at one time. Any party who crosses, either 1 or 2 people, must have the flashlight with them.

The flashlight must be walked back and forth. It cannot be thrown and other tricks like that are not needed to solve the problem. The solution is simply a matter of allocating resources in a certain order. Each band member walks at a different speed. A pair must walk together at the rate of the slower man's pace:

Bono: 1 minute to cross
Edge: 2 minutes to cross
Adam: 5 minutes to cross
Larry: 10 minutes to cross

For example: if Bono and Larry walk across first, 10 minutes have elapsed when they get to the other side of the bridge. If Larry then returns with the flashlight, a total of 20 minutes have passed and you have failed the mission.

Let’s name the as A,B,C & D and let’s assume that they take 1,2,5 and 10 minutes respectively. Here is how they should cross the bridge.
ABCD |—————————–-------|
CD |——-AB(2min)————->| ( AB comes and A returns)
ACD |<——-A-(1min)————--|B
A || ——-CD(10min)———>| BCD (CD come and B returns)
A || |<——-B-(2min)————--|
AB |—————————–-------|ABCD (AB come)
If you count all the trips ie. 2+1+10+2+2, it will be 17 minutes

Why is it very common to have a 9 minute snooze interval on alarm clocks, why not 10 instead?

By setting the snooze time to 9 minutes, the alarm clock only needs to watch the last digit of the time. So, if you hit snooze at 6.45, the alarm goes off again when the last digit equals 4. They couldn't make it 10 minutes, otherwise the alarm would go off right away, or it would take more circuitry.

A bookworm eats from the first page of an encyclopedia to the last page. The bookworm eats in a straight line. The encyclopedia consists of ten 1000-page volumes and is sitting on a bookshelf in the usual order. Not counting covers, title pages, etc., how many pages does the bookworm eat through?
On a book shelf the first page of the first volume is on the "inside"
```
__                             __
      B|  |                           |  |F
      A|1 |...........................|10|R
      C|  |                           |  |O
      K|  |                           |  |N
       |  |                           |  |T
       ---------------------------------- 
 
```
so the bookworm eats only through the cover of the first volume, then 8 times 1000 pages of Volumes 2 - 9, then through the cover to the 1st page of Vol 10. He eats 8,000 pages.

An Arab sheikh tells his two sons to race their camels to a distant city to see who will inherit his fortune. The one whose camel is slower will win. The brothers, after wandering aimlessly for days, ask a wise man for advise. After hearing the advice they jump on the camels and race as fast as they can to the city. What does the wise man say?

Solution »

An 18-wheeler is crossing a 4 kilometer bridge that can only support 10,000 kilograms and that's exactly how much the rig weighs. Halfway across the bridge a 30 gram sparrow lands on the cab, but the bridge doesn't collapse. Why not?

Solution »

A completely black dog was strolling down Main Street during a total blackout affecting the entire town. Not a single streetlight had been on for hours. Just as the dog was crossing the middle line a Buick Skylark with 2 broken headlights speedily approaches his position, but manages to swerve out of the way just in time. How could the driver have possibly seen the dog to swerve in time?

Solution »

In a small cabin in the woods, two men lay dead. The cabin itself is not burned, but the forest all around is burned to cinders. How did the men die?

Solution »

Ida puts her coffee into the microwave, as she does every morning, for exactly 2 minutes. When the microwave goes off, she opens the door, but then closes the door again and sets the microwave for 2 more seconds. What good would 2 more seconds be?

Solution »

Beulah died in the Appalachians while Craig died at sea. Everyone was much happier with Craig's death. Why?

Solution »

You are a cook in a remote area with no clocks or other way of keeping time other than a four minute sandglass timer and a seven minute sandglass timer. (The kind you turn over - hourglass shaped) You do have a stove, however, with water in a pot already boiling. Somebody asks you for a nine-minute egg, and you know this person is a perfectionist and will be able to tell if you undercook or overcook the eggs by even a few seconds. What is the least amount of time it will take to prepare the egg? And how will you prepare it so that it is neither undercooked or overcooked?

Solution »

I am the owner of a pet store. If I put in one canary per cage, I have one bird too many. If I put in two canaries per cage, I have one cage too many. How many cages and canaries do I have?

Solution »

Here is a series of numbers. What is the next number in the sequence?
1
11
21
1211
111221
312211
13112221

Solution »

My daughter has many sisters. She has as many sisters as she has brothers. Each of her brothers has twice as many sisters as brothers. How many sons and daughters do I have?

Solution »

What seven-letter word has hundreds of letters in it?

Solution »

If you had a ton of feathers and a ton of stones which would be heavier?

Solution »

Tom's mother has three children. One is named April, one is named May. What is the third one named?

Solution »

Two women apply for a job. They are identical. They have the same mother, father and birthday. The interviewer asks, "Are you twins?" to which they honestly reply, "No".

How is this possible?

Solution »

You are standing outside a closed door. On the other side of the door is a room that has three light bulbs in it. The room is completely sealed off from the outside. It has no windows and nothing can get in or out except through the door. On the outside of the room there are three light switches that control each of the respective light bulbs on the other side of the door.

Your assignment is to determine which light switch controls which light bulb. You are allowed to enter the room only once, and once you come out, you must be able to state with 100% certainty which light switch controls which light bulb.

Solution »

If a bottle and a cork cost a dollar and a nickel, and the bottle costs a dollar more than the cork, how much does the cork cost?

Solution »

A boat has a ladder that has six rungs. Each rung is one foot apart. The bottom rung is one foot from the water. The tide rises at 12 inches every 15 minutes. High tide peaks in one hour.

When the tide is at its highest, how many rungs are under water?

Solution »

You have a lighter and two fuses that take exactly one hour to burn, but they don't burn at a steady rate. For example, one fuse could take 59 minutes to burn the first inch and then burn the rest of the fuse in the last minute.

How would you use these two fuses to measure 45 minutes?

Solution »

You have two buckets - one holds exactly 5 gallons and the other 3 gallons. How can you measure 4 gallons of water into the 5 gallon bucket?

(Assume you have an unlimited supply of water and that there are no measurement markings of any kind on the buckets.)

Solution »

A princess is as old as the prince will be when the princess is twice the age that the prince was when the princess's age was half the sum of their present ages.

What are their ages?

Solution »

During WWII, there was a bridge connecting Germany and Switzerland, and on the German side, there was a sentry tower with a guard in it. He would come out every three minutes to check on the bridge, and he had orders to turn back anyone who tried to get into Germany, and shoot anyone trying to escape without a pass. There was a woman who desperately needed to get into Switzerland, and she knew she didn't have time to get a pass. It would take her at least six minutes to cross the bridge, but she managed to do it. How?

Solution »

A man can make perfect counterfeit bills. They look exactly like real ones, they're made of exactly the same materials, made the same way, everything. So perfect, one could pretty much call them real bills. One day he successfully makes a perfect copy of another bill. However, he gets caught when he tries to use the copy. How is this possible?

Solution »

A prisoner is told "If you tell a lie we will hang you; if you tell the truth we will shoot you." What can he say to save himself?

Solution »

How many people can read hex if only you and dead people can read hex?

Solution »

A man is traveling with a fox and two chickens, if he leaves the fox alone with the chickens the fox will eat the chickens. He comes to a river and needs to cross it, he finds a small boat that can carry only him and one animal, how does he get himself, the fox and two chickens across the river safely?

Solution »

A man is looking at a picture of a man on the wall and states: Brothers and sisters I have none, but this man's father is my father's son. Who is the man in the picture in relation to the man looking at the picture?

Solution »

A man and his son had a terrible car accident and were rushed to the hospital. The man died on the way, but the son was still alive and a surgeon was called in to operate. However, the surgeon saw the young boy and said, "I can't operate on this boy. He's my son."
How is this possible?

Solution »

A wise king devised a contest to see who would receive the Princess' hand in marriage. The Princess was put in a 50x50 foot carpeted room. Each of her four suitors were put in one corner of the room with a small box to stand on. The first one to touch the Princess hand would be the winner and become the new King.
The rules of the test were that the contestants could not walk over the carpet, cross the plane of the carpet, or hang from anything; nor could they use anything but their body and wits (i.e. no magic or telepathy, nor any items such as ladders, block and tackles etc). One suitor figured out a way and married the Princess and became the new King. What did he do?

Solution »

Two guards were on duty outside a barracks. One faced up the road to watch for anyone approaching from the North. The other looked down the road to see if anyone approached from the South. Suddenly one of them said to the other, "Why are you smiling?"

How did he know his companion was smiling?

Solution »

You're riding a horse. To the right of you is a cliff and in front of you is an elephant going the same pace as you and you can't overtake it. To the left of you is a hippo running at the same speed and behind you is a lion chasing you. How do you get to safety?

Solution »

You have 50 quarters on the table in front of you. You are blindfolded and cannot discern whether a coin is heads up or tails up by feeling it. You are told that x coins are heads up, where 0 < x < 50. You are asked to separate the coins into two piles in such a way that the number of heads up coins in both piles is the same at the end. You may flip any coin over as many times as you want. How will you do it?

Solution »

You have four chains. Each chain has three links in it. Although it is difficult to cut the links, you wish to make a single loop with all 12 links. What is the fewest number of cuts you must make to accomplish this task?

Solution »

Walking down the street one day, I met a woman strolling with her daughter. "What a lovely child," I remarked. "In fact, I have two children," she replied. What is the probability that both of her children are girls?

Solution »

Three closed boxes have either white marbles, black marbles or both, and they are labeled white, black and both. However, you're told that each of the labels are wrong. You may reach into one of the boxes and pull out only one marble. Which box should you remove a marble from to determine the contents of all three boxes?

Solution »

A glass of water with a single ice cube sits on a table. When the ice has completely melted, will the level of the water have increased, decreased or remain unchanged?

Solution »

You are given eight coins and told that one of them is counterfeit. The counterfeit one is slightly heavier than the other seven. Otherwise, the coins look identical. Using a simple balance scale, can you determine which coin is counterfeit using the scale only once?

Solution »

You are given eight coins and told that one of them is counterfeit. The counterfeit one is slightly heavier than the other seven. Otherwise, the coins look identical. Using a simple balance scale, can you determine which coin is counterfeit using the scale only twice?

Solution »

I was visiting a friend one evening and remembered that he had three daughters. I asked him how old they were. "The product of their ages is 72," he answered. Quizzically, I asked, "Is there anything else you can tell me?" "Yes," he replied, "the sum of their ages is equal to the number of my house." I stepped outside to see what the house number was. Upon returning inside, I said to my host, "I'm sorry, but I still can't figure out their ages." He responded apologetically, "I'm sorry, I forgot to mention that my oldest daughter likes strawberry shortcake." With this information, I was able to determine all of their ages. How old is each daughter? You have enough information to solve the puzzle.

Solution »

You're in a room with two doors. There's a guard at each door. One door is the exit, but behind the other door is something that will kill you. You're told that one guard always tells the truth and the other guard always lies. You don't know which guard is which. You are allowed to ask one question to either of the guards to determine which door is the exit. What question should you ask?

Solution »

How far can a dog run into the forest?

Solution »

If eggs are 12¢ a dozen, how much would it cost for 100 eggs?

Solution »

You are a prisoner sentenced to death. The Emperor offers you a chance to live by playing a simple game. He gives you 50 black marbles, 50 white marbles and 2 empty bowls. He then says, "Divide these 100 marbles into these 2 bowls. You can divide them any way you like as long as you use all the marbles. Then I will blindfold you and mix the bowls and marbles up. You can then choose one bowl and remove one marble. If the marble is white, you live, but if the marble is black...you die.

How do you divide the marbles up so that you have the greatest probability of choosing a white marble?

Solution »

What is the next number in this series?
1, 2, 6, 42, 1806, ?

Solution »

What do the following numerals specify?
11111121113122223222

Solution »

You must buy 100 chickens for exactly $100. You must buy at least one chicken from each store. The first store charges 5 cents/chicken, the second charges $1/chicken and the third charges $5/chicken. How many chickens should you buy from each store?

Solution »

What is special about the following number sequence?
8, 5, 4, 9, 1, 7, 6, 10, 3, 2, 0

Solution »

Adding 2 character puzzles

ABC + DEF + GHI = JJJ

If different letters represent different digits, and there are no leading zeros, what does J represent?

Answer The value of J must be 9.
Since there are no leading zeros, J must be 7, 8, or 9. (JJJ = ABC + DEF + GHI = 14? + 25? + 36? = 7??) Now, the remainder left after dividing any number by 9 is the same as the remainder left after dividing the sum of the digits of that number by 9. Also, note that 0 + 1 + ... + 9 has a remainder of 0 after dividing by 9 and JJJ has a remainder of 0, 3, or 6. The number 9 is the only number from 7, 8 and 9 that leaves a remainder of 0, 3, or 6 if you remove it from the sum 0 + 1 + ... + 9. Hence, it follows that J must be 9.