CareerCup

Wow ... they asked me the exact same question during my phone interview. Should have prepared a little better, I guess. The idea to simply treat the occurrences of each word as a array of indexes came to me pretty quickly, but then I spent too much time ascertaining which combinations of indexes I would need to pair to cover all relevant distances.

Fortunately, I found a solution eventually, and I remember it seemingly being shorter (and maybe even simpler) than any of the solutions here, from what I can tell glancing over the solutions. Will post it shortly ...

Trying to think if this can solved in less than O(n) time.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class WordFinder {
	private Map<String, ArrayList<Integer>> dictionary = new HashMap<String, ArrayList<Integer>>();

	public WordFinder(String[] list) {
		for (int i = 0; i < list.length; i++) {
			addToDictionary(list[i], i);
		}
	}

	private void addToDictionary(String word, int position) {
		ArrayList<Integer> positions = dictionary.get(word);
		if (positions == null) {
			positions = new ArrayList<Integer>();
		}

		positions.add(position);
		dictionary.put(word, positions);
	}

	public int findDistance(String a, String b) {
		if (a == null || b == null) {
			return -1;
		}

		if (a.equals(b)) {
			return 0;
		}
		ArrayList<Integer> posA = dictionary.get(a);
		ArrayList<Integer> posB = dictionary.get(b);
		if (posA == null || posB == null) {
			return -1;
		}

		int min = 0;
		for (int x : posA) {
			for (int y : posB) {
				int distance = Math.abs(x - y);
				if (min > distance || min == 0) {
					min = distance;
				}
			}
		}

		return min;
	}

	public static void main(String[] args) {
		String[] a = new String[] { "the", "quick", "brown", "fox", "quick" };
		WordFinder distanceFinder = new WordFinder(a);
		System.out.println("Distance between words is: "
				+ distanceFinder.findDistance("fox", "the"));
		System.out.println("Distance between words is: "
				+ distanceFinder.findDistance("quick", "fox"));
		System.out.println("Distance between words is: "
				+ distanceFinder.findDistance("brown", "brown"));
		System.out.println("Distance between words is: "
				+ distanceFinder.findDistance("apple", "mango"));
	}
}

public class WordDistanceFinder {
	
	private String[] text;
	
	public WordDistanceFinder(String[] list) {
		this.text = list;
	}

	/**
	 * Brute Force method to find the distance between two words.
	 * Time Complexity: O(n)
	 * Space Complexity: O(1)
	 * 
	 */
	public int findDistance(String a, String b) {
		int size = text.length;
		int distance = -1; //distance between words to be sent as output when they are not present in the given text
		
		/* When both words are same then distance should be zero*/
		if(a == b) {
			return 0; 
		}
		for(int i = 0; i < size; i++) {
			if(text[i] == a || text[i] == b) {
				 boolean temp = text[i] == a;
				 b = temp ? b : a; //Search for b if a is found or search for a
				 distance++; //reset distance from -1 to 0
				 
				 while(i < (size - 1) && text[i] != b) {
					 i++;
					 distance++;
					 if(text[i] == b) {
						 return distance;
					 }					 
				 }
			}
		}
		
		return distance;
	}
	
	public static void main(String[] args) {
		
		String[] a = new String[] {"the", "quick", "brown", "fox", "quick"};
		WordDistanceFinder distanceFinder = new WordDistanceFinder(a);
		
		System.out.println("Distance between words is: " + distanceFinder.findDistance("fox", "the"));
		System.out.println("Distance between words is: " + distanceFinder.findDistance("quick", "fox"));
		System.out.println("Distance between words is: " + distanceFinder.findDistance("brown", "brown"));
		System.out.println("Distance between words is: " + distanceFinder.findDistance("apple", "mango"));

	}

}

public static int getMinDistance(List<String> list, String A, String B){
    if(list == null || A == null || B == null) return -1;
    if(A.equals(B)) return 0;

    int minDistance = -1, indexOfA = -1, indexOfB = -1;
    for(int i = 0; i < list.size(); ++i){
        String word = list.get(i);
        if(word.equals(A)){
            if(indexOfB >= 0){
                minDistance = minDistance == -1 ? i - indexOfB : Math.min(minDistance, i - indexOfB);
            }
            indexOfA = i;
        }
        else if(word.equals(B)){
            if(indexOfA >= 0){
                minDistance = minDistance == -1 ? i - indexOfA : Math.min(minDistance, i - indexOfA);
            }
            indexOfB = i;
        }
    }
    return minDistance;
}

public class WordDistanceFinder {
	
	private List<String> wordList;
	
	public WordDistanceFinder(List<String> list) {
		this.wordList = list;
	}
	
	public int distance(String word1, String word2) {
		String[] wordsArray = wordList.toArray(new String[wordList.size()]);
		
		int word1Pos = 0;
		int word2Pos = 0;
		int distance = 0;
		boolean word1Found = false;
		boolean word2Found = false;
		for (int i=0; i<wordsArray.length; i++) {
			if ((wordsArray[i].equals(word1))) {
				if (!word1Found) {
					word1Found = true;
					word1Pos = i;
				} else {
					if (!word2Found) word1Pos = i;
					else if (distance > Math.abs(i - word2Pos)) word1Pos = i;
					
				}
			} else if ((wordsArray[i].equals(word2))) {
				 if (!word2Found) {
					word2Found = true;
					word2Pos = i;
				 } else {
					 if (!word1Found) word2Pos = i;
					 else if (distance > Math.abs(word1Pos - i)) word2Pos = i;
				 }
			}
			distance = Math.abs(word1Pos - word2Pos);
		}			
		return distance;
	}
	
}

This is my solution. I was going for an O(1) solution - but could not figure out a way to do it with duplicate words.

Assuming all the words are unique then it's easy - figuring out the min distance between two points is where the time complexity comes in.

Can anyone think of a solution that doesn't have nested for loops?

/**
 * 
 */
package WordDistance;

import java.util.Arrays;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;


/**
 * 
 * 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);
 */
public class WordDistanceFinder {

	private HashMap<String, ArrayList<Integer>> map = new HashMap<String, ArrayList<Integer>>();

	public WordDistanceFinder(List<String> list) {

		for (int i = 0; i < list.size(); i++) {

			String word = list.get(i);

			if (this.map.containsKey(word)) {
				ArrayList<Integer> positions = this.map.get(word);
				positions.add(i); // since we add in order we assume positions
									// is sorted
				this.map.put(word, positions);

			} else {
				ArrayList<Integer> positions = new ArrayList<Integer>();
				positions.add(i);
				this.map.put(word, positions);
			}

		}

	}

	/*
	 * Return the distance between words
	 * 
	 * Cases to consider: 
	 * 1. word(s) does not exist - return -1 
	 * 2. Repeated words - which one counts? ASSUME min 
	 * 3. what if a = b? for example quick ASSUME 0
	 */
	public int distance(String a, String b) {
		if (map.containsKey(a) && map.containsKey(b)) {
			// return Math.abs(map.get(a) - map.get(b)); //only works if words
			// are unique

			ArrayList<Integer> positionsA = map.get(a);
			ArrayList<Integer> positionsB = map.get(b);

			ArrayList<Integer> distances = new ArrayList<Integer>();

			for (Integer i : positionsA) {
				for (Integer j : positionsB) {
					distances.add(Math.abs(i - j));
				}
			}

			return Collections.min(distances);
		}

		else
			return -1;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		WordDistanceFinder finder = new WordDistanceFinder(Arrays.asList("the", "quick", "brown", "fox", "quick"));

		System.out.println(finder.distance("fox", "the") == 3);
		System.out.println(finder.distance("quick", "fox") == 1);
		System.out.println(finder.distance("quick", "quick") == 0);
		System.out.println(finder.distance("quick", "the") == 1);
	}

}

Create a Map<String, List<Integer> using the word as the key and the position (index) in the list.

e.g.
"the", "quick", "brown", "fox", "quick"
Quick entry would be "Quick", {1,4}

To calculate the distance just compare the positions of the two words and return the smallest one.

private Map<String, ArrayList<Integer>> dictionary = new HashMap<String, ArrayList<Integer>>();

	public WordFinder(String[] list) {
		for (int i = 0; i < list.length; i++) {
			addToDictionary(list[i], i);
		}
	}

	private void addToDictionary(String word, int position) {
		ArrayList<Integer> positions = dictionary.get(word);
		if (positions == null) {
			positions = new ArrayList<Integer>();
		}

		positions.add(position);
		dictionary.put(word, positions);
	}

	public int findDistance(String a, String b) {
		if (a == null || b == null) {
			return -1;
		}

		if (a.equals(b)) {
			return 0;
		}
		ArrayList<Integer> posA = dictionary.get(a);
		ArrayList<Integer> posB = dictionary.get(b);
		if (posA == null || posB == null) {
			return -1;
		}

		int min = 0;
		for (int x : posA) {
			for (int y : posB) {
				int distance = Math.abs(x - y);
				if (min > distance || min == 0) {
					min = distance;
				}
			}
		}

		return min;
	}

O(n) solution
O(1) space

public int findShortestDistance(String[] words, String a, String b) {
        Map<String, Integer> parityValueMap = new HashMap<String, Integer>();
        parityValueMap.put(a, 0);
        parityValueMap.put(b, 1);

        Map<String, Integer> posMap = new HashMap<String, Integer>();
        posMap.put(a, 0);
        posMap.put(b, 0);
        int[] min = new int[words.length];
        int minDistance = Integer.MAX_VALUE;
        Integer parityValue = Integer.MAX_VALUE;
        int wordsLength = words.length;
        for (int i = 0; i < wordsLength; i ++) {
            if (parityValueMap.containsKey(words[i])) {
                posMap.put(words[i], i);
                // First time we see a required word
                if (parityValue == Integer.MAX_VALUE) {
                    parityValue = parityValueMap.get(words[i]);
                    // we found the word other than the one found last time so lets calculate distance
                } else if (!parityValue.equals(parityValueMap.get(words[i]))) {
                    parityValue = parityValueMap.get(words[i]);
                    int tempMin = posMap.get(words[i]) - posMap.get(words[i].equals(a)? b : a);
                    if (tempMin < minDistance) {
                        minDistance = tempMin;
                    }
                }
            }
        }
        return minDistance;
    }

Find any word out of the two
if you find a word out of the given two , save its position
if you find the same word as you did the last time, update its position and continue
if you find the other word, update its position and calculate distance and update min distance if its lower than before

use a flip bit to mark which word did you see before.

import java.util.ArrayList;
import java.util.HashMap;

public class Finder {
	HashMap<String,ArrayList<Integer>> words;
		
	public Finder(String w[]) {
		words = new HashMap<String,ArrayList<Integer>>();
		for (int i = 0; i < w.length; i++) {
			ArrayList<Integer> l = new ArrayList<Integer>();
			if (!words.containsKey(w[i])) {
				l.add(i);
				words.put(w[i], l);
			} else {
				l = words.get(w[i]);
				l.add(i);				
			}
		}
	}
	
	public int distance(String a, String b) {
		if (a.equals(b)) {
			return 0;
		}
		ArrayList<Integer> indices_a = words.get(a);
		ArrayList<Integer> indices_b = words.get(b);
		int dist = -1;		
		int min_dist = Math.abs(indices_a.get(0) - indices_b.get(0));
		for (int l = 0; l < indices_a.size() ; l++) {
			for (int m = 0; m < indices_b.size(); m++) {
				dist = Math.abs(indices_a.get(l) - indices_b.get(m));
				if (dist == 1)
					return 1;
				if (dist < min_dist) {
					min_dist = dist;
				}
			}
		}
		return min_dist;
	}
	
	public void printWords(){
		System.out.println(words);
	}
	
	public static void main(String[] args) {
		String w[] = new String[] {"the", "quick", "brown", "fox", "quick"};
		Finder myFinder = new Finder(w);
		myFinder.printWords();
		System.out.println(myFinder.distance("fox","quick"));
	}

}

{{
public class WordsDistance {
public int distance(String a, String b, String[] array) {
int minDist = -1;
String stored = null;
int storedIndex = -1;


for(int i=0; i<array.length; i++) {
if(array[i] == a || array[i] == b) {
if(stored != null) {
if(stored != array[i]) {
if (minDist != -1) {
minDist = Math.min(minDist, i - storedIndex);
} else {
minDist = i - storedIndex;
}
}
}
stored = array[i];
storedIndex = i;
}
}
return minDist;
}

public static void main(String[] args) {
WordsDistance wd = new WordsDistance();
String[] input = {"the", "quick", "brown", "fox", "quick"};
int dist = wd.distance("quick", "fox", input);

System.out.print("min dist is " + dist);
}
}

}}

public class WordsDistance {
	public int distance(String a, String b, String[] array) {
		int minDist = -1;
		String stored = null;
		int storedIndex = -1;
		
		
		for(int i=0; i<array.length; i++) {
			if(array[i] == a || array[i] == b) {
				if(stored != null) {
					if(stored != array[i]) {
						if (minDist != -1) {
							minDist = Math.min(minDist, i - storedIndex);
						} else {
							minDist = i - storedIndex;
						}
					}
				}
				stored = array[i];
				storedIndex = i;
			}
		}
		return minDist;
	}
	
	public static void main(String[] args) {
		WordsDistance wd = new WordsDistance();
		String[] input = {"the", "quick", "brown", "fox", "quick"};
		int dist = wd.distance("quick", "fox", input);
		
		System.out.print("min dist is " + dist);
	}
}

void distanceBetweenWords(char a[],char b[])
{
char *str[] = {"the\0", "quick\0", "brown\0", "fox\0","quick\0"};
int posA = -1;
int posB = -1;
for(int i=0;i<5;i++)
{
if(strcmp(str[i], a) == 0 || strcmp(str[i], b) == 0)
{
if(!strcmp(str[i], a))
{
if(posA == -1)
posA = i;
else if(abs(posA - posB) > abs(i - posB))
posA = i;
}
else if(!strcmp(str[i], b))
{
if(posB == -1)
posB = i;
else if(abs(posA - posB) > abs(i - posA))
posB = i;
}
}

}
printf("distance : %d",abs(posA - posB));
}

public class FindShortestDistanceWords {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String[] inputArray = { "the", "quick", "brown", "fox", "summer",
				"fox", "the", "brown", "fox", "summers", "quick", "quick",
				"quick", "summer", "fox" };

		System.out.println("Minimum Distance between (the) and (fox) "
				+ findSDistance(inputArray, "the", "fox"));
		System.out.println("Minimum Distance between (quick) and (fox) "
				+ findSDistance(inputArray, "quick", "fox"));

	}

	private static int findSDistance(String[] inputArray, String string1,
			String string2) {
		// TODO Auto-generated method stub
		int string1Index = -1;
		int string2Index = -1;
		int minDistance = Integer.MAX_VALUE;
		for (int i = 0; i < inputArray.length; i++) {
			if (inputArray[i].equals(string1)) {
				string1Index = i;
			}
			if (inputArray[i].equals(string2)) {
				string2Index = i;
			}
			if (minDistance > Math.abs(string1Index - string2Index)
					&& (string1Index != -1 && string2Index != -1)) {
				minDistance = Math.abs(string1Index - string2Index);
			}

		}
		return minDistance;

	}

}

public class WordDistanceFinder {
    List<String> input;

    WordDistanceFinder(List<String> input) {
        this.input = input;
    }

    public static void main(String[] args) {
        WordDistanceFinder finder = new WordDistanceFinder(Arrays.asList("the",
                "quick", "brown", "fox", "quick"));
        System.out.println((finder.distance("fox", "the") == 3));
        System.out.println((finder.distance("quick", "fox") == 1));

    }

    int distance(String a, String b) {
        int distance = 0;
        Map<String, Integer> pMap = new HashMap<String, Integer>();
        for (int i = 0; i < input.size(); i++) {
            if (pMap.get(a) != null && pMap.get(b) != null) {
                distance = Math.abs(pMap.get(a) - pMap.get(b));
                if (input.get(i).equals(a)) {
                    if (Math.abs(i - pMap.get(b)) < distance) {
                        distance = Math.abs(i - pMap.get(b));
                        pMap.put(input.get(i), i);
                    }
                } else if (input.get(i).equals(b)) {
                    if (Math.abs(i - pMap.get(a)) < distance) {
                        distance = Math.abs(i - pMap.get(a));
                        pMap.put(input.get(i), i);
                    }
                } else {
                    pMap.put(input.get(i), i);
                }
            } else {
                pMap.put(input.get(i), i);
            }
        }
        return distance;
    }
}

int distance(vector<string> & dict, string word1, string word2){
    if(dict.size() < 2) return -1;
    int lastWord1 = -1, lastWord2 = -1;
    int minDistance = INT_MAX;
    for(int i = 0; i < dict.size(); i++){
        if(dict[i] == word1){
            lastWord1 = i;
            if(lastWord2 != -1){
                int distance = i - lastWord2 -1;
                minDistance = distance < minDistance? distance:minDistance;
            }
        }
        if(dict[i] == word2){
            lastWord2 = i;
            if(lastWord1 != -1){
                int distance = i - lastWord1 -1;
                minDistance = distance < minDistance? distance:minDistance;
            }
        }
    }
    return minDistance == INT_MAX? -1: minDistance;

int distance(vector<string> & dict, string word1, string word2){
    if(dict.size() < 2) return -1;
    int lastWord1 = -1, lastWord2 = -1;
    int minDistance = INT_MAX;
    for(int i = 0; i < dict.size(); i++){
        if(dict[i] == word1){
            lastWord1 = i;
            if(lastWord2 != -1){
                int distance = i - lastWord2 -1;
                minDistance = distance < minDistance? distance:minDistance;
            }
        }
        if(dict[i] == word2){
            lastWord2 = i;
            if(lastWord1 != -1){
                int distance = i - lastWord1 -1;
                minDistance = distance < minDistance? distance:minDistance;
            }
        }
    }
    return minDistance == INT_MAX? -1: minDistance;

/*
*
* Probably a bit verbose, but (for me) a stack fits naturally with process of checking which value was processed last (word1? or word2?)
*
* Description of this simple algorithm:
*
* - At the beginning the stack is empty, so you just push the fist index of the word encountered then the word itself
*
* - if You encounter another word, peek the stack :

* * If they match, then just clear it and push the new index and word
* * Otherwise we have a different word, compute the distance (you have to do couple of pushs), update if necessary
* then push new index and word
*
*/

public static int shortestDistance(String[] words, String word1, String word2) {
		int minValue = Integer.MAX_VALUE;
		// Use a Stack so you would remember what was the last word seen 1 or 2
		Stack<String> stack = new Stack<String>(); 	
		for (int i=0; i < words.length; i++) {
			if (words[i]==word1 || words[i]==word2) {
				// if Stack is empty, simply push index then the word
				if (stack.isEmpty()) {
					stack.push(String.valueOf(i));
					stack.push(words[i]);	
				}
				else {
				// if same value clear stack and put new Value
					if (stack.peek()==words[i]) {
						stack.clear();
						stack.push(String.valueOf(i));
						stack.push(words[i]);	
					}
					else {
						// At the top of the stack, you have the value of the last word processed, plus it sits on top of its index
						// remove top value as it's useless ( first pop()), then get the index (second pop() )
						stack.pop();
						int i1 = Integer.valueOf(stack.pop());
						int localMin = Math.abs(i-i1);
						if (localMin < minValue) {
							minValue = localMin;
						}
						// don't forget to push the last values seen (process should carry on, otherwise stack would be empty ...)
						stack.push(String.valueOf(i));
						stack.push(words[i]);	
					}
				}
			}	
		}
		return minValue;
	}

The code complexity is O(n) and space complexity is O(1)

int distance(vector<string> list,string s1, string s2)
{
	int distance = list.size();
	int index1 = -1;
	int index2 = -1;

	for(unsigned int i=0;i<list.size();i++)
	{
		if(list[i].compare(s1) == 0)
		{
			index1=i;
		}

		if(list[i].compare(s2) == 0)
		{
			index2=i;
		}

		if((index1 != -1 && index2 != -1) && distance > abs(index1 - index2))
		{
			distance = abs(index2-index1);
		}
	}

	if(index1 == -1 || index2 == -1)
		distance = -1;

	return distance;
}

public static int distance(List<String> words, String word1, String word2) {
		if (words == null || words.isEmpty()) {
			return -1;
		}

		String[] strArr = (String[]) words.toArray();
    	List<Integer> indexesWord1 = new ArrayList<Integer>();
    	List<Integer> indexesWord2 = new ArrayList<Integer>();		

		// build all indexes of word 1 and 2.		
		for (int j = 0; j < strArr.length; j++) {
			if (strArr[j].equals(word1)) {
				indexesWord1.add(j);
			} else if (strArr[j].equals(word2)) {
				indexesWord2.add(j);
			}
		}				
		
		if(indexesWord1.isEmpty() || indexesWord2.isEmpty()) {
			return -1;
		}
		
		// check from indexes the min distance
		int minFoundSoFar = Integer.MAX_VALUE;
		for (Integer i : indexesWord1) {
			for (Integer j : indexesWord2) {
				if (i < j) {
					int dist = (j - i);
					if (dist < minFoundSoFar) {
						minFoundSoFar = dist;
					}
				} else if (i > j) {
					int dist = (i - j);
					if (dist < minFoundSoFar) {
						minFoundSoFar = dist;
					}					
				}		
			}			
		}
				
		if (minFoundSoFar != Integer.MAX_VALUE) {
			return minFoundSoFar;
		}
			
		return -1;
	}

Add all the words to a hashmap with word as key and value as index.
then return ABS(word1.value - word2.value).

This WILL work for duplicates, if its ok to return nearest distance or longest distance, not both.

By using HashMap, this problem can be solved efficiently

public class ShortestDistBwWords {

private HashMap<String, ArrayList<Integer>> map = new HashMap<String, ArrayList<Integer>>();
private ArrayList<Integer> indexArray;

ShortestDistBwWords (String strs []) {
for (int i = 0; i < strs.length; i++) {
if (map.containsKey(strs[i])) {
indexArray = map.get(strs[i]);
} else {
indexArray = new ArrayList<Integer>();
}
indexArray.add(i);
map.put(strs[i], indexArray);
}
}

int distance (String word1, String word2) {

if (!map.containsKey(word1) || !map.containsKey(word2))
return -1;

ArrayList<Integer> indexArrayWord1 = map.get(word1);
ArrayList<Integer> indexArrayWord2 = map.get(word2);

int min = map.size();

for (int i: indexArrayWord1) {
for (int j: indexArrayWord2) {
if (Math.abs(i - j) < min)
min = Math.abs(i - j);
}
}

System.out.println(min);
return min;
}

public static void main (String [] args) {

String [] strArgs = {"the", "quick", "brown", "fox", "quick"};
ShortestDistBwWords sh = new ShortestDistBwWords(strArgs);

sh.distance("fox", "the");
sh.distance("quick", "fox");
}
}

var input = ["car", "toy", "bike", "scooter", "cycle", "bike", "car"];
function getDistance(input, word1, word2){
var pos1 = -1, pos2 = -1;
var minDistance = 100;
for(var i = 0; i < input.length; i++){
if(input[i] == word1)
pos1 = i;
if(input[i] == word2)
pos2 = i;
console.log(pos1, pos2);
if(pos1 != -1 && pos2 != -1){
if(minDistance > Math.abs(pos2 - pos1))
minDistance = Math.abs(pos2 - pos1);
}
}
return minDistance;
};
var distance = getDistance(input, "car", "bike");
console.log(distance);