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.
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.
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.
These questions come up all the time. You just need to be proficient enough with algorithms to identify them.
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.
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.
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-...
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.
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.
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.
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.
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?