InterviewDB
Question
Absolute Sort: Sort an Array by Absolute Value with Tie-Breaking by Original Value
phone
Question Details
Problem
Given an array of integers (may include negatives), sort it by absolute value in ascending order. For elements with the same absolute value, the negative number should come before the positive.
python
def absolute_sort(arr: list[int]) -> list[int]:
pass
Example:
arr = [-3, 1, -1, 2, -2, 3, 0]
-> [0, -1, 1, -2, 2, -3, 3]
arr = [5, -5, 3, -3]
-> [-3, 3, -5, 5]
arr = [4, -4, 4]
-> [-4, 4, 4]
Follow-ups
- Write the one-line
keyfunction in Python that captures both the absolute value and the tie-breaking rule. - Is Python's
sorted()stable? How does stability affect the correctness of a two-pass sorting approach here? - How would you implement this in C++ using a custom comparator
passed to std::sort?
4. What is the time complexity, and can you do better than O(n log n) if you know the range of values is bounded (e.g., -1000 to 1000)?
Full Details
Problem
Given an array of integers (may include negatives), sort it by absolute value in ascending order. For elements with the same absolute value, the negative number should come before the positive.
python
def absolute_sort(arr: list[int]) -> list[int]:
pass
Example:
arr = [-3, 1, -1, 2, -2, 3, 0]
-> [0, -1, 1, -2, 2, -3, 3]
arr = [5, -5, 3, -3]
-> [-3, 3, -5, 5]
arr = [4, -4, 4]
-> [-4, 4, 4]
Follow-ups
- Write the one-line
keyfunction in Python that captures both the absolute value and the tie-breaking rule. - Is Python's
sorted()stable? How does stability affect the correctness of a two-pass sorting approach here? - How would you implement this in C++ using a custom comparator
passed to std::sort?
4. What is the time complexity, and can you do better than O(n log n) if you know the range of values is bounded (e.g., -1000 to 1000)?
Free preview. Unlock all questions →
Topics
Coding
Onsite
Phone