## Interview Question

• 0

Country: United States
Interview Type: Phone Interview

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

Total tosses = n

Given "k" tosses, probability that all "k" tosses have the same type of toss (or be a "Streak")
= probability of all heads in "k" tosses + probability of all tails in "k" tosses
= (1/2)^k + (1/2)^k = 2*(1/2)^k

Given "n" tosses, # of sets of subsequent "k" tosses
= (n-k+1)

expected number of k-streaks
= number of subsequent "k" tosses * probability that one set of "k" tosses is a streak
= (n-k+1)*2*(1/2)^k

Comment hidden because of low score. Click to expand.
0

I share the same thoughts with you.
Just consider it as a Binomial distribution..

Comment hidden because of low score. Click to expand.
0

But aren't they all dependent events?
Say I get an event that from n = 1 to n = k is one streak, then the chance of getting a streak from 2 to k+1 increases. Your approach would be valid is the chance of getting streaks to start from subsequent values of n (1,2,3...) would be independent probabilities.

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

count no. of continous tails and heads.
no_t=no. of continous tails.
no of k streaks: no_t - (k - 1) + no_h - (k-1).

to count no of continous tails and heads. simply keep count in array of size.

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

For a run, the chance of it occurring is 2^n, where n is the length of the run. For example for the given run the probability is 0.015625.

The total number of runs found will be roughly N * 0.015625. To test this, I wrote a little program that runs this as a simulation. When running it, the first value I got was 0.0156219, so I'm pretty confident this is the right answer.

``````package a3;

import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.Random;

public class RandomCoinFlipper {
static final Random rand = new Random();

public static class CoinFlipper
{
private List<Boolean> seq;

public CoinFlipper()
{

}

public void setSequence(List <Boolean> seq)
{
this.seq = seq;
}

public int simulate(int simNr)
{
int found = 0;
Queue <Boolean> curRun = new LinkedList<Boolean>();

for(int i = 0; i < simNr; i++)
{
boolean curFlip = rand.nextBoolean();

if(curRun.size() >= seq.size())
{
curRun.poll();
}

Queue <Boolean> copy = new LinkedList<>(curRun);
boolean isRun = true;
//	System.out.println(seq.size() + ", " + curRun.size());
for(int at = 0; at < seq.size(); at++)
{
//	System.out.print(seq.get(at) + ":" + copy.peek() + ", ");
if(seq.get(at) != copy.poll())
{
isRun = false;
break;
}
}
//		System.out.println();
if(isRun)
{
System.out.println("Found one");
found++;
}
}
return found;
}
}

public static void main(String[] args)
{
//HTTTHH
List <Boolean> l = new ArrayList <>();

CoinFlipper flip = new CoinFlipper();
flip.setSequence(l);

int simNr = 10000000;
int runsFound = flip.simulate(simNr);

System.out.println(runsFound);
System.out.println((float)runsFound/(float)simNr);
}

}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Look at one consecutive pair:
Probability of this pair being the same is 1/2.

In n tosses, there are n-1 pairs.

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.

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