Amazon Interview Question for SDE-2s


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
0
of 0 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)

- adr October 10, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you give java solution..

- john October 18, 2018 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Anonymous October 28, 2018 | Flag
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).

- ss October 12, 2018 | Flag Reply
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)?

- Himanshu October 13, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous November 12, 2018 | Flag
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)
         {
            result.addAll(store[k]);
            break;
         }
      }
      return result;
   }

- Anonymous October 28, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous October 28, 2018 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous November 15, 2018 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Harpz November 05, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Harpz November 05, 2018 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- harpz November 05, 2018 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Anonymous November 28, 2018 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 ?

- Anonymous November 28, 2018 | Flag
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)

- MT November 13, 2018 | Flag Reply
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)

- MT November 13, 2018 | Flag Reply
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)

- MT November 13, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def closestXDestionation(forward, backward, maximum):

- MT November 13, 2018 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More