Amazon Interview Question
SDE-3sCountry: United States
Interview Type: Phone Interview
We note that the distance between the three words will always be equal to twice the distance between the two extreme words.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Ed2
{
public class Ed2
{
public static int MinDistance(IList<string> text, string word1, string word2, string word3)
{
int result = 0;
int position1 = -1;
int position2 = -1;
int position3 = -1;
for (int position = 0; position < text.Count(); position++)
{
if (text[position] == word1)
position1 = position;
else if (text[position] == word2)
position2 = position;
else if (text[position] == word3)
position3 = position;
if (position1 != -1 && position2 != -1 && position3 != -1)
{
int distance = (Max(position1, position2, position3) - Min(position1, position2, position3)) * 2;
if (result == 0 || distance < result)
result = distance;
}
}
return result;
}
static int Min(int a, int b, int c)
{
return Math.Min(a, Math.Min(b, c));
}
static int Max(int a, int b, int c)
{
return Math.Max(a, Math.Max(b, c));
}
}
}
using System;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using Ed2;
namespace Ed2UnitTest
{
[TestClass]
public class UnitTest
{
[TestMethod]
public void TestMethod1()
{
Assert.AreEqual(Ed2.Ed2.MinDistance(new string[] { "2", "1", "0", "2", "0", "3", "0" }, "1", "2", "3"), 8);
}
[TestMethod]
public void TestMethod2()
{
Assert.AreEqual(Ed2.Ed2.MinDistance(new string[] { "2", "1", "0", "2", "0", "3", "1" }, "1", "2", "3"), 6);
}
}
}
public int minDistance(String[] wrds, String[] arr)
{
if(wrds.length!=3 || arr==null||arr.length<3)
{
return -1;
}
int idxOne=-1;
int idxTwo=-1;
int idxThree=-1
HashMap<String,Boolean> w=new HashMap<String,Boolean>();
for(int i=0;i<wrds.length;i++)
{
w.put(wrds[i],i);
}
int min=-1;
for(int i=0;i<wrds.length;i++)
{
if(w.containsKey(wrds[i]))
{
int x=w.get(wrds[i]);
if(x==0)
{
idxOne=i;
}else if (x==1)
{
idxTwo=i;
}else{
idxThree=i;
}
}
if(idxOne!=-1 && idxTwo!=-1 && idxThree!=-1)
{
int diff=Math.max(idxOne,Math.max(idxTwo,IdxThree))-Math.min(idxOne,IdxTwo,IdxThree)
min=min==-1?diff:Math.min(min,diff);
}
}
return min;
}
- (int)minimumIndexDistance:(NSArray<NSString*> *)words
search:(NSArray<NSString*> *)searchWords {
int minIndexDistance = INT_MAX;
int index0 = -1, index1 = -1, index2 = -1;
NSSet *selectedWordsSet = [NSSet setWithArray:searchWords];
NSMutableDictionary<NSString*,NSNumber*> *selectionBucket = [NSMutableDictionary new];
for (int i = 0; i < words.count; i++) {
NSString *currentWord = words[i];
// check if count of stored digits is 3, then lets compute the differences of the indices
if (selectionBucket.count == 3) {
index0 = selectionBucket[searchWords[0]].intValue;
index1 = selectionBucket[searchWords[1]].intValue;
index2 = selectionBucket[searchWords[2]].intValue;
int potentialMinIndex = abs(index0-index1) + abs(index0-index2) + abs(index1-index2);
minIndexDistance = MIN(potentialMinIndex, minIndexDistance);
}
if ([selectedWordsSet containsObject:currentWord]) {
selectionBucket[currentWord] = [NSNumber numberWithInt:i];
}
}
return minIndexDistance;
}
So it's only 3 words that you need to look for? I was looking for a more generalized solution at first and thought it was pretty tricky. Here's how I would do it:
- JoseCuervo April 01, 2016