Katkat
Back

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

GoogleSoftware Engineer · Onsite
EasySoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

Find the smallest distance between occurrences of two given words in a list, then build a class over the word list that answers repeated distance queries and checks whether two words are anagrams. It tests linear-time scanning, precomputation for repeated queries, and correct letter-count comparison.

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.

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).

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.

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

Hints

Hint 1

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.

Hint 2

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.

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?