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?

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

[1] https://apps.dtic.mil/dtic/tr/fulltext/u2/a219064.pdf

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.

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.

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.

Excellent examples. There is no library for this.

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.

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.

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?

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.

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/ in three commands for your organization and extract a lot more value while resolving the issue.

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();}

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).

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.

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/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.

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/...

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=t...

[1] https://www.geeksforgeeks.org/level-order-tree-traversal/

[2] https://gist.github.com/tohsa/2d906942f8712abdfc7df72128479c...

[3] 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/2d906942f8712abdfc7df72128479c...

[5] https://www.geeksforgeeks.org/dfs-traversal-of-a-tree-using-...

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.

> 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.

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.

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.

> 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.

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.

> 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.

BFS is common sense. It’s what you use when you’ve lost your car keys for example. Quickly check each room in the house, then if no luck go one layer deeper in each room.

uh, I thoroughly search each room, starting at the left corner and recursively iterating via a hilbert curve.

doesn't everybody?

Two different approaches. Each have their adherents. But when someone can’t find their phone or keys that that just had, they probably don’t start by ripping one room apart top to bottom.

I might pull the couch cushions, but I'm not going to start moving furniture until I check other places first.

so, basically A* search

I would certainly probe deeper if given that as evidence for a strong grasp on the utility of BFS.

So you’d do a DFS on a BFS

That's definitely now how I do it. I go deeper into each room, the depth (as well as the order) being decided by (roughly) how much time I spend in each room every day. E.g., Go waay deeper in living room, less so in bedroom, lesser still in bath room and so on :-). This I'd imagine is "more" common sense than than an un-informed BFS?

If you just go depth, it is well depth first :)

I actually thought this through a bit :-) Neither is it a DFS, unlike in DFS I'm expanding nodes at different depths. E.g., I'm shallow expanding bathroom/kitchen compared to living room. Only when I've exhausted living do I return to kitchen again to do a deeper search. I wonder if this kind of search has any other use. Debugging seems like a similar activity. Go deeper into logs, if nothing turns up then examine metrics, read code, return to logs again etc.,?

Sorry, past midnight here after a busy day at work :-P

Heuristically guided search. :) For some nodes you go wide, for some deep, sometimes you retreat back up a few levels instead of exhausting a subtree (but you might come back to that subtree later), all depending on what the heuristic says is more likely to get you to your goal the quickest. A* is a well-known base algorithm for this, widely used in game programming to efficiently find the shortest path from A to B in the presence of obstacles etc.

A DFS would be you check your living room, you check under the cushions of the sofa, you tear open the cushions and comb through the insides... all before glancing at your bedroom when you didn't quickly see the keys in the living room.

This is actually not how I search. After the first search, if I am getting frustrated, I do what I was told when I was a child: "start picking up stuff until you find it". So I guess that's kind of a depth first search after going over the top layer.

I'd use an indexed search and remote activate the beeper in the key chain

I don't think I've ever lost my car keys so does that make me a NULL pointer!

In that case you get O(1) regardless of algo choice.

> If you're stubborn enough to not spend 10 mins on this the best of luck

I know. These people are expecting to be paid way above the average salary - I'd expect them to know the fundamentals, or (more importantly) be able to figure it out.

"BFS?? I'd use a library for that" - well, thanks for that... instead of hiring you I'll just download some libraries instead.

Watch me get downvoted to hell though :)

The creator of ruby on rails wouldn't pass a whiteboard interview. Ruby on Rails had more of an impact at Twitter, Github, Airbnb than BFS is my guess

DHH's tweet https://twitter.com/dhh/status/1085987159406927872

There's a reason such tweets resonate so well:

1. Creator of top software project can't pass whiteboard interviews.

2. I can't pass whiteboard interviews.

Therefore, they are stupid for not hiring me.

It strokes everyone's inner narcissist--why spend the hours on leetcode, they are stupid anyway.

i mean if had to choose between no graph theory vs no ruby on rails...i would probably go with no ruby on rails

What if you had to choose between someone with a proven track record of building high quality software used by millions of people who has also shown they're capable of leading groups of people in successful projects but hasn't memorized the specific algorithm you asked about and another candidate who doesn't have as good of a track record but can totally nail that easy algorithm you asked for?

Edit: Typos.

You think every candidate who comes in is like this. There are anomalies and outliers. The truth is resume padding is so common in the valley. Everyone can just say all these things. It's very hard to hire like this.

I don't work in SV. I assume it's like everywhere else where a potential employee who feels their skills are weak will take credit for things done by their teammates even if they were only tangentially involved.

My above comment was strictly related to the idea that DHH shouldn't be considered for a job over anther candidate who is an unknown quantity simply because DHH apparently is not good at algorithm problems in interviews.

Would you choose one-hit-wonder over proven engineers (Jeff Dean, Sanjay, other ex SUN microsystems folks?) that lead high-profile projects?

I know that sounds rude... but one seems better to be a leader while others are better engineers would you agree?

Total cop out answer but if DHH and people like Jeff Dean are both interviewing for a position with me you can be sure I'm doing everything I can to hire all of them. Even if it means starting entirely new departments.

I'd totally fanboy and hire Jeff though if it came down to just one though.

I don't mean to diminish/belittle DHH. What he's done (web framework, productivity SaaS, self-help books, sales/marketing, conference speakers, racing) it's not what Google does (web-browser, OS, AI, maps, search, scale, etc).

I also don't get why people like DHH is assumed to be a "miss" for not being hired by some of these company...

DHH is a unique individual with his own way of thinking. He wouldn't be DHH if he works for someone else (or under someone).

You don't generally hire people like that to work for you on something specific. You hire them with a very broad goal and give them the resources to accomplish the task how they see fit. With a bit of nudging here and there you should end up with a very marketable outcome wether it's a product or a prestigious research division or widely used piece of software that everyone knows is associated with your company.

What DHH does could absolutely be incorporated by Google. Angular => RoR, GCE => Saas, conference speakers => conference speakers.

Anyway the point is that even at a company like Google there's plenty of room for people that haven't memorized algorithms and data structures but companies that only interview on these sorts of things are missing out on them because they seemingly don't care or haven't figured out how to interview someone substantially different from what they normally hire.

SaaS != GCE.

I find the skillset required to build Basecamp differs greatly with building AWS/GCE portfolio (with over hundred different services that can be combined to deliver solutions for multiple ranges of companies...)

I don't think Google was looking for someone to build RoR or Angular. Those were merely side projects that came out once every few years. No offense but some of the key components of RoR were implementation of Martin Fowler's Enterprise Application Architecture patterns.

I wouldn't hire someone who cares so little about getting a job that he didn't spend the most basic amount of time studying for obvious questions that he was of course expected to be asked.

Such a situation would show me that he either does not care about getting the job, or is so arogent that he automatically expected that people who throw job offers at him.

That shows that this person has horrible personality problems and that I would not want to work with him, no matter how much he has accomplished in his life.

I didn't know about "BFS trees", do you have any references? I tried Googling but I could only find breadth-first searching (which I do know well, though apparently not the acronym BFS), but that's just a traversal algorithm.

BFS is "Breadth first search". One tree you would do this on is a BST or "Binary Search Tree". Probably OP got the acronyms mixed up.

There's actually a thing called BFS tree. It's a tree that depicts the order of node expansion/visitation when a graph is traversed BFS. Even I wasn't aware of it until I recently read Peter Norvig's AI book. However, I'm not sure if the author referring this.

Right, since I didn't pick up on the acronym I thought I had missed something. Cheers!