Quantitative Interview questions and answers

[exenGT]

In my opinion, the answer to question #5 should be \(P\approx 38.6\%\).
The reason is as follows:

To make a triangle, any of the three segments' lengths must not be greater than the sum of the two others. So let's first consider segment \(a\). Apparantly, \(a<1/2\), so that's a 50% probability.

Similarly, \(b<1/2\) and \(c<1/2\). But \(b+c=1-a\), so \(b,c>\frac{1}{2}-a\). It's easy to see that by letting \(\frac{1}{2}-a<b<1/2\), \(c\) automatically falls in the same range. Thus for a given \(a\), the probability to choose a proper \(b\) (and hence \(c\)) is given by \(\frac{1/2-(1/2-a)}{1-a}=\frac{a}{1-a}\).But \(a\) can range from 0 to 1/2, as previously shown. So the total (conditional) probability that \(a,b,c\) form a triangle is
\(\int_0^{1/2} \frac{a}{1-a} da \div 50\%= (-\frac{1}{2} + \ln 2) \times 2 \approx 38.6\%\).

 

[Andrew Hess]

A stair of 100 steps. You can either climb either one step or two steps but no more each time and you can walk up entire stair any way you like with rule above obeyed. How many possible combinations of ways to finish the walk?

Let F(N) = the number of ways to get to step N

for your final step to arrive at step N, you can either take 1 or 2 steps (depending on where you are)

F(N) = F(N-1) + F(N-2) // Looks a lot like a fibonacci sequence doesn't it?

So for 100 steps, the answer is:

F(100) = F(99) + F(98) = Fib(100) // it's a giant number (354224848179261915075)

 

[rothmann]

Two players toss different (unbiased) coins at each step of a game. Player A wins if he gets a H before player B gets two H in a row. What is the probability for this to happen?

 

[jeeudr]

Two players toss different (unbiased) coins at each step of a game. Player A wins if he gets a H before player B gets two H in a row. What is the probability for this to happen?

The expected number of rolls to get two H in a row is 6 [1].
The probability that player A does not get any H within the first 5 throws = 1/2^5 = 1/32
so the probability that player A wins = 31/32

[1] http://people.ccmr.cornell.edu/~ginsparg/INFO295/mh.pdf

 

[aaronhotchner]

Your answer might be right. I haven't tried to solve the problem yet. But I am troubled by the methodology. I can create an event with an expected number of trials equal to 6 by doing the following:
50% of the time it takes 2 flips to get 2 heads
50% of the time it takes 8 flips to get 2 heads
There are no other ways to get 2 heads

Obviously this is not an unbiased coin, and maybe your answer works for the unbiased coin, but comparing a probability to an expected number of trials is raising a huge red flag in my mind.

 

[AndrewChang]

The expected number of rolls to get two H in a row is 6 [1].
The probability that player A does not get any H within the first 5 throws = 1/2^5 = 1/32
so the probability that player A wins = 31/32

[1] http://people.ccmr.cornell.edu/~ginsparg/INFO295/mh.pdf

your reasoning isn't correct

Look at the problem as a markov chain problem.

let X_i denote the probability player A wins from state i and X_0 is the starting state where neither player has flipped a head yet, X_1 is the state where player B's previous flip was a head and player A has not flipped a head, X_2 is the state where player B flipped 2 heads in a row before player A and X_3 be player A flipped a head before player B flipped 2 heads.

now from X_0, you can go to X_1, and X_3 only.
from X_1, you can go to X_0, X_1, and X_3.
X_3 = 1 and X_2 = 0 obviously. now, putting this down in to equations,

X_0 = .5 * X_1 + .5 * X_3
X_1 = .5 X_2 + .25 X_3 + .25 X_0
X_2 = 0
X_3 = 1
two non parallel linear equations with 2 unknowns. Can be solved, and you find that X_0 = 5/7, which intuitively makes much more sense than 31/32.

using same concept, you can solve what is on average how long will this game take.

 

[aaronhotchner]

I interpret "player A wins if he gets a H before player B gets two H in a row" to mean that player B wins on a "tie," e.g. player A hits his first head on turn 3 and player B hits his second consecutive head on turn 3.

When I simulate it I get a probability of 0.8180 +/- 0.0013.

I feel like it must be higher than 5/7 intuitively. A has a 50% probability of winning immediately, and a 68.75% chance of winning in two turns (50% chance of immediate win + 50% chance to miss the immediate win * 50% to hit the H on the second flip * 75% chance B did not hit HH).

 

[AndrewChang]

I interpret "player A wins if he gets a H before player B gets two H in a row" to mean that player B wins on a "tie," e.g. player A hits his first head on turn 3 and player B hits his second consecutive head on turn 3.

When I simulate it I get a probability of 0.8180 +/- 0.0013.

I feel like it must be higher than 5/7 intuitively. A has a 50% probability of winning immediately, and a 68.75% chance of winning in two turns (50% chance of immediate win + 50% chance to miss the immediate win * 50% to hit the H on the second flip * 75% chance B did not hit HH).

sorry, i made a mistake. the markov chain was incorrect. X_0 = 9/11 which is .818181. I fixed the equations below and you can just solve it and show it is true. logic is still correct

X_0 = .25 * X_1 + .25*X_0 + .5 * X_3
X_1 = .5 X_2 + .25 X_3 + .25 X_0
X_2 = 0
X_3 = 1

 

[xcx]

7. There are 14 identical-looking balls. 13 of them have the same weight while one of them is heavier than the rest. What is the minimum times you can weight to identify the heaviest ball ? How do you generalize for n balls ?

The minimum is 2.

5 vs 5 + (4 remaining)
a. they are same (1 move)

• add one to each side from 4
• if different - then have final answer (total 2 moves)
  • if same add one each side - have final answer (total 3 moves)###

b. one side (of 5) is heavier
1 vs 1 (3 remaining)***

• if different have final answer (total 2 moves)
• if same add one each side (1 odd-ball remaining)
  • if different we have final answer (total 3 moves)
  • if same then it is the odd left over - we have final answer (3 moves) no need to measure.

So we have tested all in 3 moves or less.
The minimum being 2. (4 balls identified in 2 moves)

***did you see what I did there?
By doing 1 vs 1 instead of the seemingly obvious 2 vs 2 (plus 1 left over)
we can identify potentially 40% of remainder (between 2 balls) immediately rather than than only 20% (the single spare one) as in the 2 vs 2 case...
### see half move solution further below

You could do 7 vs 7
One or other is heavy (1 move)

• split heavy stack into 3 vs 3 plus remainder 1
  • if same - have answer its the remainder (2 moves.)
  • if different we have one of 3 balls left
  • 1 vs 1
    • if same then odd ball is heavy - final answer (3 moves)
    • if different - final answer (3 moves)

So minimum is again 2. (but only 1 ball can be identified in 2 moves)

Of course if you were really thinking outside the box....
You could simply put 1 on each side of the scale (from 14) and if they are different =1 move.
Which is really the answer - the question doesn't require you to find the best algorithm...

You would get my vote if you told me that in an interview.

 

[xcx]

7. Assume that you measure with a two-dish mass balance. We should observe that we always weigh even number of balls on the balance to compare the weight of both sides. I think it's a standard question.
...
In conclusion, the minimum number is \(\max\{3,3,3\} = 3\) (why maximum is used because it is for the worst case).

It can be done in minimum of two weighings.
Also you can effectively weigh 3 at a time. If two on the scale are equal then the thrid is different.

Suppose \(n =4\). If we weigh only 2 balls (one ball each side) and these 2balls are equal, we still have to determine the heavier ball by measuring the other two balls once more. So we should measure 4 balls altogether, and this eliminates two balls one side after the first measurement, and then obtain the heavier ball in the second. So in either case the minimum number of measurements is 2, and we are sure this is the minimum.

No, the minimum for N=4 is 1.
Put one on each side 50% chance of immediate answer.
If not add the second two balls one each side, ok this takes 1 more weighing but the question was what is the minimum. If you found it on first move you wouldn't do anymore...

In fact, being anal about it, if we didn't find it on the first we could do it in only 1/2 move later...
Put one on each side - they are the same 1 move.
Swap only one ball on the scale for one of the two remaining (only 1/2 move) if it is the same then the heavier is the remaining one, or the heaviest on the scale.

 

[aaronhotchner]

The question is asking the minimum number of measurements to always identify the odd ball. You can always do it in 3 moves.

 

[xcx]

Yes, and mine always does it in 3, or less.
And the minimum is 2, 28% of the time...[correction 43% of time]

If reducing the minimum came at the cost of increasing the number of tests (>3) in the worst case then I would agree it isn't a valid answer. But this optimization comes for free.

Some people would pay money for optimizations like that.

If the best you can come up with is 3 which works up to (at least) 27 balls then its hardly a quant question.

• 9vs9 (9 over)
• one set of 9 is heavy - its either on the scale or not
• break it into 3 vs 3 (3 over)
• one set of 3 is heavy
• 1 vs 1 (one over) - (3 moves)

Generalized solution something like takes MAXIMUM x moves for N balls where 3^(x-1) < N <= 3^x (but for some non worst cases it can be less, as low as 1 move)

 

[aaronhotchner]

If you allow for a chance to be wrong, the answer is always 1 -- you pick a ball randomly, and either you're right (good job!) or you're not (more likely). If I was interviewing someone and they answered 1, I would show them the door.

 

[xcx]

If you allow for a chance to be wrong, the answer is always 1 -- you pick a ball randomly, and either you're right (good job!) or you're not (more likely). If I was interviewing someone and they answered 1, I would show them the door.

Yeah, ok.
Well, after thinking about it more, no. For 14 yes, 2 move minimum, but for some cases (N must be odd, but not all N <27 in this example) it is possible that one move solution is the MINIMUM. e.g 15 balls - do as 7vs 7 but if the 15th is the heavy one you will know immediately. You will look like a right dick in the interview if you keep weighing balls after you have already found the heavy one -good luck explaining why the minimum number of weigh-ins is 3 when you actually found it in 2. Yes of course it isn't going to happen every time, but the question asks for the minimum.

I still maintain that the question asks for the minimum, and this method leaves only 4 or 5 untested (out of 14) in one move. One move later you have tested 2/4 or 2/5 and only if the odd ball was one of 8/14 positions (57%) at the beginning does it take a total of 3 moves.

If you could tell your boss that could save nearly 30% the time/effort/money (assuming a weighing costs some time effort or money or all three) in 43% of the (6/14) trials compared to the current way of doing things.. you'd be looking for a bonus.

Or I could claim that my tests may take 50% longer (3 days) 57% of the time (43% take 2 only days) , but your test take 50% longer (3 days ) 100% of the time!

 

[xcx]

Yes, and mine always does it in 3, or less.
And the minimum is 2, 28% of the time...

Correction 2 moves 43% of trials.

5 5 4
o o o
o o o
o o x
x x x
x x

x = Positions that heaviest ball can be identified in 2 moves.
o = takes 3 moves
There are 6 two move locations = 43%
There are 8 three move locations =57%

 

[xcx]

Correct. Since the sides are from a unit length, we can calculate that any side of the triangle must be strictly less than 1/2. The prob that the length of each stick being less than 1/2 is 50% and this condition must hold for all three of them. Hence I have 1/8

.

1/8 seems too small.

Remember there are only 2 breaks to make 3 pieces.
Both breaks have to happen on the same half of the stick to fail to make a triangle - thus leaving one bit >1/2L.
So it is 1/2 * 1/2
=1/4

Addendum: I just found this- http://math.ucsd.edu/~wgarner/reference/math181c_fa09/handouts/handout3.pdf
Addendum2: seems I got the right answer the wrong way.

 

[Hi Rez]

Greetings everyone,

Here is a question I stumbled upon, it sounds like finite automata and generating functions will be involved but I do not have a solution:
How many times would you expect to see the pattern HHHHHHTTTTTT (6 H's 6T's) in 1,000,000 coin tosses?

It has been my experience that the easier the problem statement, the harder the question really is.
Thanks in advance.

 

[Karth]

Greetings everyone,

Here is a question I stumbled upon, it sounds like finite automata and generating functions will be involved but I do not have a solution:
How many times would you expect to see the pattern HHHHHHTTTTTT (6 H's 6T's) in 1,000,000 coin tosses?

It has been my experience that the easier the problem statement, the harder the question really is.
Thanks in advance.

Good one! This problem is actually a lot easier than it seems - no automata or generating functions needed. I believe that the answer is * (1000000 - 12) / 2^12, which is about 244.14. Here's the logic I went through -- seems a bit complex, but once you get the hang of it, it should be possible to come up with this pretty quickly (< 10 seconds).

Define the random variables X1, X2, ..., X_{1000000 - 12} where Xi is a random variable which takes on the value 1 if the substring i, i+1, i+2, ..., i + 11 is equal to HHHHHHTTTTTT and 0 otherwise. Note that E[X1] = E[X2] = ... = E[999988] = 1 / 2^12. We are simply trying to compute E[X1 + X2 + ... + X999988]. By linearity of expectation, this is just 999988 / 2048, which is roughly 244.14.

Problems that involve expected value which seem intrinsically difficult can usually be solved via linearity of expectation. That is, if we have some random variables X1, X2, X3, ..., Xn, then we have that E[X1 + X2 + ... + Xn] = E[X1] + E[X2] + ... + E[Xn]. The best part is that this is true regardless of how correlated X1 through Xn are to each other -- we could literally have X1 = X2 = ... = Xn and this would be true, or have X1 ... Xn be independent and this would be true! The hard part about these problems involves (1) figuring out how to break the problem down into the random variables, (2) determining the probability distributions underlying the random variable, and (3) figuring out the values to assign to the random variable.

We can claim something stronger by the above argument -- say that we had some arbitrary pattern of size L. We don't care about what the actual pattern is. How many times could we expect to see that pattern in N coin tosses? By the same logic, the answer must be (N - L) / 2^N. In our case, we have N = 1000000 and L = 12.

EDIT: 2^12 = 4096 and not 2048, oops. Thanks to Hi Rez for catching this!

 

[Hi Rez]

Thanks for looking into this.
But:
Aren't the rv's Xi and Xi+1 dependent: if Xi is the beginning of the pattern then Xi+1 cannot be the beginning of the pattern (Xi = 1 => Xi+1 = 0).
Also, 2^12 = 4096, not 2048.
Again, thanks for taking the time to look into this.

 

[Karth]

You're welcome!

It's ok that the rv's are dependent. Concretely, the variables Xi and Xj are dependent if and only if |i - j| <= 11 in our case. Linearity in expectation doesn't care about this, though. It doesn't matter what dependency structure the Xi's have, we still have that E[X1 + ... + Xn] = E[X1] + ... + E[Xn].

And oops! You're right. It's 4096, not 2048. I'll edit my post to reflect this. By the way, if you don't believe the argument, try running the following code (C++) which simulates the experiment.

#include <iostream>
#include <stdlib.h>

bool array_eq(int* a, int* b, int lo_a, int hi_a, int lo_b, int hi_b) {
for (int i = lo_a; i < hi_a; ++i) {
if (a != b[lo_b + i - lo_a]) {
return false;
}
}
return true;
}

int trial() {
const int n = 1000000;

// Initialize trials
int trials[n];
for (int i = 0; i < n; ++i) {
trials = rand() % 2;
}

// Pattern
int pattern[] = {1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0};

// Run the count
int count = 0;
for (int i = 0; i < n - 12; ++i) {
count += array_eq(trials, pattern, i, i + 12, 0, 12);
}

return count;
}

int main() {
int n_trials = 1000;
int average = 0;
for (int i = 0; i < n_trials; ++i) {
average += trial();
}
std::cout << "Expectation: " << 1.0 * average / n_trials << std::endl;
}