Andela assessment: Question 3


Mary is a famous shopkeeper who sells n items in her shop. She assigns each item a unique popularity rating in the inclusive range from 1 to n.

The shop only has one shelf, so the items are displayed array-style in a single row spanning from left to right in a random order. She wants to rearrange the items on the shelf by decreasing popularity rating such that the rating for the i item is always greater than the popularity rating of the (i + 1) item. Mary can swap any two items, i and j, in a single operation.




ratings: Array (of Integers) – an array of numbers indicating the popularity rating of each item on the shelf.Return Value

Integer – denotes the minimum number of swap operations Mary must perform to order all n items by decreasing popularity rating.Constraints

n = number of items in ratings array

each rating value (arri) will be unique

1 ≤ n ≤ 2 × 105

1 ≤ arri ≤ n


ratingsReturn Value
Example #1[3,1,2]1
Example #2[3,1,2,4]2

My solution

def minimum_swaps(ratings):
  #sorting in descending order
  n = len(ratings)

  #new array with the enumerated value, position
  arrpos = list(enumerate(ratings)) 

  #sort the array
  arrpos.sort(reverse = True, key = lambda it:it[1]) 

  vis = {k:False for k in range(n)}
  #initialiaze the value of swapsa
  swaps = 0

  #loop through checking if already visited or if value doesnt need to be swapped
  for i in range(n):
    if vis[i] or arrpos[i][0] == i: 
     #finding the number of nodes in the cycle
    size = 0
    j = i
    while not vis[j]:
      vis[j] = True
      j = arrpos[j][0] 
      size += 1
     #adding no of nodes to swap
    if size > 0: 
      swaps += (size - 1) 
  return swaps

My tests

import unittest
 class Test(unittest.TestCase):
   def test_minimum_swaps_should_handle_single_swap(self):
     self.assertEqual(minimum_swaps([3,1,2]), 1)
   def test_minimum_swaps_should_handle_multiple_swaps(self):
     self.assertEqual(minimum_swaps([3,1,2,4]), 2)
   def test_minimum_swaps_already_sorted(self):
     self.assertEqual(minimuma_swaps([4,3,2,1]), 0)
   def test_minimum_swaps_should_handle_completely_unsorted(self):
     self.assertEqual(minimum_swaps([1,2,3,4]), 2)
   def test_minimum_swaps_should_handle_one_item(self):
     self.assertEqual(minimum_swaps([1]), 0)

Leave a Reply

Your email address will not be published. Required fields are marked *