Quantitative Interview questions and answers

[drowsy]

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

Huh? It is obvious that 18^n-1 is divisible by 17, but why would n^2 be divisible by 17?

 

[drowsy]

1. There are 3 computers. One always tells the truth, one always tell the opposite of the truth and the third one sometimes tells the truth, sometimes tells the opposite of the truth. We do not know which computer is the one that tells the truth, which is the one that tells the opposite of truth etc. We have only one opportunity to ask a question to one computer. Based on the answer, we want to pick the computer that sometimes tells the truth and sometimes doesn't. We do not need to find out which computer is the one that always tells the truth or which is the one that always tells the opposite of the truth. What question should we ask to one computer?

I think this is impossible.
You will have one answer yes/no(2 possibilities) and you need to choose one out of three.
Picking a non-random computer is easy though.
Maybe there was a twist, like make the computer crash with a tricky question because it does not know how to answer...
By the way, see
http://en.wikipedia.org/wiki/The_Hardest_Logic_Puzzle_Ever

 

[quantyst]

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?

Answers:

1. This is a standard calc question. The anti-derivative of sec(x) is log[sec(x) + tan(x)]. So the answer is (1/2)log(3).

2. The answer is 2/5.

The problem is equivalent to the following: Suppose there are two drawers, L and R. In drawer L there are n white socks (for some n) and 3 black socks (this would occur if a black sock is added to the bag as mentioned in the problem). In drawer R there are 2 black socks and (n+1) white socks (this would occur if a white sock is added to the bag as mentioned in the problem). Let S denote the random variable that selects either drawer L or drawer R, each with the same probability 1/2. Let X(S) denote the random variable of choosing a sock from the drawer S.

We are to compute P{S=R | X(S)=b}, where "b" denotes "black".

P{S=R | X(S)=b}=P{S=R & X(S)=b}/P{X(S)=b}. (**1**)

But P{S=R & X(S)=b}=P{X(S)=b & S=R}=P{X(S)=b | S=R}*P{S=R}=(1/2)*(2/(n+3)). (**2**)

Also

P{X(S)=b}=P{X(S)=b & (S=L or S=R)}=P{(X(S)=b, S=L) or (X(S)=b, S=R)}. (**3**)

Since the events (X(S)=b, S=L) and (X(S)=b, S=R) are mutually exclusive, then (**3**) can be written as:

P{X(S)=b}=P{(X(S)=b, S=L)} + P{(X(S)=b, S=R)}. (**4**)

But P{(X(S)=b, S=L)}=P{(X(S)=b | S=L)}*P{S=L}=(1/2)*(3/(n+3)),

and similarly P{(X(S)=b, S=R)}=P{(X(S)=b | S=R)}*P{S=R}=(1/2)*(2/(n+3)).

So, (**4**) can be written as

P{X(S)=b}=P{(X(S)=b | S=L)}*P{S=L} + P{(X(S)=b | S=R)}*P{S=R}=(1/2)*(5/(n+3)).(**5**)

By (**5**) and (**2**), we can write (**1**) as

P{S=R | X(S)=b}=P{X(S)=b | S=R}*P{S=R}/[P{(X(S)=b | S=L)}*P{S=L} + P{(X(S)=b | S=R)}*P{S=R}]= ... =2/5.

3. Not answered for now.

4. Let E denote the expectation of the number of flips before we get HHH.

Let X(i) denote the result of the i-th flip.

On the first flip:

E=1+(1/2)*[X(1)=T, in which case the process begins anew, so again we have E]+(1/2)*[X(1)=H, in which case we will stop the process if we get two consecutive Hs on the next two flips, otherwise we begin the process anew].

On the second flip:

E=1+(1/2)*E+(1/2)(1+(1/2)*[X(1)=H, X(2)=T, so the process begins anew, so again we have E]+(1/2)*[X(1)=H, X(2)=H, in which case the process will stop if we get a last H on the next flip, otherwise we begin the process anew]).

On the third flip:

E=1+(1/2)*E+(1/2)+(1/4)*E)+(1/4)*(1+(1/2)*[X(1)=H, X(2)=H, X(3)=T, so the process begins anew, so again we have E]+(1/2)*[X(1)=H, X(2)=H, X(3)=H, so the process stops, and we have zero flips from this point on].

Simplifying, we get:

E=1+(1/2)*E+(1/2)+(1/4)*E)+(1/4)*(1+(1/2)*E)+(1/2)*(0)).

Solving for E, we get: E=14.

Note: there are standard ways to do this problem. The above method is quite tedious but instructive.

 

[drowsy]

Answers:


2. The answer is 2/5.

This is done in one line using Bayes theorem.
Suppose there are x white socks.
A -- the event of adding a white sock, B -- event of picking up a black sock.
Apply Bayes' theorem:
\(P(A|B)=\frac{P(B|A)P(A)}{P(B)}=\frac{\frac{2}{x+1}\cdot\frac{1}{2}}{\frac12\cdot\frac{2}{x+1}+\frac12\cdot\frac{3}{x+1}}=\frac25.\)

Your answer to Q4 is correct, but I did not read the solution -- you appear to be using "[" and "]" in a way which is new to me.

 

[drowsy]

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

Here is a solution I know:
Denote (N_k) the expected number of coin flips to get "H" k times in a row. We are going to find a connection between \(N_k\) and \(N_{k-1}\).

Here is the equation:

\(N_k=\frac12(N_{k-1}+1)+\frac12(N_{k-1}+1+N_k)\)

Consider a sequence that ends in k-1 head for the first time.
Then the next is either "H" and we get k heads in a row, or it is a tail.
If it is a tail, then, since all flips are independent, the past does not matter and
we can expect to wait N_k flips starting from this moment to get k heads.
This is an intuitive explanation. One can prove this equation by breaking the space into events (N_{k-1}=i, N_k=j), and summing the expectation up using the above argument.


Now, we need to calculate N_1. This is easy:

\(N_1=\frac12+\frac24+\frac38+\cdots+\frac{n}{2^n}+\cdots\).

One can either write this as a sum of infinitely many geometric sums, or
calculate it using Taylor series(as the value of the derivative of some function at 1/2).
You get N_1=2. Hence N_2=6 and N_3=14.

 

[drowsy]

1. Find least number n>17 such that \(n^2\) divides \(18^n - 1\).

Well, I cannot find the smallest such number. But I can find one.
\(n=\frac{18^{17}-1}{17}\) works. Let me explain why.

All numbers that we consider are natural \((\mathbb{N})\) .

Lemma. Suppose that A mod k = 1. Then \(A^k-1\) is divisible by\ (A-1)k\).

Proof. This is easy. Just factor the thing:
\(A^k-1=(A-1)(A^{k-1}+A^{k-2}+\cdots+A^2+A+1)\),
with k terms in the second bracket. Since every power of A has remainder 1 when divided by k, the second bracket is divisible by k (it has k terms with remainder 1). Hence the whole thing is divisible by (A-1)k.


Let us now go back to the original question. Denote \(A=18^{17}\).

By the lemma \(A-1=17^2k\) for some k.
Hence A mod k = 1 and \(m=\frac{A^k-1}{(A-1)k}\) is an integer.

Take n=17k. Then

\(18^n-1=A^k-1=(A-1)k m=17^2 k^2 m = n^2m, \) since \((A-1)k=17^2k^2. \)


Hence this n works. Using the same argument, one can show that
n=17a, where a is a divisor of k, works too. As I said, this is all not a solution, since we did not prove that this number is the smallest.

 

[drowsy]

A couple of updates to my last post:

First of all, if n satisfies the question, then it has to be divisible by 17,
and 17 is the smallest prime dividing it(the proof is very cute, you need to use Fermat's little theorem).

Second, \(n=\frac{18^{17}-1}{17^2}=7563707819165039903\) is a prime number (just FYI).

http://gmplib.org/cgi-bin/gmp_calc.pl?expr=(18^17-1)%2F(17*17)

Update: So yeah, (18^17-1)/17 is the solution.
One needs to calculate ord_p(18) for different primes p dividing a solution,
where ord_p is "the multiplicative order", see
http://en.wikipedia.org/wiki/Multiplicative_order
One can argue that for the smallest prime dividing p ord_p(18)=1, hence p=17.
Then for the second smallest prime p_2 the order ends up being 17, hence p_2 is the huge prime found
above. It is also possible to show that n cannot equal 17^k, hence the smallest is (18^17-1)/17

 

[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.

So, we solved the first one. The second one has a similar solution(I suppose...),
but you need to know that
(\frac{20^{19}-1}{19^2}=14523213296398891966759)
factors into two primes as
(14523213296398891966759 = 192696104561\times 75368484119 ).

The third one was solved in 2007, see
http://www.research.att.com/~njas/sequences/A128472
the answer is n=22420 and 11^22420-2 is a prime.
When Andy posted it in May 2007 it was an open problem!
The answer to the fourth one is either unknown or some monster number too. Ufff!!!

I think I can even guess who asked these questions at an interview:Alexander Adamchuk from Chicago.

 

[radosr]

A nice probability puzzle

A fair, six-sided die is rolled repeatedly and the rolls recorded. When two consecutive rolls are identical, the process is ended. Let S denote the sum of all the rolls made. Is S more likely to be even, odd or just as likely even as odd?

 

[radosr]

puzzle

You are given 8 unit cubes such that 24 of the faces are painted blue and 24 of the faces are painted red. Prove that it is always possible to use these cubes to form a 2x2x2 cube that has the same number of blue and red unit squares on its surface.

 

[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] ?

Hint: the answer is (\frac{k}{k+1}(N+1)).
I proved this using some formula from "Heard on the street questions..." book.

 

[drowsy]

2. We buy a bag of candy. In the bag, there are 5 candies. Each candy can be one of 50 different candy types, being equally likely from each type. What is the expected number of types of candy we will have in the bag? As an example, if there are two orange candy, two apple candy and one strawberry candy in the bag, then there are 3 types of varieties.

I did not see anybody posting the answer to this question, so I will do it.

Answer: (\frac{50^5-49^5}{50^4}\approx 4.8)

The idea is to calculate this by induction on the number of candies.

Denote P_k(m) the probability to have m varieties out of k candies
and E_k the expected number of types out of k random candies.

Suppose you already picked k candies and have m different types.
Then with probability m/50 you will still have m types after k+1 steps,
or m+1 types with probability (50-m)/50.

Hence the following equation:

(P_{k+1}(m)=\frac{m}{50}P_k(m)+\frac{50-(m-1)}{50}P_k(m-1)).
Technically, this is already enough to compute the probabilities and the expectation.
But there is a shorter way:


Write the expectation (E_{k+1}=\sum_{m=1}^{k+1}mP_{k+1}(m))
and use the formula above to reduce P_{k+1} to P_k,
after some trivial simplifications you will get

( E_{k+1}=\frac{49}{50}E_k+1 ).
Clearly E_1=1. Therefore (E_5=\frac{50^5-49^5}{50^4}).

 

[drowsy]

3. X1, X2,...,Xn are independent random variables, uniformly distributed on [0,1]. What is the probability that X1+X2+...Xn<1.

This can be solved as follows: Denote by f_n(t) the probability that
X_1+...+X_n<t, where 0<t<1. f_1=t. Then you can do induction by the number of random variables.
(f_{n+1}(t)=\int_0^t f_n(t-x)\, dx)
You get f_n(t)=t^n/n!

 

[repoman]

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.

...


E(N) = (1)+(1/2)+(1/3)+...+(1/N).

Well, under your interpretation the question is equivalent to the "cannibal sharks" question, which was recently discussed in the Wilmott Brainteaser Forum.

 

[drowsy]

Here is a nice and simple question:

There is a nxn square board, each square contains "-1", except that in one corner there is a "+1". On each turn you pick a row or a column and
flip all signs in it. Is it possible to make all numbers +1?

 

[quantyst]

Here is a nice and simple question:

There is a nxn square board, each square contains "-1", except that in one corner there is a "+1". On each turn you pick a row or a column and flip all signs in it. Is it possible to make all numbers +1?

Nice question!

Just to mention the trivial case, for n=1, the answer is "yes", with the number of flips being zero.

Assume n>1.

Suppose corner (n,n) is +1. Let r(i) denote the number of times row i is flipped before all the entries of row i become +1. Likewise, let c(i) denote the number of times column j is flipped before all the entries of column j become +1. For each entry (i,j), with the exception of (n,n), we must have r(i)+c(j)=odd. In particular, we must have:

(*1*): r(1)+c(1)=odd,

(*2*): r(1)+c(n)=odd,

(*3*): r(n)+c(1)=odd,

(*4*): r(n)+c(n)=even.

Using the first three equations, it is easy to get an equation that contradicts the fourth equation.

So, the answer is "No".

Here's why:

(*1*) and (*2*) ----> 2*r(1)+c(1)+c(n)=odd+odd, so c(1)+c(n)=even.

Similarly, (*1*) and (*3*) ----> r(1)+r(n)=even.

Combining the last two equations, we get:

c(1)+r(1)+r(n)+c(n)=even, in which, c(1)+r(1)=odd, so (odd)+r(n)+c(n)=even, and so r(n)+c(n)=odd, which contradicts (*4*).

 

[drowsy]

Here is a nice and simple question:

There is a nxn square board, each square contains "-1", except that in one corner there is a "+1". On each turn you pick a row or a column and
flip all signs in it. Is it possible to make all numbers +1?

The best way to solve it is as follows:

For n=1 this is of course possible.
If n=2(or any other even number) the product of all numbers is negative.
When you flip all numbers in a column you effectively multiply by (-1)^n=1, hence the product is always negative => the answer is no.

For n>2 the answer is no because the nxn square contains a 2x2 sub-square. That's ALL! )))

 

[sudo]

I had an off-topic question.

What do you feel is the best strategy in case you are, in an interview, asked a known question?

Pretend to solve it or communicate the situation and ask for a new question.

Also, any tips for a CS grad who has an interview for a "quant-research" position in a day.

Thanks!

 

[ExSan]

m-gon, n-gon, doggone it!

quantyst wrote:

m-gon, n-gon, doggone it!
Inscribe a circle within a regular n-gon. Inscribe a regular m-gon within the circle. Find the ratio of the area of the regular m-gon to that of the regular n-gon.

From the Attached Zip File extract program POLYGON_polygon to your desktop and execute, It will display n-gon inscribed into N-Gon, the higher the n , the circle approaches

/*********  start  **************/
void POLYGON_polygon(void){
	
	print("Consider a regular n-sided polygon .....");

	char file_name [40] = "c:\\exsan\\POLYGON_polygon______0000.bmp";

	bool sign_this = 0;
	bool display = 1;
	bool save_image = 1;			
	bool sign_bg = 0;
	bool negative = 0;
	bool do_grey_scale = 0;
	char * string = "POLYGON ---> polygon";

	unsigned short side;
	
	unsigned long int rows =  601;
	unsigned long int cols =  rows;
	
	double x, y ;
	double xx, yy, xxx, yyy;

	xxx = yyy = 0;

	enum {temp, page_signature, draw_page, page_alphabet};

	unsigned long int pages = page_alphabet;

	NETPTR net;
	CELLPTR center_ptr;
	center_ptr =  NULL;

	net = net->create_exsan_net(pages, rows, cols); // grid def

	for(unsigned i = 0; i <= pages; i++)
	net->set_work_sheet(i, rows, cols);  

	if(sign_this){	
		net->set_file_image(net, page_alphabet, file_name);
		print("Master File: ", file_name);		
	}

	center_ptr = net->go_to(net, draw_page, rows/2 + 1, cols/2 + 1);

	double delta, eps = 0.0000000000001;
	unsigned long int  radius = rows / 2;

	double x_f_f, x_f, x_o;
	double y_f_f, y_f, y_o;
		
	do{	
                net->set_page_to_data(net, draw_page, black);	// reset frame
		do{
			print("\n    [5..n] Polygon Side");
			side = get_integer_pos();
			if(!side){ net->delete_exsan_net(net); return;}
		}while(side < 5 );

		if(side > 55) side = 55;  // visually makes no difference 
		delta = pipi/(double)side;  // pipi = 2*pi
		x_o = center_ptr->get_col() + radius;
		y_o = center_ptr->get_row()  ;

		for(double theta = pipi/(double)side; theta <= pipi; theta += delta){
			x_f = cos(theta); if(x_f < eps && x_f > -eps) x_f = 0; //print(x_f);
			y_f = sin(theta); if(y_f < eps && y_f > -eps) y_f = 0; //print(yy);
			x_f *= radius;  x_f += center_ptr->get_col();  if(x_f - int(x_f) >= .5 ) x_f = int(x_f) + 1; else x_f = int(x_f);
			y_f *= radius;  y_f += center_ptr->get_row();  if(y_f - int(y_f) >= .5 ) y_f = int(y_f) + 1; else y_f = int(y_f);
			
			net->draw_line(net, draw_page, x_o, y_o, x_f, y_f, 167);  // 167  grey color id, external polygon 							

			x_f_f = cos(theta + delta); if(x_f_f < eps && x_f_f > -eps) x_f_f = 0; //print(x_);
			y_f_f = sin(theta + delta); if(y_f_f < eps && y_f_f > -eps) y_f_f = 0; //print(yy);
			x_f_f *= radius;  x_f_f += center_ptr->get_col();  if(x_f_f - int(x_f_f) >= .5 ) x_f_f = int(x_f_f) + 1; else x_f_f = int(x_f_f);
			y_f_f *= radius;  y_f_f += center_ptr->get_row();  if(y_f_f - int(y_f_f) >= .5 ) y_f_f = int(y_f_f) + 1; else y_f_f = int(y_f_f);
			
			net->draw_line(net, draw_page, x_o, y_o, x_f_f, y_f_f, white);  // internal polygon
			
			x_o = x_f;
			y_o = y_f;				
		}

		net->display_image(net, draw_page, page_signature, string, file_name, sign_this, display, sign_bg, save_image, negative, do_grey_scale);
				
		print("Another POLYGON ---> polygon");		

	}while(get_yes_no());

	net->delete_exsan_net(net);  // freeing memory

	return;
}
/*********  end  POLYGON_polygon **************/

Download ExSan
.
.
.

 

[thegreek]

I did not see anybody posting the answer to this question, so I will do it.

Answer: (\frac{50^5-49^5}{50^4}\approx 4.8)

The idea is to calculate this by induction on the number of candies.

Denote P_k(m) the probability to have m varieties out of k candies
and E_k the expected number of types out of k random candies.

Suppose you already picked k candies and have m different types.
Then with probability m/50 you will still have m types after k+1 steps,
or m+1 types with probability (50-m)/50.

Hence the following equation:

(P_{k+1}(m)=\frac{m}{50}P_k(m)+\frac{50-(m-1)}{50}P_k(m-1)).
Technically, this is already enough to compute the probabilities and the expectation.
But there is a shorter way:


Write the expectation (E_{k+1}=\sum_{m=1}^{k+1}mP_{k+1}(m))
and use the formula above to reduce P_{k+1} to P_k,
after some trivial simplifications you will get

( E_{k+1}=\frac{49}{50}E_k+1 ).
Clearly E_1=1. Therefore (E_5=\frac{50^5-49^5}{50^4}).

I have approached the problem a little differently and got a different(although similar) result.

Answer: 4.63

There are 7 distinct ways of candies arrangements

1) all 5 candies are of different type (eg. abcde)
2) 4 candies are of different type, 1 of which is duplicate (eg. aabcd)
3) 3 candies are of different type, 2 of which are duplicate (eg. aabbc)
4) 3 candies are of different type, 1 of which is triple (eg. aaabc)
5) 2 candies are of different type, 1 of which is dup and the other triple (eg. aaabb)
6) 2 candies are of different type, 1 of which is quadriple (eg. aaaab)
7) all 5 candies are of same type (eg. aaaaa)

Lets denote
({n \choose k}\ =\ \frac{n!}{k!(n-k)!})


We can count the combinations of all the types as:

(1)\ abcde\ [5\ types]\ \longrightarrow\ {50 \choose 5})

(2)\ aabcd\ [4\ types]\longrightarrow\ 5{50 \choose 4})

(3)\ aabbc\ [3\ types]\longrightarrow\ {3 \choose 2}{50 \choose 3})

(4)\ aaabc\ [3\ types]\longrightarrow\ 3{50 \choose 3})

(5)\ aaabb\ [2\ types]\longrightarrow\ 2{50 \choose 2})

(6)\ aaaab\ [2\ types]\longrightarrow\ 2{50 \choose 2})

(7)\ aaaaa\ [1\ type]\longrightarrow\ {50 \choose 1})


By # of types the combinations then are:

(5\ types\ \longrightarrow\ {50 \choose 5})

(4\ types\ \longrightarrow\ 4{50 \choose 4})

(3\ types\ \longrightarrow\ 6{50 \choose 3})

(2\ types\ \longrightarrow\ 4{50 \choose 2})

(1\ type\ \longrightarrow\ {50 \choose 1})

(TOTAL:\ \longrightarrow\ {50 \choose 5}+4{50 \choose 4}+6{50 \choose 3}+4{50 \choose 2}+{50 \choose 1}\ =\ {54 \choose 5}*)
*This can be proven

Finally, the average number of types is
(E[num\ of\ types]\ =\ \frac{5*{50 \choose 5}+4*4{50 \choose 4}+3*6{50 \choose 3}+2*4{50 \choose 2}+1*{50 \choose 1}}{{54 \choose 5}})

This, surprisingly and perhaps coincidentally, simplifies after some calculations to
(E[num\ of\ types]\ =\ \frac{5^3}{3^3}\ \approx\ 4.63)

opinions?

btw this is my first post!!