Quantitative Interview questions and answers

[quantyst]

Quote:
(Another interview question)

You have N cars that are all traveling the same direction on an infinitely long one-lane highway. Unfortunately, they are all going different speeds, and cannot pass each other. Eventually the cars will clump up in one or more traffic jams.

In terms of N, what is the expected number of clumps of cars?

Solution (2):

***Please see Solution (1) provided previously. It is messier and much longer.***

It is understood that although the word "jam" is used in the statement of the problem, the cars never come to a stop. What happens is that when a faster-moving car reaches a slower-moving car, then both cars move at the speed of the slower-moving car. Note that the actual speed of the cars is immaterial to the solution; what matters is that given any two distinct cars, one of them moves slower than the other.

We translate the above problem to an equivalent one as follows:

Let X(1), X(2), ...,X(N) be a sequence of random variables over the set {1,2,...,N}, with X(i) different form X(j) if i is different from j. Here X(i) represents the speed of car i, and the set {1,2,...,N} represents the speeds of the cars. We can suppose that the cars, represented by C(1),C(2),...,C(N), are in the order given and move in the East-West (Left To Right) direction. So, if X(N)=N, assuming N>1, then there will be more than one clump as none of the first (N-1) cars moving behind car C(N) can catch up with C(N) that has the greatest speed; namely N. If X(1)=N, then the number of clumps will be determined by cars C(2) through C(N) because car C(1), having the greatest speed, will sooner or later catch up with car C(2) and both will have the same speed as Car (2).

Clearly P{X(N)=N}=(1/N) and P{X(N)<N}=(N-1)/N=1-(1/N). If X(N)=N, then car C(N) will form a single-car clump by itself as none of the first (N-1) cars can catch up with car C(N). So, the total number of clumps in this situation will be 1 plus the number of clumps formed by the first (N-1) cars. If X(N)<N, then the car, say C(j) for some j, that has speed X(j)=N, will sooner or later catch up with car C(j+1), and will both have the speed of car C(j+1). In this situation, we will effectively have (N-1) cars with different speeds, and so the number of clumps will be determined by (N-1) cars.

Now let E(N) denote the expected number of clumps of N cars.

It is obvious that E(0)=0.
E(N) = (P{X(N)=N}) * E[N | X(N)=N] + (P{X(N)<N}) * E[N | X(N)<N],

E(N) = (P{X(N)=N})*(1+E(N-1)) + (P{X(N)<N})*(E(N-1)),

which can be written as

E(N) = (1/N)*(1+E(N-1)) + (1-(1/N))*(E(N-1)),

which can be simplified to
E(N) = (1/N) + E(N-1),

which of course is the Harmonic series
E(N) = (1)+(1/2)+(1/3)+...+(1/N).

 

[ngohrvinet]

Its a simple, but a nice one:
\(\sum_{k=0}^{90}sin^2(k)=?\)
k is in degrees and not radians

Nice ideal

 

[zanab]

Its a simple, but a nice one:
\(\sum_{k=0}^{90}sin^2(k)=?\)

k is in degrees and not radians

Nice ideal

What a fun problem!! We can start with a trig identity:

\( sin^2(x) + cos^2(x) = 1^2 \)

Extending that,

\( \sum_{k=0}^{90} sin^2(k) + \sum_{j=0}^{90} cos^2(j) = \sum_{i=0}^{90} 1^2 \)

By symmetry,

\( \sum_{k=0}^{90} sin^2(k) + \sum_{j=0}^{90} sin^2(j) = \sum_{i=0}^{90} 1 \)

The summation of a constant a from 0 to n is (n+1)*a,

\( 2 * \sum_{k=0}^{90} sin^2(k) = 91 \)

\( \sum_{k=0}^{90} sin^2(k) = 45.5 \)

Also, I had no idea TeX was so easy to use. I'm a little bit smitten.

 

[Vu Nguyen]

\(\sqrt{2+\sqrt{2+\sqrt{2+\sqrt{2+\dots}}}}\)
The correct answers are discussed in later posts. I haven't updated my first posted for a while.

Check your calculation. It should be
\(\ln a = \frac{1}{2} \ln (2 + a)\)
\(a^2=2+a \Rightarrow a =2\)
There are easier way to do this without using log but the idea is the same.

I'm not sure if anyone did this way yet.
Suppose the sqrt exists, then:
(a^2=2+a)
(a^2-a-2=0)
((a-2)(a+1)=0)
Thus a=2 (sqrt >= 0)

Great topic, guys! This is my first post btw.

 

[dmukhin]

... a couple of fun problems

1. I have a barrel with coffee and a cup with tea (not full). I take one spoon of coffee from the barrel and pour it into the cup with tea. Then I take a spoon of the mixture from the cup and pour it back into the barrel. Now, both the barrel and the cup have some amount of foreign liquid (tea in the barrel and coffee in the cup). Where is the volume of the foreign liquid greater?

2. A sum of four natural numbers is grater than their product. The sum of three of them is 50. Find all possible solutions.

3. The distance from A to B is 50 mi. Two cyclists start moving towards each other the first one from A moving 10 mi/h and the second one from B moving 15 mi/h. A fly started with the first one moving 100 mi/h. Then it got to the forehead of the second one turned around and moved towards the first one, got to the forehead of the first one turned around and kept moving back and forth. Finally the cyclists banged their heads and squished the fly. How many miles did the fly fly before it died.

 

[Vu Nguyen]

Funnnn indeed.

3) The fly flies a total \(\frac{50}{10+15}=2\) hours. So (2*100=200) mi.

Even better, can anyone set up the time series for this problem? :wall

 

[dmukhin]

... a couple of fun problems

1. I have a barrel with coffee and a cup with tea (not full). I take one spoon of coffee from the barrel and pour it into the cup with tea. Then I take a spoon of the mixture from the cup and pour it back into the barrel. Now, both the barrel and the cup have some amount of foreign liquid (tea in the barrel and coffee in the cup). Where is the volume of the foreign liquid greater?

2. A sum of four natural numbers is grater than their product. The sum of three of them is 50. Find all possible solutions.

3. The distance from A to B is 50 mi. Two cyclists start moving towards each other the first one from A moving 10 mi/h and the second one from B moving 15 mi/h. A fly started with the first one moving 100 mi/h. Then it got to the forehead of the second one turned around and moved towards the first one, got to the forehead of the first one turned around and kept moving back and forth. Finally the cyclists banged their heads and squished the fly. How many miles did the fly fly before it died.

Answers:

1. the same
2. 1, 1, 1, 48
3. 200

 

[drowsy]

Hi,
You have an equation:

VIII - VII = VII

How do you change one of the "sticks" to make this correct?

V would be 2 sticks and I is 1 stick.

Here is one like this from me:

Make this

III=I

an identity without moving ANY matches at all. :D
Good luck :D

 

[drowsy]

1. Find (x) if \(x^{x^{x^{\ldots}}}=2\)

4. 3 points are randomly drawn on a circle. What is the probability of them being on the same semi-circle ?

5. A unit length is broken off into 3 pieces. What is the probability of them forming a triangle ?

6. Calculate \(\sqrt{2+\sqrt{2+\sqrt{2+\sqrt{2+\ldots}}}} \)

If I were interviewing in #1 and #6 I would also ask to prove that this number exists
(just 1st year calculus...). It's easy anyways.

In #4 I got 3/4 and in #5 1/4 (did both by calculating appropriate integrals). The anwer in #5, of course, depends on how you interpret the question. In what order you break the pieces, the distributions, etc.

 

[drowsy]

Two fun ones that are both pretty doable:

1. An airplane has N seats, and N passengers are waiting to board it, not in any particular order. Miraculously, everyone is assigned to a different seat on the airplane; however, the first passenger to board is a jerk and selects a seat at random. Thereafter, passengers board one at a time according to the following rule: If his or her assigned seat is vacant, the passenger sits there; otherwise, the passenger selects a vacant seat at random.

What's the probability that the last passenger to board gets his or her assigned seat?

Ok, this one is hard. Here is how I did it:

First do it not with 100, but with N passengers for small N, N=2 and 3.
Observe that the probability is 1/2 in both cases. Then one can use math. induction:

Suppose we have N passengers now and we proved for all k<N that
the probability is 1/2. Then you proceed as follows:

The jerk has probability 1/N to take his seat. In this case everything is fine and the last guy always gets his seat.

What happens if the jerk takes a seat that belongs to k-th guy,
where 2<=k<=N-1? Then all passengers in front of the kth guy
will take their seats and upon entering the plane the kth guy "mutates"
into a "jerk". At least you can think of him that way. He will take a random seat, while "his" seat is actually #1. Hence by induction in this
case the probability of success is 1/2.

Clearly if the jerk takes the seat #100 there is no chance for the last guy.

Hence the probability is

(\frac{1}{N}+\frac{1}{2}\cdot\frac{N-2}{N}=\frac{2+N-2}{2N}=\frac{1}{2}).

 

[drowsy]

Question: 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?

Here I got

(\sum_{k=0}^{50} C^k_{100-k}).

Can this be simplified? I have no idea.

The reasoning goes as follows:

Suppose you have k 2-steps, (0\le k\le 50).
Then you have 100-2k 1-steps and 100-k steps in total.
You need to decide the positions of the k 2-blocks.
You have (C^k_{100-k}) possibilities to arrange them.
Then sum over all k.


Update:
Well, this is all correct, but you can just arrange all patterns into two groups, ending in 1 or in 2,
hence F(n)=F(n-1)+F(n-2) => Fibonacci....

 

[drowsy]

5. In a class of 250 students, on JAN 2 15% of the girls and 10% of the boys are absent. If on 100% attendance there are 10 boys. Find the percentage present?

I have no idea what you wanted to say here. Could you reword it?

 

[Shlomi]

Here I got

\(\sum_{k=0}^{50} C^k_{100-k}\).

Can this be simplified? I have no idea.

The reasoning goes as follows:

Suppose you have k 2-steps, \(0\le k\le 50\).
Then you have 100-2k 1-steps and 100-k steps in total.
You need to decide the positions of the k 2-blocks.
You have \(C^k_{100-k}\) possibilities to arrange them.
Then sum over all k.

Thats not the right approach to the question.

 

[drowsy]

Replace the # sign with the correct mathematical functions, so that all statements are accurate.

....
8 # 8 # 8 = 6
....

\(\sqrt{8 / 8 + 8}\,! = 6\)

 

[drowsy]

JP Morgan interview question for a summer analyst position.

"Imagine you are in a room. There is a door, but in order to open it, you have to insert a table-tennis ball into the hole in the door. There is a table-tennis ball in the room, but it's in a very deep hole in the ground so that you cannot reach it. Given a feather and an empty box of Kellogg's corn flakes, how would you get out of the room?"

I would pour water or just pee in the hole. Can't think of anything else.

 

[quantyst]

Jelly Beans in the Pocket!

There are two pockets, a left pocket and a right pocket. Let (L(0),R(0)) denote the initial numbers of beans in each pocket respectively. Let the sequence (L(i),R(i)), where i=1,2,3,..., denote the number of beans in left and right pockets respectively after a single bean is removed from ONLY one of the two pockets on the i-th removal. For the i-th removal of a bean, either the left pocket is selected with probability p(i) or the right pocket is selected with probability q(i), where p(i) and q(i) are given below. This process ends when an empty pocket is selected for the removal of a bean. When this happens, let X denote the number of beans in the other pocket. Find E[X].

Let a(i)={L(i-1)+1}/{L(i-1)+R(i-1)+2}, b(i)= {R(i-1)+1}/{L(i-1)+R(i-1)+2} for i=1,2,3, …

Do this problem for the following two cases:

1.p(i)=a(i), q(i)=b(i).

2.p(i)=b(i), q(i)=a(i).

For a concrete case, assume L(0)=6, R(0)=6.

 

[drowsy]

Here is a question: There is a bag with N balls numbered 1,...,N.
You pick out k balls, X_1, ..., X_k. What is the expected value of the maximum, E[max X_i, 1<=i<=k] ?

 

[drowsy]

1. Find least number n>17 such that (n^2) divides (18^n - 1).
2. Find least number n>19 such that (n^2) divides (20^n - 1).
3. Find least number n>12 such that (11^n - 2) is a prime.
4. Find least number n>24 such that (23^n - 2) is a prime.

Anybody knows how to solve this?

 

[drowsy]

Here are some more interview questions:

1. Calculate \(\int_0^{\pi/6} \sec x \, dx \).

2. A bag contains 2 black socks and some white socks. One sock (black or white) is added to the bag and after that one sock is selected randomly. The selected sock happens to be black. What is the probability that the added sock was white?

3. For what values of n is \(W^n_t \) a martingale?

4. You flip a fair coin until you get "HHH"(three heads in a row).
What is the expected number of coin flips?

 

[dmukhin]

Anybody knows how to solve this?

For #1 a solution (n) should be a multiple of 17, since \(18^n-1=(17+1)^n-1=17k+1^n-1=17k\)