Page Contents
Optimal Utilization Solution
Given 2 lists a
and b
. Each element is a pair of integers where the first integer represents the unique id and the second integer represents a value. Your task is to find an element from a
and an element form b
such that the sum of their values is less or equal to target
and as close to target
as possible. Return a list of ids of selected elements. If no pair is possible, return an empty list.
Also See: Amazon OA Online Assessment 2021 Questions and Answers
Example 1:
Input:
a = [[1, 2], [2, 4], [3, 6]]
b = [[1, 2]]
target = 7
Output: [[2, 1]]
Explanation:
There are only three combinations [1, 1], [2, 1], and [3, 1], which have a total sum of 4, 6 and 8, respectively.
Since 6 is the largest sum that does not exceed 7, [2, 1] is the optimal pair.
Example 2:
Input:
a = [[1, 3], [2, 5], [3, 7], [4, 10]]
b = [[1, 2], [2, 3], [3, 4], [4, 5]]
target = 10
Output: [[2, 4], [3, 2]]
Explanation:
There are two pairs possible. Element with id = 2 from the list `a` has a value 5, and element with id = 4 from the list `b` also has a value 5.
Combined, they add up to 10. Similarily, element with id = 3 from `a` has a value 7, and element with id = 2 from `b` has a value 3.
These also add up to 10. Therefore, the optimal pairs are [2, 4] and [3, 2].
Example 3:
Input:
a = [[1, 8], [2, 7], [3, 14]]
b = [[1, 5], [2, 10], [3, 14]]
target = 20
Output: [[3, 1]]
Example 4:
Input:
a = [[1, 8], [2, 15], [3, 9]]
b = [[1, 8], [2, 11], [3, 12]]
target = 20
Output: [[1, 3], [3, 2]]
Solution
Program C++
#include <vector> #include <algorithm> #include <iterator> #include <iostream> using namespace std; vector<vector<int>> optimal(vector<vector<int>>& a, vector<vector<int>>& b, int target) { std::sort(a.begin(), a.end(), [](vector<int>& a, vector<int>& b) { return a[1] < b[1];}); std::sort(b.begin(), b.end(), [](vector<int>& a, vector<int>& b) { return a[1] < b[1];}); auto aptr = a.begin(); auto bptr = b.rbegin(); int minSum = -1 * __INT_MAX__; vector<vector<int>> res; while(aptr != a.end() && bptr != b.rend()) { int sum = (*aptr)[1] + (*bptr)[1]; if(sum > target) { //decrement bptr ++bptr; } else { //sum <= to target which is what we want if(sum > minSum) { res.clear(); } res.push_back({(*aptr)[0], (*bptr)[0]}); minSum = sum; ++aptr; } } return res; } void test(vector<vector<int>> a, vector<vector<int>> b, int target) { vector<vector<int>> res = optimal(a, b, target); for(auto i = res.begin(); i != res.end(); ++i) { for(auto j = (*i).begin(); j != (*i).end(); ++j) cout << ' ' << *j; cout << '\n'; } cout << endl; } int main() { test({{1, 2}, {2, 4}, {3, 6}}, {{1, 2}}, 7); test({{1, 3}, {2, 5}, {3, 7}, {4, 10}}, {{1, 2}, {2, 3}, {3, 4}, {4, 5}}, 10); test({{1, 8}, {2, 7}, {3, 14}}, {{1, 5}, {2, 7}, {3, 14}}, 20); return 0; }
Program Java
import java.util.*; public class OptimalUti { private static List<List<Integer>> compute(int[][] a, int[][] b, int target) { List<List<Integer>> res = new ArrayList<>(); TreeMap<Integer, List<List<Integer>>> tree = new TreeMap<>(); for (int i=0; i<a.length; i++) { for (int j=0; j<b.length; j++) { int sum = a[i][1] + b[j][1]; if (sum <= target) { List<List<Integer>> list = tree.computeIfAbsent(sum, (k) -> new ArrayList<>()); list.add(Arrays.asList(a[i][0], b[j][0])); } } } return tree.floorEntry(target).getValue(); } public static void main(String...s) { int[][][] As = { {{1, 2}, {2, 4}, {3, 6}}, {{1, 3}, {2, 5}, {3, 7}, {4, 10}}, {{1, 8}, {2, 7}, {3, 14}}, {{1, 8}, {2, 15}, {3, 9}} }; int[][][] Bs = { {{1, 2}}, {{1, 2}, {2, 3}, {3, 4}, {4, 5}}, {{1, 5}, {2, 10}, {3, 14}}, {{1, 8}, {2, 11}, {3, 12}} }; int[] targets = {7, 10, 20, 20}; for (int i=0; i<4; i++) { System.out.println(compute(As[i], Bs[i], targets[i]).toString()); } } }
Program Python
def find_element(nums, target): length = len(nums) st = 0 ed = length-1 while st < ed: mid = (st + ed + 1) // 2 if nums[mid][1] > target: ed = mid - 1 else: st = mid return nums[st] def UptimalUtilization(a, b, target): a.sort(key=lambda x:x[1]) b.sort(key=lambda x:x[1]) len1 = len(a) len2 = len(b) curval = 0 res = [] for idx1, num1 in a: idx2, num2 = find_element(b,target-num1) if num1 + num2 <= target: print(num1+num2) if curval < num1 + num2: curval = num1 + num2 res = [[idx1, idx2]] elif curval == num1 + num2: res.append([idx1, idx2]) return res a = [[1, 2], [2, 4], [3, 6]] b = [[1, 2]] target = 7 print(UptimalUtilization(a, b, target))
Also See: AMCAT Study Materials, Preparation Guide
Also See: Microsoft Online Assessment Questions and Solution
Amazon Online Assessment Questions:
- Robot Bounded in Box
- Number Game
- Find All Combination of Numbers Sum to Target / Shopping Options
- Fill the Truck
- Music Pairs
- Slowest key
- Five Star Seller
- Split String Into Unique Primes
- Storage Optimization
- Minimum Difficulty of a Job Schedule
- Autoscale Policy, Utilization Check
- Optimal Utilization
- Merge Two Sorted Lists
- Two Sum Unique Pairs
- Shopping Patterns
- Reorder Data in Log Files
- Top K Frequent Words
- Trees Height
- Counting Binary Substrings Amazon OA Solution
- Grid Connections Amazon OA Solution
- Shipment Imbalance Amazon OA Solution
- Max Profit Amazon OA Solution
- Find Lowest Price Amazon OA Solution
- Simple Cipher Amazon OA Solution
- Decode String Frequency Amazon OA Solution
- Valid Discount Coupons Amazon OA Solution
- Count Maximum Teams Amazon OA Solution
- Minimum Coin Flips Amazon OA Solution