Shortest Word Distance II

Asked atLinkedin
1Give yourself 5 minutes
2Answer out loud, not in your head
3Then compare with the answer below

The problem

Design a data structure that will be initialized with a string array, and then it should answer queries of the shortest distance between two different strings from the array.

Implement the WordDistance class:

  • **WordDistance(String[] wordsDict) **initializes the object with the strings array wordsDict.
  • int shortest(String word1, String word2) returns the shortest distance between word1 and word2 in the array wordsDict.

**Input: **calls= ["WordDistance", "shortest", "shortest"], params = [[["practice", "makes", "perfect", "coding", "makes"]], ["coding", "practice"], ["makes", "coding"]] **Output: **[null, 3, 1] Explanation:

  • WordDistance wordDistance = new WordDistance(["practice", "makes", "perfect", "coding", "makes"]);
  • wordDistance.shortest("coding", "practice"); // return 3
  • wordDistance.shortest("makes", "coding"); // return 1

**Input: **calls = ["WordDistance", "shortest", "shortest"], params = [["practice", "makes", "perfect", "coding", "makes"]], ["coding", "perfect"], ["makes", "perfect"]] **Output: **[null,1,1] Explanation:

  • WordDistance wordDistance = new WordDistance(["practice", "makes", "perfect", "coding", "makes"]);
  • wordDistance.shortest("coding", "perfect"); // return 1
  • wordDistance.shortest("makes", "perfect"); // return 1
  • 1 <= wordsDict.length <= 3 * 104
  • 1 <= wordsDict[i].length <= 10
  • wordsDict[i] consists of lowercase English letters.
  • word1 and word2 are in wordsDict.
  • word1 != word2
  • At most 5000 calls will be made to shortest.

cpp

class WordDistance {
public:
    WordDistance(vector<string>& wordsDict) {
        
    }
    
    int shortest(string word1, string word2) {
        
    }
};

/**
 * Your WordDistance object will be instantiated and called as such:
 * WordDistance* obj = new WordDistance(wordsDict);
 * int param_1 = obj->shortest(word1,word2);
 */

java

class WordDistance {

    public WordDistance(String[] wordsDict) {
        
    }
    
    public int shortest(String word1, String word2) {
        
    }
}

/**
 * Your WordDistance object will be instantiated and called as such:
 * WordDistance obj = new WordDistance(wordsDict);
 * int param_1 = obj.shortest(word1,word2);
 */

python

class WordDistance(object):

    def __init__(self, wordsDict):
        """
        :type wordsDict: List[str]
        """
        

    def shortest(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        


# Your WordDistance object will be instantiated and called as such:
# obj = WordDistance(wordsDict)
# param_1 = obj.shortest(word1,word2)

javascript

/**
 * @param {string[]} wordsDict
 */
var WordDistance = function(wordsDict) {
    
};

/** 
 * @param {string} word1 
 * @param {string} word2
 * @return {number}
 */
WordDistance.prototype.shortest = function(word1, word2) {
    
};

/** 
 * Your WordDistance object will be instantiated and called as such:
 * var obj = new WordDistance(wordsDict)
 * var param_1 = obj.shortest(word1,word2)
 */

csharp

public class WordDistance
{

    public WordDistance(string[] wordsDict)
    {

    }

    public int shortest(string word1, string word2)
    {

    }
}

/**
 * Your WordDistance object will be instantiated and called as such:
 * WordDistance obj = new WordDistance(wordsDict);
 * int param_1 = obj.shortest(word1,word2);
 */

go

type WordDistance struct {
	// You may add fields here, e.g., wordIndices map[string][]int
}

func Constructor(wordsDict []string) WordDistance {
	// Implement your constructor logic here
	return WordDistance{}
}

func (wd *WordDistance) Shortest(word1 string, word2 string) int {
	// Implement your shortest method logic here
	return 0
}
Stuck? Show a way to structure it+
  1. 01Map every word to its sorted occurrence indices.
  2. 02Build this map once in the constructor.
  3. 03For a query, walk two position lists with two pointers.
  4. 04Update the minimum absolute difference.
  5. 05Advance the smaller position.

Reference answer

Then expect these follow-ups

  • How would you handle queries where the two words are equal?

    Tests: follow-up reasoning

  • When would caching query answers help?

    Tests: follow-up reasoning

Hiring now

Linkedin has 196 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.
  • Software Engineer - Systems and Infrastructure

    Mountain View, CA, United States

  • Staff Software Engineer

    Mountain View, CA, United States

  • Staff Software Engineer, Systems Infrastructure

    Bengaluru, KA, India

Or practice this question first

Next question