Throw a coin one million times. What is the expected number of sequences of six tails, if we do not allow overlap? Question itself: Throw a coin one million times. What is the expected number of sequences of six tails, if we do not allow overlap?
I know when overlap is allowed, the answer is (1,000,000-5)/(2^6). Not sure if we can just do (1,000,000-5)/(2^6) divided by 6 if overlap is not allowed?
Some clarifications:
For example, if part of the sequence is "one H, nine T, then one H", we would count 1 sequence of six tails. (When overlap is allowed, we can count three times because each of the first 3 T can start a sequence of six tails; However, this question does not allow overlap, so 9T can only be counted as containing one sequence of six tails)
If part of the sequence is "one H, thirteen T, then one H", we would count 2 sequences of six tails.
 A: I think I can compute that with an error of plus or minus 1.
This is a sketchy argument that you can make rigorous using Ergodic Theory or Palm measures.
Let us group runs of T from left to right, so a run of 14 T's has a run of 6 starting at position 1, another run starting at position 7, and two single T's at positions 13 and 14 that are not grouped.
Imagine a doubly-infinite sequence of H and T
You can construct it as a doubly infinite sequence of H and an doubly infinite iid sequence of H^k where k+1 is random Geometric(0.5). The average distance between H's is 2 and the average number of non-overlapping runs TTTTTT before the next H equals 1/63.
So a proportion of 1/126 of the integers will be the leftmost point of a non-overlapping group of 6.
The answer would be 1,000,000/126, except that this is not counting the case where a sequence of T's start at some x<0 and ends at 0<x<6 with more T's in x+1,...,6, and it counts the case of an x near the end which is the start of a run that actually ends after the interval. So 1,000,000/126 is the expectation of a random variable that can differ from your random variable by at most 1 unit.
You can probably improve it to an exact number but I'm quite happy with this approximation.
A: Comment. I'm not sure I've got the rules exactly right, but I did some checking
with simulation in R. The rle procedure in R (for Run Length Encoding)
gives run values (0s for Tails, 1s for Heads) and lengths.
For example:
set.seed(2021)
x = rbinom(10, 1, .5);  x
[1] 0 1 1 0 1 1 1 0 1 1
rle(x)
Run Length Encoding
  lengths: int [1:6] 1 2 1 3 1 2
  values : int [1:6] 0 1 0 1 0 1
rle(x)$len
[1] 1 2 1 3 1 2

So it is easy to see how many runs of length 6 or greater we get in a particular session of a million
tosses of a fair coin. Replicating that 1000 times gives a rough idea of the
average number of such runs in a sequence of a million.
set.seed(202)
run.6 = replicate(1000, sum(rle(rbinom(10^6,1,.5))$len >=6))
mean(run.6)
[1] 15629.12

The answer seems agreeably close to your $10^6/2^6  \approx 15\,625$ runs of length 6 or more.
But if we count runs of length 12 or more as two runs of 6 or more, the
desired number is a little larger, by about an additional 244 runs. There may
not be enough runs of length 18 or more to explore fruitfully by simulation (maybe about 4 more). [See @lulu's Comment.]
S0 roughly, you're going to get something close to $15625 + 244 + 4 = 15873$ runs
of the designated type in a sequence of a million tosses.
run.12 = replicate(1000, sum(rle(rbinom(10^6,1,.5))$len >=12))
mean(run.12)
[1] 243.97
10^6/2^12
[1] 244.1406

Iterations of 10,000 or 100,000 sequences of a million tosses would give slightly more
accuracy, but my purpose here is to give rough estimates for you to
compare with your combinatorial results.
A: We can break this into two problems. First, what's the expected number of sequences of $T^{6k}$ without a preceding $H$? (I.e., number of $HT^{6k}$ in any position, or $T^{6k}$ at the beginning.) Call it $E_k.$ Second, sum over $kE_k$ to get the final answer.
We have $10^6-6k$ windows of length $6k+1.$ The probability that a given window contains $HT^{6k}$ is $1/2^{6k+1},$ and the probability that the beginning of the sequence is $T^{6k}$ is $1/2^{6k}.$ So $$E_k=\frac{10^6-6k+2}{2^{6k+1}}.$$
Next, $k$ ranges from 1 to 166,666. So the answer is
$$\sum_{k=1}^{166,666}kE_k\approx 8062.45.$$
I used Wolfram Alpha for the sum, which is probably not allowed in an interview.
A: I was inspired by Sal Elder, but I think there are some problems with his answer.
Below is my answer:
First step: calculate $E_k$:the expected number of sequences of more than 6k' T with a preceding H(or at the begining).
Second step: sum over $k(E_k-E_{k+1})$, where $E_k-E_{k+1}$ is happen to be the expected number of sequences whose T is more than 6k but less than 6(k+1).
In this way, we count each sequence exactly once without overlapping.
A: If you are considering non-overlapping occurrence of $6$ consecutive Tails, then the occurrence of $6$ consecutive Tails is a renewal event. So, the whole might of renewal theory may be applied. See for more details in Feller Vol I.
I am copying some the stuff from there. Let $ N_n $ be the number of occurrences up to the $n$-th trial. Then, we have
\begin{equation*}
E(N_n) \sim \frac{n}{\mu}, \text{ and } \text{Var}(N_n) \sim \frac{ n \sigma^2}{ \mu^3}
\end{equation*}
where we have
\begin{equation*}
\mu = \frac{ 1 - q^6 }{ p q^6 } \text{ and } \sigma^2 = \frac{ 1 }{ ( p q^6)^2 } - \frac{13}{ p q^6 } + \frac{ q }{ p^2 } 
\end{equation*}
and $ a_n \sim b_n $ if $ a_n / b_n \to 1 $ as $ n \to \infty $.
Further, there is a central limit theorem (again see Feller) which provides fantastic probability estimates for rare events.
A: The expected number $a_n$ of nonoverlapping runs of $6$ consecutive tails in a sequence of $n$ independent fair coin tosses satisfies the nonhomogeneous linear recurrence
$$a_n=\frac12a_{n-1}+\frac14a_{n-2}+\frac18a_{n-3}+\frac1{16}a_{n-4}+\frac1{32}a_{n-5}+\frac1{64}a_{n-6}+\frac1{64}(1+a_{n-6}),$$
that is,
$$a_n-\frac12a_{n-1}-\frac14a_{n-2}-\frac18a_{n-3}-\frac1{16}a_{n-4}-\frac1{32}a_{n-5}-\frac1{32}a_{n-6}=\frac1{64}$$
with initial values $a_0=a_1=a_2=a_3=a_4=a_5=0$.
Alternatively,
$$a_n=\frac{n+2}2(x+x^2+x^3+\cdots+x^{\lfloor n/6\rfloor})-3(x+2x^2+3x^3+\cdots+\lfloor n/6\rfloor x^{\lfloor n/6\rfloor})$$
where $x=(1/2)^6=1/64$. In closed form that's
$$a_n=\frac{(n+2)[1-(\frac1{64})^{\lfloor n/6\rfloor}]}{126}-\frac{64-(63\lfloor n/6\rfloor+64)(\frac1{64})^{\lfloor n/6\rfloor}}{1323}.$$
