I had a google virtual onsite round for their lateral hiring. The question I was giving was:
Let us say that there is a home and a saloon that you want to visit. You have a routes built in across. You need to check that if there is a route that exists that lets you visit the saloon.
For example: Here you have H which denotes your home and R is your route and S is your saloon.
H R R .
R . R .
. . R .
. . S .
I applied DFS and was able to solve this question.

Now there was a follow up to this question: Let us consider that at first there was no route between both of them. And slowly a route starts developing. How will you be able to check that out?
For example:
First:
H . . .
. . . .
. . S.

Second:
H . . .
. R . .
. . S .

Third:
H . . R
. R . .
. . S .

Fourth:
H . . R
R R . .
. . S .
and so on.
I tried a lot on this with different ways but I was not able to reduce its complexity down and my best complexity solution turned out to be naive one. Not able to optimise this was the reason why I got rejected later :(
Any idea how else could this have been solved?