FastPrepOptimal Utilization
Problems/Optimal Utilization

Optimal Utilization

Amazon logoAmazon● MediumOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

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 device
  • int 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^9
  • 1 <= n <= 10^5, where n is the length of foregroundAppList
  • 1 <= m <= 10^5, where m is the length of backgroundAppList
  • Each app is [id, memory] with 1 <= id <= 10^6 and 1 <= 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

Interview reports that mention this question

  • Amazon Full-Time OA Problems, Recent Reports (Part 4 of 5)

Amazon interview experiences

  • Amazon Experienced SDE Onsite Questions: 1 Experience
  • Amazon SDE Onsite Interview Questions: 9 Experiences
  • Amazon SDE II and L5 FDE Interview Questions: 4 Experiences
  • Amazon Full-Time OA Problems, Earlier Reports (Part 5 of 5)
  • Amazon New Grad OA Problems: Every Task We Have (Part 3 of 5)
See Amazon hiring insights
Saved
class Solution {
    public int[][] optimalUtilization(int deviceCapacity, int[][]foregroundAppList, int[][] backgroundAppList) {
      // write your code here
    }

}
Checking account…