[towaway1138]

I stumbled a bit on "write BFS" at a FAANG interview. The specific question was to write it for the Facebook friend graph. I just blurted out my reaction, which is that this was a terrible idea (given the space requirements). His response, "Well, pretend it's not.". Ugh.

[theamk]

Huh, what's terrible about it? BFS is exactly what I'd want.

Let's make up a synthetic problem, like "the closest friend which has property X". Then you'd first check all of your direct friends for X, then check friends-of-friends for X, then check friends-of-friends-of-friends for X, and so on. You'd go on forever until you either find a friend with property X, or run out of time/space.

This is the classic BFS problem, and I can see how it would make a good interview question.

[towaway1138]

It depends a lot on the specific question, and the connectivity of the graph, but in general, BFS can use space proportional to the size of the entire graph, which for the FB friend graph is huge. Even on a machine with a lot of RAM, you shouldn't assume this will work.

DFS or IDFS can generally use space proportional to the diameter of the graph, which is far smaller.

That caveat with BFS turns out to be so bad in practice that I've never seen the algorithm used in practice, outside of a classroom. And indeed, I first thought the point of the question was to elicit this complaint. The interviewer wasn't on that page, though.

The problem being asked was considerably more complex than "closest friend with property X". I don't recall the details, but perhaps it was something more like "find the ten shortest friend paths to (a unique but unknown) someone with property X, where those paths share no nodes".

[theamk]

Agree re "depends a lot on specific question", but the problem you specified still sounds very much like BFS, especially "shortest path" part.

My assumption for the Facebook graph would be that there is basically no way we can traverse it all, so your only hope is to find the path without expanding all the nodes. DFS will not work for that at all, but both BFS and IDFS may give you practical results.

This leaves the question of BFS vs IDFS, and that depends heavily on the details of the problem. For example, if the graph is already in RAM, then IDFS would be the best. But if the graph is not already in RAM, and you have to fetch it (from database or remote API), you'd definitely want the caching between successful IDFS rounds. And if you do that, then you might as well do BFS -- approximately the same memory performance, and much easier code.

As for usage, while BFS itself is not used this much, it's more advanced versions, Dijkstra and A*, are used all the time in graph traversals. For example, in many computer games, navigation apps and robotics planners.

(And back to original topic: if we had conversation like this during the interview, then you would likely get good score from me, even if I was fully convinced that BFS is the only way to go. After all, I am not testing for the specific bot of trivia -- I am testing for the ability to reason about algorithms)

[mcv]

> DFS or IDFS can generally use space proportional to the diameter of the graph, which is far smaller.

Maybe, but for "find the closest friend with property X" basic DFS is completely useless. It's likely to give you some distant rando with property X. Fast, sure, but not useful if you're looking for a friend.

Besides, if you have cycles in your graph, DFS also needs to keep track of which nodes you've already visited, or it's never going to end. Or use iterative deepening, which you probably want to use anyway to prevent ending up with some distant rando. Slower than BFS but consumes less memory.

> "find the ten shortest friend paths to (a unique but unknown) someone with property X, where those paths share no nodes".

Ah, but that's a completely different problem.

[towaway1138]

As above, "IDFS" == "iterative deepening DFS".

[mcv]

Yeah, I figured that out some time after I succeeded in digging through some old memory for the phrase "iterative deepening". It's been a while since I've had those classes. I do remember that at the time I didn't see the point in iterative deepening. Surely breadth first was faster than redoing the same work every time? But if you see it as a more memory-efficient way to simulate breadth-first through depth-first search, it makes sense.

Still, intuitively I'd expect that it depends a lot on the shape of your search space, the cost of your memory and the cost of traversing your network, which one is actually more efficient.

[towaway1138]

If you're generating nodes in an abstract graph (e.g., moves in chess), iterative deepening can be incredibly space-efficient, whereas BFS can rapidly consume an exponential amount of space.

As you point out, IDFS (or IDA*, etc) work far better if you have a means to avoid re-exploring the same nodes repeatedly.

Nonetheless, run-time can theoretically be greater, since you're iterating. Theoretically, though, each iteration will take N times longer than the prior, which means that the running time up to the final iteration doesn't matter that much (because it's such a small fraction of the total). The extra bookkeeping required by BFS can easily outmatch that in running time.

Definitely, it all depends.