Mercor Software Engineer Interview Experience — 25-Minute Screen, Sorting Complexity and Cache Review, Rejected

Sorting Complexity

They asked me to come up with a sorting algorithm that is as inefficient as possible and explain its time complexity. One idea is to enumerate all permutations of n distinct elements and check one by one whether each is sorted. There are n! permutations in total and each check takes O(n), so the worst-case time complexity can reach O(n × n!). Strictly speaking there is no single slowest sorting algorithm, because you can always add some useless operations to make it even slower.

Python Cache Code Review

They gave me a piece of Python code with a cache and asked me to analyze what was wrong with it. The original code was:

from library import expensive_computation
cache = {}
def compute(x):
    if x in cache
        return cache[x]
    y = expensive_computation(x)
    cache[x] = y
    return y

I felt I answered pretty well. The whole thing was 25 minutes and only 10 of those went to the technical discussion, and then for some reason I got rejected afterwards.