Oracle·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Oracle SWE coding round, one problem the whole session. Not a brutal interview but the problem had enough edge cases to trip you up if you weren't careful about the counting logic.

Questions Asked (1)

Given a list of phrases and a list of words, for each phrase count how many distinct phrases can be formed by replacing every word that has an anagram in the word list with any of its anagrams. Words with no anagram match stay fixed. If no word in the phrase can be replaced at all, return 0 for that phrase.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The multiplication part clicked pretty fast.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify that the task is to count distinct phrases, not total replacements, and that only words with at least one anagram in the word list are replaceable. Build a hash map from sorted-letter signatures to lists of anagrams, then for each phrase compute the product of (number of anagrams + 1) for each replaceable word, subtracting 1 if no word is replaceable.

Pro tip: Mention that using a canonical sorted-string key for anagrams avoids comparing every pair of words, reducing preprocessing from O(N*M*L) to O(N*L log L), and that the product formula naturally handles distinctness because anagram sets are disjoint.

1. Clarify requirements and edge cases

Confirm that 'distinct phrases' means unique sequences of words, and that a word with no anagram match stays fixed. Ask about case sensitivity, empty lists, and whether the original phrase counts as a valid formation.

2. Preprocess the word list into an anagram map

For each word in the word list, compute a canonical key (e.g., sorted characters) and group words by that key. This yields a map from key to list of anagrams.

3. Process each phrase and count replaceable words

For each word in the phrase, check if its canonical key exists in the anagram map. If yes, it is replaceable with k options (where k is the size of the anagram list); if no, it is fixed with 1 option.

4. Compute the number of distinct phrases

Multiply the number of options for each replaceable word. If no word is replaceable, the count is 0; otherwise, the product gives the total distinct phrases (including the original).

5. Analyze complexity and trade-offs

Discuss time and space complexity: O(W * L log L) for preprocessing, O(P * L log L) for phrase processing, where W is word list size, P is phrase count, L is average word length. Mention that sorting keys is a trade-off between preprocessing time and lookup speed.

Key Points to Mention

Use a hash map with sorted-string keys to group anagrams efficiently.
Distinctness is guaranteed because anagram groups are disjoint; no two different keys can produce the same word.
The count for a phrase is the product of (anagram count + 1) for each replaceable word, minus 1 if no word is replaceable.
Edge cases: empty word list, empty phrase, words with no anagrams, and case sensitivity.
Time complexity: O((W + P) * L log L) with sorting, or O((W + P) * L) with character frequency counting.
Space complexity: O(W * L) to store the anagram map.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.