Epic Systems Interview Question






Comment hidden because of low score. Click to expand.
9
of 9 vote

I am really scared from all these explanations... Markov chain Theory etc.
So lets seek the solution in simple terms.

Head:
- due to a head, there is no way we can get a head again, since it will be flipped
- duet to a tail, we may get a head or a tail
thr4, h = 0 * h + (1/2) * t

Tail:
- due to a head, we are 100% sure that we'll get a tail, since it will be flipped
- due to a tail, we may get a head or a tail
thr4, t = 1 * h + (1/2) * t

And, h + t = 1 (obvious.. you can also add both the above equations and see)

so h + t =1
(1/2)t + t = 1
t = 2/3, h = 1/3

- Britney February 15, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

by god one of few times when scrolling down was worth th effort.. cool.

- nonymus November 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

in the end it's all heads

- Anonymous April 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks Britney for a simple solution.

- Anonymous September 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

No chance of convergence unless manually flipped coins are marked.
Guaranteed convergence is even the flipped coins are not re-visited (tossed ones can be visited as mny times as robot wants to).

- Nix September 22, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The assumption in the above code is that the initial number heads and tails facing up is the equally distributed..
it is evident that the ratio of tails:heads will be 2:1 after a certain number of iteratoins

- cam September 29, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

a completely agree with cam and the ratio will be tail:head = 2:1
P(head) = 1/3
P(tail) = 2/3

- xinhua.liu@yahoo.co.cn October 02, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a Markov Chain problem.

Let j=#tails,

the the probability of j+1 tails at step t is P(N_t=j+1|N_(t-1)=j)=(n-j)/n;
and the probability of j-1 tails at step t is P(N_t=j-1|N_(t-1)=j)=j/(2n).

Hence the probability matrix P is as follows:
1. main diagonal is 0, 1/2n, 2/2n,..., n/2n;
2. upper diagonal is 1, (n-1)/n, ....,1/n;
3. lower diagonal is 1/(2n),2/(2n),...,n/(2n).

If x is the stationary ditribution, then x=x*P.

n+1 equations and n+1 variables, by the Perron–Frobenius theorem, there must be a solution.

So the answer is yes.

- chao October 07, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In fact we can explicitly solve the distribution.

It is the binomial distribution:

Let x=(x_0,...,x_n) be the stationary distribution, then by expanding the matrix multiplication,

x_0 = 1/(2n)x_1, so x_1 = 2nx_0 = 2(n choose 1)x_0;
x_1 = x_0 + 1/(2n)x_1 + 2/(2n)x_2, so x_2 = 4(n choose 2)x_0;

......

It can be proved by mathematical induction that
x_k = 2^k(n choose k)x_0,

since \sum x_i = 1, we have x_0 = 1/3^n, and x_k = 2^k/3^n(n choose k).

There is a theorem stating that
if a Markov chain is irreducible and aperiodic and a stationary distribution exists, then
it is also a limit distribution. (But that is a lot of theory!)

- chao October 07, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

There are two possible moves by the robot per iteration:
A) Robot picks up a head coin and flips it and we have one less heads and one more tails.

B) Robot picks up a tail coin and tosses it.
B1) Outcome of the toss is head so we have one less tails and one more heads.
B2) Outcome of the toss is tail so we the same number of heads and tails before the toss since tail coin is put back to other coins as tail.

Probability of A move is H / (H + T)
Probability of BX move is T / (H + T) and probability of B1 or B2 is T / (H + T) x 2.
(where H is # of heads and T is # of tails)

Now chance that number of tails is going to be one less than previous iteration is T / (H + T) x 2

Chance that number of heads is going to be one less than previous iteration is H / (H + T)

Number of heads and tails will change until system comes to an equilibrium if there is such point and such equilibrium exists when the probability of one less heads is equal to probability of one less tails:

H / (H + T) = T / (H + T) x 2

If you solve the above equation you'll see that 2H = T is the equilibrium point.

- oa October 08, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

All you have to do is find the left eigenvector of markov matrix
[0 1
0.5 0.5] corresponding to the eigenvalue =1

The eigenvector= [1/3 2/3]' which is a invariant distribution

- Piyush October 17, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You can do this rigorously without resorting to Markov chain theory:

It is sufficient to focus on just one particular coin and determine its probability of tails in the limit. Let p_n be its tail probability on the nth visit of the robot; the head probability is of course (1-p_n). We can set up the following recurrence relation for p_n:

p_n = [1-p_{n-1}] + 0.5p_{n-1}

which simplifies to

2p_n + p_{n-1} + 2 = 0

The solution of the characteristic polynomial of this relation yields the distinct roots -0.5 and 1. So the solution to the recurrence is of the form

p_n = C.(-0.5)^n + D(1)^n = C.(-0.5)^n + D, where C and D are constants

Obviously then, as n is taken to infinity, the term with coefficient C vanishes and D remains. I won't bother to compute D but others have noted it is 2/3. So it does converge.

- Bullocks January 01, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Very good job! Thanks. Actually there is another way to compute P_n:
Since p_n = [1-p_{n-1}] + 0.5p_{n-1}, we can try to see if P_n+k is geometric progression, 2(P_n+k)=-(P_{n-1}+k). Solve this equation, you can see k=-2/3. So P_n=(P_0-2/3)*(-1/2)^n+2/3. So P_n converge to 2/3.

- yfeng March 23, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

So the equilibrium point will be reached when h = (1/2) * t

- Britney February 15, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

kick ass answer

- Britney October 30, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Palang tod answer

- Anonymous October 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

lol!!

- Anonymous March 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

all heads

- Anonymous April 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Let's say you have N coins, nh heads, and nt tails.
N =nh +nt (1)
In one round, the robot goes through all of them (it is equivalent to saying that the robot randomly goes through coins if N is large). After one round
nt =(1/2) *nh (2)
nh =(1/2)*nh +nt (3)
(2) and (3) follow from the rules of the game. The process converges if there is a solution to the equations (1-3), so that after one round the distribution remains the same. Indeed, the solution is
nt =(1/3)*N
nh =(2/3)*N

- Anonymous June 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

maa chod do robot ki

- cunomad_ki_maa_ka_bhosda March 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

is it only me, i have no idea about this!!

- Ahmad July 29, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

#include <iostream>

using namespace std;

int main()
{
float heads = 50;
float tails = 50;
float factor = 0;
float difference = 0;

factor = heads /2;

for (int iCount = 0 ; iCount < 20 ; iCount++ )
{
if (iCount % 2 == 0 )
{
heads = heads + factor;
tails = tails - factor;
}
else
{
heads = heads - factor;
tails = tails + factor;
}

factor = factor/2;

cout << "Iteration: " << iCount << ": Heads = " << heads << " Tails = " << tails << endl;

}

return 0;
}

- cam September 29, 2009 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More