Coding questions · Uber
Sort by squares and find k-th smallest
This question evaluates array manipulation, ordering by derived keys (squares/absolute values), order-statistics reasoning, and algorithmic complexity analysis within the Coding & Algorithms domain.
Given a nondecreasing sorted array of integers nums, do the following:
- Reorder the original elements by increasing square value (equivalently, by absolute value). For elements whose squares are equal, any order is acceptable. Target time complexity strictly better than O(N log N); aim for O(N) time. Example: nums = [-3, -2, 0, 1, 2, 5] -> [0, 1, -2, 2, -3, 5].
- Follow-up: Given the same nums and an integer k (1-indexed), return the k-th element in the order induced by sorting by square value, without fully materializing that order. You must not explicitly sort by squares; target O(log N) time. Clearly state your algorithm, complexity, and any assumptions.
Sort Values by Increasing Square
Given a sorted array, return original values ordered by increasing square value.
Constraints
- nums is sorted non-decreasing
Examples
Example 1
Input: ([-3, -2, 0, 1, 2, 5],)
Output: [0, 1, -2, 2, -3, 5]
Explanation: Prompt example up to tie order.
Example 2
Input: ([-4, -1, 0, 3, 10],)
Output: [0, -1, 3, -4, 10]
Explanation: Mixed signs.
Hints
- Compare absolute values from both ends and fill from the back/front.
k-th Value by Increasing Square
Return the k-th original value in the order induced by sorting by square value.
Constraints
- k is 1-indexed
Examples
Example 1
Input: ([-3, -2, 0, 1, 2, 5], 1)
Output: 0
Explanation: Smallest square.
Example 2
Input: ([-3, -2, 0, 1, 2, 5], 4)
Output: 2
Explanation: Tie order follows the deterministic two-pointer order.
Hints
- This exact-match version uses the same deterministic two-pointer order as the full ordering problem.