Katkat
Back

Compute expected days until no whole pills

Qube Research & TechnologiesSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to model a stochastic process using a system of linear equations and solve it using expectation theory.

Problem: The Pill Bottle Expectation

You have a bottle containing n whole pills. Each day, you pick one pill at random from the bottle. If you pick a whole pill, you take half of it and put the other half back into the bottle. If you pick a half pill, you consume it entirely.

Write a function expected_days(n) that returns the expected number of days until there are no whole pills remaining in the bottle.

Constraints

  • n is an integer, 1 <= n <= 1000.
  • Your solution should return the result as a floating-point number.

Examples

  • expected_days(1): You pick the one whole pill. You take half, leaving one half. The next day, you pick that half and consume it. Total 2 days.
  • expected_days(2): The process stops when you have zero whole pills left.

Edge Cases

  • Consider the state transition when you transition from w whole pills and h half pills to a new state of (w', h').

Hints

Hint 1

Define E(w, h) as the expected number of additional days needed to reach 0 whole pills, given you currently have w whole pills and h half pills.

Hint 2

The transitions are: if you pick a whole pill (probability w / (w+h)), you move to state (w-1, h+1); if you pick a half pill (probability h / (w+h)), you move to state (w, h-1).

Hint 3

Notice that the number of whole pills always decreases by one, while the number of half pills increases by one when you pick a whole pill, which simplifies the state space significantly.

Follow-up questions

  • How does the expected number of days change if there are always 'h' half pills present initially?
  • Can you derive a closed-form expression for the expected value instead of using dynamic programming?
  • How would you adapt this simulation if you had a 10% chance of dropping the pill, meaning it is destroyed without being halved or consumed?