The Forbidden Sorter

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
L3
Asked in
Udemy

Problem

Given a list of single characters, return the list sorted in ascending alphabetical order. Do not use sort() or sorted(); implement your own sorting algorithm.

Put the letters in order without the obvious tool.

Example 1

Input:

chars = ["c","a","b"]

Output:

["a","b","c"]

Example 2

Input:

chars = ["z","m","a","z"]

Output:

["a","m","z","z"]

Worked solution and explanation

Why this problem exists in real interviews

This tests whether a candidate can implement a sorting algorithm from scratch. It probes understanding of comparison-based sorting mechanics and the ability to translate algorithmic logic into working code.

Break down the requirements

Step 1: Choose a sorting algorithm

Bubble sort, insertion sort, or selection sort are all appropriate for this problem since simplicity matters more than optimal performance.

Step 2: Compare characters using standard operators

Python characters compare by their Unicode code points, which gives alphabetical order for lowercase letters.

Step 3: Return the sorted list

The result should be a new list in alphabetical order.

The solution

Insertion sort for character ordering
def sort_chars(chars: list) -> list:
    result = list(chars)
    for i in range(1, len(result)):
        key = result[i]
        j = i - 1
        while j >= 0 and result[j] > key:
            result[j + 1] = result[j]
            j -= 1
        result[j + 1] = key
    return result

Common follow-up questions