Amazon SDE-1/2/SDE-Intern OA Questions | Amazon OA Questions | Kumar K | May 2026 |Set 232

Question

# Question 1 — Count Valid Subsequences

 

You are given an integer array `arr[]` of size `n`.

 

A subsequence of length `k` is considered valid if every element in that subsequence is less than or equal to `k`.

 

Formally, a subsequence `sub` is valid if:

 

[

sub[i] \le k

]

 

for all elements in the subsequence, where `k` is the size of the subsequence.

 

Return the total number of valid subsequences.

 

Notes:

 

* A subsequence is formed by deleting zero or more elements without changing the relative order.

* Different index selections are considered different subsequences.

* The empty subsequence is not counted.

 

Example:

 

```text

arr = [6,0,2,7,3,3,7]

```

 

Valid subsequences:

 

* Size 1 &rarr; only elements `<=1` &rarr; `[0]`

* Size 2 &rarr; choose 2 from `[0,2]` &rarr; `1`

* Size 3 &rarr; choose 3 from `[0,2,3,3]` &rarr; `4`

* Size 4 &rarr; choose 4 from `[0,2,3,3]` &rarr; `1`

 

Answer:

 

```text

7

```

 

Constraints:

 

```text

1 <= n <= 2 * 10^5

0 <= arr[i] <= 10^9

```

 

# Question 2 &mdash; Minimum Time to Complete Jobs

 

You are given:

 

* `jobSize[]` where `jobSize[k]` represents the size of the kth job.

* `throughput[]` where `throughput[i]` represents the maximum job size worker `i` can process.

 

A worker can process a job only if:

 

[

jobSize[k] \le throughput[i]

]

 

Rules:

 

* Each job takes exactly `1 second`.

* After completing a job, a worker must rest for `1 second` before starting another job.

* Workers operate in parallel.

* If a worker completes `x` jobs, total time taken by that worker is:

 

[

2x - 1

]

 

Return the minimum time required to complete all jobs.

 

If any job cannot be processed by any worker, return `-1`.

 

Example 1:

 

```text

jobSize = [2,3,1]

throughput = [3,1]

```

 

Optimal assignment:

 

* Worker 1 &rarr; `[2,3]` &rarr; `3s`

* Worker 2 &rarr; `[1]` &rarr; `1s`

 

Workers run in parallel.

 

Answer:

 

```text

3

```

 

Example 2:

 

```text

jobSize = [4,5]

throughput = [3,4]

```

 

No worker can process job `5`.

 

Answer:

 

```text

-1

```

 

Constraints:

 

```text

1 <= jobSize.length, throughput.length <= 2 * 10^5

1 <= jobSize[i], throughput[i] <= 10^9

```