Implement quicksort and a binary search tree, and explain how each works internally

During an algorithm-focused technical round, the interviewer went beyond the coding problem and asked how the algorithms and data structures used in the solution work underneath, for example how quicksort is implemented and how a binary search tree is implemented. The round expected more than one approach, precise answers about implementation details, and readable code. Implement both from scratch, without library sorting or tree types, and explain each one. ### Clarifying Questions - Should quicksort sort in place, or may it return a new list? Does it need to be stable? - Can the input contain many duplicates, or arrive already sorted or reverse sorted? - Which tree operations are required: insert, search and delete only, or also in-order traversal, minimum, maximum and size? - Are duplicate keys allowed in the tree, and if so, where do they go? - Is a plain binary search tree enough, with its worst case explained, or must the tree stay balanced? ### Part 1 — Quicksort Implement quicksort for a list of integers. Explain how partitioning works and why the algorithm is correct; give its best, average and worst-case running time and its extra space; explain how the choice of pivot affects them; and describe an alternative partition scheme and when it behaves differently. ```hint What partition promises State exactly what is true of the subarray after one partition step, and check that every iteration of your loop keeps that statement true, including when an element equals the pivot. ``` ```hint Where the worst case comes from Run your implementation by hand on an already sorted array and on an array of identical values, and watch how the subarray sizes shrink. ``` #### What This Part Should Cover - A correct partition with its invariant, and the recursion around it - Best, average and worst-case time, and the recursion depth with a way to bound it - Pivot selection, duplicate handling, and a comparison of partition schemes - Stability and in-place behavior ### Part 2 — Binary search tree Implement a binary search tree of integer keys with insert, search and delete, plus an in-order traversal. Explain the ordering invariant, the cost of each operation, what happens to that cost when keys are inserted in sorted order, and the ways to delete a node that has two children. ```hint The hard case of delete Removing a node with no children or one child is a local change. For a node with two children, ask which other key could take its place without breaking the ordering, and where that key lives. ``` #### What This Part Should Cover - The node structure, the ordering invariant and a duplicate-key policy - Insert, search and delete, including the two-children case and deleting the root - Cost in terms of tree height, the degenerate case, and how self-balancing trees bound the height - A clean class interface that separates public operations from private helpers ### What a Strong Answer Covers - Working, readable code for both structures, written without library helpers - Invariants stated precisely enough to justify correctness - Complexity with best, average and worst cases distinguished, including the space used by recursion - More than one approach for each, with the conditions under which each one is better - Edge cases: empty input, a single element, duplicates, sorted input, deleting the root, deleting a missing key - Awareness of how library sorts and ordered containers differ from the textbook versions, and why ### Follow-up Questions - Your language's built-in sort is not plain quicksort. What does it typically use, and why? - How can quicksort's worst case be made O(n log n) without giving up sorting in place? - How would you find the k-th smallest element of an unsorted array using the partition step, and what does it cost? - Standard-library ordered maps are usually red-black trees rather than plain binary search trees. What does that buy, and what does a red-black tree add to each node?