5 ms·

Union-find data structure: https://en.wikipedia.org/wiki/Disjoint-set_data_structure https://en.wikipedia.org/wiki/Disjoint-set_data_structure

OskarS 8y ago
Yeah, this is one of my absolute favorites as well. Such a neat idea. The analysis is also fun, where the complexity of operations is O(alpha(n)), where alpha(n) is the Inverse Ackermann Function. That function is just fun to contemplate. You wanna flex your muscles with this data structure, this is a fun Project Euler problem: https://projecteuler.net/problem=186 https://projecteuler.net/problem=186
emmanueloga_ 8y ago
I was gonna mention this one as well! So simple and clever. I like the explanation in the case study in Sedgewick's Algorithms [1]. Compare its simplicity to connected-components [2], another elegant algorithm but with a perhaps a bit more involved implementation. 1: https://algs4.cs.princeton.edu/15uf/ https://algs4.cs.princeton.edu/15uf/ 2: https://algs4.cs.princeton.edu/41graph/CC.java.html https://algs4.cs.princeton.edu/41graph/CC.java.html
tomp 8y ago
I love this algorithm (I like implementing type systems) but I always feel a bit naughty when I implement it, as AFAIK it can't be implemented with immutable data structures (not efficiently, at least).
- mattyw 8y ago
  I like implementing type systems Could you expand on this? This is something I've just started reading about. I'd be interested in good resources to use to get started. At the moment I've just started reading TAPL.
  - tomp 8y ago
    Check out https://github.com/tomprimozic/type-systems https://github.com/tomprimozic/type-systems there's been a few HN threads about it as well. I can also answer any specific questions you have, or if you want further resources I can try and find them... (there's a good online book I have in mind, but I've no idea how to find it right now!)
    - mattyw 8y ago
      Some great stuff in this repo thanks. I'm particularly interested in resources that build a type system up step by step, from very simple and working towards Hindley-Milner
      - tomp 8y ago
        Hm... I'm not sure it works that way. Type systems are quite fragile beasts, if you change one thing you can easily break the rest. Especially when it comes to type inference! Although I'd say that HM is quite simple, especially if you don't consider polymorphism (i.e. if you require that every function parameter has a concrete type like int or bool). In fact, that might be a good starting point - first implement something with the above 2 types, and where every variable and function parameter has a type annotation. From then, you could (1) add more complex types, like function types, tuples or lists, (2) implement type propagation where each variable has the type of the value it's assigned (like auto in modern C++), and then (3) go full HM type inference. TAPL definitely sounds like a good resource. The next book might be this one: Advanced Topics in Types and Programming Languages https://www.cis.upenn.edu/~bcpierce/attapl/frontmatter.pdf https://www.cis.upenn.edu/~bcpierce/attapl/frontmatter.pdf
    - DonaldPShimoda 8y ago
      Have you read TAPL? I'm curious how you think that stacks up to readily-available online resources.
      - tomp 8y ago
        No, I've just skimmed over some of its chapters to clarify some concepts. I've mostly learned by reading code and then trying to implement my own type systems. Algorithm W is really quite simple and basic. Another good resource could be Programming Language Zoo http://plzoo.andrej.com/ http://plzoo.andrej.com/ that covers different evaluation techniques as well. In general, I've been "involved" in PL design for quite some time, so I've no idea where I've gained all the knowledge I have... but in recent years, there have been quite a few modern resources, even a few on HN IIRC! e.g. http://craftinginterpreters.com/ http://craftinginterpreters.com/ http://createyourproglang.com/ http://createyourproglang.com/ (disclaimer: I haven't read them)
jedimastert 8y ago
I was recently in a coding interview where I had heard of the original problem (a version of "transform one word to another one letter at a time, making sure that each step is a real word") so instead of just skipping the question, we went straight to the "extra credit" question of "can you tell that there is a path from one word to another faster than just calculating the answer?" After hearing the word "memoization" go through my head (part of "Hacking the Coding Interview." which I recommend at least for the wealth of example questions for practice), I basically walked my way through making a disjoint-set data structure using the words as keys and the set number as values. I'm prettyy sure that making that up on the spot is what got me the job.

OskarS 8y ago

Yeah, this is one of my absolute favorites as well. Such a neat idea. The analysis is also fun, where the complexity of operations is O(alpha(n)), where alpha(n) is the Inverse Ackermann Function. That function is just fun to contemplate. You wanna flex your muscles with this data structure, this is a fun Project Euler problem: https://projecteuler.net/problem=186 https://projecteuler.net/problem=186

emmanueloga_ 8y ago

I was gonna mention this one as well! So simple and clever. I like the explanation in the case study in Sedgewick's Algorithms [1]. Compare its simplicity to connected-components [2], another elegant algorithm but with a perhaps a bit more involved implementation. 1: https://algs4.cs.princeton.edu/15uf/ https://algs4.cs.princeton.edu/15uf/ 2: https://algs4.cs.princeton.edu/41graph/CC.java.html https://algs4.cs.princeton.edu/41graph/CC.java.html

tomp 8y ago

I love this algorithm (I like implementing type systems) but I always feel a bit naughty when I implement it, as AFAIK it can't be implemented with immutable data structures (not efficiently, at least).

mattyw 8y ago
I like implementing type systems Could you expand on this? This is something I've just started reading about. I'd be interested in good resources to use to get started. At the moment I've just started reading TAPL.
- tomp 8y ago
  Check out https://github.com/tomprimozic/type-systems https://github.com/tomprimozic/type-systems there's been a few HN threads about it as well. I can also answer any specific questions you have, or if you want further resources I can try and find them... (there's a good online book I have in mind, but I've no idea how to find it right now!)
  - mattyw 8y ago
    Some great stuff in this repo thanks. I'm particularly interested in resources that build a type system up step by step, from very simple and working towards Hindley-Milner
    - tomp 8y ago
      Hm... I'm not sure it works that way. Type systems are quite fragile beasts, if you change one thing you can easily break the rest. Especially when it comes to type inference! Although I'd say that HM is quite simple, especially if you don't consider polymorphism (i.e. if you require that every function parameter has a concrete type like int or bool). In fact, that might be a good starting point - first implement something with the above 2 types, and where every variable and function parameter has a type annotation. From then, you could (1) add more complex types, like function types, tuples or lists, (2) implement type propagation where each variable has the type of the value it's assigned (like auto in modern C++), and then (3) go full HM type inference. TAPL definitely sounds like a good resource. The next book might be this one: Advanced Topics in Types and Programming Languages https://www.cis.upenn.edu/~bcpierce/attapl/frontmatter.pdf https://www.cis.upenn.edu/~bcpierce/attapl/frontmatter.pdf
  - DonaldPShimoda 8y ago
    Have you read TAPL? I'm curious how you think that stacks up to readily-available online resources.
    - tomp 8y ago
      No, I've just skimmed over some of its chapters to clarify some concepts. I've mostly learned by reading code and then trying to implement my own type systems. Algorithm W is really quite simple and basic. Another good resource could be Programming Language Zoo http://plzoo.andrej.com/ http://plzoo.andrej.com/ that covers different evaluation techniques as well. In general, I've been "involved" in PL design for quite some time, so I've no idea where I've gained all the knowledge I have... but in recent years, there have been quite a few modern resources, even a few on HN IIRC! e.g. http://craftinginterpreters.com/ http://craftinginterpreters.com/ http://createyourproglang.com/ http://createyourproglang.com/ (disclaimer: I haven't read them)

jedimastert 8y ago

I was recently in a coding interview where I had heard of the original problem (a version of "transform one word to another one letter at a time, making sure that each step is a real word") so instead of just skipping the question, we went straight to the "extra credit" question of "can you tell that there is a path from one word to another faster than just calculating the answer?" After hearing the word "memoization" go through my head (part of "Hacking the Coding Interview." which I recommend at least for the wealth of example questions for practice), I basically walked my way through making a disjoint-set data structure using the words as keys and the set number as values. I'm prettyy sure that making that up on the spot is what got me the job.