Wall Street Interview Question

It is not widely known that in interviews for finance positions on Wall Street that it is typical to ask "brainteasers".

The goal is to see how you react to an unusual technical situation when under pressure.

Here is one that was directed last month at an SUU alumnus I mentor:

Suppose you had one million cans lined up with a 7 digit integer number under each can. What is a good method to find if the can numbered 0047000 is in the lineup? The only information you were told was that the numbers 1) start at 0000001, 2) the cans are ordered from smallest to largest number, but 3) numbers may be skipped. (Hint: a 7 digit number can go much higher than one million.)

(I cleaned this up a bit so that I could use it as an exam question for a senior level class). Post answers to the comments.

FWIW: He got the offer.

I'll be posting more of these in the future, but you can also go and buy this book for a collection of somewhat older questions:

Comments

[Pelkabo]

It may be too early in the morning to answer this question, but I'd try something like this:

1. Let nf = 1 and nl = 1000000 (subscripts refer to first and last).

2. Look under cans nf and nl. Say the numbers under the cans are yf and yl.

3. Solve n = int[nl+(47000-yl)*(nl-nf)/(yl-yf)].

4. Look under cans n-1, n and n+1. If y[n-1] .LT. 47000, y[n+1] .GT. 47000 and yn .NE. 47000 then 47000 isn't there; stop. If yn = 47000, then it is there; stop. Otherwise, if yn .GT. 47000, let nf = 1 and nl = n; go to step 2. If yn .LT. 47000, let nf = n and nl = 1000000; go to step 2.

I had to use the old FORTRAN codes for less than and greater than because those symbols were not being printed for some reason. So how'd I do?

[Dave]

Of course ... I'm not an interviewer ... but if I were I probably wouldn't be happy with this answer.

It isn't that it wouldn't work, but rather how you would actually go about performing step 4. Even if you know n from step 3, how are you going to find the n'th can? Count them? How long would that take?

[Pelkabo]

If we are to imagine that someone has lined up one million cans, then we have already stepped outside reality. So in that spirit, my answer is that I tell a pixie which can I want. She flies down the line at supersonic speed, counting the cans she passes, and stops at the number I told her.

Failing that, since the line is miles long (unless the cans are microscopic) I could measure the width of one can and figure out how far I need to drive my car to get to the right one.

[Dave]

Hope I didn't offend you ...

I believe the sort of answer they are looking for is something that divides the set in two at each step, isolating the can in question in ever smaller subsets. Such a method would have a workload proportional to the log of the number of cans.

Once you are in the set of algorithms that are that efficient, they are probably looking for something that doesn't require counting, or the evaluation of a formula (as yours did). It helps, but only moderately, to have some rule about where to choose the point of division - and I'm not sure that a formula is the sort of thing they are looking for in an interview.

[Vijay]

It's a simple case of binary sort - O(logn)

[Dave Tufte]

For you and me and my former student, yes.

For many others, it seems not.

[cheap jerseys]

concerning 12L y Three.5W y 7H and has