"Is that really the gatekeeper we want?" Yes, I think so? I mean implementing a hash table in C is really easy. What is there to "forget"? If you can't do it, either you don't know what a hash table is, or you don't know how to program in C.

enum { table_size = 1024 };
typedef struct item { int k, v, full; } item;
static item table[table_size];

void put(item kv)
{
size_t orig = kv.k % table_size; // dumbest possible hash function
size_t b = (orig + 1) % table_size;
// use linear probing for collisions
while (table[b].full && b != orig) b = (b + 1) % table_size;
if (b == orig) abort(); // table full
table[b] = kv;
table[b].full = 1;
}

item *get(int k)
{
size_t orig = k % table_size;
size_t b = (orig + 1) % table_size;
while (table[b].full && table[b].k != k && b != orig) {
b = (b + 1) % table_size;
}
return (table[b].full && table[b].k == k) ? &table[b] : NULL;
}

I haven't tested that (just as I wouldn't in a whiteboard interview) so I don't know if it works. I did briefly skim the article we're talking about, but I concluded I didn't have anything to learn from it, so I didn't read it. I found a bunch of bugs in my implementation as I was writing it. And of course it's a pretty dumb hash table: linear probing is very suboptimal, it uses a statically-allocated non-resizable hash table, it's specialized for a certain type of keys, and so on.

But are you saying you can't even do that? Probably it would be bad to hire you for a C programming job, then, unless it was an entry-level position for you to learn C in.

⁂

Evidently the above comment took me 15 minutes to write. Oh, and now I see another bug or at least lacuna: if you try to update the value of an existing key, it doesn't fail, but it also doesn't update, instead adding a new entry that will never be read. And then I did write a minimal smoke test and run it, and unsurprisingly, it does work:

int main()
{
put((item) { 4, 7 });
put((item) { 1028, 9 });
put((item) { 3, 25 });
printf("%d %d %d %p %p\n", get(4)->v, get(1028)->v, get(3)->v, get(5), get(3));
return 0;
}

Writing the test and the above additional commentary, and running the test, took another 8 minutes.

Oh, and there's another bug where it will loop infinitely when the hash table is full and the key is negative. (Actually it invokes UB but typically the result will just be an infinite loop.)

If it takes you 60 or 100 minutes to write this, or to write something better, maybe you still know C and know what hash tables are. But if you throw up your hands and say "I don't remember, it's been a long time since I was in school"? Either you don't know C, or you don't know what a hash table is, which probably means you've never written anything in C but toy programs. (This is a toy program, of course, but many toy programs in C don't need hash tables.)

The compilable and fixed toy program in question is at http://canonical.org/~kragen/sw/dev3/dumbhash.c if you want to probe it for bugs.

It occurs to me that you might have been talking about something that isn't a C programming job. For example, we might be talking about a job programming an HTML database front-end in Python using Django. And of course it would be silly to reject someone for a job like that because they didn't know C, unless they claimed to know C on their résumé. And it's totally reasonable for a Python programmer, or a Python/Perl/JS/bash programmer, to not understand hash tables.