What is the probability of an 8-bit string having no more than 2 consecutive 1s? Solve using dynamic programming.

Question

Accepted Answer

Probability of an 8 bit string with no more than 2 consecutive 1's using dynamic programming.

Use dynamic programming to calculate the probability of a string with no more than 2 consecutive 1's
Create a 2D array to store the probabilities of each bit position and number of consecutive 1's
Use recurrence relation to calculate the probability for each bit position based on the previous bit position
Sum up the probabilities for all possible combinations of the last bit position and number of consecutive 1's
The final probability is the sum of probabilities for all possible combinations of the last bit position and number of consecutive 1's
Example: P(00000000) = 1, P(11111111) = 0, P(10101010) = 0.1875

Goldman Sachs Strategic Anaylst interview questions & answers