Optimal Utilization
Updated
Problem statement
A device has deviceCapacity units of memory. It must run two apps at the same time: one foreground app and one background app.
foregroundAppList[i] = [id, memory] describes one foreground app. backgroundAppList[j] = [id, memory] describes one background app. IDs are unique within each list. Every app needs some memory, at least 1 unit.
A pair is one foreground app and one background app. A pair fits when their memories add up to at most deviceCapacity. A pair is optimal when it fits and no other pair that fits uses more memory.
Return every optimal pair as [foregroundAppID, backgroundAppID]. Sort the pairs by foreground ID, then by background ID. If no pair fits, return [[]], a list with one empty pair.
For example, let deviceCapacity = 5, foregroundAppList = [[1, 2], [2, 2]] and backgroundAppList = [[1, 3]]. Both pairs use 2 + 3 = 5 memory, which fits. The answer is [[1, 1], [2, 1]].
Function
optimalUtilization(deviceCapacity: int, foregroundAppList: int[][], backgroundAppList: int[][]) → int[][]
Complete the function optimalUtilization in the editor.
optimalUtilization has the following parameters:
int deviceCapacity: the memory of the deviceint foregroundAppList[n][2]: the foreground apps, each as [id, memory]int backgroundAppList[m][2]: the background apps, each as [id, memory]
Returns
int[][]: every optimal pair, sorted, or [[]] if no pair fits
Examples
Example 1
deviceCapacity = 7foregroundAppList = [[1, 2], [2, 4], [3, 6]]backgroundAppList = [[1, 2]]return = [[2, 1]]The pairs are [1, 1] with 2 + 2 = 4, [2, 1] with 4 + 2 = 6, and [3, 1] with 6 + 2 = 8. The last one is more than 7, so it does not fit. The largest total that fits is 6. The answer is [[2, 1]].
Example 2
deviceCapacity = 10foregroundAppList = [[1, 3], [2, 5], [3, 7], [4, 10]]backgroundAppList = [[1, 2], [2, 3], [3, 4], [4, 5]]return = [[2, 4], [3, 2]]The largest total that fits in 10 is 10 itself. Foreground app 2 (memory 5) with background app 4 (memory 5) gives 10. Foreground app 3 (memory 7) with background app 2 (memory 3) also gives 10. No other pair gives 10. Sorted by foreground ID, the answer is [[2, 4], [3, 2]].
Example 3
deviceCapacity = 16foregroundAppList = [[2, 7], [3, 14]]backgroundAppList = [[2, 10], [3, 14]]return = [[]]The smallest pair is foreground app 2 (memory 7) with background app 2 (memory 10). It uses 17, which is more than 16. So no pair fits. The answer is [[]].
Constraints
1 <= deviceCapacity <= 2 * 10^91 <= n <= 10^5, wherenis the length offoregroundAppList1 <= m <= 10^5, wheremis the length ofbackgroundAppList- Each app is
[id, memory]with1 <= id <= 10^6and1 <= memory <= 10^9 - IDs are unique within each list
More Amazon interview questions
- LRU Cache for Query ResultsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Maximal SquareONSITE INTERVIEW · Seen Nov 2026
- Serialize and Deserialize a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Course SchedulePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course Schedule IIPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Diagonal Traversal of a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Spread Through a GridPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Consistent-Hash Packet RouterPHONE SCREEN · Seen Nov 2026
- Count Connected ComponentsPHONE SCREEN · Seen Nov 2026
- Maximize K-Element AND with an Increment BudgetOA · Seen Nov 2026
Similar questions at other companies
- Maximum Easy Tasks After RearrangingIBM · OAIBM interview questions
- Latest Arrival to Catch a BusAutodesk · OAAutodesk interview questions
- Maximum Concurrent ProcessesMorgan Stanley · OA · ONSITE INTERVIEWMorgan Stanley interview questions
- Minimum Removals to Balance ArraySalesforce · OASalesforce interview questions
- Count Perfect PairsAdyen · OAAdyen interview questions
- Profitable Project PairsAkuna Capital · OAAkuna Capital interview questions
- 3SumAT&T · OAAT&T interview questions
- Minimum Height Difference Between Distant PeaksRoblox · OARoblox interview questions
- Minimum Machines for TasksExpedia · OAExpedia interview questions
- Find Minimum Possible SizeMathWorks · OAMathWorks interview questions