Can You Solve These Challenging Job Interview Questions?

[daigo]

These came up for a job interview and they had to be answered relatively quickly (most of them should be answered within one minute):

1) Prove the Law of Cosines (For any triangle: a^2=b^2 + c^2 - 2abcos(theta))

2) How much would you pay to play this game: You roll a die and are paid whatever amount comes up on the die. You are allowed to roll again if the number is 4 or above. You do not get to roll again if the number is 3 or below.

3) Give an algorithm to test if a number is prime in time better than O(n)

4) If you pick two numbers between 0 and 1, what is the probability that the product of those two numbers will be greater than .5

5) If you have a fair coin and want to simulate an event that has probability 1/3 and probability 2/3, how can you do that?

6) You have two robots placed randomly on the number line. When they land, they place a marker. You are to program the robots so that they meet, and you are given the following 3 commands: Go left, go right, or if you are on a marker, change strategy. Specify the two strategies so that the robots eventually meet.

7) Give an algorithm to reverse the order of the letters of each word in a sentence. Do not change the order of the words. For instance if your sentence is "I like cookies", this algorithm should return "I ekil seikooc"

8) What is happening in Greece? What countries are in trouble? Why is the Republic of Ireland in trouble? Why are the rest of the countries in trouble? Why do all the european banks have so much Greek debt?

9) There is a 5 game series, and you would like to bet on the outcome of the series. You have 100 dollars. If your team wins, you want to get 200 dollars at the end of the series, if they lose you want 0. The problem is that you can only bet on each individual game. How do you bet on each game?

10) You have a 6 barrel revolver with 2 bullets in it, placed side by side. You are going to play Russian Roulette. You play once and don't die. Do you spin the barrel again and then pull the trigger, or do you just pull the trigger?

11) You have two options. One has a strike price of 1300, one has a strike price of 1400. Which is cheaper and why?

12) What parameters would you need to price an option?

How many could you answer and how quickly?

 

[Hare]

Wow. What kind of job was it?

 

[Evo]

What kind of job was this for? How do you have a copy of the test? When I've taken employment tests, you were not allowed to take anything with you so that it can't be given out.

 

[Jimmy Snyder]

I just picked a few low hanging fruit.

Spoiler

2) 3.5 because the rule that makes you stop playing has no effect on the expected value.

7) While there are input letters take an input letter and see if it is a space. If it is not a space, put it into a LIFO queue. If it is a space, then take the letters off of the LIFO queue one at a time and print them, then print the space. When there are no more letters, take the letters off of the LIFO queue one at a time and print them. Stop.

10) Spin the barrel again for a 2/3 chance of surviving. If you pull the trigger without spinning you will have a 1/2 chance of surviving.

11) 1400 is cheaper because you subtract the strike price from the sale price to determine the value.

12) This one is weird. Options sell in a market that is independent of their underlying securities. However, in general, there is some correlation to: The underlying security, the strike price and the expiration date.

 

[Evo]

The OP is a student, I'd be careful about giving answers.

 

[daigo]

What kind of job was this for? How do you have a copy of the test? When I've taken employment tests, you were not allowed to take anything with you so that it can't be given out.

FIG @ GS, memory

The OP is a student, I'd be careful about giving answers.

Didn't ask for solutions, just wanted to discuss the aspects of getting jobs at these types of firms.

Here's some others asked at another company:

How many ridges are on a quarter?
How many libraries are in the U.S.?
How many traffic lights are in Manhattan?
Rank yourself from 1-10, 10 being the best in the following 5 qualities. The total cannot be greater than 35: Intellect, teamwork, communication, finance, attitude

 

[jtbell]

Here's some others asked at another company:

How many ridges are on a quarter?
How many libraries are in the U.S.?
How many traffic lights are in Manhattan?

Physicists know this kind of question as "Fermi questions," after Enrico Fermi who liked to spring them on his students. The point is not the actual question or answer, but rather the process that you use to estimate an answer, within an order of magnitude or so.

A classic Fermi question is "How many piano tuners are there in Chicago?"

 

[BobG]

I wouldn't work there. I'd rather work somewhere they ask you easy questions - like, "How high can you count on your fingers and toes?" Except I'd need a slide rule to even answer that question.

Actually, some of these are easy; some I'd at least know how I wanted to start them, but would need to think about them for a few to refine my answer (the robot question, for example), and I wouldn't have a clue about #11 or #12. Plus, I couldn't answer #5, but at least I knew that immediately.

 

[Biosyn]

FIG @ GS, memory

FIG? Does that stand for Fortress Investment Group?...

 

[Astronuc]

These came up for a job interview and they had to be answered relatively quickly (most of them should be answered within one minute):

How many could you answer and how quickly?

From the math, probability, economis and financial questions and terms, I'd imagine this was a financial services company.

 

[MarcoD]

Well, I wouldn't qualify, but I like the questions. #5 is interesting, for example. Best I could come up with that with a fair coin you can chose between four things A,B,C, and D. So you flip until you hit either an A, or a B or C. So it has an answer as a limit. Can it be done easier?

 

[BobG]

Well, I wouldn't qualify, but I like the questions. #5 is interesting, for example. Best I could come up with that with a fair coin you can chose between four things A,B,C, and D. So you flip until you hit either an A, or a B or C. So it has an answer as a limit. Can it be done easier?

With enough coin flips, you could get close to 1/3 and 2/3 by merging several possible results into one category (4 heads & 3 heads out of 4 flips, for example), but it's impossible to get an exact multiple of 3 using only powers of 2.

 

[MarcoD]

With enough coin flips, you could get close to 1/3 and 2/3 by merging several possible results into one category (4 heads & 3 heads out of 4 flips, for example), but it's impossible to get an exact multiple of 3 using only powers of 2.

Yeah, I had the same conclusion. The answer has to be a 'limit.'

 

[Jimmy Snyder]

Yeah, I had the same conclusion. The answer has to be a 'limit.'

No, just flip twice, 2 heads is A, 1 head, 1 tail is B, 0 heads is ignored.

 

[MarcoD]

No, just flip twice, 2 heads is A, 1 head, 1 tails is B, 0 heads is ignored.

That's the same answer as I gave. (Chose between A,B,C and D with chance 1/4, but try again on D. )

 

[lisab]

Clearly, you use the coin to buy a 2/3-headed coin.

 

[MarcoD]

What about #2? Very sloppily I came up with less than 7, but I am very unsure about it.

 

[MarcoD]

From the math, probability, economis and financial questions and terms, I'd imagine this was a financial services company.

I googled it. One of the questions is supposedly from a Goldman Sachs interview (according to google).

 

[MarcoD]

Does #9 have a solution?

 

[jobyts]

These are typical google/facebook interviews.

I was successfully able to answer question #6 in one of my interviews.

6) You have two robots placed randomly on the number line. When they land, they place a marker. You are to program the robots so that they meet, and you are given the following 3 commands: Go left, go right, or if you are on a marker, change strategy. Specify the two strategies so that the robots eventually meet.

while(!markerSet) {

go left;
go left;
go right;
set marker;
};
while(!peerFound) {
go left;
}

7) Give an algorithm to reverse the order of the letters of each word in a sentence. Do not change the order of the words. For instance if your sentence is "I like cookies", this algorithm should return "I ekil seikooc"

for(c=each character in the string) {
if (c == NULL || c == 'space') {
while (!stackEmpty)) {
print(pop(stack));
}
}
if (c == NULL) {
break;
} else {
push(stack, c);
}
}

 

[MarcoD]

Yeah, these I found trivial. I didn't bother about them. And I didn't bother about #1 though I don't know the answer by heart.

I don't believe you got the right answers though. The #6 should be something like 'forall n: do n steps left, retreat, do n steps right, retreat' But the question is underspecified, you need to know that the robots take alternate turns.

The #7 is easy too. Should be something like: 'split on space, reverse the words, concatenate the result.' You didn't do anything that resembles that.

 

[jobyts]

I don't believe you got the right answers though. The #6 should be something like 'forall n: do n steps left, retreat, do n steps right, retreat' But the question is underspecified, you need to know that the robots take alternate turns.

My answer is correct.

The logic is,
Move slow (left,left, right) in one direction until you find a marker set. And while moving, set the marker.

Once you find the marker set (that means, the other robot has visited this spot), move faster (continuous left), so you would eventually meet the other robot that is moving slower (left, left, right).

The #9 is easy too. Should be something like: 'split on space, reverse the words, concatenate the result.' You didn't do anything that resembles that.

I didn't expand the push() and pop(). Look for stack data structures.

 

[Jack21222]

I could do four of them for sure, and I could take a pretty good stab at about another three of them. Only having a minute each would be trouble, because I don't always think that quickly.

 

[MarcoD]

Oh, I understood that both robots drop a marker where they are dropped. My answer would work too. Now I look at it more closely, hmm, I guess you can't do something n times, so you're answer is better.

Hmm, I'll look at it again.

 

[MarcoD]

I could do four of them for sure, and I could take a pretty good stab at about another three of them. Only having a minute each would be trouble, because I don't always think that quickly.

The only interesting for me was #9 I think. (But I didn't really bother doing most of them under a minute.)

 

[MarcoD]

Ah, I was afk for a moment. The trivial answer is 'walk left until you hit a marker, then double your speed.' Which is your answer. ;-) Ah well.

 

[MarcoD]

I am still annoyed about #9. I have the feeling it can't have a solution, but I am not sure why or how to prove it. Anyone?

 

[Evo]

I just picked a few low hanging fruit.

Spoiler

2) 3.5 because the rule that makes you stop playing has no effect on the expected value.

7) While there are input letters take an input letter and see if it is a space. If it is not a space, put it into a LIFO queue. If it is a space, then take the letters off of the LIFO queue one at a time and print them, then print the space. When there are no more letters, take the letters off of the LIFO queue one at a time and print them. Stop.

10) Spin the barrel again for a 2/3 chance of surviving. If you pull the trigger without spinning you will have a 1/2 chance of surviving.

11) 1400 is cheaper because you subtract the strike price from the sale price to determine the value.

12) This one is weird. Options sell in a market that is independent of their underlying securities. However, in general, there is some correlation to: The underlying security, the strike price and the expiration date.

Since people are trying to find answers, I'm restoring Jimmy's early post.

 

[MarcoD]

#2 from Jimmy I think is wrong. The expected value, I guessed, is: chance you get to the 1st throw * expected return on the 1st throw + chance you get to the 2nd throw * expected return on the 2nd throw + ... = 1.0 * 3.5 + 0.5 * 3.5 + 0.25 * 3.5 + ... = 7.

(Difference is that I read the question as if you get a return on each throw.)

(Hmm, I guess it's Jimmies interpretation? Which means 3.5 since it doesn't make sense to role a dice again if you got a better result than the expectancy?)

 

[MarcoD]

#10 from Jimmy is wrong I think. Spin the barrel for a 1/3 chance of dying, and pull the trigger for a 1/4 chance of dying. So you pull the trigger.

 

[MarcoD]

#12 I read as a reference to Black-Scholes.

 

[MarcoD]

#11 I don't know either. You don't know if it's call or put, you don't know the spot price. If it's call, the lowest strike price is probably the best. Look here, monetary value.

 

[Jack21222]

#10 from Jimmy is wrong I think. Spin the barrel for a 1/3 chance of dying, and pull the trigger for a 1/4 chance of dying. So you pull the trigger.

I think this is correct. It can be shown this way.

1 2 3 4 + +

The numbers are the blank spaces, the +s are bullets. If you pulled the trigger on 1, you're safe to pull again. If you pulled the trigger on 2, you're safe. If you pulled the trigger on 3, you're safe. If you pulled the trigger on 4, you're dead. That's 1 in 4.

 

[MarcoD]

I am probably the only one who reads #9 as: an algorithm such that you end up either with exactly 200 or 0 in the end. Right?

 

[Jimmy Snyder]

Indeed, I was wrong about #10 the russian roulette and about #2, the die game.

 

[MarcoD]

I am not sure about the die game, it depends on how you read the question. If you get a return each round, I think the answer is seven, if you are allowed to 'modify' the outcome by throwing the die again, 3.5 should be correct.

 

[BobG]

I am probably the only one who reads #9 as: an algorithm such that you end up either with exactly 200 or 0 in the end. Right?

It doesn't say you have to bet the same amount on each game.

 

[BobG]

No, just flip twice, 2 heads is A, 1 head, 1 tail is B, 0 heads is ignored.

Good point. (Except it isn't necessarily just two flips, since 0 heads isn't counted as a flip.)

 

[MarcoD]

It doesn't say you have to bet the same amount on each game.

I know. Assuming that they won't sneek a question in there which has no simple solution. I tried the following: winning means at least 3 out of 5, which means you need a minimum of $25 to double up three times. I tried some variants, doesn't work.

 

[Jimmy Snyder]

The expected value, I guessed, is: chance you get to the 1st throw * expected return on the 1st throw + chance you get to the 2nd throw * expected return on the 2nd throw + ...

This is correct.

= 1.0 * 3.5 + 0.5 * 3.5 + 0.25 * 3.5 + ...

This is not correct.

= 7

This is correct.

The probability that the game will end after a single toss is .5 and the expected value in that case is 2, i.e. the average of 1, 2, and 3. The probability that the game will end after two tosses is .25 and the expected value is 7, i.e. the average of 4, 5, and 6 for the first toss and of 1, 2, and 3 for the second. The expected value for the game is:

\frac{2}{2} + \frac{7}{4} + \frac{12}{8} + \frac{17}{16} + ...
= \frac{2}{2} + \frac{2}{4} + \frac{2}{8} + \frac{2}{16} + ...
+ \frac{5}{4} + \frac{10}{8} + \frac{15}{16} + ...
= 2 + \frac{5}{4} + \frac{5}{8} + \frac{5}{16} + ...
+ \frac{5}{8} + \frac{10}{16} + \frac{15}{32} + ...
= 2 + \frac{5}{2} + \frac{5}{4} + ... = 7

 

[AlephZero]

I am probably the only one who reads #9 as: an algorithm such that you end up either with exactly 200 or 0 in the end. Right?

I read it as "you want to make a profit of either 200 or 0", i.e. find a hedging strategy so you end up with either 300 or 100.

 

[MarcoD]

This is correct.
The probability that the game will end after a single toss is .5 and the expected value in that case is 2, i.e. the average of 1, 2, and 3. The probability that the game will end after two tosses is .25 and the expected value is 7, i.e. the average of 4, 5, and 6 for the first toss and of 1, 2, and 3 for the second.

I am not sure you just gave an argument which is an algebraic rewording/reshuffling of my original argument. (I.e., you can add the expected value/outcomes of the turns or the outcomes of the games.)

 

[MarcoD]

Actually, I am sure. You just used a different analysis to end up with a different series to end up with the same outcome.

(It becomes a lot easier if you write down the 'probability tree.' There are more manners of defining a series on it.)

If you write down a tree, you can see you're calculating the limit of:

(\frac{1}{6} + ... + \frac{6}{6}) + \frac{3}{6}((\frac{1}{6} + ... + \frac{6}{6})+ \frac{3}{6}((\frac{1}{6} + ... + \frac{6}{6})+ ... ))

which is the fixed point of

\phi = (\frac{1}{6} + ... + \frac{6}{6}) + \frac{3}{6}(\phi)

is

\phi = \frac{7}{2} + \frac{1}{2}\phi

is

\frac{1}{2}\phi = \frac{7}{2}

is\phi = 7

 

[MarcoD]

If you write down a tree, you can see you're calculating the limit of:

(\frac{1}{6} + ... + \frac{6}{6}) + \frac{3}{6}((\frac{1}{6} + ... + \frac{6}{6})+ \frac{3}{6}((\frac{1}{6} + ... + \frac{6}{6})+ ... ))

Actually, for completeness, let's see where you're reasoning -half a chance on 1,2,3, half a chance on 4,5, 6 and repeat- ends up:

(\frac{1}{2}(\frac{1}{3} + ... + \frac{3}{3}) + \frac{1}{2}((\frac{4}{3} + ... + \frac{6}{3})+ (\frac{1}{2}(\frac{1}{3} + ... + \frac{3}{3}) + \frac{1}{2}((\frac{4}{3} + ... + \frac{6}{3})+ ... ))

(It's the same series, if you rewrite a bit, but then again.)

is the solution to

\phi = \frac{1}{2}(\frac{1}{3} + ... + \frac{3}{3}) + \frac{1}{2}((\frac{4}{3} + ... + \frac{6}{3})+ \phi)

is

\phi = 7

Beaten to death by now, I guess.

(Actually, the thing is equivalent to 50% chance on a 2, and 50% on a 5 after which you repeat the process.

\phi = \frac{2}{2} + \frac{5}{2} + \frac{1}{2}\phi
= \frac{2}{2} + \frac{7}{4} + \frac{10}{4} + \frac{1}{4}\phi
= \frac{2}{2} + \frac{7}{4} + \frac{12}{8} + \frac{15}{8} + \frac{1}{8}\phi
= \frac{2}{2} + \frac{7}{4} + \frac{12}{8} + \frac{17}{16} + \frac{20}{16} + \frac{1}{16}\phi

Which is the reverse of your argument.

Now completely and utterly beaten to death.)

(A hundred and forty one manners to write the constant 7. Sheesh.)

 

[MarcoD]

I read it as "you want to make a profit of either 200 or 0", i.e. find a hedging strategy so you end up with either 300 or 100.

Impossible, I assume five double or nothing bets can be placed, which means you cannot hold on to a 100 in case you lose all of five bets.

 

[diogenesNY]

Numbers 11 and 12 are curveballs.

#11 is _absolutely impossible_ to meaningfully answer with the information provided. There are several undefined variables, and even if one assumes that each and every other particular detail of the options in question are identical, one _might_ infer that the purchase price on the option with the higher strike price was _possibly_ lower, but even then... well... no, not really. No way to meaningfully address this question. Not at all.

#12 Another bit of misdirection. Options aren't priced that way. While some analytically guidance is taken from such things as the underlying security's volatility, timeliness, previous trading range, historical volume and changes thereof, and a variety of other factors... The actual price is arrived at by a negotiation between the underwriter of the options, usually also the seller, and the prospective purchaser. This may happen rapidly... not necessarily in person even, but it is ultimately a negotiated sale.

If the option is a market traded option, once it is trading, the market (if sufficiently liquid) determines the price... this is usually some combination of any 'in the money' value of the option (if the option is in fact in the money) plus some 'opportunity vigorish'... however the thing to keep in mind:

This is a negotiated wager between parties presumably unrelated to the company.