LinkedIn·AI Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

May 2026Remote

Summary

LinkedIn AI Engineer interview with a coding problem that looks like a simple math puzzle but actually requires you to know your median proofs cold. One question, pretty focused session.

Questions Asked (1)

N people are standing at various positions on a 1-D number line. Find a meeting point that minimizes the total sum of absolute distances from each person to that point. Prove why your chosen point is optimal and implement the solution.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I knew the answer was the median basically immediately, but the proof part is where I fumbled a bit.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Recognize that the optimal meeting point is the median of the positions, which minimizes the sum of absolute deviations. Prove optimality by showing that moving away from the median increases the total distance, using a pairwise exchange argument. Implement by sorting the array and selecting the middle element (or any point between the two middle elements for even N).

Pro tip: Mention that the median is robust to outliers and that the solution runs in O(N log N) due to sorting, but can be O(N) with quickselect. Also, note that for even N, any point between the two middle values yields the same minimum sum, which is a common edge case.

1. Understand the problem and identify the objective

Restate the problem: minimize sum of absolute distances. Clarify that the point can be anywhere on the line, not necessarily at a person's position.

2. Derive the optimal point

Show that the median minimizes the sum of absolute deviations. For odd N, it's the middle element; for even N, any point between the two middle elements.

3. Prove optimality

Use a pairwise argument: if you move away from the median, the number of points on the side you move towards increases, increasing the total distance. Alternatively, use the derivative of the sum of absolute values.

4. Implement the solution

Sort the array and return the middle element (or the average of the two middle elements for even N, but any point in between works). Discuss time complexity O(N log N) and space O(1) if sorting in place.

5. Discuss trade-offs and extensions

Mention alternative algorithms like quickselect for O(N) average time. Discuss if the problem changes with weighted points or different distance metrics.

Key Points to Mention

Median minimizes sum of absolute deviations
Proof using pairwise exchange or derivative
Odd vs even N handling
Time complexity: O(N log N) sorting, O(N) quickselect
Space complexity: O(1) if in-place
Robustness to outliers compared to mean
Extensions: weighted median, Manhattan distance in higher dimensions

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