What if this became the new “invert a binary tree on a whiteboard”?
I did. Works very well as an interview question.
The K&R C Programming Language book has nearly the same example (although I recall it using linked-lists for hash collisions and not probing).
I would be mildly suspicious of anyone claiming to have a recent CS degree who wasn't familiar with the ideas.
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;
}
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;
}
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.
A merge sort isn't the fastest sort but it's pretty easy for anyone to implement. Something like a timsort is a bit more complex but is what a lot of languages use now-a-days.
Hash tables are in the same boat. A basic hashtable is pretty easy to implement. It's only when you start looking at things like ideal item placement and optimal filling that things start to get more complex.
1. It doesn't update—attempts to change the value associated with an existing key are silently ignored, although they do consume buckets.
2. It loops forever if the table is full and the key it was looking for is negative, because that invokes conversion of a negative signed value to an unsigned value, which I think is UB in C.
Maybe it has more bugs I haven't found yet.
Additionally the reason it took me 15 minutes to write 21 lines of code was that I changed a bunch of things in midstream, before posting the comment:
1. At first there was no "full" field in the hash table bucket, so there was no way to distinguish full buckets from empty buckets.
2. And then when I added it, I added it as "dead", with the opposite Boolean sense of "full", so I would have needed a separate initialization routine (to set all the dead fields to something nonzero). Instead I swapped the sense.
3. I was trying to detect the case where we'd looped back around to our starting point, indicating that the table was full and the search was unsuccessful, and I realized that the condition I wanted was not b == orig, which would always fail on the first iteration, but (b + 1) % table_size == orig. But doing that on every iteration seemed obscene, so I incremented b (mod table_size) to start out with instead.
4. At some point I think I realized I'd forgotten to set the .full field on newly inserted items.
5. Also I realized I'd forgotten to test the table[b].k == k condition in `get` as well, which would have made every search unsuccessful.
So I think it's reasonable to say that even a pretty limited hash-table implementation has plenty of opportunities to write bugs, more than I expected. But maybe I'm just running on low blood sugar this afternoon or something.
let rec getp k = function `Empty -> None
| `Node(k1, v1, x, y) ->
if k1 = k then Some v1 else getp k (if k < k1 then x else y)
and putp k v = function `Empty -> `Node(k, v, `Empty, `Empty)
| `Node(k1, v1, x, y) when k1 = k -> `Node(k, v, x, y)
| `Node(k1, v1, x, y) -> if k < k1 then `Node(k1, v1, putp k v x, y)
else `Node(k1, v1, x, putp k v y)
With four more lines of code it's also a sorting algorithm:
and dictofp = function [] -> `Empty | (k, v)::xs -> putp k v (dictofp xs)
and itemsp d = let rec iter d tl = match d with `Empty -> tl
| `Node(k, v, x, y) -> iter x ((k, v) :: iter y tl)
in iter d []
# List.map (fun (x, y) -> x) (itemsp (dictofp (List.map (fun x -> (x, x)) ["this"; "is"; "a"; "list"; "of"; "strings"])));;
- : string list = ["a"; "is"; "list"; "of"; "strings"; "this"]