## Design a Priority Task Executor with Duplicate Task IDs Design an in-memory component with two operations: - `addTask(taskId, priority, timestamp)` records a task occurrence. The same `taskId` may be added multiple times with different timestamps. - `executeTask()` selects at most one not-yet-executed task by priority. If a queued occurrence belongs to a task ID that has already executed, it must be skipped and selection must continue. The source requirement does not define priority direction or tie-breaking. Ask for those rules, then state a deterministic policy before implementing. ### Constraints & Assumptions - Execution status applies to the task ID: once one occurrence executes, all other queued occurrences of that ID are stale. - `addTask` preserves every occurrence until it is selected or lazily discarded. - `executeTask` returns an empty result when no eligible task remains. - The design must distinguish two occurrences even when all supplied fields are equal. ### Clarifying Questions to Ask - Does a larger or smaller numeric value mean higher priority? - When priorities tie, should earlier or later timestamps win, and how are equal timestamps ordered? - Can an executed task ID ever be reactivated by a later `addTask` call? - Are the two operations called concurrently, and what consistency guarantee is required? ### Part 1 — Define Ordering and State Choose a deterministic ordering policy and identify the state needed to represent queued occurrences and task IDs that have already executed. #### What This Part Should Cover - Priority direction and complete tie-breaking. - Occurrence identity separate from `taskId`. - The lifetime of executed-task state. - Empty-queue behavior. ```hint Separate an occurrence from a task Several heap records can share one task ID, but the rule that suppresses future execution belongs to the task ID. ``` ### Part 2 — Implement Both Operations Select data structures and give pseudocode for `addTask` and `executeTask`. Explain how stale duplicate occurrences are removed without scanning the whole queue on every insertion. #### What This Part Should Cover - The queue key and the purpose of an insertion sequence number. - Lazy removal of occurrences whose task ID is already executed. - When a task ID is marked executed relative to returning or invoking work. - Worst-case and amortized operation costs. ```hint Let selection clean the top A priority queue can retain stale duplicates and discard them only when they reach the top, so each occurrence is removed at most once. ``` ### Part 3 — Test and Harden the Component Describe tests for duplicate task IDs, priority and timestamp ties, an exhausted queue, and concurrent callers. Explain what changes if task execution itself can fail. #### What This Part Should Cover - A test in which the highest-ranked record is stale and selection must continue. - Deterministic outcomes for complete ties. - Linearization or locking boundaries for concurrent operations. - A deliberate policy for retrying a failed execution versus treating the ID as completed. ```hint Define the commit point Correct concurrency and retry behavior depend on the exact moment at which the task ID changes from eligible to executed. ``` ### What a Strong Answer Covers - An explicit contract for every ambiguity in priority, timestamps, retries, and duplicate IDs. - A priority queue plus task-level execution state with correct lazy deletion. - Complexity analysis that accounts for skipped records rather than calling every execution constant time. - Focused tests and a credible concurrency boundary. ### Follow-up Questions 1. How would you support changing the priority of an existing task ID? 2. How could executed-task state be bounded if task IDs are never reused? 3. What persistent records would be required to recover after a process crash? 4. How would the API change if every occurrence, rather than every task ID, must execute exactly once?