3 ms·

I can tell you really don't know what you're talking about because you can't just "use libraries to do it". You can use a library to parse a given input, but yo

I can tell you really don't know what you're talking about because you can't just "use libraries to do it". You can use a library to parse a given input, but you need to traverse the tree in a specific way. Here, I'll give you an example of the first step of the problem with proprietary info stripped out. https://gist.github.com/tohsa/2d906942f8712abdfc7df72128479c0a https://gist.github.com/tohsa/2d906942f8712abdfc7df72128479c... You plain and simple need to know BFS to do these sorts of things. You're acting like its some act of algorithmic wizardry when its not. It's not a question of speed. It's the fact that tree traversals are the best way to analyze parsed text. Although, it was quite resource intensive and we ended up distributing the workload among multiple computers so we could scan all pages at once. Luckily this was easy because pure functions are trivially parallelizable.

Benjammer 8y ago
I can tell you really don't know what you're talking about because you are mouthing off about jedberg not knowing what he's talking about.
jedberg 8y ago
Ok I see where the problem is. I read through your code and didn't think "BFS", I just thought "knows how to nest for and while loops". I suppose you could consider this "knowing BFS", but I would consider this table stakes. I would never ask about something like this in an interview. I thought you were talking about actually using BFS on a data structure, in which case I'd use a library to do it so I don't have to reimplement all the loops and because there are modern libraries that would take care of the parallelization (like this one[0]) [0] https://github.com/arjun-menon/Distributed-Graph-Algorithms/tree/master/Breadth-First-Search https://github.com/arjun-menon/Distributed-Graph-Algorithms/...
- Xeronate 8y ago
  I agree with you that my gist demonstrates "table stakes", but I think that is the level of tree traversing most interview questions require. I don't think any interviewers are asking people to implement distributed algorithms like the one you linked. They are asking for algorithms that just combine a few of the basics. With that said, I'm inclined to believe our fellow commenters are arguing about the utility of what I shared. For example people siding with me gave examples of finding the biggest file in a file system and constructing a dependency graph to refute the idea that tree traversal are useless and mentioned that there isn't any "deep understanding" in BFS because it's so simple. It reminds me of the tweet by the creator of Homebrew[0] about not being able to reverse a binary tree that so many people bring up when this topic arises. To me that's just table stakes. On the topic of my example not constituting "knowing BFS", the BFS I shared is just a slight modification of what most students are taught and is close to the second method for level order traversal of a tree on geeks for geeks[1]. If you don't like the BFS usage because it isn't on an explicit tree (although nested HTML templates most definitely form a tree), the result of parsing an AspxFile in my gist returns an explicit tree data structure[2][3] and the helper method[4] at the bottom does a standard preorder traversal[5] on that linked structure. That feels like "actually using DFS on a data structure". [0] https://twitter.com/mxcl/status/608682016205344768?ref_src=twsrc%5Etfw%7Ctwcamp%5Etweetembed%7Ctwterm%5E608682016205344768&ref_url=https%3A%2F%2Fthecodebarbarian.com%2Fi-dont-want-to-hire-you-if-you-cant-reverse-a-binary-tree https://twitter.com/mxcl/status/608682016205344768?ref_src=t... [1] https://www.geeksforgeeks.org/level-order-tree-traversal/ https://www.geeksforgeeks.org/level-order-tree-traversal/ [2] https://gist.github.com/tohsa/2d906942f8712abdfc7df72128479c0a#file-stepone-cs-L21 https://gist.github.com/tohsa/2d906942f8712abdfc7df72128479c... [3] https://github.com/PositiveTechnologies/AspxParser/blob/master/AspxParser/AspxNode.cs#L9 https://github.com/PositiveTechnologies/AspxParser/blob/mast... (AspxParseResult has a reference to the root AspxNode, and btw I didn't write this parsing library) [4]https://gist.github.com/tohsa/2d906942f8712abdfc7df72128479c0a#file-stepone-cs-L93 https://gist.github.com/tohsa/2d906942f8712abdfc7df72128479c... [5] https://www.geeksforgeeks.org/dfs-traversal-of-a-tree-using-recursion/ https://www.geeksforgeeks.org/dfs-traversal-of-a-tree-using-...

Benjammer 8y ago

I can tell you really don't know what you're talking about because you are mouthing off about jedberg not knowing what he's talking about.

jedberg 8y ago

Ok I see where the problem is. I read through your code and didn't think "BFS", I just thought "knows how to nest for and while loops". I suppose you could consider this "knowing BFS", but I would consider this table stakes. I would never ask about something like this in an interview. I thought you were talking about actually using BFS on a data structure, in which case I'd use a library to do it so I don't have to reimplement all the loops and because there are modern libraries that would take care of the parallelization (like this one[0]) [0] https://github.com/arjun-menon/Distributed-Graph-Algorithms/tree/master/Breadth-First-Search https://github.com/arjun-menon/Distributed-Graph-Algorithms/...

Xeronate 8y ago
I agree with you that my gist demonstrates "table stakes", but I think that is the level of tree traversing most interview questions require. I don't think any interviewers are asking people to implement distributed algorithms like the one you linked. They are asking for algorithms that just combine a few of the basics. With that said, I'm inclined to believe our fellow commenters are arguing about the utility of what I shared. For example people siding with me gave examples of finding the biggest file in a file system and constructing a dependency graph to refute the idea that tree traversal are useless and mentioned that there isn't any "deep understanding" in BFS because it's so simple. It reminds me of the tweet by the creator of Homebrew[0] about not being able to reverse a binary tree that so many people bring up when this topic arises. To me that's just table stakes. On the topic of my example not constituting "knowing BFS", the BFS I shared is just a slight modification of what most students are taught and is close to the second method for level order traversal of a tree on geeks for geeks[1]. If you don't like the BFS usage because it isn't on an explicit tree (although nested HTML templates most definitely form a tree), the result of parsing an AspxFile in my gist returns an explicit tree data structure[2][3] and the helper method[4] at the bottom does a standard preorder traversal[5] on that linked structure. That feels like "actually using DFS on a data structure". [0] https://twitter.com/mxcl/status/608682016205344768?ref_src=twsrc%5Etfw%7Ctwcamp%5Etweetembed%7Ctwterm%5E608682016205344768&ref_url=https%3A%2F%2Fthecodebarbarian.com%2Fi-dont-want-to-hire-you-if-you-cant-reverse-a-binary-tree https://twitter.com/mxcl/status/608682016205344768?ref_src=t... [1] https://www.geeksforgeeks.org/level-order-tree-traversal/ https://www.geeksforgeeks.org/level-order-tree-traversal/ [2] https://gist.github.com/tohsa/2d906942f8712abdfc7df72128479c0a#file-stepone-cs-L21 https://gist.github.com/tohsa/2d906942f8712abdfc7df72128479c... [3] https://github.com/PositiveTechnologies/AspxParser/blob/master/AspxParser/AspxNode.cs#L9 https://github.com/PositiveTechnologies/AspxParser/blob/mast... (AspxParseResult has a reference to the root AspxNode, and btw I didn't write this parsing library) [4]https://gist.github.com/tohsa/2d906942f8712abdfc7df72128479c0a#file-stepone-cs-L93 https://gist.github.com/tohsa/2d906942f8712abdfc7df72128479c... [5] https://www.geeksforgeeks.org/dfs-traversal-of-a-tree-using-recursion/ https://www.geeksforgeeks.org/dfs-traversal-of-a-tree-using-...