Amazon Interview Question Quality Assurance Engineers
Country: United States
Interview Type: In-Person
//Test case 4: the brown quick frog quick the a b frog frog brown (brown frog )
Not working for Test4
public class MinWordDistance {
public int wordDist(String s, String word1, String word2) {
return Math.min(forwardWordDist(s, word1, word2), forwardWordDist(s, word2, word1));
}
private int forwardWordDist(String s, String word1, String word2) {
int lastPos = Integer.MIN_VALUE;
int bestDist = Integer.MAX_VALUE;
String[] words = s.split("\\s+");
for (int i = 0; i < words.length; i++) {
if (words[i].equals(word2) && lastPos > Integer.MIN_VALUE) {
bestDist = Math.min(bestDist, i - lastPos);
}
if (words[i].equals(word1)) {
lastPos = i;
}
}
if (bestDist == Integer.MAX_VALUE)
return -1;
return bestDist;
}
public static void main(String[] args) {
MinWordDistance mwd = new MinWordDistance();
System.out.println(mwd.wordDist("the brown qucik frog quick the", "the", "quick"));
System.out.println(mwd.wordDist("the quick the brown quick brown the frog", "the", "the"));
}
}
c++, implementation
int distanceTwoWordsInString(string str, string wordA, string wordB) {
vector<int> positionA;
vector<int> positionB;
string sub;
int i, start, wordIndex, indexA, indexB, distance;
i = 0;
start = 0;
wordIndex = 0;
while (i <= str.size()) {
if (i == str.size() || str[i] == ' ') {
sub = str.substr(start, i - start);
start = i + 1;
if (sub.compare(wordA) == 0) positionA.push_back(wordIndex);
if (sub.compare(wordB) == 0) positionB.push_back(wordIndex);
wordIndex++;
if (i == str.size()) break;
}
i++;
}
if (positionA.size() == 0 || positionB.size() == 0) return -1;
indexA = 0;
indexB = 0;
distance = wordIndex;
while (indexA < positionA.size() && indexB < positionB.size()) {
if (positionA[indexA] > positionB[indexB]) {
distance = min(distance, positionA[indexA] - positionB[indexB]);
indexB++;
} else if (positionA[indexA] < positionB[indexB]) {
distance = min(distance, positionB[indexB] - positionA[indexA]);
indexA++;
} else {
indexA++;
}
}
return distance;
}
Python
def dist(str,s1,s2):
val1, val2 = [], []
i = 0
for x in str.split():
if (s1 == x):
val1.append(i)
if (s2 == x):
val2.append(i)
i += 1
result = [abs(x-y) for x in val1 for y in val2]
if (s1 == s2):
result = [abs (x - y) for x in val1 for y in val1 if (x!=y)]
if result:
return min(result)
return 0
print(dist("the quick the brown quick brown the frog", "brown", "the"))
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <limits.h>
struct lnode {
int data;
struct lnode *next;
};
int words_min_dist(char *s, char *w1, char *w2);
int ldist(struct lnode *l1, struct lnode *l2);
struct lnode *get_word_positions(char *s, char *w);
struct lnode *createLNode(int data);
/*
Given a string and two words which are present in the string, find the minimum distance between the words
Eg: "the brown qucik frog quick the", "the" "quick" O/P -> 1
"the quick the brown quick brown the frog", "the" "the" O/P -> 2
*/
int main() {
printf("%d\n", words_min_dist("the quick brown fox jumped over the frog", "the", "frog"));
}
int words_min_dist(char *s, char *w1, char *w2) {
struct lnode *pos_w1 = get_word_positions(s, w1);
struct lnode *pos_w2 = get_word_positions(s, w2);
return ldist(pos_w1, pos_w2);
}
struct lnode *get_word_positions(char *s, char *w) {
struct lnode *l=NULL, *tmp;
char *p = w;
int pos = 1;
while(*s) {
while(*p && (*s==*p)) {
s++;
p++;
}
if(*p=='\0') {
if(isspace(*s) || *s=='\0') {
if(!l)
l = tmp = createLNode(pos);
else {
tmp->next = createLNode(pos);
tmp = tmp->next;
}
}
p = w;
}
if(isspace(*s))
pos++;
if(*s)
s++;
}
return l;
}
struct lnode *createLNode(int data) {
struct lnode *n = (struct lnode *) malloc(sizeof(struct lnode));
n->data = data;
n->next = NULL;
return n;
}
int ldist(struct lnode *l1, struct lnode *l2) {
struct lnode *lo, *hi, *tmp;
int min_dist = INT_MAX;
int curr_dist;
lo = l1;
hi = l2;
while(hi) {
while(lo && (lo->data < hi->data)) {
curr_dist = hi->data - lo->data;
if(curr_dist < min_dist)
min_dist = curr_dist;
lo = lo->next;
}
tmp = lo;
lo = hi;
hi = tmp;
}
return min_dist;
}
This is the algorithm that I would propose:
1. Split the sentence via space into an array. (You can optimize with using it as well, but this is easier to explain.)
2. Maintain three int variables - Pos1 & Pos2 and Min = Integer.MAX.
3. Update pos1 with the word position when you encounter input1.
4. Update pos2 when you encounter input2.
5. Update Min if Math.abs(pos2 - pos1) < Min.
6. If Min==1 at any time you break from loop, since the distance can't be less than 1 in any case.
7. Repeat the steps till the end for worst case. By the end you have Min distance in Min variable.
PS:- If the words are same, then just modify steps 3 & 4 to be executed for the input encounters alternatively. Since input1=input2 in this case.
Also for this case you could just use pos1 variable only to store the new encounters and update the Min variable if the difference from the previous pos1 is less than Min.
int minDistance(string s, string word1, string word2){
int slow = 0;
vector<string> words;
for(int i = 0; i < s.length(); i++){
if(s[i] == ' '){
words.push_back(s.substr(slow, i - slow));
slow = i + 1;
}
}
words.push_back(s.substr(slow, s.length() - slow));
int pos1 = -1, pos2 = - 1, min = 0;
for(int i = 0; i < words.size(); i++){
if(words[i] == word1){
pos1 = i;
if(pos2 != -1 && abs(pos1 - pos2) < min){
min = abs(pos1 - pos2);
}
}
if(words[i] == word2){
pos2 = i;
if(pos1 != -1 && abs(pos1 - pos2) < min){
min = abs(pos1 - pos2);
}
}
}
return min;
}
def distanceBetweenWords(text, wordA, wordB):
indexA = 0
indexB = 0
for i, word in enumerate(text.split(' ')):
if word == wordA:
indexA = i
elif word == wordB:
indexB = i
return abs(indexA - indexB)
// split to words, calculate positions of each word
// given two positions arrays (one per each word) find min |a[i] - b[j]|:
// - current min = a[0] - b[0]
// - iterate i [1 .. a.length-1] && j [1 .. b.length-1]
// - if (a[i] > b[j]) -> j++
// - else -> i++
// - decrease current min if needed
// - return current min indexes
public class MinimumDistance {
public int findMinimumDistance(String input, String firstWord, String secondWord) {
if (input == null || input.isEmpty()) {
return -1;
}
if (firstWord == null || firstWord.isEmpty()) {
return -1;
}
if (secondWord == null || secondWord.isEmpty()) {
return -1;
}
String[] words = input.split("\\s+");
Map<String, List<Integer>> dictionary = getPositions(words);
if (firstWord.equals(secondWord)) {
return findMinimumDistance(dictionary.get(firstWord));
} else {
return findMinimumDistance(dictionary.get(firstWord), dictionary.get(secondWord));
}
}
private Map<String, List<Integer>> getPositions(String[] words) {
Map<String, List<Integer>> dictionary = new HashMap<>();
for(int i = 0; i < words.length; i++) {
List<Integer> positions = dictionary.get(words[i]);
if (positions == null) {
positions = new ArrayList<>();
dictionary.put(words[i], positions);
}
positions.add(i);
}
return dictionary;
}
private int findMinimumDistance(List<Integer> firstPositions, List<Integer> secondPositions) {
if (firstPositions == null || firstPositions.isEmpty()) {
return -1;
}
if (secondPositions == null || secondPositions.isEmpty()) {
return -1;
}
int i = 0;
int j = 0;
int currentMin = Math.abs(firstPositions.get(i) - secondPositions.get(j));
while (currentMin != 0 && i < firstPositions.size() && j < secondPositions.size()) {
int firstNumber = firstPositions.get(i);
int secondNumber = secondPositions.get(j);
if (firstNumber > secondNumber) {
j++;
} else {
i++;
}
if (i < firstPositions.size() && j < secondPositions.size()) {
firstNumber = firstPositions.get(i);
secondNumber = secondPositions.get(j);
int min = Math.abs(firstNumber - secondNumber);
if (min < currentMin) {
currentMin = min;
}
}
}
return currentMin;
}
private int findMinimumDistance(List<Integer> positions) {
if (positions.size() >= 2) {
int i = 0;
int j = 1;
int currentMin = Math.abs(positions.get(i) - positions.get(j));
i++;
j++;
while (j < positions.size()) {
int min = Math.abs(positions.get(i) - positions.get(j));
if (min < currentMin) {
currentMin = min;
}
i++;
j++;
}
return currentMin - 1;
}
return 0;
}
}
int MinDist(string sentence)
{
i = 0;
dist = Int.Infinity;
int last1 = -1, last2 = -1;
foreach(string w in sentence.Split(' '))
{
if(w == w1)
last1 = i;
else if(w == w2)
last2 = i;
i++;
if(last1 != -1 && last2 != -1)
dist = Math.Abs(last1 - last2)
}
return dist;
}
{{def distance(string,w1,w2):
mindist = 1000 #sysmax
latest_w1_index,latest_w2_index = -10000,10000
issame = w1==w2
isFirst,isSecond = True,True
for idx,w in enumerate(string.split()):
if w== w1 and isFirst:
if not issame:
latest_w1_index = idx
elif isFirst:
latest_w1_index = idx
isFirst = False
isSecond = True
elif w==w2 and isSecond :
if not issame:
latest_w2_index = idx
elif not isFirst:
latest_w2_index = idx
isFirst = True
isSecond = False
if abs(latest_w1_index-latest_w2_index) < mindist:
mindist = abs(latest_w1_index-latest_w2_index)
return mindist}}
public class MinWordDistance {
public int wordDist(String s, String word1, String word2) {
return Math.min(forwardWordDist(s, word1, word2), forwardWordDist(s, word2, word1));
}
private int forwardWordDist(String s, String word1, String word2) {
int lastPos = Integer.MIN_VALUE;
int bestDist = Integer.MAX_VALUE;
String[] words = s.split("\\s+");
for (int i = 0; i < words.length; i++) {
if (words[i].equals(word2) && lastPos > Integer.MIN_VALUE) {
bestDist = Math.min(bestDist, i - lastPos);
}
if (words[i].equals(word1)) {
lastPos = i;
}
}
if (bestDist == Integer.MAX_VALUE)
return -1;
return bestDist;
}
public static void main(String[] args) {
MinWordDistance mwd = new MinWordDistance();
System.out.println(mwd.wordDist("the brown qucik frog quick the", "the", "quick"));
System.out.println(mwd.wordDist("the quick the brown quick brown the frog", "the", "the"));
}
}
package com.shubham.shortestdistance;
public class ShortestDistance {
public static void shortestDistanceBetweenTwoWordsInString(String line, String word1, String word2){
int distance = -1;
String[] wordArray = line.split(" ");
for(int i = 0; i < wordArray.length; i++){
if(wordArray[i].equals(word1)){
for(int j = i; j < wordArray.length; j++){
if(wordArray[j].equals(word2)){
if(distance == -1 || distance>(j-i)){
distance = j-i;
}
break;
}
}
}
else if(wordArray[i].equals(word2)){
for(int j = i; j < wordArray.length; j++){
if(wordArray[j].equals(word1)){
if(distance == -1 || distance>(j-i)){
distance = j-i;
}
break;
}
}
}
else{
continue;
}
}
if(distance == -1){
System.out.println("Word not found!!");
}
else{
System.out.println("Shortest distance: "+distance);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
String line = "the brown quick frog quick the a b frog frog brown";
String word1 = "brown";
String word2 = "frog";
ShortestDistance.shortestDistanceBetweenTwoWordsInString(line, word1, word2);
}
}
package com.shubham.shortestdistance;
public class ShortestDistance {
public static void shortestDistanceBetweenTwoWordsInString(String line, String word1, String word2){
int distance = -1;
String[] wordArray = line.split(" ");
for(int i = 0; i < wordArray.length; i++){
if(wordArray[i].equals(word1)){
for(int j = i; j < wordArray.length; j++){
if(wordArray[j].equals(word2)){
if(distance == -1 || distance>(j-i)){
distance = j-i;
}
break;
}
}
}
else if(wordArray[i].equals(word2)){
for(int j = i; j < wordArray.length; j++){
if(wordArray[j].equals(word1)){
if(distance == -1 || distance>(j-i)){
distance = j-i;
}
break;
}
}
}
else{
continue;
}
}
if(distance == -1){
System.out.println("Word not found!!");
}
else{
System.out.println("Shortest distance: "+distance);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
String line = "the brown quick frog quick the a b frog frog brown";
String word1 = "brown";
String word2 = "frog";
ShortestDistance.shortestDistanceBetweenTwoWordsInString(line, word1, word2);
}
}
package com.shubham.shortestdistance;
public class ShortestDistance {
public static void shortestDistanceBetweenTwoWordsInString(String line, String word1, String word2){
int distance = -1;
String[] wordArray = line.split(" ");
for(int i = 0; i < wordArray.length; i++){
if(wordArray[i].equals(word1)){
for(int j = i; j < wordArray.length; j++){
if(wordArray[j].equals(word2)){
if(distance == -1 || distance>(j-i)){
distance = j-i;
}
break;
}
}
}
else if(wordArray[i].equals(word2)){
for(int j = i; j < wordArray.length; j++){
if(wordArray[j].equals(word1)){
if(distance == -1 || distance>(j-i)){
distance = j-i;
}
break;
}
}
}
else{
continue;
}
}
if(distance == -1){
System.out.println("Word not found!!");
}
else{
System.out.println("Shortest distance: "+distance);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
String line = "the brown quick frog quick the a b frog frog brown";
String word1 = "brown";
String word2 = "frog";
ShortestDistance.shortestDistanceBetweenTwoWordsInString(line, word1, word2);
}
}
public static void shortestUsingPosition(String givenString, String firstWord, String secondWord ){
String[] words = givenString.split("\\s+");
int min=0;
int firstPos=-1;
int secondPos=-1;
for(int i=0;i<words.length;i++){
if(words[i].equals(firstWord) && firstPos==-1)
firstPos=i;
else if(words[i].equals(secondWord) && secondPos==-1)
secondPos=i;
if(firstPos!=-1 && secondPos!= -1){
int diff =Math.abs(secondPos-firstPos);
if(min==0){
min=diff;
}
else{
min= Math.min(diff, min);
}
firstPos=-1;
secondPos=-1;
}
}
System.out.println("Minimum Distance: "+min);
}
def distanceBetweenWords(text, wordA, wordB):
indexA = []
indexB = []
for i, word in enumerate(text.split(' ')):
if word == wordA:
indexA.append(i)
elif word == wordB:
indexB.append(i)
min=abs(indexA[0]-indexB[0])
for j in range(0,len(indexA)):
for k in range(0,len(indexB)):
temp=abs(indexA[j]-indexB[k])
if temp<min:
print 'updating min %d' %min
min=temp
return min
print distanceBetweenWords('the brown quick the frog brown quick the','the','quick')
public static void main(String[] args) {
String str = "the world is the here the huge here hi the";
String w1 = "the", w2 = "the";
String[] arrSplit = str.split(" ");
int dist = 0;
ArrayList<Integer> al = new ArrayList<>();
boolean distFound = false;
for(int i=0; i<arrSplit.length; i++) {
if(arrSplit[i].equals(w1)) {
for(int j=i+1; j<arrSplit.length; j++) {
if(arrSplit[j].equals(w2)) {
distFound = true;
break;
} else {
dist++;
}
}
if(distFound) {
al.add(dist);
distFound = false;
dist = 0;
}
}
}
if(al.isEmpty()) {
System.out.println("Either one of given words is not found!");
} else {
Collections.sort(al);
System.out.println(al.get(0));
}
}
- Keshav November 14, 2015import java.util.*; public class WordDistance { public static void main(String[] args) { Scanner in=new Scanner(System.in); String s=in.nextLine(); String s1=in.nextLine(); String s2=in.nextLine(); int index1=-1; int index2=-1; boolean flag1=false; boolean flag2=false; int distance=Integer.MAX_VALUE; int answer=Integer.MAX_VALUE; String[] sarray=s.split(" "); for(int i=0;i<sarray.length;i++) { if(!s1.equals(s2)) { flag1=false; flag2=false; } if(s1.equals(sarray[i]) && flag1==false) { index1=i; flag1=true; } else if(s2.equals(sarray[i]) && flag2==false) { index2=i; flag2=true; } if(index1!=-1 && index2!=-1) { distance=Math.abs(index1-index2); flag1=false; flag2=false; } if(distance<answer) { answer=distance; } } if(answer==Integer.MAX_VALUE) { System.out.print("Words not found"); } else { System.out.print(answer); } } } //Test Case 1: the quick the brown quick brown the frog (frog brown) //Test Case 2: the quick the brown quick brown the frog (brown brown) //Test Case 3: the brown qucik frog quick the (the quick)