This is just ridiculous. BFS is such a useful building block. If you're stubborn enough to not spend 10 mins on this the best of luck.
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?
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.
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.
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.
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.
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 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.
I wouldn't hire an electrical engineer who complained that he shouldn't have to know Ohm's Law, either.
...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.
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.
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.
These questions come up all the time. You just need to be proficient enough with algorithms to identify them.
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.
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.
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.
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/...
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-...
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.
doesn't everybody?
Sorry, past midnight here after a busy day at work :-P
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.
DHH's tweet https://twitter.com/dhh/status/1085987159406927872
Edit: Typos.
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.
I know that sounds rude... but one seems better to be a leader while others are better engineers would you agree?
I'd totally fanboy and hire Jeff though if it came down to just one though.
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).
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.
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.
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.
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.