Amazon OA

Question 1

Problem

Given an integer representing the total number of wheels, determine the number of different ways to select a fleet from an unlimited supply of two-wheeled and four-wheeled vehicles so that the total number of wheels matches the given number. Two selections are considered different if they use a different count of two-wheeled or four-wheeled vehicles.

For example, if the input is wheels = [4, 5, 6], the output should be [2, 0, 2]:

• For 4 wheels: either 1 four-wheeler or 2 two-wheelers.
• For 5 wheels: it is impossible.
• For 6 wheels: either 1 four-wheeler + 1 two-wheeler or 3 two-wheelers.

The function should return an array of integers where each element represents the number of ways to form a fleet for the corresponding number in the input list.

• The first line contains an integer n, the number of elements.
• Each of the next n lines contains an integer, representing the total number of wheels.

Constraints

• (1 \leq n \leq 10^5)
• (1 \leq \text{wheels}[i] \leq 10^{9})

Sample Input

3
6
3
2

Sample Output

2
0
1

Explanation

• For 6 wheels:

  • Option 1: 1 four-wheeler and 1 two-wheeler.
  • Option 2: 3 two-wheelers.
    Total ways = 2.

• For 3 wheels:

  • It is not possible to form a fleet with 3 wheels.
    Total ways = 0.

• For 2 wheels:

  • Only possible with 1 two-wheeler.
    Total ways = 1.

---

Question 2

You are given a device with a limited amount of memory. Each device must run two applications at the same time: one foreground application and one background application. Each application is identified by a unique integer ID (unique within its type), requires a fixed non-zero amount of memory to execute, and is classified as either foreground or background.

A pair of applications (one foreground and one background) is considered optimal if:

• Their combined memory usage is less than or equal to the device's capacity.
• There is no other valid pair with a higher combined memory usage without exceeding the device's capacity.

Your task is to write an algorithm that finds all pairs of foreground and background applications that optimally utilize the device memory.

The function should return a list of pairs [foregroundAppID, backgroundAppID] representing the IDs of applications that optimally utilize the device. If no valid pair exists, return a list with an empty pair.

Input Format

• An integer deviceCapacity representing the device’s memory.
• A list of pairs for foreground applications.
• A list of pairs for background applications.

Output Format

• A list of pairs of integers [foregroundAppID, backgroundAppID] for each optimal application pair.
• If no valid pair exists, return a list containing an empty pair.

Examples

Example 1:

Input:
deviceCapacity = 7
foregroundAppList = [[1, 2], [2, 4], [3, 6]]
backgroundAppList = [[1, 2]]

Output:
[[2, 1]]

Explanation:

The possible pairs are:

• [1, 1] uses 2 + 2 = 4 memory.
• [2, 1] uses 4 + 2 = 6 memory.
• [3, 1] uses 6 + 2 = 8 memory (exceeds the device capacity).

Since 6 is the largest usage within capacity, [2, 1] is the only optimal pair.

---

Example 2:

Input:
deviceCapacity = 10
foregroundAppList = [[1, 3], [2, 5], [3, 7], [4, 10]]
backgroundAppList = [[1, 2], [2, 3], [3, 4], [4, 5]]

Output:
[[2, 4], [3, 2]]

Explanation:

There are two optimal pairs:

• Pair [2, 4]: Foreground app 2 uses 5 memory, background app 4 uses 5 memory; combined = 10.
• Pair [3, 2]: Foreground app 3 uses 7 memory, background app 2 uses 3 memory; combined = 10.

---

Example 3:

Input:
deviceCapacity = 16
foregroundAppList = [[2, 7], [3, 14]]
backgroundAppList = [[2, 10], [3, 14]]

Output:
[()]

Explanation:

No combination of one foreground and one background application fits within the device capacity. Hence, the output is a list with an empty pair.