Shortest Word Distance II

MediumDesignhashing

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Design a class WordDistance that is built once from a list of words wordsDict and then answers many distance queries against it. shortest(word1, word2) returns the smallest absolute difference |i - j| over all indices where wordsDict[i] == word1 and wordsDict[j] == word2. The two query words are always different from each other and both appear somewhere in the list. The same pair may be asked many times, in either order. Aim to make each query run in time proportional to the number of occurrences of the two words, not the length of the whole list.

Examples

Input: ["WordDistance","shortest","shortest","shortest"] [[["red","blue","green","blue","yellow","red"]],["red","yellow"],["green","red"],["blue","yellow"]]
Output: [null,1,2,1]
"red" sits at 0 and 5, "yellow" at 4, so the answer is 1. "green" (2) is 2 away from red at 0. "blue" at 3 is next to "yellow" at 4.
Input: ["WordDistance","shortest","shortest","shortest"] [[["cat","dog","bird","bird","cat","fish"]],["dog","fish"],["cat","bird"],["fish","cat"]]
Output: [null,4,1,1]
"dog" (1) and "fish" (5) are 4 apart. "bird" at 3 is adjacent to "cat" at 4, and "fish" at 5 is adjacent to that same "cat".

Constraints

  • 2 <= wordsDict.length <= 3 * 10^4
  • 1 <= wordsDict[i].length <= 10, lowercase English letters
  • `word1 != word2`, and both occur in `wordsDict`
  • At most 5000 calls to `shortest`

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More hashing problems