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)

- 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.
-1
of 1 vote

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

}

- Prithvish Mukherjee January 04, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

}

- Prithvish Mukherjee January 04, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

}

- Prithvish Mukherjee January 04, 2019 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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


}

- Abhishek Kumar June 12, 2019 | Flag Reply
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 votes

Awesome solution

- Anonymous August 24, 2019 | Flag
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
Comment hidden because of low score. Click to expand.
0
of 2 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));

- Ram December 26, 2018 | Flag Reply
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)
  {
    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;
  }	
}

- Manu Mehrotra December 29, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- Anonymous January 04, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- Prithvish Mukherjee January 04, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- prithvish.mukherjee@techolution.com January 04, 2019 | Flag Reply
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;
}

- lrainy1213 January 15, 2019 | 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