Occurrences After Bigram

Occurrences After Bigram

What is this problem about?

The Occurrences After Bigram problem gives you a text string and two words first and second. Find all words that immediately follow the pair ("first", "second") in the text. This easy string problem tests clean word tokenization and sequential pattern matching.

Why is this asked in interviews?

Google asks this easy problem to verify string parsing and pattern matching skills — specifically, scanning for a two-word pattern and collecting the next word. The string interview pattern is demonstrated at its most fundamental.

Algorithmic pattern used

Token scanning with pattern matching. Split the text into words. Scan with index i from 0 to n-3: if words[i] == first and words[i+1] == second, add words[i+2] to results. Return results.

Example explanation

text="alice is a good girl she is a good student", first="a", second="good". Words: ["alice","is","a","good","girl","she","is","a","good","student"].

• i=2: "a"=="a" ✓, "good"=="good" ✓. Append "girl".
• i=7: "a"=="a" ✓, "good"=="good" ✓. Append "student". Result = ["girl","student"].

Common mistakes candidates make

• Not splitting by spaces before scanning.
• Checking only the first occurrence and stopping.
• Index out of bounds when checking i+2 (must stop at n-3).
• Case-sensitive comparison when text might have mixed case.

Interview preparation tip

Bigram pattern problems are straightforward sliding window problems on word arrays. Always split text into words first, then scan with a window of appropriate size (3 for bigram + next word). Handle the boundary carefully: stop at len(words) - window_size. Practice similar sliding window word pattern problems to build comfort with token-based scanning.