Find the length of the longest path (directed graph)

Java Interview with a Meta engineer

Watch someone solve the longest path direct graph problem in an interview with a Meta engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Longest Path Directed Graph: Java Interview with a Facebook Engineer - YouTube

Interview Summary

Problem type
Longest Path Direct Graph
Interview question
Given a direct graph. n nodes 0 to n-1. Find the length of the longest path from all nodes.

Interview Feedback

Feedback about Stochastic Hurricane (the interviewee)
Advance this person to the next round?
Yes
How were their technical skills?
3/4
How was their problem solving ability?
4/4
What about their communication ability?
4/4

+: Strengths

+: TC can deal with ambiguity. They clarified the both important requirements: is graph cyclic and how graph is represented.
+: TC is good with data structures. TC comes up with optimal representation of adjustancy list for graph.
-: TC struggles with basic complexity analysis. TC could not talk about complexity of the DFS algorithm.
+: TC writes the modular code. TC wrote code with helper method of DFS.
+: TC can write code with good speed.
+: TC was able to change their solution for the follow up questions.
-: TC has basic testing skills. TC missed few good test cases.

Feedback about Red Maelstrom (the interviewer)
Would you want to work with this person?
Yes
How excited would you be to work with them?
4/4
How good were the questions?
4/4
How helpful was your interviewer in guiding you to the solution(s)?
4/4

That was a really good experience. His communication was good, he showed empathy/understanding and provided valuable feedback.

Interview Transcript

Red Maelstrom: Hey hi am I audible?
Stochastic Hurricane: Yeah. How's it going?
Red Maelstrom: Okay, I'm good. I'm good. How are you?
Stochastic Hurricane: Can't complain.
Red Maelstrom: Cool So basically 40, 45 to 50 minutes, focus on the coding problems. And last 10, 15 minutes, I will try to give you feedback, like, what could have been done better, or what I like and what you could keep doing?
Stochastic Hurricane: Cool. Sounds good.
Red Maelstrom: Yeah. So yeah, this is the first question. So basically, you have a directed graph. And you have to find the length of the longest path from all the nodes. So, for example, if you consider zero, you can go from zero to 1, 1 to 2, 2 to 3. So the length of the longest path originating from zero is three. And if you consider one, the length of the longest path originating from one is like one to two, two to three, so it's two. Similarly for two its, if length one, because we are just one is from two to three. There is no edge originating from three, that's why zero. And for four to three it's one, because you can go from four to three.

Stochastic Hurricane: Gotcha, that makes sense. And I'm trying to determine whether I should be worrying about cycles.
Red Maelstrom: That's a good problem. That's a good question. We can assume that for first part of this problem, we can assume that there are no cycles. It's a directed graph. And once we solve it, maybe we can introduce.

Technical discussion continues...

Feedback on Technical Skills