Implement a binary min-heap and use it to order courses with prerequisites

In one coding round of about 30 minutes, you are asked to write a heap yourself and then to use it in a variant of the course-scheduling problem. ### Constraints and Clarifications - Do not use `heapq`, `queue.PriorityQueue` or any other priority-queue library, and do not sort the whole list on each operation. - Heap elements are mutually comparable values, such as integers or tuples of integers. - The exact twist of the course-scheduling variant was not reported. This version makes the order unique by always taking the smallest-numbered available course; ask the interviewer which variant they intend. ### Clarifying Questions - Should `pop` and `peek` on an empty heap raise an error or return a sentinel value? - Besides push, pop and peek, does the heap need other operations, such as removing an arbitrary element or changing a priority? - Must Part 2 use the heap from Part 1? ### Part 1 — A binary min-heap Implement a `MinHeap` class with: - `push(x)`: insert `x`; - `pop()`: remove and return the smallest element; - `peek()`: return the smallest element without removing it; - `__len__()`: the number of elements; - a constructor that accepts an existing list of elements and builds the heap in linear time. ```hint Tree in a list Store the elements in a flat list and work out the index arithmetic that connects a position to its parent and to its children. ``` ```hint Repair one path After a single insertion or removal, think about which part of the structure can be out of order and in which direction it needs repairing. ``` #### What This Part Should Cover - The array layout and the parent and child index arithmetic - Restoring order after push and after pop, including which child to swap with - Linear-time construction and the argument for why it is linear - Behavior on an empty heap, a single element and duplicate values ### Part 2 — Ordering courses with prerequisites There are `n` courses labeled `0` to `n - 1`, and a list of pairs `[a, b]`, each meaning that course `b` must be completed before course `a`. Courses are taken one at a time. Return an order in which all `n` courses can be completed. Whenever more than one course has all its prerequisites completed, take the smallest-numbered one next. If circular prerequisites make it impossible to complete every course, return an empty list. Use your `MinHeap` from Part 1. For example, with `n = 3` and prerequisites `[[0, 1]]`, courses `1` and `2` are available at the start. Taking `1` makes `0` available, and `0` is now the smallest available course, so the answer is `[1, 0, 2]`. ```hint What makes a course available Think about what has to be true of a course at the moment it becomes available, and what changes for the other courses when you finish one. ``` ```hint Spotting the impossible case Think about what you will observe at the end of your process if some courses can never become available. ``` #### Clarifying Questions for this Part - Can the list contain duplicate pairs, or a course that lists itself as its own prerequisite? - Are all labels guaranteed to lie between `0` and `n - 1`? #### What This Part Should Cover - Representing the prerequisites and tracking when each course becomes available - Using the heap to choose the next course so that the order is unique - Detecting circular prerequisites and returning the empty list - Time and space complexity in terms of courses and prerequisite pairs ### What a Strong Answer Covers - A heap that is correct at its boundaries and is reused in Part 2 only through its public interface - Correct complexity for each heap operation, for construction and for the course ordering - Malformed input handled deliberately: duplicate pairs, self-prerequisites and out-of-range labels - Working code within the time box, checked with a short dry run that exercises the smallest-first rule ### Follow-up Questions - Any number of courses whose prerequisites are complete can be taken in the same term. What is the minimum number of terms? - How would you add an operation that changes the priority of an element already in the heap, or removes it? - What changes if the largest-numbered available course must be taken first? - When the prerequisites are circular, how would you report one cycle instead of returning an empty list?