6 ms·

I was recently asked to identify pages in our 10 million line application that use a certain piece of business logic. It involved parsing the page and their nes

I was recently asked to identify pages in our 10 million line application that use a certain piece of business logic. It involved parsing the page and their nested subcontrols into a tree with by doing a modified BFS on the linked files, doing a modifed BFS on the tree to identify the related code behinds, parsing the C# from the codebehinds into a tree, and traversing the C# tree (again with a modified BFS) to find if the code path was hit. These questions come up all the time. You just need to be proficient enough with algorithms to identify them.

jedberg 8y ago
Right, but you used libraries to do it, right? You didn't actually need to know how BFS works, did you? 10 million lines of code fits in RAM pretty easily. You could use the worst algorithm in the world and still complete that whole task with just a few seconds of compute time. I think that's the point. You don't really need to know about BFS in most cases, because in most cases you can solve the problem with any old search in just a few seconds.
- saagarjha 8y ago
  > Right, but you used libraries to do it, right? You didn't actually need to know how BFS works, did you? For BFS? Almost never, no. Libraries are generally useful for reference implementations data structures and algorithms that work on collections; I have yet to find an algorithm that works well for graph problems or when you need to subtly tweak the data structure (for example, a binary tree that counts the number of elements on its left and right). The issue with libraries is that they are built for the general use case, and a lot of time in the real world it is non-trivial to transform your problem into the format that the library will expect, so you end up having to do this yourself.
- Xeronate 8y ago
  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-...
aprdm 8y ago
You are essentially looking for patterns in text, your solutions looks not ideal and it takes a lot of time to develop vs just using some linux tools and piping output from one another. 10 millions line is nothing... (commenting based in your gist) would go even further and say that you could easily have installed something like https://oracle.github.io/opengrok/ https://oracle.github.io/opengrok/ in three commands for your organization and extract a lot more value while resolving the issue.
- Xeronate 8y ago
  It feels like OpenGrok should be able to do this, but I'm not seeing it. How do you search for a method call in a code path? E.g how do determine i function A calls function C? function file1.A(){file2.B();}, function file2.B(){file3.C();}
  - Xeronate 8y ago
    Heard back from the OpenGrok developers and they said they don't support the use case I needed. My gist was just a very small part of the overall process (and yes, for that small piece it was trivial to use a linux util instead of csharp).

jedberg 8y ago

Right, but you used libraries to do it, right? You didn't actually need to know how BFS works, did you? 10 million lines of code fits in RAM pretty easily. You could use the worst algorithm in the world and still complete that whole task with just a few seconds of compute time. I think that's the point. You don't really need to know about BFS in most cases, because in most cases you can solve the problem with any old search in just a few seconds.

saagarjha 8y ago
> Right, but you used libraries to do it, right? You didn't actually need to know how BFS works, did you? For BFS? Almost never, no. Libraries are generally useful for reference implementations data structures and algorithms that work on collections; I have yet to find an algorithm that works well for graph problems or when you need to subtly tweak the data structure (for example, a binary tree that counts the number of elements on its left and right). The issue with libraries is that they are built for the general use case, and a lot of time in the real world it is non-trivial to transform your problem into the format that the library will expect, so you end up having to do this yourself.
Xeronate 8y ago
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-...

aprdm 8y ago

You are essentially looking for patterns in text, your solutions looks not ideal and it takes a lot of time to develop vs just using some linux tools and piping output from one another. 10 millions line is nothing... (commenting based in your gist) would go even further and say that you could easily have installed something like https://oracle.github.io/opengrok/ https://oracle.github.io/opengrok/ in three commands for your organization and extract a lot more value while resolving the issue.

Xeronate 8y ago
It feels like OpenGrok should be able to do this, but I'm not seeing it. How do you search for a method call in a code path? E.g how do determine i function A calls function C? function file1.A(){file2.B();}, function file2.B(){file3.C();}
- Xeronate 8y ago
  Heard back from the OpenGrok developers and they said they don't support the use case I needed. My gist was just a very small part of the overall process (and yes, for that small piece it was trivial to use a linux util instead of csharp).