As an average/below average engineer with 15 yoe who wouldn't pass SV-style interviews no matter how many leetcode problems I solve, I've only had to use algorithms a handful of times in my career.
One of the most memorable was when I had to build a graph from sql statements, parse the sql statements, determine the dependencies between the sql statements by traversing the syntax tree and ordering the graph based on the dependencies so sql statements on each level could be evaluated in parallel.
It was one of the most fun and interesting projects I've ever worked on, it took me a few days to come up with a Java implementation and after a few bugs I rewrote it in Scala. I think I ended up with some kind of DFS algorithm if I recall, I might give it a shot at implementing it from memory and putting it on github.
I would be Interested in getting some mentorship...I have also started to learn rust and kubernetes plus doing leetcode on the side, I also want to contribute to OS projects and have some more activity on github... I am getting a bit overwhelmed and my motivation is dwindling so I think a mentor might help. How can I contact you?
Are you looking for contributors? I don't have any rust, arrow or k8s experience but been looking to learn all 3, I've also been looking to contribute to os projects so I'm happy to pick up any low hanging fruits if you are interested.
I do have a few years of experience with Spark and hadoop if that's worth anything.
A disjoint-set data structure is a data structure
that keeps track of a set of elements partitioned
into a number of disjoint (non-overlapping) subsets.
A union-find algorithm is an algorithm that
performs two useful operations on such a
data structure:
Find: Determine which subset a particular
element is in. This can be used for determining
if two elements are in the same subset.
Union: Join two subsets into a single subset.
Sorry, I should have com back, but yeah, this is a good summary. When done properly both Find and Union can be done in amortized inverse-Ackerman time, which is for all intents and purposes constant. It can pop up as a solution for a surprising number of questions.
An old, common, (banned) interview question goes something like this:
> Imagine you have a grid of squares, represented however you want, describing an ocean. I'm going to give you coordinates one by one that indicate land being created. You need to tell me in total how many islands exist after each coordinate, where an island is defined as a contiguous block of land connected horizontally or vertically, but not diagonally (or include diagonals if you want; it makes some parts of the answer messier).
The disjoint-set answer to this question is that you look at the coordinate's neighbors. If there are none, this is a new island. Create the node as part of a new set where the node is the "representative" of that set. If there is one neighbor, create node but make its representative the same as the neighbor's representative. If there are more than one neighbors then you have to do a union; create your node and make its representative one of the neighbors' representatives. Then go to all of the other neighbors and find their representatives (make take a couple hops). Then make their final representatives use the first neighbor as their representative.
At this point you have kind of a directed acyclic graph where each node has exactly one edge (maybe pointing to itself). The last improvement is to update each node's representative as you travel to be the final one. This amortizes out to a single hop for each node, after enough find or union operations.
Then you can start adding more data to the representative and dealing with merging that to solve some pretty complex problems in a shockingly low runtime.
One of the most memorable was when I had to build a graph from sql statements, parse the sql statements, determine the dependencies between the sql statements by traversing the syntax tree and ordering the graph based on the dependencies so sql statements on each level could be evaluated in parallel.
It was one of the most fun and interesting projects I've ever worked on, it took me a few days to come up with a Java implementation and after a few bugs I rewrote it in Scala. I think I ended up with some kind of DFS algorithm if I recall, I might give it a shot at implementing it from memory and putting it on github.