Number of People Aware of a Secret

Number of People Aware of a Secret

What is this problem about?

The Number of People Aware of a Secret problem simulates secret spreading: on day 1, one person learns a secret. Starting on day delay, they begin sharing it. After forget days from learning, they forget it. Each day, everyone who knows the secret (and hasn't forgotten) shares it with one new person. Count the total people who know the secret on day n. This coding problem uses a queue/DP simulation.

Why is this asked in interviews?

NCR, Arcesium, Microsoft, Amazon, and Bloomberg ask this to test queue-based simulation combined with DP. It validates understanding of "sliding window" growth — only active knowers in the window [delay, forget) share the secret. The queue, simulation, and dynamic programming interview pattern is directly applied.

Algorithmic pattern used

DP with running window sum. dp[i] = number of people who first learn the secret on day i. For each day i from 2 to n: dp[i] = sum of dp[j] for all j where i - forget < j <= i - delay (people who learned within the active sharing window). Use a prefix sum or sliding window to compute this efficiently. Answer = sum of dp[j] for j in (n-forget, n].

Example explanation

n=6, delay=2, forget=4. dp[1]=1.

• Day 2: sharers from day max(1, 2-4+1)=1 to 2-2=0 → none. dp[2]=0. Wait — let me recalculate: on day i, people who learned between day (i-forget+1) and day (i-delay) share. Day 2: (2-4+1)=-1 to (2-2)=0. No valid days. dp[2]=0.
• Day 3: range (3-4+1)=0 to (3-2)=1. dp[1]=1. dp[3]=1.
• Day 4: range 1 to 2. dp[1]+dp[2]=1. dp[4]=1.
• Day 5: range 2 to 3. dp[2]+dp[3]=0+1=1. dp[5]=1.
• Day 6: range 3 to 4. dp[3]+dp[4]=1+1=2. dp[6]=2. People who remember on day 6: dp[j] for j in (6-4, 6] = (2,6] → dp[3]+dp[4]+dp[5]+dp[6]=1+1+1+2=5. Answer = 5 (mod 10^9+7).

Common mistakes candidates make

• Off-by-one in the sharing window (delay and forget are both important bounds).
• Not applying modular arithmetic at each step.
• Counting people who have forgotten (only count those in [n-forget+1, n]).
• Using a naive O(n*forget) computation instead of prefix sums.

Interview preparation tip

Secret/virus spreading problems are "sliding window DP" problems. The number of new learners on day i = sum of dp[j] for j in a window relative to i. Use prefix sums to make this O(1) per day. Practice epidemic simulation DP problems — SIR models, infection spread, rumor propagation — they all follow the same sliding window sum pattern.