## Linkedin Interview Question for Software Engineer / Developers

• 0

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
2
of 2 vote

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 ...

Comment hidden because of low score. Click to expand.
0

Here it is:

``````static int Distance(string[] words, string word1, string word2)
{
int min = words.Length;
int last1 = -1;
int last2 = -1;

for (int i = 0; i < words.Length; i++)
{
if (words[i] == word1) last1 = i;
if (words[i] == word2) last2 = i;

if ((words[i] == word1 || words[i] == word2)
&& (last1 != -1 && last2 != -1))
{
int newDist = Math.Abs(last1 - last2);
min = Math.Min(newDist, min);
}
}
return min;
}``````

I thought I had done badly in the interview. Anyone see any bugs?

Comment hidden because of low score. Click to expand.
0

This time again with syntax highlighting?

``````static int Distance(string[] words, string word1, string word2)
{
int min = words.Length;
int last1 = -1;
int last2 = -1;

for (int i = 0; i < words.Length; i++)
{
if (words[i] == word1) last1 = i;
if (words[i] == word2) last2 = i;

if ((words[i] == word1 || words[i] == word2)
&& (last1 != -1 && last2 != -1))
min = Math.Min(Math.Abs(last1 - last2), min);
}
return min;
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

The problem with your code is that it will return incorrect length (words.Length) if one or both of the words are not found in the list/array.

``````internal class WordDistanceFinder
{
private string [] listOfWords = null;

public WordDistanceFinder(string[] listOfWords)
{
this.listOfWords = listOfWords;
}

public int Distance(string word1, string word2)
{
if (listOfWords == null || String.IsNullOrEmpty(word1) || String.IsNullOrEmpty(word2))
return -1; // something was wrong. We could also throw exception, if that is part of spec.

int index1 = -1;
int index2= -1;
int minDistance = Int32.MaxValue;

for(int i=0; i < listOfWords.Length; i++)
{
if (listOfWords[i] == word1)
index1 = i;
if (listOfWords[i] == word2)
index2 = i;

if (index1 != -1 && index2 != -1 && minDistance > Math.Abs(index1 - index2))
minDistance = Math.Abs(index1 - index2);
}

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

return minDistance;
}
}``````

Comment hidden because of low score. Click to expand.
3

I got the same question during my interview. The tricky part was that the Distance method was going to be called over and over again. So they wanted to improve the time complexity of Distance. What I did was in the constructor, take the list of words and create a hashtable with the keys being the words, and the values being a list of indexes referencing the location of the words in the sentence.

In the distance method, I just get the list of indexes from the two words passed in and find the smallest difference in indexes between the two words. Note: the list of indexes is already in ascending order so this will make finding the smallest difference easier and more efficient. Entire class took about like 30 lines of code.

This seemed to be what they were looking for since I moved onto the next step in the interview process. Let me know if you need some sample code.

Comment hidden because of low score. Click to expand.
0

Can you please provide the solution for method which is using HashMap. Its sounds efficient but I am confused that how should I get the list of indexing from HashMap for the given words, because if I iterate whole map to make a list of indices for both of the words, won't it be time taking? I am not sure though.

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0

it can test this code

``````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

it runs in O(n)
space complexity is constant O(1)

Comment hidden because of low score. Click to expand.
0

Same implementation using a tristate variable. (not found=0, found a=1, found b=2).This is a linear solution, with constant space requirement.
It handles corner cases such as neither a or b is in array, or only on is in array. In the first case it throws exception. In the second case it returns maximum integer as the distance.

Can anyone find a solution less than linear?

``````public static int dist(String[] data, String a, String b) {
int state=0; //tristate 0, 1, 2
int length = data.length;
int previous = 0;
int distance = Integer.MAX_VALUE;

for (int i=0; i<length; i++) {
String str = data[i];
if (str.equals(a)||str.equals(b)) {
if (state==0) {
state= str.equals(a)? 1:2;
previous=i;
}
else if (state==1) {
if (str.equals(b)) //found b
{
if (distance>i-previous) distance = i-previous;
state=2;
}
previous=i;
}
else if (state==2) {
if (str.equals(a)) //found a
{
if (distance>i-previous) distance=i-previous;
state = 1;
}
previous=i;
}
}
}
return distance;
}``````

Comment hidden because of low score. Click to expand.
0

Without the pre-processing step, Linear time is the best time. But in case of multiple queries, an O(n) time pre-processing step will drastically reduce the running time per query.

I posted my version of the solution below. Leave me some feedback.

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````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++) {
}
}

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

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"));
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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"));

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
// is sorted
this.map.put(word, positions);

} else {
ArrayList<Integer> positions = new ArrayList<Integer>();
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) {
}
}

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);
}

}``````

Comment hidden because of low score. Click to expand.
0

That's the solution I thought of too.. As an optimization for the nested loop i though one could reduce the complexity from O(n squared) to O(nlogn) by searching for the closest number in the list using divide and conquer. Instead of binary search I'd call it the binary find closest value ;)
For e.g.: If you're inside a loop and the current value is 7 and the second list is like this: 1 3 6 8 9. Then using a modified binary search you can find that 6 or 8 is the closest value and accordingly the smallest distance there is 1.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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++) {
}
}

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

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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])) {
words.put(w[i], l);
} else {
l = words.get(w[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"));
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

{{
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);
}
}

}}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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));
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;

}

}``````

Comment hidden because of low score. Click to expand.
0

This is what I had coded. Classic! Kudos to the simplicity!
My code, almost similar..

``````public static int findDistance(List<String> strings, String string1, String string2) {
if (null == strings || null == string1 || null == string2) {
return -1;
}
if (string1.equals(string2)) {
return 0;
}
int index1 = -1;
int index2 = -1;
int distance = Integer.MAX_VALUE;
for (int index = 0; index < strings.size(); index++) {
if (strings.get(index).equals(string1)) {
index1 = index;
if (index2 >= 0) {
// check if the distance can be reduced or not
if (distance > Math.abs(index - index2)) {
distance = Math.abs(index - index2);
}
}
} else if (strings.get(index).equals(string2)) {
index2 = index;
if (index1 >= 0) {
// check if the distance can be reduced or not
if (distance > Math.abs(index1 - index)) {
distance = Math.abs(index1 - index);
}
}
}
}
return distance;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
*
* 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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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)) {
} else if (strArr[j].equals(word2)) {
}
}

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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>();
}
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");
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.