9 ms·

I honestly don't mean this in a snide way. Can you give a few concrete examples of how a deep understanding of BFS that can't be googled and read in 10 minutes

I honestly don't mean this in a snide way. Can you give a few concrete examples of how a deep understanding of BFS that can't be googled and read in 10 minutes at the time you need it can help you ship profitable software products faster than your competitors?

mav3rick 8y ago
No problem will present in such an easy way as "oh just apply BFS". As part of a big project you often have to use many different algorithms for sub parts, often modify them to suit constraints. I think the HN crowd is heavily inclined to web apps and also front end. I can't tell you how important fundamental CS knowledge is for backend. I bet you can't use a library or API for how caches work or when paging happens. Knowing these things makes you a well rounded engineer ready to tackle different problems. I can trust you to write a mobile app or work on some part of a self driving car because you have the building blocks to do so. Most of the comments in such threads have no interest in interesting and diverse jobs because "why bother, when will I use this". To any new grad, yes the interviews can be better but please spend time on these things at school. They are an investment in your career's stock.
- Benjammer 8y ago
  I mean, I've built and released multiple mobile apps (commercial and enterprise) on both platforms for multiple companies. They've all been mostly successful at doing what the company needed them to do. They look fairly nice as well. And I don't have this kind of fundamental, "what do you mean 'google it' are you a complete and total fucking moron!?" attitude about anything in software. I routinely browse through google results (mostly SO/Medium) about very basic concepts just to read the words again and re-warm those caches in my brain.
  - saagarjha 8y ago
    It’s possible to have to solve issues like this even inside of app development. Think back to every time your app has performed poorly: has there been any cases where you didn’t know how to make it faster without giving up in the way you had designed it? Maybe the app was reading from the disk to populate your data model, and that was too slow? Maybe you were performing an O(n) operation for each row in your table view?
- deleted 8y ago
  [deleted]
watwut 8y ago
You won't be able to Google it, because you never ever asked to BFS by name. You will be asked to find the biggest file in folder structure, find largest modúle in dependency tree or the person in data structure that has no department and thus caused null pointer exception. You also won't google it, because it is simple and ylnormal programer don't need google for this.
- mav3rick 8y ago
  Excellent examples. There is no library for this.
Jach 8y ago
Do you spend 5-10 minutes googling and reading about the Linear Search algorithm[0] every time you iterate through a list and have a conditional to do something if an element matches some criterion? BFS, or a generic graph search (could be BFS, DFS...), is essentially just linear search except each element can have 0-n direct next elements, instead of 0 or 1. It's not this hard thing that never comes up... Indirection is great in this trade, a lot of what I "know" is just an index key/search strategy to go look it up again. But a lot of what I "know" I know directly. According to this old paper[1], for many fields including software you need to directly know about 70k±20k random things in the field to be in the running for expert status. Proficiency is also related to how many things you know directly. Thus you can't do an index lookup for everything unless you have no constraints on time and/or don't care about improving your level of expertise. [0] https://en.wikipedia.org/wiki/Linear_search https://en.wikipedia.org/wiki/Linear_search [1] https://apps.dtic.mil/dtic/tr/fulltext/u2/a219064.pdf https://apps.dtic.mil/dtic/tr/fulltext/u2/a219064.pdf
- andonisus 8y ago
  Can you give a concrete example of when you actually use BFS to solve this? For me, it always goes like this: * Am I iterating over a list multiple times? * Am I iterating over a list and comparing it to some elements in another list? Turn one of them into a map and continue. It's pretty simple.
  - Jach 8y ago
    I'm not sure I follow your question, what are you referring to with "solve this?" I usually find DFS/BFS applicable when I'm dealing with data that forms relations like "children" or "neighbors" or "connected". Sometimes that's explicit because the data is already in a tree or graph structure, sometimes it's not. And often rather than looking for a particular element, I want to iterate over all the data connected by the relationship to do something with after as a list/set/map of the data or some of its properties. A concrete example from a side project (it's more fun than Real Work examples, and people have given other examples in the thread anyway), I was writing a client for the board game Go. If you're not familiar, the data is just a 2D grid (easy to interpret as a graph), black/white stones get placed on coordinates like (3,4) marking intersecting lines. A single stone forms a connected group with another stone if both are the same color and separated horizontally or vertically by one. Groups have a count of "liberties" representing the number of unoccupied points the group can expand to if a stone of its color is played there -- a single stone by itself in the middle of the board will thus have 4 liberties, if you connect a stone then that group now has 6. If you cause an opponent group's liberties to go to 0 by surrounding it, the whole group dies, and its stones are removed from the board with those points becoming unoccupied again. Suicides (causing your own group to hit 0) are ok only if they capture the opponent first, otherwise are invalid moves. Handling the game rules is easy with DFS/BFS. All you need to start with is a function like get_neighbors(position) which on a grid is trivial, being the 2-4 surrounding points depending on whether position is an edge/corner. Then you can use DFS/BFS (doesn't matter) and several lines of code later you've got a function like get_group_member_positions(start_position) that gives you every member stone's position no matter which one you query first. Now you can make a function count_liberties(group_positions) -- which can be solved as another depth-first traversal problem over the neighbors of each member of the group that are empty and haven't been counted already. Even less code this time though; have you ever had to write 4 lines of code like "for el in list, for child in el.children(), if child blah, do something"? That's a DFS, just not a general one since you know how many layers there are (or that you care about), and it assumes children aren't shared between els. From all that you can then have a function like get_stones_captured_by_move(move) that tells you what (if any) stones need to be removed if move were to go through: for each neighbor of the move, if any are the opponent's color, count the liberties for that neighbor's group and if it's 1 then those will die when the move is played (takes the last liberty). If it's all one big enemy group around the move you'll have to account for duplicate positions to remove, but those are minor optimization details. Similarly the fact that everything is recalculated all the time, that could be optimized with more storage. BFS/DFS are just basic building blocks here.
Const-me 8y ago
No but I can give a few examples where I refactored code from these antique pointer-based trees (inspired by classic CS books, half century old now) towards something more cache friendly, and improved performance by an order of magnitude.
skookumchuck 8y ago
There is no "deep understanding" of BFS. All it is is look at your siblings before your children. I wouldn't hire an electrical engineer who complained that he shouldn't have to know Ohm's Law, either.
- purple_ducks 8y ago
  > All it is is look at your siblings before your children. ...And how you are keeping track of that and other such minutiae. What data structures are you using and why? And how about if X which would invalidate your approach. Also, it's not about "knowing" it. It's about implementing it in such a way as to please the interviewers. It's pop quiz nonsense.
  - saagarjha 8y ago
    > And how you are keeping track of that and other such minutiae. What data structures are you using and why? This is a good question, IMO, because it tests “I need to do this, which data structure would work well for it”, which does come up often in real life.
  - skookumchuck 8y ago
    Programming is exactly about handling such "minutia". It's a totally fair question. As for pleasing the interviewers, of course it is about pleasing the interviewers. They're making the "buy" decision on the talents you're "selling". Of course the seller needs to please the buyer to close the sale. I don't know how it could work any other way.
Xeronate 8y ago
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.

mav3rick 8y ago

No problem will present in such an easy way as "oh just apply BFS". As part of a big project you often have to use many different algorithms for sub parts, often modify them to suit constraints. I think the HN crowd is heavily inclined to web apps and also front end. I can't tell you how important fundamental CS knowledge is for backend. I bet you can't use a library or API for how caches work or when paging happens. Knowing these things makes you a well rounded engineer ready to tackle different problems. I can trust you to write a mobile app or work on some part of a self driving car because you have the building blocks to do so. Most of the comments in such threads have no interest in interesting and diverse jobs because "why bother, when will I use this". To any new grad, yes the interviews can be better but please spend time on these things at school. They are an investment in your career's stock.

Benjammer 8y ago
I mean, I've built and released multiple mobile apps (commercial and enterprise) on both platforms for multiple companies. They've all been mostly successful at doing what the company needed them to do. They look fairly nice as well. And I don't have this kind of fundamental, "what do you mean 'google it' are you a complete and total fucking moron!?" attitude about anything in software. I routinely browse through google results (mostly SO/Medium) about very basic concepts just to read the words again and re-warm those caches in my brain.
- saagarjha 8y ago
  It’s possible to have to solve issues like this even inside of app development. Think back to every time your app has performed poorly: has there been any cases where you didn’t know how to make it faster without giving up in the way you had designed it? Maybe the app was reading from the disk to populate your data model, and that was too slow? Maybe you were performing an O(n) operation for each row in your table view?
deleted 8y ago
[deleted]

watwut 8y ago

You won't be able to Google it, because you never ever asked to BFS by name. You will be asked to find the biggest file in folder structure, find largest modúle in dependency tree or the person in data structure that has no department and thus caused null pointer exception. You also won't google it, because it is simple and ylnormal programer don't need google for this.

mav3rick 8y ago
Excellent examples. There is no library for this.

Jach 8y ago

Do you spend 5-10 minutes googling and reading about the Linear Search algorithm[0] every time you iterate through a list and have a conditional to do something if an element matches some criterion? BFS, or a generic graph search (could be BFS, DFS...), is essentially just linear search except each element can have 0-n direct next elements, instead of 0 or 1. It's not this hard thing that never comes up... Indirection is great in this trade, a lot of what I "know" is just an index key/search strategy to go look it up again. But a lot of what I "know" I know directly. According to this old paper[1], for many fields including software you need to directly know about 70k±20k random things in the field to be in the running for expert status. Proficiency is also related to how many things you know directly. Thus you can't do an index lookup for everything unless you have no constraints on time and/or don't care about improving your level of expertise. [0] https://en.wikipedia.org/wiki/Linear_search https://en.wikipedia.org/wiki/Linear_search [1] https://apps.dtic.mil/dtic/tr/fulltext/u2/a219064.pdf https://apps.dtic.mil/dtic/tr/fulltext/u2/a219064.pdf

andonisus 8y ago
Can you give a concrete example of when you actually use BFS to solve this? For me, it always goes like this: * Am I iterating over a list multiple times? * Am I iterating over a list and comparing it to some elements in another list? Turn one of them into a map and continue. It's pretty simple.
- Jach 8y ago
  I'm not sure I follow your question, what are you referring to with "solve this?" I usually find DFS/BFS applicable when I'm dealing with data that forms relations like "children" or "neighbors" or "connected". Sometimes that's explicit because the data is already in a tree or graph structure, sometimes it's not. And often rather than looking for a particular element, I want to iterate over all the data connected by the relationship to do something with after as a list/set/map of the data or some of its properties. A concrete example from a side project (it's more fun than Real Work examples, and people have given other examples in the thread anyway), I was writing a client for the board game Go. If you're not familiar, the data is just a 2D grid (easy to interpret as a graph), black/white stones get placed on coordinates like (3,4) marking intersecting lines. A single stone forms a connected group with another stone if both are the same color and separated horizontally or vertically by one. Groups have a count of "liberties" representing the number of unoccupied points the group can expand to if a stone of its color is played there -- a single stone by itself in the middle of the board will thus have 4 liberties, if you connect a stone then that group now has 6. If you cause an opponent group's liberties to go to 0 by surrounding it, the whole group dies, and its stones are removed from the board with those points becoming unoccupied again. Suicides (causing your own group to hit 0) are ok only if they capture the opponent first, otherwise are invalid moves. Handling the game rules is easy with DFS/BFS. All you need to start with is a function like get_neighbors(position) which on a grid is trivial, being the 2-4 surrounding points depending on whether position is an edge/corner. Then you can use DFS/BFS (doesn't matter) and several lines of code later you've got a function like get_group_member_positions(start_position) that gives you every member stone's position no matter which one you query first. Now you can make a function count_liberties(group_positions) -- which can be solved as another depth-first traversal problem over the neighbors of each member of the group that are empty and haven't been counted already. Even less code this time though; have you ever had to write 4 lines of code like "for el in list, for child in el.children(), if child blah, do something"? That's a DFS, just not a general one since you know how many layers there are (or that you care about), and it assumes children aren't shared between els. From all that you can then have a function like get_stones_captured_by_move(move) that tells you what (if any) stones need to be removed if move were to go through: for each neighbor of the move, if any are the opponent's color, count the liberties for that neighbor's group and if it's 1 then those will die when the move is played (takes the last liberty). If it's all one big enemy group around the move you'll have to account for duplicate positions to remove, but those are minor optimization details. Similarly the fact that everything is recalculated all the time, that could be optimized with more storage. BFS/DFS are just basic building blocks here.

Const-me 8y ago

No but I can give a few examples where I refactored code from these antique pointer-based trees (inspired by classic CS books, half century old now) towards something more cache friendly, and improved performance by an order of magnitude.

skookumchuck 8y ago

There is no "deep understanding" of BFS. All it is is look at your siblings before your children. I wouldn't hire an electrical engineer who complained that he shouldn't have to know Ohm's Law, either.

purple_ducks 8y ago
> All it is is look at your siblings before your children. ...And how you are keeping track of that and other such minutiae. What data structures are you using and why? And how about if X which would invalidate your approach. Also, it's not about "knowing" it. It's about implementing it in such a way as to please the interviewers. It's pop quiz nonsense.
- saagarjha 8y ago
  > And how you are keeping track of that and other such minutiae. What data structures are you using and why? This is a good question, IMO, because it tests “I need to do this, which data structure would work well for it”, which does come up often in real life.
- skookumchuck 8y ago
  Programming is exactly about handling such "minutia". It's a totally fair question. As for pleasing the interviewers, of course it is about pleasing the interviewers. They're making the "buy" decision on the talents you're "selling". Of course the seller needs to please the buyer to close the sale. I don't know how it could work any other way.

Xeronate 8y ago

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.