Coding questions · LinkedIn

Answer Repeated Shortest Word Distance Queries

Preprocess a fixed word array and answer many shortest-distance queries between distinct repeated words. The prompt defines case-sensitive matching, ordered batch outputs, repeated queries, valid-word guarantees, and input sizes that reward indexed occurrence lists and two-pointer scans.

You are given a fixed array words and many queries. Each query contains two distinct words that both appear in the array.

For each query, return the minimum absolute difference between an index containing the first word and an index containing the second word.

Implement:

shortestWordDistances(words, queries) -> integer[]

Preprocess the word array once, then answer queries in order. Word comparison is case-sensitive, and repeated identical queries must produce repeated answers.

Constraints

1 <= words.length <= 200,000
1 <= queries.length <= 200,000
Every query has exactly two distinct words present in words.

Examples

Example 1

words = ["practice", "makes", "perfect", "coding", "makes"]
queries = [["coding", "practice"], ["makes", "coding"]]
output = [3, 1]

Example 2

words = ["a", "b", "a", "c", "b", "a"]
queries = [["a", "b"], ["a", "c"], ["a", "b"]]
output = [1, 1, 1]

Answer Repeated Shortest Word Distance Queries

Hints

Store the sorted positions at which each word occurs.
Repeated queries may reuse a previously computed distance but still need repeated output entries.

Approach

Build a sorted occurrence-index list for every word in one pass over words. For a query, merge its two occurrence lists with two pointers. The smaller current index can be advanced because keeping it cannot improve the distance to any later index on the other list; checking every crossed pair this way therefore finds the minimum. Cache the answer in both word orders so repeated or reversed queries do not repeat the merge, while still appending an answer for every query position.

Time complexity: O(n + q + sum(a+b) over first-seen unordered query pairs), where a and b are the queried words' occurrence counts.
Space complexity: O(n + p + q) for occurrence lists, cached pairs, and the returned answers.