Package Dependency Resolver

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 (including the target) such that every dependency appears before the package that requires it. The problem extends into cycle detection and printing the dependency graph, including cycles, as bonus parts.

Interview Feedback

Feedback about Doctor Pangolin (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. Was able to also do a good job of walking through the code. From a technical perspective they were able to implement Kahn's topological sorting algorithm which was great!

areas of improvement:
initially had to be prompted for that extra edge case (albeit trivial)
added unnecessary logic to the if statement (again trust your loops!) one of the biggest signs interviewers look for is that do you understand all the edge cases present in the code
the solution itself for the topological sort was good but very convoluted and not necessary and took more time to implement, a much simpler approach would have been to implement DFS and reuse a majority of the code written for the first solution and change the queue to a stack.

advice:
always trust your loops!
first think what is the easiest solution I can pattern match the solution this interview question is asking for to. i.e. is this a variation of dfs, binary search, bubble sort etc... then think if something more complex is necessary. Doing this will save the interviewee time and help them get to more parts of the interview questions should they exist (and help them with the time management)

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? Yeah, I can hear you. Can you hear me? Yeah, I can hear you. Okay.
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? Actually, it got worse. It's a little further away right now. Testing, testing. Let me know if this is better.
Doctor Pangolin: I think it's about the same. I think it should be okay. Okay.
Spasmodic Sauce: Sorry about that. I don't know why.
Doctor Pangolin: This is running into some technical issues here, but— oh, hold on. Okay, how about now?
Spasmodic Sauce: Is this better? Yeah, that's great. Okay, great, awesome. Um, yeah, so kind of just, just diving right into it. Um, gonna do a problem today. It's gonna be a multi-part problem, but— Okay. Um, we're gonna get through as much as we can, and, you know, each part is gonna potentially build on the other. But so the— what we're trying to build is a package dependency resolver. And the way that this would work is if you have— oh, by the way, do you have a Here, I'll just actually write this out in plain text and then you can pick whichever language.
Doctor Pangolin: Yeah, Python. Okay, great. So same. So this should be pretty smooth to at least copy paste over, or actually let's just switch to Python right now. Okay, so we have this dependency graph, and so part 1 of the question is we basically want to build this function right here, which is the findDependencies. What this would look like is given a set of dependencies, we would like— let's say we have app, so then it points to a list of strings. In this case, API, UI, we would need API and UI to be installed before app does. For example, if we have something like this and we call it, We would expect results to be— a potential valid result to be something like this.
Doctor Pangolin: Okay. Does that make sense?
Spasmodic Sauce: Of like the order in which we need to install it?
Doctor Pangolin: Okay. And so, we do API and then database. Database has no prerequisites. So, then we can do auth and then UI. So, it's essentially the— package and then its dependencies. So everything that needs to be like its prerequisites essentially.
Spasmodic Sauce: Yeah, exactly.
Doctor Pangolin: That needs to be installed before it.
Spasmodic Sauce: Yes, yes, exactly.
Doctor Pangolin: Got it, got it, got it. Sounds good. So, so let me just make sure I understand this. So we have, um, we're given our dictionary of dependencies, which is mapping each of the packages to— you would call this a package, right? Like app, API, UI.
Spasmodic Sauce: Yeah. It could be multiply nested. For example, if you see API under app, the API package needs to be installed before app does. But if you look at the API package, database and database and auth package needs to be like installed first.
Doctor Pangolin: Right, right. Okay. And, and these can show up in different places as well. Like API can show up maybe in auth as well, potentially. Well, maybe not for this case, um, but like it's not necessary that one package just show up in like one other package's dependencies, correct?
Spasmodic Sauce: Yes, it can definitely show up in multiple packages.

Key Points of Implementation

1. Find Dependencies: Create a method find_dependencies(dependencies, target) that returns direct and indirect dependencies.
2. Installation Order: Develop another method install_order(dependencies, target) that produces a valid installation order based on the prerequisites.
3. Cycle Detection: Consider implementing logic to handle circular dependencies in the future.
4. Edge Cases: Check for scenarios such as empty dependencies or missing target keys in the dependency list.