5 ms·

What if this became the new “invert a binary tree on a whiteboard”?

by bluedino 6y ago

deleted 6y ago
[deleted]
Google234 6y ago
This is pretty straight forward stuff.
- 0xbadcafebee 6y ago
  Hash tables are deceptively complicated, like sorting algorithms.
  - cogman10 6y ago
    Like sorting algorithms, they can be as complicated as you want them to be. 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.
    - kragen 6y ago
      Dunno, I wrote https://news.ycombinator.com/item?id=26595520 https://news.ycombinator.com/item?id=26595520 just now and my super dumb hash table has two bugs in its 21 lines of code: 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.
      - kragen 6y ago
        By contrast this binary search tree code I wrote in OCaml seems to have worked as soon as I got it to compile, although its worst-case performance is pretty bad, and, unlike the much longer hash table code, very likely: 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) And it's about a third the size of the hash-table code. OTOH I spent the last hour writing it. 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 [] Look: # 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"] Of course the same comments about worst-case performance apply...
SavantIdiot 6y ago
This shouldn't be a mystery to someone who's had a datastructures course. It's a fundamental data structure. Yes, optimization always goes down a rabbit-hole, but Knuth's "Algorithms in C" was mandatory in most engineering schools' CS degrees in the early 90's, and it essentially what this website describes, but with more rigor.
- philzook 6y ago
  Sedgewick's?
- deleted 6y ago
  [deleted]
- oldmanhorton 6y ago
  Ok, but school was years ago. I've had years of relevant experience that would make me a good fit for some job since, but I've forgotten how to implement a hash table in C within 30 minutes. Is that really the gatekeeper we want?
  - jstanley 6y ago
    Knowing how to implement a hash table in C doesn't strike me as something you can "forget". If you know how to write C and you know how a hash table works, what is there to forget?
  - 908B64B197 6y ago
    Honestly it's such a simple concept it shouldn't be hard to remember.
  - kragen 6y ago
    "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 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.
thrower123 6y ago
Hashtables are probably more directly useful than all the binary tree gymnastics. 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.
seanwilson 6y ago
I wouldn't ask someone to whiteboard it but I think "what is a hash table?" is a brilliant interview question. The depth someone can go into tells you a lot and can bring up lots of other topics to discuss. It tells you a lot if a senior developer doesn't know what a hash table is or only knows "it's a class from Java" too.
- 908B64B197 6y ago
  > I wouldn't ask someone to whiteboard it I did. Works very well as an interview question.
anaerobicover 6y ago
Who said anything about interviews? This is just in the context of "something interesting to read with your morning cuppa".

What if this became the new “invert a binary tree on a whiteboard”?

deleted 6y ago

[deleted]

Google234 6y ago

This is pretty straight forward stuff.

0xbadcafebee 6y ago
Hash tables are deceptively complicated, like sorting algorithms.
- cogman10 6y ago
  Like sorting algorithms, they can be as complicated as you want them to be. 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.
  - kragen 6y ago
    Dunno, I wrote https://news.ycombinator.com/item?id=26595520 https://news.ycombinator.com/item?id=26595520 just now and my super dumb hash table has two bugs in its 21 lines of code: 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.
    - kragen 6y ago
      By contrast this binary search tree code I wrote in OCaml seems to have worked as soon as I got it to compile, although its worst-case performance is pretty bad, and, unlike the much longer hash table code, very likely: 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) And it's about a third the size of the hash-table code. OTOH I spent the last hour writing it. 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 [] Look: # 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"] Of course the same comments about worst-case performance apply...

SavantIdiot 6y ago

This shouldn't be a mystery to someone who's had a datastructures course. It's a fundamental data structure. Yes, optimization always goes down a rabbit-hole, but Knuth's "Algorithms in C" was mandatory in most engineering schools' CS degrees in the early 90's, and it essentially what this website describes, but with more rigor.

philzook 6y ago
Sedgewick's?
deleted 6y ago
[deleted]
oldmanhorton 6y ago
Ok, but school was years ago. I've had years of relevant experience that would make me a good fit for some job since, but I've forgotten how to implement a hash table in C within 30 minutes. Is that really the gatekeeper we want?
- jstanley 6y ago
  Knowing how to implement a hash table in C doesn't strike me as something you can "forget". If you know how to write C and you know how a hash table works, what is there to forget?
- 908B64B197 6y ago
  Honestly it's such a simple concept it shouldn't be hard to remember.
- kragen 6y ago
  "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 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.

thrower123 6y ago

Hashtables are probably more directly useful than all the binary tree gymnastics. 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.

seanwilson 6y ago

I wouldn't ask someone to whiteboard it but I think "what is a hash table?" is a brilliant interview question. The depth someone can go into tells you a lot and can bring up lots of other topics to discuss. It tells you a lot if a senior developer doesn't know what a hash table is or only knows "it's a class from Java" too.

908B64B197 6y ago
> I wouldn't ask someone to whiteboard it I did. Works very well as an interview question.

anaerobicover 6y ago

Who said anything about interviews? This is just in the context of "something interesting to read with your morning cuppa".