Shortest Distance Between Two Words, Then a Word-List Class With an Anagram Check

You are given a list of words, which may contain repeats, and two words `word1` and `word2`. Return the smallest distance between an occurrence of `word1` and an occurrence of `word2`, where the distance between positions `i` and `j` is the absolute difference of the two indices. The interview asked a variant of this word-distance task, but the variant's change was not described, so Part 1 states the base form. The follow-up then asked for a class that implements several specific word methods, such as checking whether two words are anagrams of each other. ```text words = ["the", "quick", "fox", "jumps", "over", "the", "lazy", "fox"] distance between "the" and "fox" -> 2 distance between "over" and "the" -> 1 "listen" and "silent" are anagrams -> True ``` ### Clarifying Questions - Can `word1` and `word2` be the same word, meaning the distance between two different occurrences of it? - What should happen if one of the words does not appear in the list? - Are comparisons case-sensitive, and should the anagram check consider only letters? - For the class, is the word list fixed after construction, and roughly how many queries will it serve? - Which methods besides the anagram check should the class offer? ### Part 1 — Shortest distance between two words Implement `shortest_distance(words, word1, word2)`. ```hint Not every pair matters Count how many position pairs a brute force compares, then ask which of those pairs can actually be the closest one. ``` #### What This Part Should Cover - A correct algorithm, with an argument for why it never misses the closest pair - Time and space complexity - Edge cases: adjacent words, repeated occurrences, a missing word ### Part 2 — A word-list class Write a class that is built once from the word list and implements several word methods. The method reported is an anagram check: whether two words consist of the same letters with the same counts, in any order. Assume the class also answers the Part 1 distance query, now asked many times on the same list. ```hint Pay once, query many times Decide what the constructor should precompute so that each distance query avoids rescanning the whole list, and what an anagram check really needs to compare. ``` #### What This Part Should Cover - The class interface and what the constructor precomputes - The time per method call, compared with the one-shot function - A correct anagram check, including words of different lengths and repeated letters - Tests for each method ### What a Strong Answer Covers - Clarifies same-word queries, missing words and case rules before coding - A linear-time Part 1 with a clear correctness argument - A class whose precomputation makes repeated queries cheaper, with the complexity of each method stated - An anagram check that compares letter counts, not just the set of letters - Clean, readable code with test cases ### Follow-up Questions - `word1` and `word2` may now be the same word. What changes in the function and in the class? - One word appears very often and the other only a few times. How fast is your distance query, and can it be faster? - Add a method that returns every group of words in the list that are anagrams of one another. - The words arrive as a stream too large to store. Which methods can you still support?