Amazon Online Assessment (OA) - Optimal Utilization
Given two 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.
Input
a
, a list of integer pairs
where the first integer represents the unique id and the second integer represents a value.
b
, a list of integer pairs
where the first integer represents the unique id and the second integer represents a value.
target
, an integer
representing the target number.
Examples
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
. Similarly, 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
,