## Amazon Online Assessment Questions 2020 OA2 - Optimize Memory Usage

Give a computer with total K memory space, and an array of foreground tasks and background tasks the computer needs to do. Write an algorithm to find a pair of tasks from each array to maximize the memory usage.
Notice the tasks could be done without origin order.

**Input**

The input to the function/method consists of three arguments :

foregroundTask, an array representing the memory usage of the foreground tasks,

backgroundTask, an array representing the memory usage of the background tasks,

K, the total memory space of the computer.

**Output**

Return a list of pairs of the task ids.

**Examples 1**

Input:

foregroundTasks = [1, 7, 2, 4, 5, 6]

backgroundTasks = [3, 1, 2]

K = 6

Output:

[(3, 2), (4, 1), (5,-1)]

Explaination:

Here we have 5 foreground tasks: task 0 uses 1 memeory. task 1 uses 7 memeory. task 2 uses 2 memeory..

And 5 background tasks: task 0 uses 3 memeory. task 1 uses 1 memeory. task 2 uses 2 memeory..

We need to find two tasks with total memory usage sum <= K.

Here we can return the foreground task 3 and background task 2, which total use 6 units of memory.

Or we can return the foreground task 4 and background task 1. Also use total 6 units of memory.

Or we can return the foreground task 5 only without any background task. Also use total 6 units of memory.

**Examples 2**

Input:

foregroundTasks = [1, 7, 2, 4, 5, 6]

backgroundTasks = [1, 1, 2]

K = 10

Output:

[(1, 2)]

Explaination:

Here we can return the foreground task 1 and background task 2. Total memory usage is 7 + 2 = 9, which is smaller than 10. Given there is no larger better memory usage combination than 9 , this is the optimal solution.

##### Solve the problem:

Python3#### Get one-to-one training from Google Facebook engineers

##### Top-notch Professionals

Learn from Facebook and Google senior engineers interviewed 100+ candidates.

Most recent interview questions and system design topics gathered from aonecode alumnus.

One-to-one online classes. Get feedbacks from real interviewers.

##### Customized Private Class

Already a coding expert? - Advance straight to hard interview topics of your interest.

New to the ground? - Develop basic coding skills with your own designated mentor.

Days before interview? - Focus on most important problems in target company question bank.