The Placement Fixer

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L4
Asked in
Citadel

Problem

Given a list of integers in range 1..n with possible duplicates (where n = len(list)), return a sorted version using cyclic sort logic (each distinct value i is placed at index i-1). If duplicates exist, the exact algorithmic behavior is: return the sorted list for the simple no-duplicate case. With duplicates, return the sorted list as well.

Each value belongs in exactly one spot.

Example 1

Input:

nums = [1,2,3,4,5]

Output:

[1,2,3,4,5]

Example 2

Input:

nums = [1,2,3,4,5,6]

Output:

[1,2,3,4,5,6]

Worked solution and explanation

Why this problem exists in real interviews

This tests the cyclic sort algorithm, an O(n) in-place sorting technique for arrays where values are within a known range. Interviewers use it to check whether candidates know this niche but powerful pattern for range-bounded data.

Break down the requirements

Step 1: Iterate through the array

For each index, check if the value at that index is in its correct position (value v at index v-1).

Step 2: Swap until correct or duplicate

While nums[i] != i + 1 and the target position does not already hold the correct value, swap.

Step 3: Handle duplicates

If nums[i] == nums[nums[i]-1], a duplicate is in the way. Move on to the next index.

The solution

Cyclic sort with in-place swapping
def cyclic_sort(nums):
    i = 0
    while i < len(nums):
        correct_idx = nums[i] - 1
        if nums[i] != nums[correct_idx]:
            nums[i], nums[correct_idx] = nums[correct_idx], nums[i]
        else:
            i += 1
    return nums

Common follow-up questions