שאלות תכנות - חלק ב

11.

Problem: four people are on this side of the bridge. The bridge will be destroyed by a bomb in 17 minutes. Everyone has to get across before that. Problem is that it's dark and so you can't cross the bridge without a flashlight, and they only have one flashlight. Plus the bridge is only big enough for two people to cross at once. the four people walk at different speeds: one fella is so fast it only takes him 1 minute to cross the bridge, another 2 minutes, a third 5 minutes, the last it takes 10 minutes to cross the bridge. When two people cross the bridge together (sharing the flashlight), they both walk at the slower person's pace. Can they all get across before the bridge blows up?

Solution: of course it's possible, otherwise it wouldn't be a very interesting question. The only trick is in realizing that you want to get the two slowest people across together, because otherwise you are wasting too much time. But then once you get them across, how do you not make one of them walk back with the flashlight? Well, you just have one of the fast people already there waiting to sprint the flashlight back across.

Another solution which is valid is to have A bring the flashlight back in step 2. It only changes the solution slightly. This is supposed to be a "classic" Microsoft interview question but it seems absurdly easy to be a good interview question (especially coupled with the fact that everyone has probably heard it already).

12.

This is a card trick without the trick. There is no sleight of hand, no tricks up my sleeve, no magic whatsoever. It's all done with logic, yet it will amaze most people.

Joel and I are working together as a team to do the trick. Babak will be the culprit.

I ask babak to pick 5 cards out of a deck. He can pick any five cards, he can shuffle the deck 7 times, it really doesn't matter. He honestly picks out 5 cards that i cannot see. He hands the five cards to me (Joel can't see any of this). i look at the cards and i pick 1 card out and give it back to babak. i then arrange the other four cards in a special way, and give those 4 cards all face down, and in a neat pile, to joel. Joel looks at the 4 cards i gave him, and says out loud which card babak is holding (suit and number).

I did not convey any information to joel other than the way i ordered the 4 cards, (all face down, aligned in line with one another) so how did i encode babak's card using that method?

hint 1: card trick without the trick hint 2: card trick without the trick

Solution: hint 1 talks about how there are guaranteed to be at least 2 cards with the same suit in a series of five cards. I use this to signal to joel the suit of the card. I have to make a decision though between which of the two cards to give back to babak. Which one do i pick?

hint 2 talks about how if i use one of the cards to signal the suit, that only leaves me with 3 cards. I can only arrange 3 cards in six permutations. How do i signal a number between 2 and 13 using only six permutations?

Simple really. Consider that the series of cards is a cycle.

2 3 4 5 6 7 8 9 10 J Q K A 2 3 4 5 6 7 8 9 10 J Q K A 2 ... etc

i take the two cards of the same suit (if there are more than two of the same suit, then i choose any two, it won't affect the solution) and i pass babak the one that is further to the right in the cycle. if i do it correctly, the one further to the right will be no more than 6 places away than the one to the left. (it just depends on how you think about the cycle).

For example. Say we had the 2 and the 9 of hearts. if you look at it as the 2 to the left and the 9 to the right, it is seven cards away. but if you look as the 9 to the left and the 2 to the right in the cycle, the 2 is only 6 cards away.

Then i just come up with a system of the permutations that signals how many places to the right to count to find the correct card

One such system could be: sort the 3 non-same suit cards first by number then by suit (diamonds, spades, hearts, clubs) to give a unique sort for every card. Label the cards as A, B, and C.

place the cards in the following order to signal how many places away babak's card is:

then put the suit card on top and give the pile to joel.

example: babak picks out the following five cards:

3C 7D 10S QH AD

the 7 of diamonds (7D) and the ace of diamonds (AD) are the two suit cards. i recognize that AD is going to be the left card and 7D the right (because the other way they are 7 spaces apart). i give babak back the 7D. i sort the other cards, 3C 10S QH. i have to signal 6 places to the right (7D - AD = 6). so i place them in C B A format: QH 10S 3C. i then place the AD on top and pass to joel.

joel pulls off the first card and sees that it is the AD. (he knows babak's card is a diamond). he looks at the next 3 cards and realizes their ordering is C B A. signalling 6, he counts 6 spots from the ace. (2 3 4 5 6 7). then he says "7 of diamonds" and the crowd is amazed.

another sneakier card trick (with the trick) works as follows.

babak picks one card out of the deck and shows it to me. he doesn't tell joel and i don't speak. after seeing the card, i sneakily use my one hand to signal both the number and suit of the card. i use my four fingers (not the thumb) as bits signalling a binary number. if they are extended it means 1, if i don't extend them it means 0. the pinky is the least significant. so to signal 7 i would extend all fingers except my index finger. the suit is signalled by four positions of the thumb (hidden, adjacent to the hand, slightly ajar, fully extended). i can use this method to tell joel the card without saying anything (and making any noticeable motions). with some practice it can really amaze people (at least it worked with my family).

13.

problem: a slightly different version of the original pirates problem (read that one first to get all the rules). 6 pirates, only one gold coin. as before, the pirates are super-smart, and they value, in this order: (i) their lives, (ii) getting money, (iii) seeing other pirates die. so if given the choice between two outcomes, in which they get the same amount of money, they'd choose the outcome where they get to see more of the other pirates die. how can pirate 6 save his skin?1 pirate case is obvious. 2 pirate case is obvious, pirate 2 keeps the coin.

3 pirate case: pirate 3 has to give the coin to pirate 1, because if he gives it pirate 2 pirate 2 will say "screw that i wanna see you die and i'm going to get the coin anyway." so in 3 pirate case, we have pirate 1 gets 1 coin, pirates 2 and 3 get 0.

4 pirate case: pirate 4 can't give the coin to pirate 1, because pirate 1 would rather see him die since he's going to get 1 coin anyway. But pirate 4 could give the coin to either pirate 2 or pirate 3.

5 pirate case: pirate 5 just dies, and it goes to the 4 pirate case. there is no way for him to convince two people to vote for him.

6 pirate case: pirate 6 can count on his own vote, plus pirate 5's vote, because 5 won't want to die. now who should he give the coin to? he could give it to pirate 1 or to pirate 4, since in the 4 pirate case they are guaranteed to get nothing. it's unclear whether he could give it to pirate 2 or 3. neither pirate 2 nor pirate 3 is guaranteed to get a coin in the 4 pirate case. so the question is, how do they value (i) definitely getting a coin from pirate 6 vs. (ii) definitely seeing pirates 6 and 5 die, with the chance of getting a coin from pirate 4. since we don't have enough information to answer that, to be safe, i would just say pirate 6 should offer the coin to pirate 1 or pirate 4.

14.

Problem: a mad bomber is out on the job, making bombs. He has two fuses (pieces of string) of varying thickness which each burn for 30 seconds. Unfortunately he wants this bomb to go off in 45 seconds. he can't cut the one fuse in half because the fuses are different thicknesses and he can't be sure how long it will burn. (for example: the first half of the fuse might burn up in 10 seconds and the second half in 20 seconds.. the fuse doesn't burn at a constant rate, but the total time it would burn is 30 seconds). How can he arrange the fuses to make his bomb go off at the right time?

Solution: light both ends of one of the fuses. When that fuse goes out, 15 seconds has elapsed. Then light the other fuse.

15.

Dave Winer is stuck on a deserted island, with lots of trees, which is very thin and ten miles long (east to west). Large cliffs surround the entire island and if he jumped off, he wouldn't survive the fall. A fire starts burning at the west side of the island. unfortunately this island always has a west to east blowing wind blowing at 2mph and this moves the fire slowly toward dave at 1mph. (so he only has ten hours left). Save dave (or maybe, let him burn :-) ! what to do?

Someone suggested he could dig a pit across the island to act as a firebreak. good suggestion, if he had a shovel and the ground wasn't too hard.

But even if he didn't have a shovel, he could pick up a branch and run up to the fire and light the branch. Then run all the way to the eastern edge of the island, but stop about a mile short. There he could light all those trees on fire and they would start burning and the fire would move east. It would consume all that vegetation in an hour, and then dave could wait for awhile for that part to cool down some. When the initial fire reached him, he could just run into the already burnt part, and the fire couldn't get him.

Dave is saved!

16.

Problem: using 31 dominoes, where one domino covers exactly two squares, can you cover all the empty squares on this chessboard (which has 62 spaces). If so, how? If not, why?

Solution: I think everyone's first inclination is to try and figure out how it is possible. then again, if you've heard a bunch of these questions before, you usually know that if the question says "if not, why?" or "prove whether its possible or impossible", you can infer that it is not possible (otherwise, the question usually just asks for the solution).

After a while fiddling around with the dominoes, you will start to realize that the most obvious solutions are not viable. If you start to think it's impossible, think about why.

A reader emailed me telling me that using the picture of the chessboard without the squares colored will result in a very small percentage of people solving the problem. if i use the following picture

A much higher percentage of people will be able to solve the problem. The people who solve the problem using only the grid, usually represent the problem in their heads as the colored board.

Still can't figure it out? Using the colored board, remember that a domino always covers a black square and a white square.

If you look at the board, you will see that the two squares missing are both black. This means that for all the squares on the board, each white square has a corresponding black square, except for two white ones. so even if you covered all the black/white pairs, you would still be left with two white squares, which will never be adjacent to each other, no matter how you lay out the dominoes.

17.

Problem: three cannibals and three anthropologists have to cross a river. The boat they have is only big enough for two people. If at any point in time there are more cannibals on one side of the river than anthropologists, the cannibals will eat them. What plan can the anthropologists use for crossing the river so they don't get eaten?

Note that if you violate the "anthropologists > cannibals" rule at any point in time, it is illegal... For example if a boat with a cannibal and an anthropologist travels to a shore with one cannibal on it, then # cannibals > # anthropologists, even if you say the anthropologist immediately takes the boat back.

Let W be the west shore which they are all on. Let E be the east shore where they want to go.

18.

five webloggers - joshua Allen, meg Hourihan, jason Kottke, robert Scoble, and joel Spolsky - were competing for karma points on the major search engines: google, yahoo, altavista, <>lycos, and msn. karma was distributed on a five point scale. The most popular weblog received 5 points, and the least popular received 1 point. For each search engine, no two webloggers received the same number of points. Overall scores were determined by adding up the individual scores from each search engine.

Allen got the highest number of karma points - 24. Kottke was consistent in his scores: he got the same karma points from 4 different search engines. Spolsky got 5 points from lycos, and 3 from msn.

No two webloggers got the same total score, and the final rankings were as follows: Allen, Hourihan, Kottke, Scoble, and Spolsky. How many karma points did Hourihan get from lycos?

Solution: let's start with what we know

The only possible values for Allen achieving 24 is { 5 5 5 5 4 } and since Spolsky got a 5 from lycos, we know that is where Allen's 4 comes from.

We also know that the total number of points given out was 75. (5 * (5 + 4 + 3 + 2 + 1))

spolsky had to have at least 11 points. If Spolsky had more than 11 points, say 12, then is it possible to achieve a solution? Scoble would have had to have at least 13 (since there were no ties), and Kottke 14, and Houlihan 15. That would yield an overall total of 78. too much! So Spolsky definitely had 11 points.

Using the same logic as before, we also know that Scoble could not have gotten more than 12 points. If he had 13, and Kottke 14, and Houlihan 15, the total would be 77. Still too much. So Scoble had 12, and continuing on Kottke had to have 13 and Houlihan 15, otherwise the totals would be over 75.

Now we know Kottke had 14 points. if he got four 4's for consistency, it wouldn't work (already over 16). if he got four 2's, it also wouldn't work (8 points plus the maximum 5 is still only 13). so he had to have received four 3's. And since he couldn't have gotten a 3 from msn, that is where he received a 1.

Let's look at scoble. We can see from the chart that all 5's and 3's have already been given out (and there is only one 1 left). So Scoble's scores can only contain 4's, 2's, or a single 1. Given that information the only possible combination of 5 scores that would yield 12 is { 2 2 2 2 4 }. Since Allen already has a 4 from lycos, Scoble must have a 2 there.

Hence Houlihan must have a 1 from lycos!

19.

A disfunctional family has to cross the river. On one side of the river are a mom and 2 daughters, dad and 2 sons, the maid and the dog. There is a boat only big enough to hold 2 people (counting the dog as 1 person). Only the adults are capable of operating the boat. Everyone has to get to the other side, without anything bad happening.

Difficulties: if the dog is left with anyone and the maid isn't there to control him, he'll bite. the dad can't be left with any of the daughters when the mom isn't there. Likewise, the mom can't be trusted alone with either of the sons when the dad isn't there.

Remember! Only an adult can operate the boat, AND the boat can't drive itself.

solution: we start with a mother (m), two daughters (d1, d2), a father (f), two sons (s1, s2), a housemaid (h), and a dog (c - canine) on the west (W) shore, and they all want to get to the east (E) shore.

W = {m, d1, d2, f, s1, s2, h, c} // everyone on the west shoreE = {} // no one on the east shore

let's move everyone, over...

housemaid and canine go east, and the housemaid comes back:

W = {m, d1, d2, f, s1, s2, h}E = {c}

housemaid and s1 go east, h and c come back:

W = {m, d1, d2, f, s2, h, c}E = {s1}

father and s2 go east, father comes back:

W = {m, d1, d2, f, h, c}E = {s1, s2}

mother and father go east, mother comes back:

W = {m, d1, d2, h, c}E = {f, s1, s2}

h and c go east, father comes back:

W = {m, d1, d2, f}E = {s1, s2, h, c}

father and mother go east, mother comes back:

W = {m, d1, d2}E = {f, s1, s2, h, c}

mother and d1 go east, housemaid and c come back:

W = {d2, h, c}E = {m, d1, f, s1, s2}

h and d2 go east, h comes back

W = {h, c}E = {m, d1, d2, f, s1, s2}

h and c go east

W = {}E = {m, d1, d2, f, s1, s2, h, c}

done!

20.

This is a classic problem which i have heard many times before. This is the "harder" of the two problems, since in this one, you do not know if the invalid item weighs more or less than the others.

Solving it is only half the battle. Writing up a solution that anyone including your grandma could understand, is very hard.

Problem: the evil king from before sends his own assassin to take care of the evil queen who tried to poison him. Of course, her trusty guards catch the assassin before any harm is done. The queen notices that the assassin is quite handsome and doesn't really want to punish him by death. She decides to test his wisdom.

The queen gives the assassin 12 pills which are all completely identical in shape, smell, texture, size, except 1 pill has a different weight. The queen gives the man a balance and tells him that all the pills are deadly poison except for the pill of a different weight. The assassin can make three weighings and then must swallow the pill of his choice. If he lives, he will be sent back to the bad king's kingdom. If he dies, well, thats what you get for being an assassin.

Only one pill is not poison and it is the pill which has a different weight. the assassin does not know if it weighs more or less than the other pills. how can he save his skin?

solution: easy.

Choose any eight of the pills and put four of them on each side of the balance.

There are two possibilities:

(1) one side of the balance comes out lighter. In this case, you know that the abnormal (safe) pill is one of the pills already on the balance. label the pills on the lighter side A B C and D, and the pills on the heavier side E F G and H. label the pills not on the balance NORM (you know they’re normal pills).

(2) the balance is even. in this case, you know that the abnormal (safe) pill is one of the pills not on the balance. label the pills already on the balance NORM, and label the four pills not on the balance I J K and L.

let’s proceed with possibility (1).

consider why the side ABCD came out higher than the side EFGH. this could be because:

A is the abnormal pill, and it’s lighter than the other pills.

B is the abnormal pill, and it’s lighter than the other pills.

C is the abnormal pill, and it’s lighter than the other pills.

D is the abnormal pill, and it’s lighter than the other pills.

E is the abnormal pill, and it’s heavier than the other pills.

F is the abnormal pill, and it’s heavier than the other pills.

G is the abnormal pill, and it’s heavier than the other pills.

H is the abnormal pill, and it’s heavier than the other pills.

now let’s make another weighing, with two of the ABCD pills on either side, and one of the EFGH pills on either side. for example, let’s weigh ABE versus CDF. how would this weighing come out given each of those 8 possibilities we just listed?

if A is the light pill, the ABE/CDF weighing will come out with ABE high.

if B is the light pill, the ABE/CDF weighing will come out with ABE high.

if C is the light pill, the ABE/CDF weighing will come out with ABE low.

if D is the light pill, the ABE/CDF weighing will come out with ABE low.

if E is the heavy pill, the ABE/CDF weighing will come out with ABE low.

if F is the heavy pill, the ABE/CDF weighing will come out with ABE high.

if G is the heavy pill, the ABE/CDF weighing will come out even.

if H is the heavy pill, the ABE/CDF weighing will come out even.

OK, so we observe how the ABE versus CDF weighing actually comes out.

(a) if it comes out even, then we know that the abnormal pill is either G or H. for our third weighing, we can weigh G against one of the pills we already know to be normal (one of the pills we labelled NORM). if it comes out even, then G is normal and H must be the abnormal pill. if it comes out uneven, then G is the abnormal pill.

(b) as we can see from our chart above, if the ABE/CDF weighing comes out with ABE high, then the situation is either: A is the light pill, B is the light pill, or F is the heavy pill.

(c) as we can see from our chart above, if the ABE/CDF weighing comes out with ABE low, then the situation is either: C is the light pill, D is the light pill, or E is heavy pill.

so in either situation (b) or (c), we have two possible light pills and one possible heavy pill. what we do in that case is we put one of the possible light pills and the possible heavy pill on one side of the scale, and two NORM pills on the other side of the scale. this is our third weighing. if it comes out even, then we know that the other possible light pill is the abnormal pill. if it comes out with the two NORM pills high, then we know that one of the pills on the other side is abnormally heavy, so we know that the possible heavy pill is the culprit. if it comes out with the two NORM pills low, then we know that one of the pills on the other side is abnormally light, so we know that the possible light pill on the scale is the culprit.

that takes care of case (1), where the first weighing came out uneven.

what about case (2), where the first weighing comes out even?

then we know the abnormal pill is one of I J K or L, and we have two weighings to find the abnormal pill in.

for our second weighing, we put I and J on one side of the scale, and two NORM pills on the other.

(a) if this comes out uneven, we know the abnormal pill is I or J; we weigh I against one NORM pill to see if I is abnormal and if it isn’t, we can conclude that J is the abnormal pill.

(b) if the IJ versus 2 NORM weighing comes out even, we know the abnormal pill is K or L; we weight K against one NORM pill to see if K is abnormal and if it isn’t, we can conclude that L is the abnormal pill.

finished.