Apple·Software Engineer·Technical Phone Screen·Senior

Senior

May 2026

Summary

Apple SWE interview with a tricky oracle-based median problem. No standard library calls, no direct access to the data, just a query interface and your brain. Made me rethink how much I rely on just sorting things.

Questions Asked (1)

You have N numbers you can't see directly. You can query any value x and get back how many of the N numbers are greater than x and how many are less than x. Find the median. Also discuss how query count scales, how to deal with duplicates, and what changes when N is even.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

This one took me a minute to even understand what they were asking.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Treat the query as an oracle that returns the rank of x, enabling binary search over the value domain to find the median. Discuss how to handle duplicates by finding the smallest value with count_less ≥ target, and for even N, define the median as the average of the two middle values (or lower median) and adjust the search accordingly. Analyze query complexity in terms of the value range and N, and mention optimizations like interpolation search if distribution is known.

Pro tip: Clarify upfront whether the numbers are integers or reals, and whether the value range is known; this determines if binary search is over a finite domain or requires a different approach. Also, explicitly state the median definition for even N (average of two middle values) and how to retrieve both middle values efficiently.

1. Understand the query and define median

Explain that a query returns (less, greater) counts, so you can compute the rank of x. Define median: for odd N, the (N+1)/2-th smallest; for even N, typically the average of the N/2-th and (N/2+1)-th smallest (or lower median).

2. Binary search over value domain

If the value range [min, max] is known, binary search for the smallest x such that count_less(x) ≥ target rank. Use the query to adjust low/high based on whether count_less(x) < target.

3. Handle duplicates and exact median

Duplicates mean multiple equal values; the condition count_less(x) ≥ target finds the smallest value with enough elements less than it, which is the median value. For even N, find both middle values by searching for ranks N/2 and N/2+1, then average if needed.

4. Analyze query complexity

Binary search takes O(log R) queries where R is the value range size (if discrete). If values are real, use a tolerance-based approach or interpolation search for O(log log N) expected queries under uniform distribution.

5. Discuss trade-offs and edge cases

Mention that if the range is unknown, you can first find min and max with queries, or use a selection algorithm. Also address that for even N, you might need two searches, doubling queries, but can optimize by reusing information.

Key Points to Mention

The query returns counts of less and greater, so you can compute the rank of any x.
Binary search over the value domain to find the smallest x with count_less(x) ≥ target rank.
Duplicates are handled naturally because the condition finds the smallest value with enough elements less than it.
For even N, median is the average of the two middle values; find both by searching for ranks N/2 and N/2+1.
Query complexity is O(log R) for discrete range R, or O(log log N) with interpolation search under uniform distribution.
If the value range is unknown, first determine min and max with queries or use a selection algorithm like quickselect with queries.

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