The Long Way Around

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

Domain
Python
Difficulty
easy
Seniority
L4
Asked in
Athenahealth

Problem

A batch job runs in a restricted runtime where the ordering built-ins are gone: no sorted(), no list.sort(), and no min() or max() to reach for. Given a list of integers nums, return them ordered smallest to largest.

Anyone can call the function. Order it by hand.

Example

Input:

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

Output:

[1,1,3,4,5]

Worked solution and explanation

What this really is

Strip the costume and this is 'can you order a list when every ordering built-in is taken away.' sorted(), list.sort(), min(), and max() are all off the table, so you cannot even lean on min() to pluck the next smallest each pass. The whole problem is the loop you would normally never have to write: walk the list, and for each new element slide it left past everything larger than it. Anyone can name insertion sort. The trick lives in the inner loop boundary: you have to test j >= 0 BEFORE you touch nums[j], or you walk off the front of the list. Get that order backwards and it is an IndexError on the first element that belongs at position zero.

How to build it

Step 1: Pick the simplest sort you can defend

Insertion sort is the cleanest choice here: it is a handful of lines, sorts in place, and degrades gracefully. Selection sort works too, but with min() gone you would have to hand-scan for the smallest on every pass; insertion sort keeps the one comparison inline and finishes in a single pass over data that is already close to ordered.

Step 2: Hold the left side sorted

Everything to the left of the current index stays sorted at all times. Take the next element, remember it in key, and shift the sorted neighbors one slot to the right until you find the gap where key belongs. That invariant is the thing an interviewer actually wants to hear you say out loud.

Step 3: Land the element and return

Guard the inner loop with j >= 0 and nums[j] > key. Short-circuit evaluation means j >= 0 is checked first, so you never index a negative-then-invalid position. Drop key into nums[j + 1] once the loop stops. The list is mutated in place, so return nums.

The solution

Insertion sort with in-place shifting
def manual_sort(nums):
    for i in range(1, len(nums)):
        key = nums[i]
        j = i - 1
        while j >= 0 and nums[j] > key:
            nums[j + 1] = nums[j]
            j -= 1
        nums[j + 1] = key
    return nums

Common follow-up questions