# Word Container - Coach Answer Key ## The Problem Given a list of words, find all words that contain at least one other word from the list as a substring. **Quick examples:** - `["apple", "app", "banana", "nana"]` → `["apple", "banana"]` (apple contains "app", banana contains "nana") - `["work", "worker", "rework"]` → `["worker", "rework"]` (both contain "work") - `["cat", "dog", "bird"]` → `[]` (no word contains another) A word cannot contain itself (exact matches don't count). The contained word must be strictly shorter than the container. --- ## Structure The candidate gets two files to work with: - **WordList** — manages a collection of words, validates them, checks substring relationships. Has two bugs. - **Solver** — stubbed returning empty list. Candidate implements `find_containers()`. There are three run targets: Run Main, Test Word List, and Test Solver. Several tests are commented out with `????` placeholders. --- ## Phase 1: Bug Fix (~10 minutes) ### Bug 1: Off-by-One in Substring Check In `contains_as_substring()`, the length check uses `<=` instead of `<`: ``` def contains_as_substring(self, container, contained): if len(contained) <= len(container): # BUG: Should be < not <= return contained in container return False ``` When `container` and `contained` are the same length, `len(contained) <= len(container)` is True, and `contained in container` is also True if the strings are equal. So "app" is incorrectly reported as containing "app" (itself). **The fix:** Change `<=` to `<` so equal-length words are not considered substrings. **Commented-out tests:** - `test_contains_same_word` — "app" contains "app"? The `????` answer is **`False`**. - `test_contains_longer_word` — "app" contains "apple"? The `????` answer is **`False`**. ### Bug 2: Missing Empty String Check in is_valid_word In `is_valid_word()`, empty strings pass validation: ``` def is_valid_word(self, word): if ' ' in word: return False return True ``` Only spaces are rejected. An empty string `""` passes validation, which is wrong. **The fix:** Add `if not word: return False` before the space check. **Commented-out tests:** - `test_valid_word_empty` — empty string valid? The `????` answer is **`False`**. - `test_valid_word_spaces` — "hello world" valid? The `????` answer is **`False`** (this one already passes). - `test_valid_word_normal` — "hello" valid? The `????` answer is **`True`**. - `test_filters_invalid_words` — filters list with empties/spaces. The `????` answer is **`3`** valid words. ### What to Watch For - Bug 1 is a classic off-by-one. Do they understand "proper substring" means strictly shorter? - Bug 2 is an edge case. Some candidates will spot it from reading; others need the test. - The bugs are independent — they don't compound each other. --- ## Phase 2: Implement Solver (~15 minutes) The `find_containers()` method is stubbed returning an empty list. Candidates must implement it to find all words containing other words as substrings. ### Expected Approach: Naive O(n² × m) ``` def find_containers(self): words = self.word_list.get_words() containers = [] for word in words: for other in words: if other != word and self.word_list.contains_as_substring(word, other): containers.append(word) break # Only need to find one contained word return containers ``` ### Key Points 1. Don't check a word against itself 2. Break early once we find any contained word — no need to find all matches 3. Return the container words, not the contained ones 4. The `break` is important for performance — without it, "apple" would be added once for each word it contains ### Tests | Test | Input | Expected | |------|-------|----------| | `test_simple_containers` (commented) | `["apple", "app", "banana", "nana"]` | `["apple", "banana"]` | | `test_no_containers` (commented) | `["cat", "dog", "bird", "fish"]` | `[]` | | `test_multiple_containers` (commented) | `["work", "worker", "rework", "working", "homework"]` | Count = **4** | | `test_nested_containers` (commented) | `["a", "an", "ant", "rant", "grant"]` | Count = **4** | | `test_from_file_small` (commented) | `words_small.txt` (20 words) | Min = **5** containers | ### What to Watch For - Do they use the `break` after finding a match? Without it, a word could appear multiple times in the result. - Do they skip self-comparison (`other != word`)? - Some candidates will try to return the contained words instead of the containers — watch for this. - The nested loop is fine for Phase 2. Don't push optimization yet. --- ## Phase 3: Optimization (~15 minutes) ### The Challenge The naive O(n² × m) approach becomes slow for large word lists: | Words | Naive Time | Optimized Time | |-------|------------|----------------| | 5,000 | ~0.5s | ~0.005s | | 10,000 | ~2.7s | ~0.02s | ### The Key Insight Instead of checking every pair, flip the approach: for each word, check if any of its substrings exist in the word set. ### Optimization Strategy: Set-Based Substring Check ``` def find_containers_optimized(self): words = self.word_list.get_words() word_set = set(words) containers = [] for word in words: for start in range(len(word)): for end in range(start + 1, len(word) + 1): if start == 0 and end == len(word): continue # Skip the full word itself substring = word[start:end] if substring in word_set: containers.append(word) break else: continue break return containers ``` ### Why This Is Faster **Naive:** For each of n words, check against n-1 others → O(n² × m) **Optimized:** For each of n words, enumerate its m² substrings and check set membership → O(n × m²) When n >> m (many words, short average length), this is dramatically faster: - 10,000 words averaging 8 characters: n² × m ≈ 800 billion vs n × m² ≈ 640,000 ### Alternative: Sort + Length Filter A simpler optimization that helps but isn't as dramatic: ``` sorted_words = sorted(words, key=len) for i, word in enumerate(sorted_words): for j in range(i): shorter = sorted_words[j] if len(shorter) < len(word) and shorter in word: containers.append(word) break ``` This skips equal-length comparisons and uses Python's optimized `in` operator directly. ### Tests | Test | Words | Time Limit | |------|-------|------------| | `test_medium_wordlist` (commented) | 500 | **1.0** seconds | | `test_large_wordlist` (commented) | 5,000 | **0.5** seconds | | `test_huge_wordlist` (commented) | 10,000 | **1.0** seconds | ### What to Watch For - Do they recognize the fundamental algorithmic insight? (enumerate substrings of each word, not compare all pairs) - Can they explain why O(n × m²) is better than O(n² × m)? (n is large, m is small) - Do they handle the self-exclusion correctly? (skip the full word when checking substrings) - The double-break pattern (for/else + break) is tricky in Python. Some candidates will use a helper function or flag variable instead. All approaches are fine. - Set membership is O(1) average — do they understand this? --- ## Common Candidate Paths ### The Strong Path 1. Spots both bugs quickly — `<=` vs `<` and empty string edge case 2. Implements clean nested loop with break 3. Immediately sees the set-based substring approach for optimization 4. Passes all tests including the 10,000-word stress test ### The Good Path 1. Finds bugs via test failures 2. Implements naive nested loop correctly 3. Performance tests fail — needs to think about optimization 4. Realizes they can enumerate substrings instead of comparing all pairs 5. Implements set-based approach, passes ### The Struggling Path 1. Confused by the off-by-one (doesn't understand "proper substring") 2. Forgets the `break` — gets duplicate results 3. Optimization is hard to conceptualize — stuck on trying to make O(n²) faster 4. Needs the insight that flipping the approach (substrings of word vs checking against all words) changes the complexity --- ## Hints to Give (If Needed) **Phase 1 — If stuck on bugs:** - "Should 'app' contain itself? What does 'proper substring' mean?" - "What about an empty string — is that a valid word?" - "Look at the length comparison in contains_as_substring — what happens when both words are the same length?" **Phase 2 — If stuck on implementation:** - "For each word, check if any OTHER word is a substring of it." - "When you find a match, you can stop checking — one contained word is enough." - "Make sure you don't include a word as a container of itself." **Phase 3 — If stuck on optimization:** - "Instead of checking word A against all other words, what if you listed all substrings of word A?" - "How many substrings does a word of length m have?" (~m²) - "If you put all words in a set, you can check if a substring exists in O(1)." - "Which is bigger for your dataset: n² or n × m²? That tells you which approach is faster." --- ## Follow-Up Discussion Questions - **"What's the naive time complexity?"** — O(n² × m) — for each of n words, check against n-1 others, each check is O(m) substring search. - **"Why is O(n × m²) better?"** — When n >> m (many words, short average length). For 10,000 words of length ~8: n² × m ≈ 800M vs n × m² ≈ 640K. - **"What data structure would help for prefix matching?"** — A Trie. But we need substring matching (not just prefix), so the set approach with substring enumeration works better here. - **"Could you use suffix trees?"** — Yes, a generalized suffix tree could find all substring relationships in O(n × m) time. But it's complex to implement and the set approach is simpler and fast enough. - **"What about very long words?"** — If m is large, O(n × m²) gets expensive. You'd want a suffix array or Aho-Corasick algorithm for multi-pattern substring matching. --- ## Data Files Reference | File | Words | Description | |------|-------|-------------| | `words_small.txt` | 20 | Hand-picked words with known containers | | `words_medium.txt` | 500 | Common English words | | `words_large.txt` | 5,000 | Optimization test threshold | | `words_huge.txt` | 10,000 | Stress test | --- ## Timing Guide | Phase | Target Time | If Running Long | |-------|------------|----------------| | Bug Fix | ~10 min | Point out the `<=` vs `<` and empty string checks | | Implementation | ~15 min | Walk through the nested loop logic, emphasize the break | | Optimization | ~15 min | Explain the "flip" — enumerate substrings, not pairs | | Total | ~40 min | Leave 5-10 min for discussion questions |

	Problem	Difficulty
	Battleship	Easy

	Inventory Packer	Easy

	Spell Checker	Easy

	Card Game	Medium

	Maze Solver	Medium

	Route Planner	Medium

	Task Scheduler	Medium

	Word Container	Medium

	Maximize Unique Characters	Hard

	Nonogram Solver	Hard

AI Coding Guided Practice

Questions

Learn

Links

Legal

Contact