Amazon Interview Question
SDE1sCountry: United States
Interview Type: Phone Interview
private static int[] getMinimum(List<String> target, List<String> available) {
//Add to the map
Map<String, List<Integer>> listMap = new HashMap<>();
int counter = 0;
for(String availableItem : available) {
if(listMap.containsKey(availableItem))
listMap.get(availableItem).add(counter);
else {
List<Integer> temp = new ArrayList<>();
temp.add(counter);
listMap.put(availableItem, temp);
}
counter++;
}
List<Integer> resultList = new ArrayList<>();
int k=0;
//add all element list to resultList
for(String targetItem : target) {
if(listMap.get(targetItem) == null)
break;
else {
int count = 0;
int listLength = resultList.size();
List<Integer> l =listMap.get(targetItem);
while(count < l.size()) {
//if you see an element getting inserted which is less that the
//last element remove one element from the front
if(listLength > 0 && l.get(count) < resultList.get(listLength-1))
resultList.remove(k++);
//add otherwise
resultList.add(l.get(count));
count++;
}
}
}
int left = resultList.get(0);
int right = resultList.get(resultList.size()-1);
return new int[] {left, right};
}
vector<int> getMinimum(vector<String> target, vector<String> available) {
unordered_map<string, int> target_map;
for (int i = 0; i < target.size(); ++i) {
++target_map[target[i]];
}
int min_idx = 0;
int min_len = INT_MAX;
int total = 0;
int i = 0;
int count = target.size();
while ( i < available.size()) {
string str = available[i];
if (target_map.find(str) == target_map.end()) {
++i;
continue;
}
--target_map[str];
if (target_map[str] >= 0) {
++total;
}
if (count == total) {
int j = min_idx;
while (count == total && j < i) {
while (j < i) {
if (j - i + 1 < min_len) {
min_idx = j;
min_len = i - j + 1;
}
string str1 = available[j];
if (target_map.find(str1) == target_map.end()) {
++j;
} else {
++j;
++target_map[str1];
if (target_map[str1] > 0) {
--total;
break;
}
}
}
}
min_idx = j;
}
++i;
}
vector<int> result;
if (min_len < INT_MAX) {
result.push_back(min_idx);
result.push_back(min_idx + min_len - 1);
}
return result;
int main() {
string pt[2]={"cat","dog"};
string s[6]={"south","test","dog","get","spain","cat"};
unordered_map<string,int> mp;
int ct=0,b=0,si=0,e=0,mx=INT_MAX;
for(int i=0;i<2;i++){
mp[pt[i]]++;
ct++;
}
while(e<6){
if(mp[s[e]]--> 0)
ct--;
while(ct == 0){
if(mx>e-b){
si=b;
mx = e-b;
}
if(mp[s[b++]]++ == 0)
ct++;
}
}
cout<<si<<mx;
return 1;
}
int findInInput(string target, vector<string> input, int offset) {
for (int i = offset; i < input.size(); i++) {
if (input[i] == target)
return i;
}
return -1;
}
pair<int,int> findTarget(vector<string> target, vector<string> input, int offset) {
pair<int,int> result;
int beginIndex = -1, endIndex = -1;
for (auto t : target) {
int index = findInInput(t, input, offset);
if (index == -1)
break;
(beginIndex == -1) ? beginIndex = index : endIndex = index;
}
result = make_pair(beginIndex, endIndex);
return result;
}
void getMinClosure() {
vector<string> target = { "eat", "in", "south"};
vector<string> input = {"eat", "to", "eat", "in", "eat", "go", "bye", "south"};
int minDist = INT_MAX;
for (int i = 0; i < input.size(); i++) {
pair<int, int> range = findTarget(target, input, i);
if (range.first != -1 && range.second != -1)
minDist = min(minDist, range.second - range.first);
}
}
private static int[] getMinimum(List<String> target, List<String> available) {
- Vinod February 01, 2018//Add to the map
Map<String, List<Integer>> listMap = new HashMap<>();
int counter = 0;
for(String availableItem : available) {
if(listMap.containsKey(availableItem))
listMap.get(availableItem).add(counter);
else {
List<Integer> temp = new ArrayList<>();
temp.add(counter);
listMap.put(availableItem, temp);
}
counter++;
}
List<Integer> resultList = new ArrayList<>();
int k=0;
//add all element list to resultList
for(String targetItem : target) {
if(listMap.get(targetItem) == null)
break;
else {
int count = 0;
int listLength = resultList.size();
List<Integer> l =listMap.get(targetItem);
while(count < l.size()) {
//if you see an element getting inserted which is less that the
//last element remove one element from the front
if(listLength > 0 && l.get(count) < resultList.get(listLength-1))
resultList.remove(k++);
//add otherwise
resultList.add(l.get(count));
count++;
}
}
}
int left = resultList.get(0);
int right = resultList.get(resultList.size()-1);
return new int[] {left, right};
}