Linkedin Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
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?
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;
}
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 -1; // indicate one of the word was not found.
return minDistance;
}
}
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.
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.
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)
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;
}
}
}
if(state==0) throw new IllegalArgumentException("Not found");
return distance;
}
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);
}
}
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.
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;
}
}
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;
}
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;
}
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);
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.
- The Internet August 13, 2014Fortunately, 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 ...