Amazon Interview Question
Country: United States
Interview Type: In-Person
#include <iostream>
#include <climits>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <map>
using namespace std;
void calcMinDist(vector<pair<int, int> > &arr,vector<pair<int, int> > &dep, int maxDist)
{
int flag = 0;
multimap<int, int> mp;
map< int, pair<int,int> > nmp;
multimap<int, int> :: iterator it;
for(int i = 0; i < dep.size(); i++)
mp.insert(pair<int,int>(dep[i].second,dep[i].first));
//for(it = mp.begin(); it != mp.end(); ++it)
// std::cout << it->first << " " << it->second << "\n\n";
while(maxDist > 0)
{
flag = 0;
for(int i = 0; i < arr.size(); i++)
{
//if()
it = mp.find(maxDist - arr[i].second);
//cout<<(maxDist - arr[i].second)<<endl;
if(it != mp.end())
{
cout<<arr[i].first <<" "<<it->second<<endl;
flag = 1;
}
}
if(flag == 1)
break;
else
maxDist--;
}
}
int main()
{
vector<pair<int, int> > arr;
vector<pair<int, int> > dep;
arr.push_back(make_pair(1,2));
arr.push_back(make_pair(2,4));
arr.push_back(make_pair(3,6));
//arr.push_back(make_pair(4,10));
//dep.push_back(make_pair(1,2));
//dep.push_back(make_pair(2,3));
//dep.push_back(make_pair(5,5));
//dep.push_back(make_pair(3,4));
dep.push_back(make_pair(1,2));
calcMinDist(arr,dep,7);
/*for(int i = 0; i < arr.size(); i++)
std::cout<<arr[i].first<<" "<<arr[i].second<<std::endl;
for(int i = 0; i < dep.size(); i++)
std::cout<<dep[i].first<<" "<<dep[i].second<<std::endl;*/
}
Collapse
Concur, I can't make sense out of question or the answer.
Is the following close the what was intended:
"Given two lists, find a pair of numbers that equals the given target."
In example 1, Assuming pairs are added, none of them equals 7.
list1 1+2=3, 2+4=6, 3+6=9
list2 1+2=3
So where do the 4, 6, 8 come from?
And [2,1] as a pair is not in either list.
Lastly what is the reason for 2 lists?
def Aircraft(forward, ret, maxValue):
n = len(forward)
m = len(ret)
i = 0; j = m-1; ans = []
temp = -1
while i < n and j >= 0:
print (i , j)
sumVal = forward[i][1] + ret[j][1]
if temp < sumVal and sumVal <= maxValue:
ans = []
temp = sumVal
ans.append([i+1, j+1])
i += 1
elif temp == sumVal and sumVal <= maxValue:
ans.append([i+1, j+1])
i += 1
elif sumVal > maxValue:
j -= 1
return ans
This question is so unclear. is the input two list of pairs ? How to match target , by adding two pairs ( total 4 values ) ?
- Anonymous January 07, 2019