Answer Repeated Shortest Word Distance Queries

Question

This question asks the candidate to implement a solution for repeated shortest word distance queries between two words in a list of words.

Codemia · Accepted Answer

To solve the problem of finding the shortest distance between two words in a list, we can utilize a hash map to store the indices of each word. This allows us to quickly access the positions of the words when processing queries. For each query, we can then calculate the distance by comparing the indices.

1. Create a hash map to store the indices of each word in the list.
2. For each query, retrieve the lists of indices for both words.
3. Use a two-pointer technique to find the minimum distance between the two lists of indices. This involves iterating through both lists simultaneously and updating the minimum distance found.

The time complexity for preprocessing the words into a hash map is O(n), where n is the number of words. Each query can be answered in O(k) time, where k is the length of the shorter list of indices. Therefore, the overall complexity for q queries is O(n + q * k). The space complexity is O(n) due to the hash map.

```python
class WordDistance:
    def __init__(self, wordsDict: List[str]):
        self.word_indices = defaultdict(list)
        for index, word in enumerate(wordsDict):
            self.word_indices[word].append(index)

def shortest(self, word1: str, word2: str) -> int:
        indices1 = self.word_indices[word1]
        indices2 = self.word_indices[word2]
        i, j, min_distance = 0, 0, float('inf')
        while i < len(indices1) and j < len(indices2):
            min_distance = min(min_distance, abs(indices1[i] - indices2[j]))
            if indices1[i] < indices2[j]:
                i += 1
            else:
                j += 1
        return min_distance
```

Interviewers will look for clarity in your explanation and whether you can articulate the reasoning behind your approach. They will also evaluate your coding style, efficiency of the solution, and your ability to handle edge cases and potential errors.

Answer Repeated Shortest Word Distance Queries

LinkedIn

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

LinkedIn Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string