Hacker News new | ask | show | jobs
by morgante 3553 days ago
If you ignore the terminology, DFS is basically just recursively walking a graph, something which actually happens all the time in most dev jobs. I'm sure I wrote a DFS long before I had heard the term.

I hate brain teaser interviews as much as the next guy, but being able to do basic operations on basic data structures is pretty much the minimum to be a developer.
1 comments
vonmoltke 3553 days ago
> If you ignore the terminology, DFS is basically just recursively walking a graph, something which actually happens all the time in most dev jobs.

In ten years of full-time professional development I have never needed to recursively walk a graph. Hell, the only data structures in the software I worked on for the first six (real-time signal processing code) didn't use any data structures other than lists, arrays, and C structs. I would not be able to answer the interview question that started this subthread, despite my track record of efficient and well-designed code.

link
morgante 3553 days ago
Are you sure? Keep in mind that a graph doesn't always come up and slap you saying that it's a graph.

This very comment thread is a graph which is being printed depth-first.

link
vonmoltke 3553 days ago
I'm very sure. The signal processing code had no graph structures whatsoever.

That's certainly not the case with the NLP code I have been working on for the past 4.5, but I have never personally needed to search the (usually) trees in a structured manner. Most of our code that searches for things doesn't care about the structure of the graph during the search; it just searches a node list. Once the node is found, structure matters. There are some algorithms that use calculations like shortest path and tree height, but I didn't write the code to actually do that.

link
djb_hackernews 3553 days ago
Do you think you've ever had to do something as algorithmically complex as recursively walk a graph?

Sometimes these questions are used to probe the meta understanding of a candidate and using Graphs/Trees/DFS are universally understood concepts that make doing that easy.

link
vonmoltke 3553 days ago
Define "algorithm". In the broader definition, yes. Kalman filtering, motion compensation, track association, XY-mapping, and similar signal processing algorithms. For NLP it has been various forms of statistical modeling and general multithreaded architecture and coordination.

As for the algorithms typical of computer science, not really. Searching and sorting has not been much a part of what I have done. My experience is mainly in translating math into code, often into code with real-time deadlines.

link