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

31.

You die and the devil says he'll let you go to heaven if you beat him in a game. The devil sits you down at a round table. He gives himself and you a huge pile of quarters. He says "ok, we'll take turns putting quarters down, no overlapping allowed, and the quarters must rest on the table surface. The first guy who can't put a quarter down loses." the devil says he wants to go first.

Being the smart programmer you are, you realize that if the devil goes first, he may automatically win. So you convince him to let you go first, which makes your day because you know you can't lose. What is your winning strategy?

First, put the first quarter exactly in the center of the (perfectly circular) table.

Next, for each quarter the opponent places, place one directly opposite it. That is, place it so that the center of the table is halfway between your piece and the opponent's previous piece.

This will generate a completely symettric (about the center) layout of quarters on the table. This means that whenever the opponent selects a free space to place a quarter in, the space opposite is guaranteed to be free as well. Since we are always guaranteed an open space, we will never lose with this strategy (and thus win when there are finally no more spaces for the opponent to use).

32.

There is a pot of N noodles. (So there are 2N ends). A person randomly grabs two ends and merges them. The person keeps doing it, until there are no more noodles, (and only loops), left in the pot. What's the average number of loops in the pot?

OK, all the answers so far just list formulae, without giving any explanation. I'll try to work it out out loud. (At this point I have no idea what the answer is.) Also, it's a math problem, so I'll assume we can ignore factors like how much the noodles stick together, how stiff they are, and so on. I'm sure I have no idea to take account of those factors.

Call the first end he picks up Noodle i. The second end he picks up is Noodle i*.

When he sticks the first two ends together, there are two possible outcomes:

(a) i* is the other end of noodle i, so he has created a loop.

(ii) i* is a different noodle from i, so he has created one long noodle out of two.

What are the odds of (a) happening? There are (2n-1) ends left in the bowl once he picks up the end of noodle i, and only 1 of them is the other end of the same noodle. Abstracting away from all physical details, let's say the odds of getting the other end of the same noodle are 1/(2n-1).

So the odds of (b) happening are 1-[1/(2n-1)], which is [(2n-1)-1]/(2n-1), i.e. (2n-2)/(2n-1).

If (a) happened, now we have a bowl with one loop in it, and n-1 other unlooped noodles. We add 1 to our count of loops, and repeat the problem for n-1.

If (b) happened, now we have a bowl with 0 loops in it, and n-1 other unlooped noodles. It's just that one of those noodles is especially long. We don't add anything to our count of loops; we just repeat the problem for n-1.

Now, when we get down to 1 unlooped noodle left in the bowl, the odds of (a) happening are

33.

A person dies, and arrives at the gate to heaven. There are three doors. One of them leads to heaven. Another one leads to a 1-day stay at hell, and then back to the gate, and the other leads to a 2-day stay at hell, and then back to the gate. Every time the person is back at the gate, the three doors are reshuffled. How long will it take the person to reach heaven?

this is a probability question - i.e. it is solvable and has nothing to do with religion, being sneaky, or how au dente the pasta might be ;-)

Solution: heaven

1/3 of the time, the door to heaven will be chosen, so 1/3 of the time it will take zero days. 1/3 of the time, the 1-day door is chosen; of those, the right door will be chosen the next day, so 1/9 trips take 1 day. Similarly, 1/9 will take two days (choosing the 2-day door, then the right door).

After that, the cases split again, and again, and again. I can't seem to make a nice infinite sum this way, so let's try again.

Suppose the average days spent is X. 1/3 of the cases are done in zero days as before. 1/3 of the cases are 1 day plus X. 1/3 are 2 + X. So:

X = 1/3 * 0 + 1/3 * (1 + X) + 1/3 * (2 + X)

= 0 + 1/3 + X/3 + 2/3 + X/3

= 1 + 2X/3

Therefore,

X/3 = 1

X = 3

On average, it takes three days to get to heaven. Two if the noodles are limp.

.

34.

Someone walks into your room and dumps a huge bag of quarters all over the floor. they spread them out so no quarters are on top of any other quarters. a robot then comes into the room and is programmed such that if it sees a head, it flips it to tails. If it sees a tail, it throws it in the air. the robot moves around randomly forever. Will there be a convergence in distribution of heads vs. tails?

Hmmm. I made a little math trick out of it. If the 'bot finds a head, it flips. If the bot finds a tail, there's a fifty percent chance this will become a head, as well.

(P_h = #heads/#coins, P_t = #tails/#coins)

So, delta h = -P_h + .5 P_t

= -(1 - P_t) + .5 P_t

= 1.5 P_t -1

Which is zero when P_t is 2/3. It's important to remember that a flip to a tail results in no change to the number of tails -- this threw me off for a second.

35.

How does one find a loop in a singly linked list in O(n) time using constant memory? you cannot modify the list in any way (and constant memory means the amount of memory required for the solution cannot be a function of n.)

I first figured this out when I was asked the question in a Microsoft interview, so there's verification that one question in the book was from a real interview. The best part of this problem is that I actually needed to write the code out for it a little while ago to detect a bug.

One way to detect a loop is to iterate over the list with 2 pointers at the same time where one is iterating at double speed. If the 2 pointers are ever equal after they iterate once and before they both reach an end, there's a loop.

Now for another puzzle.. I think the next question I had to answer was something along the lines of "OK, How do you remove a loop in a linked list with the same constraints?" The latter question definitely seems harder, but in the sequence of questions I'd already answered for the interviewer, the solution was pretty obvious. I'll leave that solution to someone else today.

36.

You have 20 blue balls and 14 red balls in a bag. You put your hand in and remove 2 at a time. If they're of the same color, you add a blue ball to the bag. If they're of different colors, you add a red ball to the bag. (Assume you have a big supply of blue & red balls for this purpose. note: when you take the two balls out, you don't put them back in, so the number of balls in the bag keeps decreasing). What will be the color of the last ball left in the bag?

Once you tackle that, what if there are 20 blue balls and 13 red balls to start with?

Solution: last ball

You always take off Red Balls two by two!

So if you start with 14 Red Balls, you cannot have one single Red ball at the end.

... so the last ball is blue.

But if you start with 13 Red Balls, as you take them off 2 by 2 (at one moment or the other you'll do it !) you will arrive at a moment when you have 1 red ball in the bag. But as you can only take off Red Balls 2 by 2 (Did I already say that ?!) you'll remove the last Blue Balls, one by one......

So the lastball will be red...

Oh, by the way, did I tell you that you take off Red Balls 2 by 2 ?! ;->

For tired people here is why you take off Red Balls 2 by 2 : - If you take off 1 RED and 1 BLUE, in fact you will take off 1 BLUE - If you take off 2 RED, in fact you will take off 2 RED (and add 1 BLUE) - If you take off 2 BLUE, in fact you will take off 1 BLUE

37.

Every night, i dump all the change in my pocket into a big bucket.

When I buy things, i never hand over coins. Always bills. So I accumulate a lot of coins. Even if the purchase price is $1.01, and i have lots of coins in my pocket, i pay $2 and take the 99c in change. All the more coins to dump in my change bucket!

After about 10 years of this, i decide to roll all the coins into rolls. Remember that a quarter roll is $10, a dime roll is $5, nickels $2, pennies 50 cents. So I go to the Banking Supply Store and buy empty paper rolls.

The Banking supply store, conveniently, sells assortment packs of coin rolls. Each assortment pack contains W quarter rolls, X dime rolls, Y nickel rolls, and Z penny rolls.

The question: what is the optimum ratio of W to X to Y to Z to maximize the probability that I will use up the assortment packs at the same rate, e.g. without lots of leftover nickel tubes and stuff.

p.s. this problem should ideally be solved using Excel (but if you really like doing these things by hand, be my guest).

Submitted by joel

Paul brinkley makes these assumptions which are all good assumptions to make: Assumption 1: The price of purchases made, modulo $1, is an even distribution from 0 cents to 99 cents. Assumption 2: The cashier will always give you the least number of coins mathematically possible, and will always have enough of each type of coin to do this. So you'll never get 99 pennies as change for a $1.01 purchase, for example. Assumption 3: Half dollars don't exist.

Solution: coin rolls

"Brute force" approach:

I guess I'll begin with a few assumptions:

Assumption 1: The price of purchases made, modulo $1, is an even distribution from 0 cents to 99 cents. Probably not true, but we can cover that later.

Assumption 2: The cashier will always give you the least number of coins mathematically possible, and will always have enough of each type of coin to do this. So you'll never get 99 pennies as change for a $1.01 purchase, for example.

Assumption 3: Half dollars don't exist.

Over the long haul, then, you'd get N sets of 0 cents, 1 cent, 2 cents, and so on up to 99 cents. So let's consider one of each. How many of each coin would you end up with?

Easy first: let's do quarters. 25-49 cents each gets you one. 50-74 each gets you two. 75-99 each gets you three. That's (1+2+3)*25, or 150 quarters.

Dimes next. 10-19 gets you one. 20-24, two. (You'd get a quarter instead for 25 and up.) 35-44, one. 45-49, two. 60-69, 85-94, one. 70-74, 95-99, two. So that's 4*(10+5*2), or 80 dimes.

Nickels. One for 5-9, 15-19, and that same pattern for +25, +50, +75, so it's 4*10 or 40 nickels. You'll never get two at a time, since a dime (at least) will do.

Pennies. Let's cut to the chase: 1,2,3, and 4 cents gets 10 pennies in all, and that pattern happens 20 times, so that's 200 pennies.

Let's double-check. 200 pennies, 40 nickels, 80 dimes, 150 quarters. That's 200*1 + 40*5 + 80*10 + 150*25 cents = 200+200+800+3750 = 4950 cents, which is the sum of all numbers from 0 to 99, so it checks.

15/8/4/20 would be the ratio then, IF coin rolls all hold the same number of coins, but they don't. Quarter rolls hold 40 coins, dime rolls hold 50, nickel rolls 40, penny rolls 50. So you need 5/4 as many quarter and nickel rolls. The final ratio is 75/32/20/80. Seems like a lot of quarters and pennies, except for the assumption that you'll tend to get them much more often than nickels and dimes as change.

The numbers change slightly when you figure in things like frequency of coins in circulation, the supply the cashier has at any one time, the actual distribution of change values, and the cashier's inclination to give you two dimes and a nickel instead of a quarter just because...

So what numbers do assortment packs really contain?

38.

A man has two cubes on his desk. Every day he arranges both cubes so that the front faces show the current day of the month. What numbers are on the faces of the cubes to allow this?

Solution: calendar cubes

Hmm. I don't know why this would warrant four aha's, but we'll see...

First, to show all possible days, we'd need one of each of the ten digits. We'd also need two 1s and two 2s to show 11 and 22. That's twelve numbers right there. Two cubes, twelve faces, so every face is used. Quite elegant.

We know each cube will need a 1 and a 2. Let's put the 3 on one of them. The 0 has to go on the other. We put 4, 5, and 6 on the 3-cube since we need to show 04 05 06.

But now where do 7, 8, and 9 go? The 0-cube needs them to be on the 3-cube, but it's full. I'm beginning to see why this gets four aha's.

Let's try this: clear both cubes, put the 0 on one of them. Now 1-9 have to go on the other cube to show 01-09. We can't put a 0 on the other cube, too, because that puts us over the 12-digit limit. It seems I have mathematical proof that this cannot be done! What am I missing? It's not like you can turn one of the other numbers sidewise to make another 0...

Heh.

You CAN make a 9 out of a 6, though. That frees up a digit. So you put 0, 1, and 2 on both cubes. Put 3 on one of them. 4 and 5 can go on it too. Put 6, 7, and 8 on the other. Now you can show 01-31 with no problem, and even 00 and 32 if you're feeling weird.

39.

In a country in which people only want boys, every family continues to have children until they have a boy. if they have a girl, they have another child. If they have a boy, they stop. What is the proportion of boys to girls in the country?

Solution: boys and girls

Pretty simple. Half the couples have boys first, and stop. The rest have a girl. Of those, half have a boy second, and so on.

So suppose there are N couples. There will be N boys. There will be an "infinite" sum of girls equal to N/2 + N/4 + N/8 + ... As any college math student knows, this sum adds up to N. Therefore, the proportion of boys to girls will be pretty close to 1:1, with perhaps a few more boys than girls because the sum isn't actually infinite.

40.

I flip a penny and a dime and hide the result from you. "one of the coins came up heads", i announce. What is the chance that the other coin also came up heads?

Solution: painfully easy

Assuming complete honesty on the part of the flipper, wouldn't the solution be 33%?

There are four possible scenarios:

HH TH HT TT

Obviously the TT possibility can be discounted because it does not result in one of the two being heads.

This lees us with three possibilities, only one of which has the other coin also being heads.

Therefore one third.