Decide and implement DP/heap and approximation

Q: Decide and implement DP/heap and approximation

This is a Coding & Algorithms interview question from Optiver for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.

Decide and implement DP/heap and approximation

Comments (0)