Katkat
Back

Shortest Word Distance Queries

LinkedInSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Tests designing an inverted index and using two-pointer or binary search techniques to efficiently compute the minimum absolute index distance between word occurrences across repeated queries.

Shortest Word Distance Queries

Design a data structure that accepts a list of words during initialization and repeatedly finds the minimum index distance between two occurrences of specified words.

Implement the WordDistance class:

  • WordDistance(words_dict: list[str]): Initializes the object with the list of strings words_dict.
  • shortest(word1: str, word2: str) -> int: Returns the minimum distance |i - j| such that words_dict[i] == word1, words_dict[j] == word2, and i != j.

Note that word1 and word2 may refer to the same string, in which case you must find two distinct occurrences of that word.

Examples

Example 1:

wd = WordDistance(["practice", "makes", "perfect", "coding", "makes"])

wd.shortest("coding", "practice")
# Output: 3
# Explanation: "coding" is at index 3, "practice" is at index 0. |3 - 0| = 3.

wd.shortest("makes", "coding")
# Output: 1
# Explanation: "makes" appears at indices 1 and 4. The closest pair is index 4 and index 3. |4 - 3| = 1.

wd.shortest("makes", "makes")
# Output: 3
# Explanation: The two occurrences of "makes" are at indices 1 and 4. |4 - 1| = 3.

Example 2:

wd = WordDistance(["a", "c", "b", "a", "a"])

wd.shortest("a", "b")
# Output: 1
# Explanation: "b" is at index 2, "a" appears at indices 0, 3, 4. The closest "a" to index 2 is at index 3. |3 - 2| = 1.

wd.shortest("a", "a")
# Output: 1
# Explanation: Consecutive occurrences of "a" at indices 3 and 4 have distance 1.

Constraints

  • 2 <= len(words_dict) <= 100,000
  • 1 <= len(words_dict[i]) <= 10
  • words_dict[i] consists only of lowercase English letters.
  • word1 and word2 are guaranteed to exist in words_dict.
  • If word1 == word2, the word is guaranteed to appear at least twice in words_dict.
  • At most 50,000 calls will be made to shortest.
  • An O(N) scan per query will exceed the time limit.

Hints

Hint 1

Preprocess the list into an inverted index mapping each unique word to a sorted list of its occurrence indices.

Hint 2

For distinct words, merge-scan the two sorted index lists using two pointers in O(len(A) + len(B)) time, or use binary search if one list is drastically smaller than the other.

Hint 3

Handle the case where word1 == word2 by inspecting adjacent elements in a single index list, and consider caching results for repeated queries.

Follow-up questions

  • If a few common words (stop words) appear hundreds of thousands of times while other words are rare, how would you optimize the comparison between two high-frequency word lists?
  • How would you adapt your design if the collection of words is dynamic, allowing words to be appended to the end of the text stream continuously?
  • If the corpus cannot fit on a single machine's memory, how would you partition the index across multiple nodes to maintain low query latency?