Katkat
Back

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

GoogleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

Implement quicksort and a binary search tree from scratch and explain how each works internally, including partitioning, pivot choice, insertion, search and deletion. Tests correctness invariants, best, average and worst-case complexity, duplicate and sorted inputs, alternative approaches, and how library implementations differ.

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.

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.

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

Hints

Hint 1

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 2

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.

Hint 3

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.

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?