3 ms·
My understanding of bnoordhuis' proposed was that the elements of the hash table would be students, rather than lists of students.
by anonymoushn 16y ago
My understanding of bnoordhuis' proposed was that the elements of the hash table would be students, rather than lists of students.
- bnoordhuis 16y agoThe 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 16y agoThanks, 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.