Hacker News Reader

Comment by dagw | Hacker News Reader

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.

View on HN

This 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

That 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

Yes, you are completely correct.

It only works for fruit trees.

Actually 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).

What’s great is that it’s constant time, once you’ve prepared the data structure. Never underestimate the parallelism of physical systems.

How 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?

Reply on news.ycombinator.com