## Amazon Interview Question for SDE-2s

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
1
of 1 vote

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))

``````def find(F, B, T):
ans = [0, 0, 0]
F = sorted([x, i] for i,x in F)
for idy,y in B:
f = 0
end = len(F)
z = T - y
while f != end:
m = (f + end)/2
if F[m][0] <= z:
f = m+1
else:
end = m
if f != 0 and y+F[f-1][0] > ans[0]:
ans = [y+F[f-1][0], F[f-1][1], idy]
return ans[1:]

print find([(1,3000),(2,5000),(3,4000),(4,10000)],
[(1,2000),(2,3000),(3,4000)], 11000)``````

Comment hidden because of low score. Click to expand.
0

can you give java solution..

Comment hidden because of low score. Click to expand.
0

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?

Comment hidden because of low score. Click to expand.
0

``````package com.sample.test;

import java.util.Arrays;
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) {
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
break;
}

}
}
if (result.size() > 0) {
break;
}
maxDist--;
}
return result;
}

}``````

Comment hidden because of low score. Click to expand.
0

``````import java.util.Arrays;
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) {
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
break;
}

}
}
if (result.size() > 0) {
break;
}
maxDist--;
}
return result;
}

}``````

Comment hidden because of low score. Click to expand.
0

package com.sample.test;

import java.util.Arrays;
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) {
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
break;
}

}
}
if (result.size() > 0) {
break;
}
maxDist--;
}
return result;
}

}

Comment hidden because of low score. Click to expand.
1
of 1 vote

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));``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)?

Comment hidden because of low score. Click to expand.
0

For each direction (forward & return) the distances are unique

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)
{
break;
}
}
return result;
}``````

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

I think it's storing all the pairs but returning only the top pair using count sort and exiting from the loop once found a value that is not null. So, you get only the pair whose sum <= capacity and not all pairs.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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?

Comment hidden because of low score. Click to expand.
0

With what value to compare in condition “if maxValue greater than clear the list ”
And why clear the list and and add sum to it ? Can you please put working code if you can ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``def closestXDestionation(forward, backward, maximum):``

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````// java code
import java.util.*;

public class OptimalRoute
{
public static void main(String[] args)
{

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);
i++;
} else if(forwardList.get(i).get(1) + returnList.get(j).get(1) == max) {
// no need to reset result list
i++;
} else {
j--;
}
}
return result;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````package com.sample.test;

import java.util.Arrays;
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) {
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
break;
}

}
}
if (result.size() > 0) {
break;
}
maxDist--;
}
return result;
}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````package com.sample.test;

import java.util.Arrays;
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) {
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
break;
}

}
}
if (result.size() > 0) {
break;
}
maxDist--;
}
return result;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.Arrays;
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) {
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
break;
}

}
}
if (result.size() > 0) {
break;
}
maxDist--;
}
return result;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.