[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. :-)

[anonymoushn]

Thanks, I'm sorry I misunderstood your brief description.

There's no hash table here, this is just bucket sort. I don't think anyone should care about the difference between counting sort and bucket sort, though. The only thing I would mind about this is that it allocates 100x the necessary memory, but I'm sure you wouldn't actually do that when it matters.