Quantitative Interview questions and answers

[glkev]

I should have revise the boundary, when N = 1, it's 0 cut; when N = 2, it's 1 cut with 1, 1; when N = 3, it's 1 cut with 1, 2. And here's the application of my iteration:

Assuming N = 23,

1. N = 2Sk -1, we have Sk = 12
2. Now N becomes 23 - 12 = 11, appy N = 2Sk - 1, we have Sk = 6
3. Now N becomes 11 - 6 = 5, apply N = 2SK - 1, we have Sk = 3
4. N becomes 5 - 3 = 2, then we have 1, 1 (boundary)

so the cut is 1, 1, 3, 6, 12 for 23 gold.

 

[Prateek Bhatia]

You've got someone working for you for N days. You own a gold chain of N rings to be paid as compensation to the worker. The gold chain consists of N sequentially connected equal rings with two free ends. You must remit the worker one gold ring at the end of every day for N days. You are only allowed to make MINIMAL number of cuts in the gold chain. How do you EACH DAY pay your worker?

So, what is the minimal number of cuts you need to make in the gold chain, where in the gold chain are these cuts made, and how are the payments made?

Note that a cut ring is equal in value to one that is not cut. For an example to understand this problem better, assume N=7. The minimal number of cuts to be made is one and that occurs on the third ring as follows: 2+1+4=7. So, on the first day, you pay out 1 (the cut) ring. On the second day, you pay out the piece consisting of two connected rings and in return get back the single (cut) ring. On the third day, you pay out the single ring. On the fourth day, you pay out the piece consisting of 4 connected rings and in return you get beck the rings held by the worker. For the remaining days you give out the three rings as before.



Another example: N=23



Solution: 3+1+6+1+12=23.

This problem is similar to the more general one with coins wherein you are asked to find what minimum no. of coins you will need to be able to pay any amount up to a certain number (assuming you can have coins of any denomination of course).

The correct answer (I think) involves the power series of two. You always cut the chain in powers of two. You make pieces of 1,2,4 rings and so on. and the last piece will be whatever is remaining. For 23 you will make pieces of 1,2,4,8 and 8 with which you will be able to pay all amounts.

Say you have a piece of 1 and 2. With that you can pay any amount up to 3.

Now you also want to be able to pay 4. So you add a piece of 4 rings.
With this you can pay any amount till 4+3=7. Before you could pay any amount till 3 and now you can this any amount till 3 to the 4ring piece and pay any amount till 7.

We have reached 7. Now you want to able to pay 8. So you cut a piece of 8. With this you can pay any amount till 15. ( earlier we could pay anything up to 7, now with addition of 8 we can we can pay till 8+7=15)

... and so on till the last remaining piece is less than the next power of 2.

The reason it comes to powers of 2 is because the sum of powers of 2 till n is one less than 2 raised to n+1 ( which is the next amount we want to be able to pay after we have managed till 2^0 + 2^1 + ... 2^n)

The same reasoning is what gives the answer 1,1,3,6,12. Except I'm starting with 1 and 2 which I think is a better thing to do because with 1 and 1 you can pay up to 2 but with 1 and 2 you can pay up to 3 which is more efficient.

Also say the amount is 31. The suggested method gives 1,1,3,6,12 and 8. which is 6 cuts. This method of powers of two gives 1,2,4,8 and 16 which is 5 cuts.

Let me know what you think. I haven't tested my answer exhaustively as is my habit.

 

[quantyst]

Gold Chain Mystery Revealed!

Problem:

You've got someone working for you for N days. You own a gold chain of N rings to be paid as compensation to the worker. The gold chain consists of N sequentially connected equal rings with two free ends. You must remit the worker one gold ring at the end of every day for N days. You are only allowed to make MINIMAL number of cuts in the gold chain. How do you EACH DAY pay your worker?

So, what is the minimal number of cuts you need to make in the gold chain, where in the gold chain are these cuts made, and how are the payments made?

Note that a cut ring is equal in value to one that is not cut. For an example to understand this problem better, assume N=7. The minimal number of cuts to be made is one and that occurs on the third ring as follows: 2+1+4=7. So, on the first day, you pay out 1 (the cut) ring. On the second day, you pay out the piece consisting of two connected rings and in return get back the single (cut) ring. On the third day, you pay out the single ring. On the fourth day, you pay out the piece consisting of 4 connected rings and in return you get beck the rings held by the worker. For the remaining days you give out the three rings as before. Another example: A gold chain of N=23 rings has solution: 3+1+6+1+12=23.



Solution:

Let x denote the number of single cut rings. So for the first x days you will give out a single cut ring a day. Come day (x+1), what will you give out? Obviously you will give out a subchain consisting of (x+1) connected rings and in return you will get the x single rings back. Now for the next x days you will give out a single cut ring a day. So, on day (2x+1) you will give out the last single cut ring in your possession. So, what will you give out on day (2x+2)? Obviously you will give out a subchain consisting of (2x+2) connected rings and in return you will get back a mix of (2x+1) rings. So, for the next (2x+1) days you will give out all this mix of (2x+1) rings just like before, by which time the worker will have accumulated a mix of (4x+3) rings. But on day (4x+4) you will give out a subchain consisting of (4x+4) connected rings and in return receive the worker's mix of (4x+3) rings. So, continuing in this fashion, what will you give out for the next (4x+3) days? Obviously you will give out the mix of (4x+3) rings, by which time the worker will have accumulated a mix of (8x+7) rings. So, on day (8x+8) you give out a subchain of (8x+8) connected rings and in return get back the mix of (8x+7) rings. This pattern continues until your last remaining subchain of connected rings is less than or equal to all that the worker will have accumulated.


So, here are the subdivisions of the chain of N connected rings:


x single cut rings,


a subchain of (x+1) rings,


a subchain of (2x+2) rings,


a subchain of (4x+4) rings,


a subchain of (8x+8) rings,

.
.
.
.
a subchain of \([2^k]x+[2^k]\) rings, (where k is an 'appropriate' number)


and whatever is 'left over'.



For a given x, what is the maximum value of N?


Answer: Since we will have x single rings, then N is maximum when the gold chain of N rings can be broken down as follows:


S(x)=(x+1)+1+(2x+2)+1+(4x+4)+1+(8x+8)+1+....+1+([2^x]x+[2^x], (**^**)


where the 1's add up to x.


Simplifying, we get S(x)=-1+(x+1)*(2^(x+1)) .


So, if S(x-1) < N <= S(x) , then we will have x single rings to begin with. Thereafter the pattern is identical to the discussion given above.


For example, for N=7, the only integer x that satisfies the inequality S(x-1) < N <= S(x) is x=1, as S(1-1)=S(0)=1 and S(1)=7, and S(1-1)=1<N=7<=S(1)=7.


For N=17, the only integer x satisfying the inequality S(x-1) < N <= S(x) is x=2. Similarly, for N=23, the only integer x satisfying the inequality S(x-1) < N <= S(x) is x=2. For N=24, the only integer x satisfying the inequality S(x-1) < N <= S(x) is x=3.


Without getting into a detailed proof, we can tell that the inequality S(x-1) < N <= S(x) gives a minimal x because of the way S(x) was determined. Recall (**^**) gives the largest value of N if we begin with x single rings. Suppose y<x and y represents a minimal number of single cut rings for an N-ringed gold chain, given that N satisfies the inequality S(x-1) < N <= S(x). A little bit of thought might convince us that this cannot be! So, x must be minimal.

 

[glkev]

1. define F(n, k) as the way to put n mathematicians in k rooms with at least 1 M in a room (so for n < k, F(n, k) = 0)
2. F(n, 1) = 1; F(k, k) = k!;
3. F(n, k) = C(n, 1)*F(n-1, k-1) + C(n, 2)*F(n-2, k-1) + .. C(n, i)*F(n-i, k-1) + ... + C(n, n - k + 1 )*F(k-1, k-1); C(n, i)*F(n-i, k-1) means choose i from n, and put them into room 1, and put the rest of n-i mathematician into k-1 rooms
4. computing algorithm to iterate the solution

 

[Prateek Bhatia]

Problem:

You've got someone working for you for N days. You own a gold chain of N rings to be paid as compensation to the worker. The gold chain consists of N sequentially connected equal rings with two free ends. You must remit the worker one gold ring at the end of every day for N days. You are only allowed to make MINIMAL number of cuts in the gold chain. How do you EACH DAY pay your worker?

So, what is the minimal number of cuts you need to make in the gold chain, where in the gold chain are these cuts made, and how are the payments made?

Note that a cut ring is equal in value to one that is not cut. For an example to understand this problem better, assume N=7. The minimal number of cuts to be made is one and that occurs on the third ring as follows: 2+1+4=7. So, on the first day, you pay out 1 (the cut) ring. On the second day, you pay out the piece consisting of two connected rings and in return get back the single (cut) ring. On the third day, you pay out the single ring. On the fourth day, you pay out the piece consisting of 4 connected rings and in return you get beck the rings held by the worker. For the remaining days you give out the three rings as before. Another example: A gold chain of N=23 rings has solution: 3+1+6+1+12=23.



Solution:

Let x denote the number of single cut rings. So for the first x days you will give out a single cut ring a day. Come day (x+1), what will you give out? Obviously you will give out a subchain consisting of (x+1) connected rings and in return you will get the x single rings back. Now for the next x days you will give out a single cut ring a day. So, on day (2x+1) you will give out the last single cut ring in your possession. So, what will you give out on day (2x+2)? Obviously you will give out a subchain consisting of (2x+2) connected rings and in return you will get back a mix of (2x+1) rings. So, for the next (2x+1) days you will give out all this mix of (2x+1) rings just like before, by which time the worker will have accumulated a mix of (4x+3) rings. But on day (4x+4) you will give out a subchain consisting of (4x+4) connected rings and in return receive the worker's mix of (4x+3) rings. So, continuing in this fashion, what will you give out for the next (4x+3) days? Obviously you will give out the mix of (4x+3) rings, by which time the worker will have accumulated a mix of (8x+7) rings. So, on day (8x+8) you give out a subchain of (8x+8) connected rings and in return get back the mix of (8x+7) rings. This pattern continues until your last remaining subchain of connected rings is less than or equal to all that the worker will have accumulated.


So, here are the subdivisions of the chain of N connected rings:


x single cut rings,


a subchain of (x+1) rings,


a subchain of (2x+2) rings,


a subchain of (4x+4) rings,


a subchain of (8x+8) rings,

.
.
.
.
a subchain of ([2^k]x+[2^k]) rings, (where k is an 'appropriate' number)


and whatever is 'left over'.



For a given x, what is the maximum value of N?


Answer: Since we will have x single rings, then N is maximum when the gold chain of N rings can be broken down as follows:


S(x)=(x+1)+1+(2x+2)+1+(4x+4)+1+(8x+8)+1+....+1+([2^x]x+[2^x], (**^**)


where the 1's add up to x.


Simplifying, we get S(x)=-1+(x+1)*(2^(x+1)) .


So, if S(x-1) < N <= S(x) , then we will have x single rings to begin with. Thereafter the pattern is identical to the discussion given above.


For example, for N=7, the only integer x that satisfies the inequality S(x-1) < N <= S(x) is x=1, as S(1-1)=S(0)=1 and S(1)=7, and S(1-1)=1<N=7<=S(1)=7.


For N=17, the only integer x satisfying the inequality S(x-1) < N <= S(x) is x=2. Similarly, for N=23, the only integer x satisfying the inequality S(x-1) < N <= S(x) is x=2. For N=24, the only integer x satisfying the inequality S(x-1) < N <= S(x) is x=3.


Without getting into a detailed proof, we can tell that the inequality S(x-1) < N <= S(x) gives a minimal x because of the way S(x) was determined. Recall (**^**) gives the largest value of N if we begin with x single rings. Suppose y<x and y represents a minimal number of single cut rings for an N-ringed gold chain, given that N satisfies the inequality S(x-1) < N <= S(x). A little bit of thought might convince us that this cannot be! So, x must be minimal.

Lets take the case of N=31 which I had described earlier.
In the above case with the function of S(x) we have
S(0)=1
S(1)=7
S(2)=24
S(3)=64

So for N=31 we get x=3 as per the inequality stated above.

So we have 3 single cut,
and we will have a subchain of (x+1)=4 rings
and we will have a subchain of (2x+2)=8 rings
and we will have a subchain of (4x+4)=16 rings

so we have 1+1+1+4+8+16=31
That is 6 pieces and needs 5 cuts.

We can do it in 5 pieces and 4 cuts as I had posted earlier using powers of 2
1+2+4+8+16=31 in powers of 2.

So it doesn't seem to work for N=31

As I said earlier, its inefficient to use more than one single cuts.

Its either this or I'm misunderstanding what you are saying. Also the example in the question stated

"For an example to understand this problem better, assume N=7. The minimal number of cuts to be made is one and that occurs on the third ring as follows: 2+1+4=7."

Isn't the no. of cuts made in this case two (1+2+4) - 3 pieces means two cuts. Either this is a simple typo or I am not getting something-may be you are folding the chain and then cutting or something, but that would open another pandora's box! (for me at least)

 

[quantyst]

WHAT is a chain of rings?

WHAT is a chain like?

Why don't you get a chain (with two free ends) and horizontally lay it down in front of you and ask yourself what happens if you cut a middle ring. The answer is: you get three separate pieces: the cut ring, the portion to the left of the cut ring, and the portion to the right of the cut ring. A cut in a ring not only releases that cut ring from other parts of the chain, but also releases whatever subchain was connected to that cut ring before the ring was cut.

So, when you cut the third ring (from the left) of a 7-ringed chain, you get the cut ring, the 2-ringed subchain to the left of the cut ring, and the 4-ringed subchain to the right of the cut ring. That is, 2+1+4=7, which has only 1 cut. Or, 3+1+6+1+12=23, which has only 2 cuts.

Please get a chain in front of you. That'll do wonders for you!

 

[quantyst]

Prateek Bhatia wrote:

" So for N=31 we get x=3 as per the inequality stated above.

So we have 3 single cut,
and we will have a subchain of (x+1)=4 rings
and we will have a subchain of (2x+2)=8 rings
and we will have a subchain of (4x+4)=16 rings

so we have 1+1+1+4+8+16=31
That is 6 pieces and needs 5 cuts."


It is incorrect to say, as you did in the quote above, that " That is 6 pieces and needs 5 cuts."

Remember what x represents! It represents the number of cuts to begin with. So, by your own statement above, the number of cuts is x=3, NOT 5.

Your solution entirely misses the point!

Please get a chain in front of you. It'll do wonders for you!

 

[quantyst]

Please read my solution several times, if need be, until you grasp the situation better.

 

[Prateek Bhatia]

Please read my solution several times, if need be, until you grasp the situation better.

Sorry about that. I got your solution but missed the fact that cutting a ring frees three pieces. As you said I wasn't thinking of rings- more like equal blocks of gold connected together so I missed your point. My sincerest apologies once again.

 

[glkev]

There are n horses. You are to determine the minimum number of races it takes to identify the j fastest horses amongst the n horses. Each horse's speed is constant and different than that of any other horse. Each horse race is comprised of a maximum of k horses where k>j. You don't have a stop watch to time the horses' speeds. All you can infer from each race is the rankings of the horses with respect to their speeds in that race.

Here's my thoughts with following assumptions

1. F(N, k, j) defines as finding jth fastest horse from N horses and run maximum k horse at a time
2. F(N, k, j) = F(N, k, N-j+1) - finding jth fastest horse is the same as finding jth slowest horse
3. F(N, k, j) = 1 for any k >= N

Now, the strategy to find the fastest horse is to divide N horse to N/k group for N/K race, and divide the group winner to N/(k^2) groups for race, this strategy goes on, and we have the following

F(N, k, 1) = [N/K] + [N/k^2] + [N/k^2] + ... + [N/k^m]; and (m-1)^k < N <= m^k; [N/K] represents the upper bound integer of the N/k.

During this process of finding the fastest one, we have build a k-nary tree, with each non-leaf node has at most k children, and the parent node is the fastest horse comparing the all the children nodes. The tree would have level m ;

After finding the 1st horse, we pick the fastest horse from the subtree of the 1st horse, and replace all the 1st horse position in the tree until the top, and we would have to run (m-1) race to find out the second fastest horse

F(N, k, 2) = F(N, k , 1) + (m-1)

Continue this strategy, we have F(N, k, j) = F(N, k, 1) + (j-1)*(m-1) for all j < k

I can verify this strategy for N = k^m; say N = 9, k = 3, 2, and j = 1, 2

for the fastest horse it's 9/3 + 9/9 = 4 times, and the 2nd fastest horse is 5 times.


The question I have is how to prove this strategy finds out the minimal number of race?

 

[glkev]

Sorry about that. I got your solution but missed the fact that cutting a ring frees three pieces. As you said I wasn't thinking of rings- more like equal blocks of gold connected together so I missed your point. My sincerest apologies once again.

Thanks quantyst, I wasn't thinking about the cutting ring neither.

 

[quantyst]

Here's my thoughts with following assumptions

1. F(N, k, j) defines as finding jth fastest horse from N horses and run maximum k horse at a time
2. F(N, k, j) = F(N, k, N-j+1) - finding jth fastest horse is the same as finding jth slowest horse
3. F(N, k, j) = 1 for any k >= N

Now, the strategy to find the fastest horse is to divide N horse to N/k group for N/K race, and divide the group winner to N/(k^2) groups for race, this strategy goes on, and we have the following

F(N, k, 1) = [N/K] + [N/k^2] + [N/k^2] + ... + [N/k^m]; and (m-1)^k < N <= m^k; [N/K] represents the upper bound integer of the N/k.

During this process of finding the fastest one, we have build a k-nary tree, with each non-leaf node has at most k children, and the parent node is the fastest horse comparing the all the children nodes. The tree would have level m ;

After finding the 1st horse, we pick the fastest horse from the subtree of the 1st horse, and replace all the 1st horse position in the tree until the top, and we would have to run (m-1) race to find out the second fastest horse

F(N, k, 2) = F(N, k , 1) + (m-1)

Continue this strategy, we have F(N, k, j) = F(N, k, 1) + (j-1)*(m-1) for all j < k

I can verify this strategy for N = k^m; say N = 9, k = 3, 2, and j = 1, 2

for the fastest horse it's 9/3 + 9/9 = 4 times, and the 2nd fastest horse is 5 times.


The question I have is how to prove this strategy finds out the minimal number of race?

It seems you have misunderstood the problem.

You are to determine the j fastest horses, not the j fastest horse.

 

[glkev]

"You are to determine the j fastest horses, not the j fastest horse."

OK. According my strategy, it takes [N/K] + [N/K^2] + ... + [N/K^m] races to find out the fastest horse, then every m-1 races for the 2nd, ... to jth fastest horses. So the total race of finding out the j fastest horses is the same as finding out the j-th fastest horse.

I am not certain this is the minimal race strategy though.

 

[quantyst]

"You are to determine the j fastest horses, not the j fastest horse."

OK. According my strategy, it takes [N/K] + [N/K^2] + ... + [N/K^m] races to find out the fastest horse, then every m-1 races for the 2nd, ... to jth fastest horses. So the total race of finding out the j fastest horses is the same as finding out the j-th fastest horse.

I am not certain this is the minimal race strategy though.

This problem is what it is BECAUSE of the need to prove that one's answer (however it is discovered or produced) is indeed the MINIMUM given N, k, j.

Any other consideration, any strategy, any insight or discovery, as useful as it may be in its own right, does NOT solve the problem without a successful proof that the number produced is indeed the minimum.

I can think of about 35,000 different strategies that purport to produce the minimum number. But you will never (almost never!) see me show any one of these strategies because I do not have any proof for any one of them.

 

[ramnik]

[Puzzle] What's my salary?

This is not an interview question but a simple puzzle.

Say there are n people (P_{1}, P_{2} .... P_{n}) in a room and each person earns an amount (X_{i} ). Now the people want to know the mean of their salaries without disclosing their individual income. Define a protocol for communication such that the objective is achieved.

Assume individuals to be infinitely intelligent.

 

[ramnik]

[Puzzle] Weighing Problem

Probably this problem has been discussed before but just in case :-k

Assume you have been given 12 distinguishable balls and it is known exactly one of them is either heavier or lighter. In exactly 3 chances find which ball is heavier or lighter and tell the type {whether it is heavier or lighter}

Given a general n how many weigh ins are needed? [warning: I don't know the solution to this part of the problem]

 

[quantyst]

This is not an interview question but a simple puzzle.

Say there are n people (P_{1}, P_{2} .... P_{n}) in a room and each person earns an amount (X_{i} ). Now the people want to know the mean of their salaries without disclosing their individual income. Define a protocol for communication such that the objective is achieved.

Assume individuals to be infinitely intelligent.

Your problem is not well stated. It is too vague and engenders a lot of unanswered questions.

You need to delineate the components of "protocol for communication" in a systematic way so that the problem solver knows who speaks to whom, how he/she speaks, who hears it, etc. etc.

Incidentally, your problem has no solution in the case n=2. Suppose it did and the publicly revealed average salary is S. So, either of the two people in the room can tell what the other person got by subtracting his/her salary from 2S.

 

[quantyst]

This is not an interview question but a simple puzzle.

Say there are n people (P_{1}, P_{2} .... P_{n}) in a room and each person earns an amount (X_{i} ). Now the people want to know the mean of their salaries without disclosing their individual income. Define a protocol for communication such that the objective is achieved.

Assume individuals to be infinitely intelligent.

Now, notwithstanding my earlier post, I will give a solution below only because your problem has been around the net long enough that I have seen it before with a specific value for n. There are many distinct solutions to your problem. Below is one, of my own creation.

Assume n>3. [Originally it was n>2, which, of course, for n=3, the below solution would not work]

Person P(i) breaks down his (all singular third person pronouns refer to both genders equally) salary X(i) into two arbitrary numbers L(i) and R(i): X(i)=L(i)+R(i).

Now all the people in the room line up around a circle. Person P(i) quietly and exclusively reveals to the person to his left the number L(i) and to the person to his right the number R(i). Like every one else in the room, person P(i) receives two numbers L and R from two different people. He adds these two numbers and publicly announces the sum L+R. Everyone in the room by adding these n announcements gets the sum of all the salaries. Etc.

 

[ramnik]

Now, notwithstanding my earlier post, I will give a solution below only because your problem has been around the net long enough that I have seen it before with a specific value for n. There are many distinct solutions to your problem. Below is one, of my own creation.

Perfecto! Sorry that the problem was not well framed.
I had a different solution which used pretty much the same idea. Using [income + R(i)] this problem could be solved (will have to iterate over all individuals twice)
The weighing problem is tougher. You'll like that.

 

[quantyst]

PENTAGON -----> pentagon

Join the diagonals of a regular pentagon to form a smaller pentagon. Each vertex of the smaller pentagon is the intersection of two diagonals of the original pentagon. Find the ratio of the area of the smaller pentagon to that of the original pentagon.