LinkedIn·AI Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

May 2026Remote

Summary

LinkedIn AI Engineer interview with a math-heavy coding question that felt more like a stats exam than a typical algo round. One question, but it had layers.

Questions Asked (1)

Given a 1D array of coordinates, find the point c that minimizes the total sum of absolute distances to all points. Prove mathematically that the optimal c is the median, then implement it efficiently.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I knew the answer was the median from some vague memory but actually proving it on the spot was a different story.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, restate the problem and clarify that the objective is to minimize the sum of absolute deviations. Then, prove that the median minimizes this sum by using the subgradient method or a pairwise exchange argument. Finally, implement an efficient solution using quickselect (or sorting) to find the median in O(n) expected time.

Pro tip: Mention that for even-sized arrays, any point between the two middle elements is optimal, and that the median minimizes L1 loss, which is more robust to outliers than the mean (L2 loss).

1. Clarify and Restate

Confirm the problem: given a 1D array of coordinates, find c that minimizes f(c) = sum_i |x_i - c|. Note that the points can be unsorted and may contain duplicates.

2. Mathematical Proof

Prove that the median minimizes f(c). Use the subgradient method: f'(c) = (# points < c) - (# points > c), and set to zero. Alternatively, use a pairwise exchange argument: if c is not a median, moving it toward the median reduces the sum.

3. Algorithm Design

Choose an efficient algorithm to find the median. Options: sort the array (O(n log n)) or use quickselect (O(n) expected). For large n, quickselect is preferred. Handle even n by picking either middle element.

4. Implementation

Implement the chosen algorithm. For quickselect, write a partition function and recursively select the k-th element. Ensure it handles edge cases (empty array, single element, duplicates).

5. Complexity and Trade-offs

Analyze time and space complexity: O(n) expected time for quickselect, O(1) extra space if in-place. Discuss trade-offs: sorting is simpler but slower; quickselect has worst-case O(n^2) unless using median-of-medians.

Key Points to Mention

The objective function is convex, and the median is a minimizer.
Subgradient of f(c) is the number of points less than c minus the number greater than c.
For even n, any c between the two middle values is optimal.
Quickselect gives O(n) expected time, while sorting gives O(n log n).
The median minimizes L1 loss, which is robust to outliers compared to the mean (L2 loss).
Edge cases: empty array (no solution), single element (c = that element), duplicates (median still works).

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