## Amazon Interview Question

SDE-2s**Country:**United States

**Interview Type:**In-Person

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

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