5 ms·
Which is why all the LeetCode interviews always struck me as odd. They focus on algorithms, not data structures I helped my nephew preparing some competitive c
by dagw 3y ago
Which is why all the LeetCode interviews always struck me as odd. They focus on algorithms, not data structures
I helped my nephew preparing some competitive coding event, and transforming the data into the right data structure was a huge part of solving most problems. For example most of the code you might end up writing is for finding the longest path through a weighted DAG, but the trick was realising that you could represent the problem as a weighted DAG, and if you did then the length of the longest path through that graph was your answer. If you didn't spot that then you might very well still be able to solve the problem, but your solution would end up being much slower and more complicated.
- pfisherman 3y agoHow much of this is finding the right data structure (graph) vs translating the problem into a new domain? I think maybe the former follows from the latter?
- mikhailfranco 3y agoThis is the low-hanging fruit algorithm: - build the DAG with heavy nodes (e.g. lead split-shot) - use string or fishing line for edges, with length proportional to 'weights' - hold the root node(s) high in the air, if more than one, hold them together, at the same height - the lowest node, or the length of taught line (drop distance below your hand), is the answer
- roughly 3y agoWhat’s great is that it’s constant time, once you’ve prepared the data structure. Never underestimate the parallelism of physical systems.
- a1369209993 3y agoThat doesn't actually work, because a DAG only lacks directed cycles. Consider: /-3-> D A -1-> B -1-> C \------4------^ In this case, the longest path is A-C, but C will be held at level 2 by B, leaving D lowest at level 3. This works for a fully-acyclic directed graph (eg a tree), but not for a directed-acyclic directed graph. It can also find the node whose shortest path is the longest (so longest shortest path, minimax style). (It also works for a acyclic undirected graph, as illustrated at [0], but that's a bit tangential.) 0: https://www.youtube.com/watch?v=wGrOPSBPpyk https://www.youtube.com/watch?v=wGrOPSBPpyk
- mikhailfranco 3y agoYes, you are completely correct. It only works for fruit trees.
- a1369209993 3y agoActually it works for all trees, fruit or otherwise (and also for some non-tree graphs, though I'd have trouble giving a useful category more general than tree).