How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Optiver.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Optiver during technical interviews.

Decide and implement DP/heap and approximation

Quick Overview

This question evaluates dynamic programming for counting constrained subsequences, priority-heap implementation and API robustness for job scheduling, and heuristic approximation methods for NP-hard selection problems, along with algorithmic complexity analysis.

Decide and implement DP/heap and approximation

Company: Optiver

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

You have 90 minutes to complete three related coding tasks: a) Dynamic programming: Given an integer array nums (n ≤ 2e 5) and a threshold T, design and implement an algorithm to count the number of non-empty subsequences whose sum is at most T; explain why brute force is infeasible, justify your chosen DP or optimized approach, and analyze time and space complexity. b) Heap simulation: Implement a job scheduler that supports up to 2e5 operations over jobs with APIs INSERT(jobId, priority), POP() returning the smallest-priority job with stable tie-breaking, and DECREASE_KEY(jobId, delta); guarantee O(log n) per operation using a binary heap (or equivalent) and handle invalid/duplicate operations robustly. c) Approximate optimization: For selecting k items from n to minimize total score given item weights and pairwise penalties (an NP-hard objective), propose and implement a greedy or simulated-annealing heuristic; specify initialization, temperature/cooling or selection rules, stopping criteria, and how you will evaluate approximation quality versus a baseline.

Quick Answer: This question evaluates dynamic programming for counting constrained subsequences, priority-heap implementation and API robustness for job scheduling, and heuristic approximation methods for NP-hard selection problems, along with algorithmic complexity analysis.

Count Subsequences With Sum At Most T (DP / Meet-in-the-Middle)

Given an integer array `nums` and a threshold `T`, count the number of non-empty subsequences (chosen by index, order irrelevant) whose element sum is at most `T`. The array may contain negative numbers, so a positive-only knapsack DP is not directly applicable. Brute force enumerates all 2^n subsequences and is infeasible for large n. For arbitrary (possibly negative) values where T can be any integer, a counting DP keyed on the sum is only viable when the sum range is bounded; the general robust approach for a moderate n is meet-in-the-middle: split the array in half, enumerate all subset sums of each half (2^(n/2) each), sort one side, and for every left-half sum binary-search how many right-half sums keep the combined total at most T. This brings the cost from O(2^n) down to O(2^(n/2) * (n/2)). Subtract 1 at the end to exclude the empty subsequence (whose sum 0 would otherwise be counted whenever T >= 0). Return the count as an integer.

Constraints

0 <= n <= 30 (meet-in-the-middle range; brute force is infeasible beyond ~30)
nums[i] may be negative, zero, or positive
T can be any integer (positive, zero, or negative)
The empty subsequence is NOT counted

Examples

Input: ([1, 2, 3], 3)

Expected Output: 4

Explanation: Non-empty subsequences with sum <= 3: [1], [2], [3], [1,2]. Count = 4.

Input: ([4, 5], 3)

Expected Output: 0

Explanation: Smallest element is 4 > 3, so no non-empty subsequence qualifies.

Input: ([-1, -2, 5], 0)

Expected Output: 3

Explanation: Subsequences with sum <= 0: [-1], [-2], [-1,-2]. Count = 3.

Input: ([], 5)

Expected Output: 0

Explanation: Empty array has no non-empty subsequences.

Input: ([2], 2)

Expected Output: 1

Explanation: Only [2] with sum 2 <= 2.

Input: ([3, 1, 2, 4], 5)

Expected Output: 8

Explanation: Singletons [3],[1],[2],[4] (4) plus pairs summing <=5: [3,1],[3,2],[1,2],[1,4] (4). Total = 8.

Hints

Why is 2^n infeasible? With n only in the 40s, 2^n already exceeds 10^12 enumerations — you cannot list every subsequence.
Negative numbers break the monotonic 'stop early when the partial sum exceeds T' pruning, so a simple positive knapsack does not apply.
Split nums in half. Enumerate all subset sums of each half (2^(n/2) each), sort one side, and binary-search the complementary bound T - leftSum for each left sum.
Both halves' enumerations include the empty subset (sum 0), so the combined count includes the global empty subsequence once — subtract 1 when T >= 0.

Priority Job Scheduler (INSERT / POP / DECREASE_KEY with Stable Ties)

Implement a job scheduler driven by a list of `operations`. Each operation is a list: - `["INSERT", jobId, priority]` — add a job. A duplicate INSERT of a currently-live jobId is ignored. - `["DECREASE_KEY", jobId, delta]` — set the job's priority to (old priority - delta). An operation on an unknown or already-popped jobId is ignored. - `["POP"]` — remove and report the job with the smallest priority. Ties are broken by insertion order (the earliest-inserted live job wins — stable). If the scheduler is empty, report `-1`. Return the list of POP outputs in order. Each operation must run in O(log n). Use a binary heap keyed on `(priority, insertionSeq, jobId)`. Because a standard binary heap has no decrease-key handle, use lazy deletion: on DECREASE_KEY push a fresh `(newPriority, seq, jobId)` entry and, on POP, discard any heap-top whose stored priority no longer matches the job's current priority (or whose job is no longer live). The insertionSeq tie-breaker makes POP ordering deterministic and stable.

Constraints

Up to 2e5 operations
jobId values are integers; priorities and deltas are integers (priority may go negative via DECREASE_KEY)
POP on an empty scheduler returns -1
Duplicate INSERT of a live job, and DECREASE_KEY/POP-target of an unknown job, are ignored
Ties in priority are broken by insertion order (stable)

Examples

Input: ([['INSERT', 1, 5], ['INSERT', 2, 3], ['POP'], ['POP'], ['POP']],)

Expected Output: [2, 1, -1]

Explanation: Job 2 (priority 3) pops before job 1 (priority 5); the third POP finds an empty scheduler -> -1.

Input: ([['INSERT', 1, 5], ['INSERT', 2, 5], ['POP'], ['POP']],)

Expected Output: [1, 2]

Explanation: Equal priorities; stable tie-break pops the earlier-inserted job 1 first.

Input: ([['INSERT', 1, 5], ['DECREASE_KEY', 1, 10], ['INSERT', 2, 0], ['POP'], ['POP']],)

Expected Output: [1, 2]

Explanation: DECREASE_KEY makes job 1's priority 5-10=-5, beating job 2's 0.

Input: ([['POP']],)

Expected Output: [-1]

Explanation: POP on an empty scheduler returns -1.

Input: ([['INSERT', 1, 5], ['INSERT', 1, 1], ['DECREASE_KEY', 9, 3], ['POP']],)

Expected Output: [1]

Explanation: Duplicate INSERT of live job 1 ignored (priority stays 5); DECREASE_KEY on unknown job 9 ignored; POP returns job 1.

Input: ([],)

Expected Output: []

Explanation: No operations -> no POP outputs.

Hints

A plain binary heap cannot decrease a key in place. Avoid an O(n) search-and-sift by using lazy deletion.
Key heap entries on (priority, insertionSeq, jobId). The insertionSeq guarantees stable, deterministic tie-breaking.
On DECREASE_KEY, just push a new (newPriority, seq, jobId) entry and update the job's current priority in a side map. Don't try to find and edit the old entry.
On POP, skip any heap-top whose job is no longer live or whose stored priority doesn't equal the job's current priority — those are stale duplicates.

Approximate k-Subset Selection by Deterministic Greedy

You must select exactly `k` items from `n` to minimize a total score that combines per-item `weights` and symmetric `penalties[i][j]` paid whenever both i and j are selected: score(S) = sum(weights[i] for i in S) + sum(penalties[i][j] for i < j in S) This objective is NP-hard in general (it generalizes dense-subgraph / quadratic selection problems), so an exact search is infeasible at scale. Implement a deterministic greedy heuristic and return the score of the set it produces. Greedy rule: start with an empty selection. Repeat k times, each step adding the not-yet-selected item whose *marginal* score increase — its own weight plus the penalties it incurs against the already-selected items — is smallest. Break ties by smallest index. Accumulate and return the total score of the chosen set. (In an interview you'd extend this with simulated annealing — random swaps with a cooling acceptance probability — and compare its score against this greedy baseline; the greedy result is the deterministic baseline this function computes.) If k <= 0 or n == 0, return 0; if k > n, select all n items.

Constraints

weights has length n; penalties is an n x n symmetric matrix with a zero diagonal
0 <= k; if k > n, all n items are selected
weights[i] and penalties[i][j] are non-negative integers in the test cases
The greedy result is a heuristic, not guaranteed globally optimal

Examples

Input: ([1, 2, 3], [[0, 1, 1], [1, 0, 1], [1, 1, 0]], 2)

Expected Output: 4

Explanation: Pick item 0 (cost 1), then item 1 (cost 2 + penalty 1 = 3). Total 1+3 = 4.

Input: ([5, 5, 5], [[0, 0, 0], [0, 0, 0], [0, 0, 0]], 2)

Expected Output: 10

Explanation: No penalties; any two items cost 5+5 = 10.

Input: ([10, 1, 1], [[0, 9, 9], [9, 0, 0], [9, 0, 0]], 2)

Expected Output: 2

Explanation: Greedy picks item 1 (cost 1) then item 2 (cost 1 + penalty[2][1]=0). Item 0 is avoided. Total 2.

Input: ([3, 4], [[0, 0], [0, 0]], 0)

Expected Output: 0

Explanation: k = 0 selects nothing; score 0.

Input: ([7], [[0]], 5)

Expected Output: 7

Explanation: k > n, so select the single item; score 7.

Input: ([2, 2, 2, 2], [[0, 5, 5, 5], [5, 0, 0, 0], [5, 0, 0, 0], [5, 0, 0, 0]], 3)

Expected Output: 16

Explanation: Pick item 0 (2), item 1 (2+5=7), item 2 (2+pen[2][0]+pen[2][1]=2+5+0=7). Total 2+7+7 = 16.

Hints

The objective is quadratic in the selection (pairwise penalties), so it is NP-hard — don't try every k-subset for large n.
Greedy adds one item at a time. The cost of adding item i now is weights[i] plus the penalties between i and every item already selected.
Recompute each candidate's marginal cost against the current selection; pick the minimum, breaking ties by smallest index for determinism.
To go beyond greedy, seed simulated annealing with this greedy set and accept worsening swaps with probability exp(-delta/T) under a cooling schedule, then compare final scores.

Quick Overview

Decide and implement DP/heap and approximation

Company: Optiver

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Count Subsequences With Sum At Most T (DP / Meet-in-the-Middle)

Constraints

0 <= n <= 30 (meet-in-the-middle range; brute force is infeasible beyond ~30)
nums[i] may be negative, zero, or positive
T can be any integer (positive, zero, or negative)
The empty subsequence is NOT counted

Examples

Input: ([1, 2, 3], 3)

Expected Output: 4

Explanation: Non-empty subsequences with sum <= 3: [1], [2], [3], [1,2]. Count = 4.

Input: ([4, 5], 3)

Expected Output: 0

Explanation: Smallest element is 4 > 3, so no non-empty subsequence qualifies.

Input: ([-1, -2, 5], 0)

Expected Output: 3

Explanation: Subsequences with sum <= 0: [-1], [-2], [-1,-2]. Count = 3.

Input: ([], 5)

Expected Output: 0

Explanation: Empty array has no non-empty subsequences.

Input: ([2], 2)

Expected Output: 1

Explanation: Only [2] with sum 2 <= 2.

Input: ([3, 1, 2, 4], 5)

Expected Output: 8

Explanation: Singletons [3],[1],[2],[4] (4) plus pairs summing <=5: [3,1],[3,2],[1,2],[1,4] (4). Total = 8.

Hints

Why is 2^n infeasible? With n only in the 40s, 2^n already exceeds 10^12 enumerations — you cannot list every subsequence.
Negative numbers break the monotonic 'stop early when the partial sum exceeds T' pruning, so a simple positive knapsack does not apply.
Split nums in half. Enumerate all subset sums of each half (2^(n/2) each), sort one side, and binary-search the complementary bound T - leftSum for each left sum.
Both halves' enumerations include the empty subset (sum 0), so the combined count includes the global empty subsequence once — subtract 1 when T >= 0.

Priority Job Scheduler (INSERT / POP / DECREASE_KEY with Stable Ties)

Constraints

Up to 2e5 operations
jobId values are integers; priorities and deltas are integers (priority may go negative via DECREASE_KEY)
POP on an empty scheduler returns -1
Duplicate INSERT of a live job, and DECREASE_KEY/POP-target of an unknown job, are ignored
Ties in priority are broken by insertion order (stable)

Examples

Input: ([['INSERT', 1, 5], ['INSERT', 2, 3], ['POP'], ['POP'], ['POP']],)

Expected Output: [2, 1, -1]

Explanation: Job 2 (priority 3) pops before job 1 (priority 5); the third POP finds an empty scheduler -> -1.

Input: ([['INSERT', 1, 5], ['INSERT', 2, 5], ['POP'], ['POP']],)

Expected Output: [1, 2]

Explanation: Equal priorities; stable tie-break pops the earlier-inserted job 1 first.

Input: ([['INSERT', 1, 5], ['DECREASE_KEY', 1, 10], ['INSERT', 2, 0], ['POP'], ['POP']],)

Expected Output: [1, 2]

Explanation: DECREASE_KEY makes job 1's priority 5-10=-5, beating job 2's 0.

Input: ([['POP']],)

Expected Output: [-1]

Explanation: POP on an empty scheduler returns -1.

Input: ([['INSERT', 1, 5], ['INSERT', 1, 1], ['DECREASE_KEY', 9, 3], ['POP']],)

Expected Output: [1]

Explanation: Duplicate INSERT of live job 1 ignored (priority stays 5); DECREASE_KEY on unknown job 9 ignored; POP returns job 1.

Input: ([],)

Expected Output: []

Explanation: No operations -> no POP outputs.

Hints

A plain binary heap cannot decrease a key in place. Avoid an O(n) search-and-sift by using lazy deletion.
Key heap entries on (priority, insertionSeq, jobId). The insertionSeq guarantees stable, deterministic tie-breaking.
On DECREASE_KEY, just push a new (newPriority, seq, jobId) entry and update the job's current priority in a side map. Don't try to find and edit the old entry.
On POP, skip any heap-top whose job is no longer live or whose stored priority doesn't equal the job's current priority — those are stale duplicates.

Approximate k-Subset Selection by Deterministic Greedy

Constraints

weights has length n; penalties is an n x n symmetric matrix with a zero diagonal
0 <= k; if k > n, all n items are selected
weights[i] and penalties[i][j] are non-negative integers in the test cases
The greedy result is a heuristic, not guaranteed globally optimal

Examples

Input: ([1, 2, 3], [[0, 1, 1], [1, 0, 1], [1, 1, 0]], 2)

Expected Output: 4

Explanation: Pick item 0 (cost 1), then item 1 (cost 2 + penalty 1 = 3). Total 1+3 = 4.

Input: ([5, 5, 5], [[0, 0, 0], [0, 0, 0], [0, 0, 0]], 2)

Expected Output: 10

Explanation: No penalties; any two items cost 5+5 = 10.

Input: ([10, 1, 1], [[0, 9, 9], [9, 0, 0], [9, 0, 0]], 2)

Expected Output: 2

Explanation: Greedy picks item 1 (cost 1) then item 2 (cost 1 + penalty[2][1]=0). Item 0 is avoided. Total 2.

Input: ([3, 4], [[0, 0], [0, 0]], 0)

Expected Output: 0

Explanation: k = 0 selects nothing; score 0.

Input: ([7], [[0]], 5)

Expected Output: 7

Explanation: k > n, so select the single item; score 7.

Input: ([2, 2, 2, 2], [[0, 5, 5, 5], [5, 0, 0, 0], [5, 0, 0, 0], [5, 0, 0, 0]], 3)

Expected Output: 16

Explanation: Pick item 0 (2), item 1 (2+5=7), item 2 (2+pen[2][0]+pen[2][1]=2+5+0=7). Total 2+7+7 = 16.

Hints

The objective is quadratic in the selection (pairwise penalties), so it is NP-hard — don't try every k-subset for large n.
Greedy adds one item at a time. The cost of adding item i now is weights[i] plus the penalties between i and every item already selected.
Recompute each candidate's marginal cost against the current selection; pick the minimum, breaking ties by smallest index for determinism.
To go beyond greedy, seed simulated annealing with this greedy set and accept worsening swaps with probability exp(-delta/T) under a cooling schedule, then compare final scores.