Comment by bnoordhuis

The language was C and my solution (adapted to the article) was something like this:

    // TODO enforce! see also: soylent green
    #define MAX_AGE 100

    struct student {
        const char *name;
        int age;
    };

    struct students {
        long n_students;
        struct student *students[10e6];
    };

    struct students all_students[MAX_AGE];

    void insert(struct student *s) {
        struct students *ss = &all_students[s->age];
        ss->students[ss->n_students++] = s;
    }

So O(1) insertion and O(n) post-processing to stitch the arrays together again. Seems like pretty acceptable performance to me but the Google guy thought otherwise, the answer he was looking for was (probably) a counting sort.

I tried to argue that my solution was a fair bit faster and simpler to boot. That's probably why I didn't get a follow-up interview - no-one likes a smart arse. :-)