Create a function that takes in a list of unsorted prices and a maximum possible price value, and return a sorted list of prices

By Subham, a year ago
  • Bookmark
1

Create a function that takes in a list of unsorted prices (integers) and a maximum possible price value, and return a sorted list of prices

Requirements

  • Your function should be able to perform this in less than O(nlogn) time.

Interview questions
Data structure
Python
1 Answer
0

Solution :

We can actually solve this problem by using a counting sort. Basically a counting sort works well when you know the range of integer values you will have ahead of time.


An implementation is here below :.


def solution(unsorted_prices,max_price):
   
  # list of 0s at indices 0 to max_price
  prices_to_counts = [0]* (max_price+1)
   
  # populate prices
  for price in unsorted_prices:
    prices_to_counts[price] +=1
     
  # populate final sorted prices
  sorted_prices = []
   
  # For each price in prices_to_counts
  for price,count in enumerate(prices_to_counts):
     
    # for the number of times the element occurs
    for time in range(count):
       
      # add it to the sorted price list
      sorted_prices.append(price)
       
  return sorted_prices


solution([4,6,2,7,3,8,9],9)
[2, 3, 4, 6, 7, 8, 9]


https://en.wikipedia.org/wiki/Counting_sort -- Read the wikipedia article for a full break down

– Neha Apr 23, 2021 at 5:22 PM

Your Answer

Webinars

More webinars

Related Discussions

Running random forest algorithm with one variable

View More