Amazon Interview Question
SDE-2sCountry: United States
Interview Type: In-Person
What if there is more than a pair for the same optimal value? Also, what if we have same values with different Id's? Should the solution cover all those different value pairs with same distance but different Id's?
package com.sample.test;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;
public class OptimalFlightDistant {
public static void main(String[] args) {
// sample input
System.out.println(getIdPairsForOptimal(
Arrays.asList(Arrays.asList(1, 3000), Arrays.asList(2, 5000), Arrays.asList(3, 7000),
Arrays.asList(4, 10000)),
Arrays.asList(Arrays.asList(1, 2000), Arrays.asList(2, 9000), Arrays.asList(3, 5000)), 10000));
}
public static List<List<Integer>> getIdPairsForOptimal(List<List<Integer>> forwardList,
List<List<Integer>> backwardList, int maxDistance) {
List<List<Integer>> result = new LinkedList<List<Integer>>();
forwardList = forwardList.stream().sorted((x1, x2) -> Integer.compare(x2.get(1), x1.get(1)))
.collect(Collectors.toList());
backwardList = backwardList.stream().sorted((x1, x2) -> Integer.compare(x1.get(1), x2.get(1)))
.collect(Collectors.toList());
int maxDist = maxDistance;
while (true) {
for (List<Integer> l : forwardList) {
for (List<Integer> b : backwardList) {
int forward = l.get(1);
int backward = b.get(1);
int tot = (forward + backward);
if (tot > maxDist) {
break;
}
if (tot == maxDist) {
// print the pair of Id and optimum distance
result.add(Arrays.asList(l.get(0), b.get(0), maxDist));
break;
}
}
}
if (result.size() > 0) {
break;
}
maxDist--;
}
return result;
}
}
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;
public class OptimalFlightDistant {
public static void main(String[] args) {
// sample input
System.out.println(getIdPairsForOptimal(
Arrays.asList(Arrays.asList(1, 3000), Arrays.asList(2, 5000), Arrays.asList(3, 7000),
Arrays.asList(4, 10000)),
Arrays.asList(Arrays.asList(1, 2000), Arrays.asList(2, 9000), Arrays.asList(3, 5000)), 10000));
}
public static List<List<Integer>> getIdPairsForOptimal(List<List<Integer>> forwardList,
List<List<Integer>> backwardList, int maxDistance) {
List<List<Integer>> result = new LinkedList<List<Integer>>();
forwardList = forwardList.stream().sorted((x1, x2) -> Integer.compare(x2.get(1), x1.get(1)))
.collect(Collectors.toList());
backwardList = backwardList.stream().sorted((x1, x2) -> Integer.compare(x1.get(1), x2.get(1)))
.collect(Collectors.toList());
int maxDist = maxDistance;
while (true) {
for (List<Integer> l : forwardList) {
for (List<Integer> b : backwardList) {
int forward = l.get(1);
int backward = b.get(1);
int tot = (forward + backward);
if (tot > maxDist) {
break;
}
if (tot == maxDist) {
// print the pair of Id and optimum distance
result.add(Arrays.asList(l.get(0), b.get(0), maxDist));
break;
}
}
}
if (result.size() > 0) {
break;
}
maxDist--;
}
return result;
}
}
package com.sample.test;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;
public class OptimalFlightDistant {
public static void main(String[] args) {
// sample input
System.out.println(getIdPairsForOptimal(
Arrays.asList(Arrays.asList(1, 3000), Arrays.asList(2, 5000), Arrays.asList(3, 7000),
Arrays.asList(4, 10000)),
Arrays.asList(Arrays.asList(1, 2000), Arrays.asList(2, 9000), Arrays.asList(3, 5000)), 10000));
}
public static List<List<Integer>> getIdPairsForOptimal(List<List<Integer>> forwardList,
List<List<Integer>> backwardList, int maxDistance) {
List<List<Integer>> result = new LinkedList<List<Integer>>();
forwardList = forwardList.stream().sorted((x1, x2) -> Integer.compare(x2.get(1), x1.get(1)))
.collect(Collectors.toList());
backwardList = backwardList.stream().sorted((x1, x2) -> Integer.compare(x1.get(1), x2.get(1)))
.collect(Collectors.toList());
int maxDist = maxDistance;
while (true) {
for (List<Integer> l : forwardList) {
for (List<Integer> b : backwardList) {
int forward = l.get(1);
int backward = b.get(1);
int tot = (forward + backward);
if (tot > maxDist) {
break;
}
if (tot == maxDist) {
// print the pair of Id and optimum distance
result.add(Arrays.asList(l.get(0), b.get(0), maxDist));
break;
}
}
}
if (result.size() > 0) {
break;
}
maxDist--;
}
return result;
}
}
import java.util.*;
public class OptimalFlightDistant {
public static void main(String[] args) {
// sample input
System.out.println(getIdPairsForOptimal(
Arrays.asList(Arrays.asList(1, 3000), Arrays.asList(2, 5000), Arrays.asList(3, 7000),
Arrays.asList(4, 10000)),
Arrays.asList(Arrays.asList(1, 3000), Arrays.asList(2, 9000), Arrays.asList(3, 5000)), 10000));
}
public static List<List<Integer>> getIdPairsForOptimal(List<List<Integer>> forwardList,
List<List<Integer>> backwardList, int maxDistance) {
List<List<Integer>> result = new LinkedList<>();
List<List<Integer>> temp = new ArrayList<>();
int max = Integer.MIN_VALUE;
for (int i = 0; i < forwardList.size(); i++) {
for (int j = 0; j < backwardList.size(); j++) {
int cmax = forwardList.get(i).get(1) + backwardList.get(j).get(1);
if (cmax <= maxDistance) {
if (cmax > max) {
max = cmax;
result = new ArrayList<>();
result.add(Arrays.asList(forwardList.get(i).get(0), backwardList.get(j).get(0)));
} else if (cmax == max) {
result.add(Arrays.asList(forwardList.get(i).get(0), backwardList.get(j).get(0)));
}
}
}
}
return result;
}
}
This can be done using maximum contiguous sum subarray.
1. First add forward and backward for each location. like 1 forward + 2 backward for 1st index i.e. ith forward + (i+1)th backward for ith index cost.
2. Now apply maximum contiguous sum subarray to get the subarray <i,j>. Answer would be <i, j+1>.
Time Complexity: O(n) + O(n).
Space Complexity: O(n). (for storing the result. we can make it O(1), if we reuse the any of the forward and backward input array).
What about the case when all pairs are valid?
forward-> [1,1000],[2,1000],[3,1000]
backward->[1,1000],[2,1000],[3,1000]
Reqd = 2000
Here all a pairs are possible - so how can you give in O(n)?
Two pointer approach:
public List<List<Integer>> findOptimalMemory(final int capacity, final List<List<Integer>> foreground,
final List<List<Integer>> background)
{
int i = 0;
int j = background.size() - 1;
final List<List<Integer>> result = new ArrayList<>();
final List<List<Integer>>[] store = new ArrayList[capacity + 1];
Collections.sort(foreground, new Comparator<List<Integer>>()
{
@Override
public int compare(final List<Integer> f, final List<Integer> s)
{
return Integer.compare(f.get(1), s.get(1));
}
});
Collections.sort(background, new Comparator<List<Integer>>()
{
@Override
public int compare(final List<Integer> f, final List<Integer> s)
{
return Integer.compare(f.get(1), s.get(1));
}
});
while (i < foreground.size() && j > -1)
{
final int current = foreground.get(i).get(1) + background.get(j).get(1);
if (current <= capacity)
{
if (store[current] == null)
store[current] = new ArrayList<>();
store[current].add(Arrays.asList(new Integer[] { foreground.get(i).get(0), background.get(j).get(0) }));
}
if (current <= capacity)
{
++i;
}
else if (current > capacity)
{
--j;
}
}
while (i < foreground.size())
{
final int current = foreground.get(i).get(1) + background.get(0).get(1);
if (current < capacity)
{
if (store[current] == null)
store[current] = new ArrayList<>();
store[current].add(Arrays.asList(new Integer[] { foreground.get(i).get(0), background.get(0).get(0) }));
}
++i;
}
while (j > -1)
{
final int current = foreground.get(foreground.size() - 1).get(1) + background.get(j).get(1);
if (current < capacity)
{
if (store[current] == null)
store[current] = new ArrayList<>();
store[current]
.add(Arrays.asList(new Integer[] { foreground.get(foreground.size() - 1).get(0), background.get(j).get(0) }));
}
--j;
}
for (int k = capacity; k > -1; --k)
{
if (store[k] != null)
{
result.addAll(store[k]);
break;
}
}
return result;
}
I think your solution returns all the pairs for which sum <= capacity but the question asks to find all the pairs for which sum <= capacity AND this there is no other pairs with their sum > this sum and <= capacity. Correct me if I am wrong.
This question ask me too..
Here the approach which i come to.
1 Sort the both list Backward and forward.
2. Implement sliding window technique
- take one variable for maxValue
- take two pointer one for assign first value Forward list let take it LEFT
- second assign to the last element of backward list let take it RIGHT
3 Start the loop with condition LEFT < forward.lenght And RIGHT >= 0
- sumValue = sum of LEFT index Value and Right Index value
if(maxTarget >= sum){
- if maxValue greater than clear the list and insert sum value to list result increment the left index by 1
- if maxValue == sum
add point id in list result;
else
left ++;
}else{
right--;
}
4 return the result list
Time Complexity: O((n log n) + (m log m) + (m+n))
Space complexity max(m,n)
n is the length of forward route
m is the length of backward route
Time Complexity O((n log n) + (m log m) + m + n)
Space Complexity o(Max(n,m))
n is the length of Forward routes
m is the length of backward routes
With what value to compare for condition “if maxValue greater than clear the list ”
And why clear the list and add sum instead of point ids?
def closestXDestionation(forward, backward, maximum):
combined = [[i, j] for i in forward for j in backward]
lessThanMax = []
for i in range(len(combined)):
if combined[i][0][1] + combined[i][1][1] <= maximum:
lessThanMax.append([combined[i][0],combined[i][1]])
largest = max(lessThanMax, key=lambda x:x[0][1] + x[1][1])
route = [path[0] for path in largest]
print(route)
F = [[1,1000],[2,2000],[3,3000],[4,4000], [5,5000],[6,6000],[7,7000], [8, 8000]]
B = [[1,2000],[2,3000],[3,3000],[4,4000], [5,5000],[6,6000]]
m = 11000
closestXDestionation(F, B, m)
def closestXDestionation(forward, backward, maximum):
combined = [[i, j] for i in forward for j in backward]
lessThanMax = []
for i in range(len(combined)):
if combined[i][0][1] + combined[i][1][1] <= maximum:
lessThanMax.append([combined[i][0],combined[i][1]])
largest = max(lessThanMax, key=lambda x:x[0][1] + x[1][1])
route = [path[0] for path in largest]
print(route)
F = [[1,1000],[2,2000],[3,3000],[4,4000], [5,5000],[6,6000],[7,7000], [8, 8000]]
B = [[1,2000],[2,3000],[3,3000],[4,4000], [5,5000],[6,6000]]
m = 11000
closestXDestionation(F, B, m)
def closestXDestionation(forward, backward, maximum):
combined = [[i, j] for i in forward for j in backward]
lessThanMax = []
for i in range(len(combined)):
if combined[i][0][1] + combined[i][1][1] <= maximum:
lessThanMax.append([combined[i][0],combined[i][1]])
largest = max(lessThanMax, key=lambda x:x[0][1] + x[1][1])
route = [path[0] for path in largest]
print(route)
F = [[1,1000],[2,2000],[3,3000],[4,4000], [5,5000],[6,6000],[7,7000], [8, 8000]]
B = [[1,2000],[2,3000],[3,3000],[4,4000], [5,5000],[6,6000]]
m = 11000
closestXDestionation(F, B, m)
Used a sliding window model and solved it in JS .
space complexity : O(M +N )
Time complexity : O( M + N ) + mLogM + nLogN
N = Number of fwd options
M = Number of backward options
Algorithm :
-----------------
- use a two pointer approach , one starting from 0 index of fwd list and another from last index of bwdlist.
-Keep track of best sum achieved so far, compare and increment pointers accordingly.
- store results when you find a better best / max .
---
Note : this works for multiple combinations , but would not work if either the fwd or the backward path distances are duplicated.
function findRoute(fwdList,bwdList,max) {
let fList = fwdList.sort((a,b) => a[1] > b[1]);
let bList = bwdList.sort((a,b) => a[1] > b[1]);
let fHash = new Map();;
let bHash = new Map();
for(let tuple of fList){
fHash.has(tuple[1]) || fHash.set(tuple[1],tuple[0]);
}
for(let tuple of bList ){
bHash.has(tuple[1]) || bHash.set(tuple[1],tuple[0]);
}
fList = fList.map(tuple => tuple[1]);
bList = bList.map(tuple => tuple[1]);
console.log(fList);
let result = [];
let left = 0;
let right = bList.length-1;
let best = 0;
while (left<fList.length && right>=0){
let sum = fList[left] + bList[right];
console.log(`left is ${left} , right is ${right}`);
console.log(`sum is ${sum}, max is ${max}`);
if(sum<=max){
if(sum>best) {
result = [];
result.push([fHash.get(fList[left]),bHash.get(bList[right])]);
best = sum;
}
else if(sum === best){
result.push([fHash.get(fList[left]),bHash.get(bList[right])]);
}
left++;
}
else if(sum>max){
right--;
}
}
return result.length === 0 ? [] :result.length>1? result : result[0];
}
let f = [[1,3000],[2,5000],[3,4000],[4,10000],[5,9000],[6,7000]];
let b = [[1,2000],[2,3000],[3,4000],[4,1000]];
console.log(findRoute(f,b,11000));
// java code
import java.util.*;
public class OptimalRoute
{
public static void main(String[] args)
{
List<List<Integer>> forwardList = new LinkedList<List<Integer>>();
forwardList.add(new ArrayList<Integer>(Arrays.asList(1, 2000)));
forwardList.add(new ArrayList<Integer>(Arrays.asList(2, 4000)));
forwardList.add(new ArrayList<Integer>(Arrays.asList(3, 6000)));
List<List<Integer>> returnList = new LinkedList<List<Integer>>();
returnList.add(new ArrayList<Integer>(Arrays.asList(1, 2000)));
System.out.println(calculateOptimalRoute(7000, forwardList, returnList));
}
public static List<List<Integer>> calculateOptimalRoute(final int capacity, final List<List<Integer>> forwardList, final List<List<Integer>> returnList)
{
System.out.println(forwardList);
System.out.println(returnList);
// sort forward list
Collections.sort(forwardList, new Comparator<List<Integer>>() {
@Override
public int compare(List<Integer> o1, List<Integer> o2) {
return o1.get(1) - o2.get(1);
}
});
// sort return list
Collections.sort(returnList, new Comparator<List<Integer>>() {
public int compare(List<Integer> o1, List<Integer> o2) {
return o1.get(1) - o2.get(1);
}
});
int max = 0;
int i = 0;
int j = returnList.size() - 1;
List<List<Integer>> result = null;
while(i < forwardList.size() && j >= 0) {
if (forwardList.get(i).get(1) + returnList.get(j).get(1) > max &&
forwardList.get(i).get(1) + returnList.get(j).get(1) <= capacity) {
max = forwardList.get(i).get(1) + returnList.get(j).get(1);
result = new LinkedList<List<Integer>>();
result.add(new ArrayList<Integer>(Arrays.asList(forwardList.get(i).get(0), returnList.get(j).get(0))));
i++;
} else if(forwardList.get(i).get(1) + returnList.get(j).get(1) == max) {
// no need to reset result list
result.add(new ArrayList<Integer>(Arrays.asList(forwardList.get(i).get(0), returnList.get(j).get(0))));
i++;
} else {
j--;
}
}
return result;
}
}
package com.sample.test;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;
public class OptimalFlightDistant {
public static void main(String[] args) {
// sample input
System.out.println(getIdPairsForOptimal(
Arrays.asList(Arrays.asList(1, 3000), Arrays.asList(2, 5000), Arrays.asList(3, 7000),
Arrays.asList(4, 10000)),
Arrays.asList(Arrays.asList(1, 2000), Arrays.asList(2, 9000), Arrays.asList(3, 5000)), 10000));
}
public static List<List<Integer>> getIdPairsForOptimal(List<List<Integer>> forwardList,
List<List<Integer>> backwardList, int maxDistance) {
List<List<Integer>> result = new LinkedList<List<Integer>>();
forwardList = forwardList.stream().sorted((x1, x2) -> Integer.compare(x2.get(1), x1.get(1)))
.collect(Collectors.toList());
backwardList = backwardList.stream().sorted((x1, x2) -> Integer.compare(x1.get(1), x2.get(1)))
.collect(Collectors.toList());
int maxDist = maxDistance;
while (true) {
for (List<Integer> l : forwardList) {
for (List<Integer> b : backwardList) {
int forward = l.get(1);
int backward = b.get(1);
int tot = (forward + backward);
if (tot > maxDist) {
break;
}
if (tot == maxDist) {
// print the pair of Id and optimum distance
result.add(Arrays.asList(l.get(0), b.get(0), maxDist));
break;
}
}
}
if (result.size() > 0) {
break;
}
maxDist--;
}
return result;
}
}
package com.sample.test;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;
public class OptimalFlightDistant {
public static void main(String[] args) {
// sample input
System.out.println(getIdPairsForOptimal(
Arrays.asList(Arrays.asList(1, 3000), Arrays.asList(2, 5000), Arrays.asList(3, 7000),
Arrays.asList(4, 10000)),
Arrays.asList(Arrays.asList(1, 2000), Arrays.asList(2, 9000), Arrays.asList(3, 5000)), 10000));
}
public static List<List<Integer>> getIdPairsForOptimal(List<List<Integer>> forwardList,
List<List<Integer>> backwardList, int maxDistance) {
List<List<Integer>> result = new LinkedList<List<Integer>>();
forwardList = forwardList.stream().sorted((x1, x2) -> Integer.compare(x2.get(1), x1.get(1)))
.collect(Collectors.toList());
backwardList = backwardList.stream().sorted((x1, x2) -> Integer.compare(x1.get(1), x2.get(1)))
.collect(Collectors.toList());
int maxDist = maxDistance;
while (true) {
for (List<Integer> l : forwardList) {
for (List<Integer> b : backwardList) {
int forward = l.get(1);
int backward = b.get(1);
int tot = (forward + backward);
if (tot > maxDist) {
break;
}
if (tot == maxDist) {
// print the pair of Id and optimum distance
result.add(Arrays.asList(l.get(0), b.get(0), maxDist));
break;
}
}
}
if (result.size() > 0) {
break;
}
maxDist--;
}
return result;
}
}
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;
public class OptimalFlightDistant {
public static void main(String[] args) {
// sample input
System.out.println(getIdPairsForOptimal(
Arrays.asList(Arrays.asList(1, 3000), Arrays.asList(2, 5000), Arrays.asList(3, 7000),
Arrays.asList(4, 10000)),
Arrays.asList(Arrays.asList(1, 2000), Arrays.asList(2, 9000), Arrays.asList(3, 5000)), 10000));
}
public static List<List<Integer>> getIdPairsForOptimal(List<List<Integer>> forwardList,
List<List<Integer>> backwardList, int maxDistance) {
List<List<Integer>> result = new LinkedList<List<Integer>>();
forwardList = forwardList.stream().sorted((x1, x2) -> Integer.compare(x2.get(1), x1.get(1)))
.collect(Collectors.toList());
backwardList = backwardList.stream().sorted((x1, x2) -> Integer.compare(x1.get(1), x2.get(1)))
.collect(Collectors.toList());
int maxDist = maxDistance;
while (true) {
for (List<Integer> l : forwardList) {
for (List<Integer> b : backwardList) {
int forward = l.get(1);
int backward = b.get(1);
int tot = (forward + backward);
if (tot > maxDist) {
break;
}
if (tot == maxDist) {
// print the pair of Id and optimum distance
result.add(Arrays.asList(l.get(0), b.get(0), maxDist));
break;
}
}
}
if (result.size() > 0) {
break;
}
maxDist--;
}
return result;
}
}
public static List<List<int>> GetOptimalRoute1(int maxDistance, List<List<int>> forwardList, List<List<int>> returnList)
{
List<List<int>> result = new List<List<int>>();
forwardList = forwardList.OrderByDescending(x => x[1]).ToList();
returnList = returnList.OrderByDescending(x => x[1]).ToList();
int tempDistance = 0;
//look data back
for(int i=0;i< forwardList.Count;i++)
{
for (int j = 0; j < returnList.Count; j++)
{
if ((forwardList[i][1] + returnList[j][1]) < tempDistance)
break;
if((forwardList[i][1]+ returnList[j][1])<= maxDistance && (forwardList[i][1] + returnList[j][1])>= tempDistance)
{
tempDistance = forwardList[i][1] + returnList[j][1];
if((forwardList[i][1] + returnList[j][1]) >= tempDistance && result.Count==0)
result.Add(new List<int> { forwardList[i][0], returnList[j][0] });
else if ((forwardList[i][1] + returnList[j][1]) > tempDistance && result.Count > 0)
{
result.Clear();
result.Add(new List<int> { forwardList[i][0], returnList[j][0] });
}
else if ((forwardList[i][1] + returnList[j][1]) == tempDistance && result.Count > 0)
{
result.Add(new List<int> { forwardList[i][0], returnList[j][0] });
}
}
}
}
return result;
}
Sort one of the arrays of length N. Iterate the other array of length M and do a binary search in the first array updating the global maximum. O(N*log(N) + M*log(N))
- adr October 10, 2018