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.
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.
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.
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.