Nio·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Nio SWE interview had at least one solid algorithms question that required more than just knowing the answer. You had to actually talk through the tradeoffs, which I wasn't fully prepared for.

Questions Asked (1)

Given an unsorted array of integers and a value k, find the k-th smallest element in expected O(n) time without sorting the whole array. Be ready to discuss pivot selection, average vs worst-case complexity, and the median-of-medians approach if pushed.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I knew Quickselect going in but fumbled the complexity conversation.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Lead with the Quickselect algorithm as the primary solution, explaining how it leverages the partition step from Quicksort to narrow the search to one subarray rather than sorting the entire input. Walk through the algorithm with a small example, then proactively address pivot selection strategies and complexity trade-offs before the interviewer has to ask.

Pro tip: Volunteering the median-of-medians algorithm unprompted — and honestly acknowledging its O(n) worst-case guarantee comes at the cost of a larger constant factor making it slower in practice — signals the kind of engineering maturity Nio looks for in systems-level thinking.

1. State the Core Idea

Introduce Quickselect: partition the array around a pivot so elements smaller than the pivot are on the left and larger on the right, then recurse only into the partition that contains the k-th index. This avoids sorting the irrelevant half.

2. Walk Through a Concrete Example

Use a small array (e.g., [7, 2, 5, 1, 9, 3], k=3) to illustrate one partition step, showing how the pivot's final index determines which subarray to recurse into. This grounds the explanation and demonstrates clarity of thought.

3. Discuss Pivot Selection & Complexity

Explain that random pivot selection yields O(n) expected time but O(n²) worst-case (e.g., already-sorted input with always picking the smallest element). Contrast this with median-of-medians, which guarantees O(n) worst-case by selecting a pivot within the true median range.

4. Address Median-of-Medians Trade-offs

Describe the median-of-medians approach: divide into groups of 5, find each group's median, then recursively find the median of those medians as the pivot. Acknowledge the higher constant factor (~10x) makes it slower in practice despite the superior asymptotic guarantee.

5. Mention Practical Alternatives & Edge Cases

Briefly note alternatives like a min-heap of size k (O(n log k)) or introselect (used in C++ nth_element), and handle edge cases such as duplicate elements, k out of bounds, and single-element arrays.

Key Points to Mention

Quickselect algorithm: partition-based selection that recurses into only one subarray, achieving O(n) expected time and O(1) extra space (in-place variant)
Pivot selection strategies: random pivot for practical O(n) average case vs. deterministic median-of-medians for O(n) worst-case guarantee
Worst-case O(n²) scenario for naive Quickselect and why randomization mitigates it in expectation
Median-of-medians: groups of 5, recursive median finding, and the mathematical proof that it guarantees at least 30% of elements on each side of the pivot
Practical trade-offs: introselect (hybrid approach used in production), heap-based O(n log k) alternative when k is very small
Handling duplicates: three-way partitioning (Dutch National Flag) to correctly handle arrays with repeated values

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.