7 ms·

DFS == Depth First Search?

by somedangedname 10y ago

ng12 10y ago
Yeah, given an acyclic graph print out each node's value. Passing candidates generally got it in five minutes.
- jnordwick 10y ago
  Sometimes I get these questions in interviews and I really don't know if I should be offended. My resume is pretty good, and I wonder who T.F. applies to these places that they have to have such simple weeder questions. Then I get all paranoid that there is some hidden complication and soon I'm producing FizzBuzz in TensorFlow: http://joelgrus.com/2016/05/23/fizz-buzz-in-tensorflow/ http://joelgrus.com/2016/05/23/fizz-buzz-in-tensorflow/
  - vacri 10y ago
    I think you shouldn't be offended at interview questions around skill unless you've been on the other side of the table. It's eye-opening, the range of people that apply for these positions.
- sheeshkebab 10y ago
  was writing DFS from scratch ever needed to perform dev job or was it a thing that stumped 95% of applicants (and let you read some hacker news/email on your phone/laptop in the mean time)?
  - ng12 10y ago
    It only stumped the candidates that clearly wouldn't make it through the rest of the problem. One sixth was a probably a high estimate. DFS for an acyclic graph is about five lines of code and shows me that you A. know a programming language B. can figure out a data structure. I would argue both are needed to perform a dev job.
  - DontGiveTwoFlux 10y ago
    Eh, I had to write a DFS the other day at work.
  - ap22213 10y ago
    I've written DFS about 1-2 times a year, on average, for the last 15 years. Why do I need to? Usually, because I need to modify or create a data structure that is kind of graph-like but not quite. If someone didn't know how to write one or at least derive it, they would confuse a lot of people, so yeah it's kind of important.
    - lawnchair_larry 10y ago
      No, they'd probably look it up, skim a blog for a few minutes, then figure it out and promptly forget. This is no different than forgetting the order of the arguments to socket() and accusing that person of being incapable of writing networking code.
      - ap22213 10y ago
        The difference is that the arguments to socket() were arbitrarily defined, but DFS is an algorithm. Anyone who has taken a intro data structures course should be able to at least derive the pseudo code for DFS.
  - morgante 10y 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.
    - vonmoltke 10y 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.
      - morgante 10y 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.
        vonmoltke 10y 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.
      - djb_hackernews 10y 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.
- dastbe 10y ago
  Do you give them a graph data structure or something that is explicitly a tree?
  - dnautics 10y ago
    A acyclic graph is isomorphic to a tree, but the way you access the vertices and edges is completely different.
    - palunon 10y ago
      Depends on your memory representation of the graph. If you simply use the obvious one (a node have a list of pointers to its successors), I don't see the difference except for successors[]/children[]
      - dnautics 10y ago
        You're right. I mentioned acyclic graph and my mind slipped to general graphs. Although often graphs are represented as say a sparse matrix.
- deleted 10y ago
  [deleted]
- kirab 10y ago
  Should every node's value be printed out exactly once and if so, are there nodes which have two parents? If so, I would keep the pointers in a set to mark nodes as processed but is there a more elegant solution?
  - drakonandor 10y ago
    Each node is an object and has a "checked" variable.
  - ng12 10y ago
    I would explicitly tell them that you should revisit nodes, and give them a few examples illustrating that point -- so all they needed to do was traverse edges.

DFS == Depth First Search?

ng12 10y ago

Yeah, given an acyclic graph print out each node's value. Passing candidates generally got it in five minutes.

jnordwick 10y ago
Sometimes I get these questions in interviews and I really don't know if I should be offended. My resume is pretty good, and I wonder who T.F. applies to these places that they have to have such simple weeder questions. Then I get all paranoid that there is some hidden complication and soon I'm producing FizzBuzz in TensorFlow: http://joelgrus.com/2016/05/23/fizz-buzz-in-tensorflow/ http://joelgrus.com/2016/05/23/fizz-buzz-in-tensorflow/
- vacri 10y ago
  I think you shouldn't be offended at interview questions around skill unless you've been on the other side of the table. It's eye-opening, the range of people that apply for these positions.
sheeshkebab 10y ago
was writing DFS from scratch ever needed to perform dev job or was it a thing that stumped 95% of applicants (and let you read some hacker news/email on your phone/laptop in the mean time)?
- ng12 10y ago
  It only stumped the candidates that clearly wouldn't make it through the rest of the problem. One sixth was a probably a high estimate. DFS for an acyclic graph is about five lines of code and shows me that you A. know a programming language B. can figure out a data structure. I would argue both are needed to perform a dev job.
- DontGiveTwoFlux 10y ago
  Eh, I had to write a DFS the other day at work.
- ap22213 10y ago
  I've written DFS about 1-2 times a year, on average, for the last 15 years. Why do I need to? Usually, because I need to modify or create a data structure that is kind of graph-like but not quite. If someone didn't know how to write one or at least derive it, they would confuse a lot of people, so yeah it's kind of important.
  - lawnchair_larry 10y ago
    No, they'd probably look it up, skim a blog for a few minutes, then figure it out and promptly forget. This is no different than forgetting the order of the arguments to socket() and accusing that person of being incapable of writing networking code.
    - ap22213 10y ago
      The difference is that the arguments to socket() were arbitrarily defined, but DFS is an algorithm. Anyone who has taken a intro data structures course should be able to at least derive the pseudo code for DFS.
- morgante 10y 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.
  - vonmoltke 10y 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.
    - morgante 10y 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.
      - vonmoltke 10y 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.
    - djb_hackernews 10y 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.
dastbe 10y ago
Do you give them a graph data structure or something that is explicitly a tree?
- dnautics 10y ago
  A acyclic graph is isomorphic to a tree, but the way you access the vertices and edges is completely different.
  - palunon 10y ago
    Depends on your memory representation of the graph. If you simply use the obvious one (a node have a list of pointers to its successors), I don't see the difference except for successors[]/children[]
    - dnautics 10y ago
      You're right. I mentioned acyclic graph and my mind slipped to general graphs. Although often graphs are represented as say a sparse matrix.
deleted 10y ago
[deleted]
kirab 10y ago
Should every node's value be printed out exactly once and if so, are there nodes which have two parents? If so, I would keep the pointers in a set to mark nodes as processed but is there a more elegant solution?
- drakonandor 10y ago
  Each node is an object and has a "checked" variable.
- ng12 10y ago
  I would explicitly tell them that you should revisit nodes, and give them a few examples illustrating that point -- so all they needed to do was traverse edges.