Katkat
Back

Return Integers in Descending Ranked Order

YelpData Scientist · Technical Screen
EasyData ScientistTechnical ScreenCoding & Algorithms

Last updated

This problem tests the ability to manipulate lists and sort data while maintaining the relative order of duplicate elements using common programming patterns.

Problem Statement

Given an unsorted list of integers, return a new list containing all elements sorted in descending order. If the list contains duplicate integers, they must all be preserved in the final output and appear adjacent to each other.

Function Signature

def get_descending_ranked(nums: list[int]) -> list[int]:

Constraints

  • 0 <= len(nums) <= 10^5
  • -10^9 <= nums[i] <= 10^9

Examples

Example 1: Input: [3, 1, 4, 1, 5] Output: [5, 4, 3, 1, 1]

Example 2: Input: [10, 10, 8, 20] Output: [20, 10, 10, 8]

Considerations

  • How does your solution handle an empty input list?
  • What is the time complexity of your chosen sorting approach?
  • Can you achieve this without using built-in sorting functions if required by the interviewer?

Hints

Hint 1

Consider using the built-in sorting method provided by your language, which typically implements Timsort or Quicksort.

Hint 2

If you need to sort in descending order using a standard sorting function, you can either reverse the output of an ascending sort or specify a reverse flag parameter.

Hint 3

If you were asked to implement a custom sort, consider the time complexity of bubble sort versus more efficient algorithms like merge sort.

Follow-up questions

  • What is the time complexity of your solution, and can you explain why the language's built-in sort performs at that complexity?
  • How would your approach change if you were required to return only the unique integers in descending order?
  • Suppose the input list is extremely large and does not fit into memory; how would you modify your approach to handle this using an external sorting strategy?