Package Dependency Resolver

Watch someone solve the the problem: package dependency resolver problem in an interview with a FAANG engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Package Dependency Resolver: Python Interview with a FAANG Engineer

Interview Summary

Problem type
The Problem: Package Dependency Resolver

Interview question
Given a dictionary mapping packages to their list of required dependencies, implement two functions: one that returns all direct and indirect dependencies for a given target package, and a second that produces a valid installation order that includes the target, lists each package exactly once, and places every dependency before the package that requires it. Later parts of the problem cover cycle detection and printing the full dependency graph, including cycles.

Interview Feedback

Feedback about Doctor Pangoli (the interviewee)
Advance this person to the next round? Yes

How were their technical skills?
4/4

How was their problem solving ability?
3/4

What about their communication ability?
4/4

Strengths:

• Was able to get to a working solution for both part 1 and part 2.
• Was able to think about the edge cases afterwards and test them and fix parts of the code well.
• Did a good job of writing clean code and articulating their thought process, especially with the code comments and writing out their logic beforehand.

Areas of improvement:

• Initially had to be prompted for that extra edge case (all-be-it trivial).
• Added unnecessary logic to the if statement (again trust your loops!).
• The solution for the topological sort was convoluted and could be simplified.

Advice:

• Always trust your loops!
• Consider the simplest solution first.

Feedback about Spasmodic Sauce (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

Interview Transcript

Spasmodic Sauce: Hello?
Doctor Pangolin: Hello, can you hear me?

Spasmodic Sauce: Great. Uh, how's your day going so far?

Doctor Pangolin: Pretty good. Uh, your voice is a little hard to hear.

Spasmodic Sauce: Okay. Is this better?

...

Doctor Pangolin: All right, sounds good. So then we would return all of its dependencies and keep track of all dependencies added so that we do not have a duplicated list.

...

Spasmodic Sauce: Okay. One thing I'm realizing is I didn't write any tests, should I do that right now?

Doctor Pangolin: Uh, sure.

...

Installation Order

The next part that we want to do is to produce an install order. Given a list of the dictionary mapping of the dependencies and the target, we want to make sure that we include all direct and indirect dependencies.

Algorithm Overview:

• Create a mapping of every dependency to its child dependencies.
• Track the in-degree counts for each package based on how many dependencies they have.
• Use a queue to process through each level of dependencies ensuring we respect the order.

Edge Cases

• Misconfigured dependencies.
• Packages that reference themselves.

The final result should provide the comprehensive list of installation order of packages.

Conclusion

Overall, the interview went well, and the candidate demonstrated a good grasp of dependency resolving tasks. Further iterations could refine the approach using DFS to simplify the install order generation.