For my phone (and Collabedit) question, I was asked to implement functionality matching the description of this API:

/* This class will be given a list of words (such as might be tokenized
* from a paragraph of text), and will provide a method that takes two
* words and returns the shortest distance (in words) between those two
* words in the provided text.
* Example:
* WordDistanceFinder finder = new WordDistanceFinder(Arrays.asList("the", "quick", "brown", "fox", "quick"));
* assert(finder.distance("fox", "the") == 3);
* assert(finder.distance("quick", "fox") == 1);
*
* "quick" appears twice in the input. There are two possible distance values for "quick" and "fox":
* (3 - 1) = 2 and (4 - 3) = 1.
* Since we have to return the shortest distance between the two words we return 1.
*/

Question

For my phone (and Collabedit) question, I was asked to implement functionality matching the description of this API:

/* This class will be given a list of words (such as might be tokenized
 * from a paragraph of text), and will provide a method that takes two
 * words and returns the shortest distance (in words) between those two
 * words in the provided text.
 * Example:
 *   WordDistanceFinder finder = new WordDistanceFinder(Arrays.asList("the", "quick", "brown", "fox", "quick"));
 *   assert(finder.distance("fox", "the") == 3);
 *   assert(finder.distance("quick", "fox") == 1);
 *
 * "quick" appears twice in the input. There are two possible distance values for "quick" and "fox":
 *     (3 - 1) = 2 and (4 - 3) = 1.
 * Since we have to return the shortest distance between the two words we return 1.
 */

Anonymous · Accepted Answer

My original — over the phone — solution was in Objective C and was a bit more brute force than this, but here is an optimized version in Swift.  

The minimum distance between elements of the two arrays was my original idea but the Swift code that finds indexes for matching words in the word array is definitely not very intuitive (I used StackOverflow to find those “enumerated” lines; something I couldn’t have done quickly or easily while on the phone with the LinkedIn interviewer).

class WordDistanceFinder
{
    var words : [String]?
    
    init(array : [String])
    {
        words = array
    }
    
    func distance(_ word1: String, _ word2: String) -> Int
    {
        var distance = 99999
        
        // dereference optional
        if let words = words
        {
            // find indexes for word1 matches in the word array
            let arrayA = words.enumerated().filter {
                $0.element.contains(word1)
                }.map{$0.offset}

            // and word2, too
            let arrayB = words.enumerated().filter {
                $0.element.contains(word2)
                }.map{$0.offset}
            
            // now use binary search to find element with closest value in the index arrays
            var i = 0
            var j = 0
            var finished = false
            
            repeat {
                if arrayA[i] == arrayB[j]
                {
                    return 0
                }
                
                let diff = abs(arrayA[i] - arrayB[j])
                
                distance = min(distance, diff)

                if arrayA[i] > arrayB[j]
                {
                    j = j+1
                } else {
                    i = i+1
                }
                
                if(j >= arrayB.count)
                {
                    finished = true
                }
                
                if(i >= arrayA.count)
                {
                    finished = true
                }
            } while (finished == false)
                
        }
        
        return distance;
    }
}

which you can test with a main.swift that looks like:

let wordDistanceFinderObject = WordDistanceFinder(array: ["the", "quick", "brown", "fox", "quick"])

let distance = wordDistanceFinderObject.distance("fox", "the")

Sav · Answer

using two pointers from the beginning of the list.

for(int i=0; i

LinkedIn

LinkedIn Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches