Fog Creek Software
Discussion Board




Bad interviews

The craziest telephone interview I had was a month ago with a small software/web design company in London.

One of their questions was the cost of finding the hardness of a batch of identical eggs as measured by the highest rung of a ladder one egg can be dropped from without breaking. The ladder has 1000 rungs.

I immediately said this was a binary search type problem and the cost was LOGARITHMIC. I said the 2 to the power of 10 is 1024. As 1024 is near to 1000, the cost is approxmiately 10.

When I was told this was incorrect, I stressed I said approximately and that the real answer will be slightly less than 10.

Well the telephone interviewer went on and on and despite me saying the cost was logarithmic and 2 to the power of 10 is 1024, we didnt get anywhere.

Finally the man said the answer was log n.

I almost hung up at that point. He obviously ignored my saying the cost was logarithmic and didn't know that

2 to the power of 10 = 1024
is another way of saying
log(2) 1024 = 10

I didn't get the job. This stresses the important point that if people ask technical questions they should at least understand them. These non-technical gatekeepers just keep programmers away from jobs.

Bagpuss_2003
Friday, May 09, 2003

Doesn't just happen in programming. In the mid 70's I had an interview for a teaching/translation job in Paris.

I was given about 100 sentences to translate into English. Round about the middle of the list was the sentence "Elle est très forte". The literal translation is "She is very strong", but this was before the age of hormone-gobbling female weight lifters and would have sounded a lilttle strange. The phrase in fact is normally used in contexts such as "Elle est très forte au piano" - "She's a very good pianist" -- and I gave him that example and said that out of context it would be impossible to translate it.

However he had clearly been given an approved translation from a fan of sub-Woosterian girls public school literature, and regretfully informed me that I had failed the test as the correct translation was "She's very bully."!

Stephen Jones
Friday, May 09, 2003

Nowadays everyone has a C++ test they want to administer.  Invariably, the test is written by someone with a year or two of experience in the language, and it shows.  In the past, I would grit my teeth, dutifully fill them out, and hope for the best.

Lately, though, I've decided to seize control of this part of the interview.  First, I smile broadly and say, "Hey, let's do this together!"  Then, we go through each question, and I explain why the answer they want is incorrect, incomplete, or debateable.  If none of those apply, then I ask a related, but harder, question, like, "Yeah, but guess what the ARM says about forward declarations and destructors?"

I get away with this by (a) smiling a lot, (b) approaching it as a "fun" experience for all involved, and (c) never directly criticizing their questions.  The results have been much better.

If you're in a bad interview, you have to do what it takes to make it a good interview.

Spaghetti Rustler
Friday, May 09, 2003

>> "log(2) 1024 = 10"

Not on my calculator.  Then again I flunked the 1st grade.


Friday, May 09, 2003

On most calculators you have base 10 and base e (approx 2.71) log functions. They have the keys log and ln respectively. For this you need logs with base 2.

This is a formula somewhere to convert a log of one base into another but it's been too long since I did a A level maths.

Bagpuss_2003
Friday, May 09, 2003

On MS Calc in sci mode: log(1024)/log(2)=10

Thomas Eyde
Friday, May 09, 2003

Hmm... also if by 'cost' one understands the cost of an egg, then you can do in with only one egg starting to drop it from the lowest step of the ladder.
And, of course, given the stress caused to the egg does not accumulate :)

Emo
Saturday, May 10, 2003

But with a 1000 rungs it could take you some time to find the right rung.

Bagpuss_2003
Saturday, May 10, 2003

Here's a slightly more complex version of this problem:

Your task is the same, but you have only 2 eggs.

What's the optimal strategy and how many drops will it take in this case?

Hint: you can do better than 500 or 100 or even 50 attmepts!

raindog
Saturday, May 10, 2003

Method 1: wait for egg 1 (male) and egg 2 (female) to hatch.  Breed resulting chickens.  In time, you will have enough eggs to complete this task

Method 2:
for (i = 32; i < 1000; i += 32) // 32 = sqrt(1024)
  if (breaksWhenDropped(i))
      for (j = i - 32; ; j++)
          if (breaksWhenDropped(j)) return j;

This requires around 64 drops, worst-case.  I donno how to get it under 50.

Alyosha`
Sunday, May 11, 2003

Actually, I am not sure why one would need to breed resulting chickens.  All that is required is one chicken to be female.

Alyosha`
Sunday, May 11, 2003

Yeah, I've heard the problem before, and you need to state it explicitly:

"You have 2 crystal orbs of exactly the same strength and a 100 floor building. You need to find the exact lowest floor at which the orbs will break (you must be exactly right, not close). Minimize the worst case scenario for the number of attempts at dropping the orbs."

The typical first answer is a binary search, but the worst case scenario for a binary search is 50 (you start at floor 50, and the first orb breaks, so you must start at 1, and if the orbs don't break until 49, you took 50 attempts).

The right answer comes from the knowledge that every successive drop of the first orb adds attempts, so each drop of the first orb must mean less attempts with the second orb. The first orb attempts are made at floor 14, then you move up 13 floors to 27, then up 12 floors to 39, etc. The worst case scenario, then, is 14 drops, because each successive drop of the first orb yields one less drop required by the second orb. (14 then 1-13 for 14 drops; or 14, 27, then 15-26 for 14 drops; 14, 27, 39, then 28-38 for 14 drops; etc.).

Brad Wilson (dotnetguy.techieswithcats.com)
Sunday, May 11, 2003

Oh, and unless my fingers messed with me, the worst case scenario with the same algorith for 1000 floors/rungs is 45 attempts.

using System;

public class MathFun
{
  public static void Main()
  {
    int result = 0;
    int idx = 0;

    while (result < 1000)
      result += ++idx;

    Console.WriteLine("{0} iterations required", idx);
  }
}

Brad Wilson (dotnetguy.techieswithcats.com)
Sunday, May 11, 2003

Dear Brad,
                  Are you sponsored by The National Poultry Producers Federation?

                    The answer as originally stated is 10. It's logarithmic base 2. You start at 500. If it breaks you can forget about the rungs on top after 500. If it doesn't break you can forget about the ones below. You then go to rung 250 or 750, depending on whether it broke or not, and keep doing it unitl you're down to one rung.

                    The other advantage of this method is that you lose a load of weight running up and down the ladder. (And you can program it in Visual Basic with nested ifs so you've got spaghetti to go with the omelette!).

Stephen Jones
Sunday, May 11, 2003

I was answering the SECOND version, not the original. So, uh, did you just read the first version, skip over everything else, and then come down here to call me an idiot?

Here's a mirror. :-D

Brad Wilson (dotnetguy.techieswithcats.com)
Sunday, May 11, 2003

Brad, your solution is exactly right. One needs 45 attempts.

P.S. There's no need to iterate, if you rember the formula for arithmetic series sum:

N x (N+1)/2 >= 1000

and N = 45

raindog
Sunday, May 11, 2003

Um... I find that I have nothing useful to add to this conversation. I'm thankful for this.

My problem with these interview questions is exactly what you see here, they are pointless.

I don't know about you folks, but I write software that people use to make their jobs or lives a little better.

So my answer: Find a math geek and ask him. While he calculates the best method, I'll go about writing an application that people will actually want to use.

Marc
Monday, May 12, 2003

Until they have done the testing, how do they know the eggs are identical?


Monday, May 12, 2003


It's called a "given"

Joe AA
Monday, May 12, 2003

YM they have found some way of making identical eggs? Oh, okay. Must have mass produced them in one of those factory farms I hear about.

Still seems an odd way of determining how hard they are. One would normally use some kind of pressure guage, shirley?


Monday, May 12, 2003

Hmm, but what about physics?

Since the ground does not move, the difference between the momentum (mass times velocity) of the egg before and after it hits the ground is the impulse from the collision, or the Force exerted times the time its exerted over.

When the egg is dropped, it has only potential energy, an this energy is m*g*h.  Assuming negligable air resistance, all of this energy is turned into kinetic energy when the egg hits the ground, si m*g*h=1/2*m*v^2, so the velocity on impact is sqrt(2*g*h).

Thus, we have m*sqrt(2*g*h)=F*dt.  Assuming dt doesn't change, and factoring out the constants, the end result is F=sqrt(h)*C.

Now, lacking any other knowledge, assume that there is no particular force that is more likely to break the egg than another, that is, the probability distribution of the neessary force is uniform.  (Since the units are arbitrary, this seems very reasonable.)  This means that the probability distrbution for heights should be exponential.  So now when you do your binary search you want to divide not in halfs, but at some point that will put more numbers in the lower interval so that the probablility between the two inervals is the same (exactly what this fraction is will depend on some constants).  This gives a better best-case scenario, a worse worse-case scenario, and *a better average case*.  I would interpret the "cost" as the average case, so this method should statistically be cheaper.

I believe this is still O(log n), but should be better for any given value of n.

On the other hand, if you disagree with any of the above assumptions, you're better off splitting the difference and going with the standard binary search.

Michael Chansky
Monday, May 12, 2003

Nobody said the ladder rungs were evenly spaced ;-).

Just me (Sir to you)
Tuesday, May 13, 2003

"but what about physics"

That was kind of what I was getting at when I mentioned a pressure guage (or whatever you call such a gizmo, I'm no eggspert). I see no reason why you can't measure the force needed to break an egg and then work out the vertical height required, and then measure that against the ladder. Thus your answer as to the cost becomes "1". If you wanted to you could then drop more eggs to test the theory, but you probably will not get a cost higher than 2.

The disadvantage of the binary search method is that the results depend on too many external factors - the angle of the ladder, the surface being dropped on, and even a random factor in which part of the shell the egg lands on (the effect of landing on one of the ends reduces the likelihood of breakage as the stress is spread around the shell).


Tuesday, May 13, 2003

Are they white eggs or brown eggs?

The Word
Tuesday, May 13, 2003

> Are they white eggs or brown eggs?

It's probably illegal to ask that question in an interview. :-)

David Clayworth
Tuesday, May 13, 2003

Also, are they African or European eggs?

Brandon
Wednesday, May 14, 2003

*  Recent Topics

*  Fog Creek Home