Sort by squares and find k-th smallest

Q: Sort by squares and find k-th smallest

This is a Coding & Algorithms interview question from Uber for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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 by squares and find k-th smallest

Comments (0)