Python Interview with a FAANG engineer.
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 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. 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; 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 about what is the easiest solution I can pattern match the solution this interview question is asking for. 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 time management).
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. Uh, do you have a preferred 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: 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.
Doctor Pangolin: We have auth over here, which is in 2 packages.
Spasmodic Sauce: Exactly, right. So, the goal is here, though, to build the first— before we get into the ordering and stuff, actually, let's implement findDependencies where if I give you a package, we can go through and get the list of dependencies needed for that package. Does that make sense? And this would be like the raw skeleton here.
Doctor Pangolin: Uh, I'm sorry, so you're saying the first method we want to implement is this, find_dependencies method? Given this, uh, graph, we want to return all the dependencies for this, um, package?
Spasmodic Sauce: Yes, exactly. So, okay, yeah, for app you would have API, UI. Then also there might be nested packages. API has its own set of packages that we would need.
Doctor Pangolin: Not just the plain list, but we need to get all of those nested dependencies as well.
Spasmodic Sauce: Exactly. You got it.
Doctor Pangolin: Sure. What I'm thinking there then is we start with our root that we're searching for, not necessarily root, but our target package that we're searching for. And then we go through each of its dependencies. As we go through each of its dependencies, then we also look at all of its dependencies. And we're going to start adding these to a list. Does the order matter for this?
Spasmodic Sauce: Let's assume for right now the order doesn't matter.
Doctor Pangolin: Okay, sounds good. So then we would return all of its dependencies and we'd keep track of, um, like all of the dependencies we've already added so that we don't have a duplicated list. Um, and then when we have no more, uh, dependencies to explore, then we can just return the list of dependencies that we have. How does that sound?
Spasmodic Sauce: Yeah, that sounds good. Let's, uh, Let's write it up.
Doctor Pangolin: All right, so we're going to make this find_dependencies method which takes in dependencies and our target, I'll just call it.
Spasmodic Sauce: Okay.
Doctor Pangolin: All right, and we have— this is our map and this is our target. We're going to want to use some sort of queue, is what I'm thinking, to kind of go through each of these nested dependencies, like, go dive into each of these dependencies. So, we can first start with actually just the most basic, which is all of the dependencies in its list. So, we can go through— we can go through that. So, let's have our depend— Just gonna call it our result dependencies. It's gonna be our list. And we can also— you might actually wanna keep this as a set to start with. And we're gonna go through each of the dependencies in dependencies of target.
Spasmodic Sauce: Okay.
Doctor Pangolin: And we're going to want to add these to our set as well as add them to the queue that we are going to be searching through. All right. We can use a deque for that. And I think we'll have to import. From collections import deque. All right. And now we're gonna add these to both our set as well as our, as well as our deck.
Spasmodic Sauce: Okay.
Doctor Pangolin: I also want to ensure that in our dependencies list there won't be duplicates, correct?
Spasmodic Sauce: In our dependencies list, like the— there'd be, there'd be no unique, like, um, I guess let me— each key would be unique inside the dependencies.
Doctor Pangolin: Each key is going to be unique.
Spasmodic Sauce: Right, like we wouldn't have multiple entries for app.
Doctor Pangolin: And then in this list, for example, there won't be duplicates like API, for example?
Spasmodic Sauce: No, no, you don't have to worry about that, no.
Doctor Pangolin: All right, sounds good. So adding to our resultant dependencies set as well as our queue, and now we're going to go through our queue. So, while queue, we want to enqueue these dependencies that we have.
Spasmodic Sauce: Also, I may be highlighting parts of your code just for my own notes, but just don't, don't, don't be alarmed if you see me highlighting stuff.
Doctor Pangolin: Okay, got it. Also want to call this a package. So this is going to be like our list of packages, okay, essentially. And so then we're going to pop from our queue and we want to search all of its dependencies. So then we're going to do something very similar to this where we're going to go through all the dependencies in this map of package, and we're going to add it to our set. But also, we don't have to research. So if this is already— okay, I'm trying to think through the thought process behind having this resultant dependencies, because just because it's in the set doesn't mean that we have already explored it. So maybe we should not add to our resultant dependencies until after we have explored that.
Spasmodic Sauce: Nice, yeah, good catch.
Doctor Pangolin: Okay, so let's leave that until later. Once we pop it, then we can add this to our resultant dependencies. And then we're going to go through each of its dependencies. So for the dependencies in package, we're going to append each of them. And we only want to append it if it's not already in resultant_dependencies. So if p not in resultant_dependencies, then we're going to add that to our queue. All right. And then once we have nothing left, then we can just return a list of our resultant dependency set. Okay? So yeah, let's just do a quick run-through of this. We're given our dependencies list, we're given our target, we create a set of our resultant dependencies so that we can easily search through that and make sure we're not adding duplicate dependencies, and then we're going to convert it to a list at the end as we see here. We're going to have a queue for processing each of the packages. We're going to go through each of the dependencies for this target package and add them to our queue. We're going to process each element in the queue one by one, and we're going to append elements to the queue based off of its dependencies if it's not already in the resultant dependencies list.
Spasmodic Sauce: Right.
Doctor Pangolin: Okay. One thing I'm realizing is I didn't write any tests, so I guess I can do that right now. So, we're going to want to print find_dependencies(dependencies, app), as you wrote.
Spasmodic Sauce: Okay, let's test it.
Doctor Pangolin: If we were to do this, let me just do a dry run real quick first before executing this. With app, we're going to add— let me replicate these here. Those dependencies, and we're going to have our queue. All right, so with app, first thing we do is add in all of the dependencies of app, which is going to be API and UI. So it's going to be API and UI. One thing I'm also noticing right now is that it might be possible that there was a dependency like app, for example, that comes later on in the list. Like maybe API might call auth, which might be a circular dependency, which would mean that this is not possible to resolve. Is that something we want to worry about for this part?
Spasmodic Sauce: For part 1, let's not worry about cycle detection right now.
Doctor Pangolin: Okay, got it. So resultant dependencies will be API and UI. That's going to be added to our queue, not to resultant dependencies. Okay, and then we go through our queue, we're gonna pop, so package is gonna be API, resultant_dependencies.add package, which is going to be API. And then we're gonna go through all the dependencies of package, which is gonna be database and auth. Neither of those are in resultant_dependencies, so they're gonna get added to the queue.
Spasmodic Sauce: Okay.
Doctor Pangolin: What was it? Something database and auth. Database and auth. And again, API is removed. All right, so then moving forward, we pop the next one. Packages UI. UI is added to our list. This is popped. We go through all the dependencies of UI, which is just auth. Auth is not in resultant dependencies, so it gets added, which means that we're going to have a duplicate in our queue, which could potentially be fine. Let's go through.
Doctor Pangolin: Let me note that we can keep a visiting set. We can separate a visiting set so that we can make sure that we don't add multiple duplicates onto the queue. Okay, does that make— yeah, does that make sense?
Spasmodic Sauce: Yeah, yeah.
Doctor Pangolin: So instead of resultant dependencies, which would be visited, we can keep this as a list and then keep visiting as our set.
Spasmodic Sauce: Okay.
Doctor Pangolin: Okay, so resultant dependencies .append, and then this will be visiting. And whenever we add to a— the queue, we're going to add it into visiting. visiting.add(dependency). And we're going to add that same line here. Okay, so then in that case, auth would not be added here. Coming back to the example here, so UI is added. What was it? Auth and database and auth of API were added. Then auth of UI was added. But in this case, it would not be added. Then we would move on to the next one, which is database. Database gets popped. Comes here to add it to our list. And then, uh, what are the dependencies of database? There are none. So then that's fine, nothing is added. And finally, we pop the last thing, which is auth. Auth, what are auth's dependencies? None. So that is the end of the list, and we should return, uh, all 4 of these. So, let us see if that is what happens.
Spasmodic Sauce: Okay, yeah, let's test it. All right, auth, API, database. Nice. Okay, cool.
Doctor Pangolin: Great.
Spasmodic Sauce: This was, this was a good first implementation. Um, so quick, before we move on to part 2, there's some quick follow-up questions I wanted to ask. Can you think of some potential edge cases here? Like, what are some things that we— that might— that may happen, and does your code account for all of them? So, uh, yeah, sure.
Doctor Pangolin: So one thing that I'm thinking about is, um, like, we don't know what the structure of dependencies would be. It might be possible that this target package does not even exist in dependencies. Um, so for example, if we have just an empty map over here, this, this would give us an error currently, give us a KeyError right over here. So instead what we can do is that we can, we can add a quick check and make sure that if that package does not even— if that target does not even exist in dependencies, and then just return like an error or something.
Spasmodic Sauce: Yeah, that makes sense to me.
Doctor Pangolin: Another thing is that—
Spasmodic Sauce: Um, let me pause you right there. Where, just to make sure for completion, uh, where would you add that check?
Doctor Pangolin: Oh, um, yeah, we could add that even like as a first line within the find_dependencies. Should I write it real quick? Yeah, um, yeah, you can do something like that. Um, so, or we can also just do if not dependencies, dependencies, or target not in dependencies, and we can just return something like an empty list, for example.
Spasmodic Sauce: Yeah. Okay.
Doctor Pangolin: So this handles cases where we have no dependency list or cases where this target package doesn't exist in our dependency list. Okay, great.
Spasmodic Sauce: Any other edge cases you can think of?
Doctor Pangolin: So, there's going to be no duplicate keys in our dependency list. Um, the keys are as expected. Uh, and you said this, this key will not exist within its own dependencies.
Spasmodic Sauce: Um, right, let's not worry about cycles. There's still one potential edge case here.
Doctor Pangolin: Okay. Maybe if we're given like an empty target, that could be something that we have to like handle. So for example, if not target as well, then we could also return an empty list.
Spasmodic Sauce: Okay, so you're in this case, the— if the empty target, if you get an empty target, your second case, your second check, the target not in dependencies, will We'll automatically catch that. So, you've already accounted for that.
Doctor Pangolin: Okay.
Spasmodic Sauce: So, that first part of that code is actually redundant and not necessary.
Doctor Pangolin: Okay. That makes sense. Another edge case. So, you have dependencies and we have target. Target is guaranteed to be a string. Dependency is going to be a string mapped to a list of strings.
Spasmodic Sauce: Um, it is very— just to give you a quick hint, it is very similar to that first check that you did. What do you think could potentially be something else we should check while we're traversing the dependency graph?
Doctor Pangolin: Oh, that like one of these nested dependencies does not exist within the graph?
Spasmodic Sauce: Exactly. Bingo.
Doctor Pangolin: Okay. All right. So, where would we do that? If— right over here, dependencies of package. Okay, so if package does not exist, if package does not exist in dependencies, then we want to return an empty list as well. Do you want me to write some tests for each of these?
Spasmodic Sauce: Yeah, let's write a test for the second one. Yeah, let's write a test for that edge case that I mentioned.
Doctor Pangolin: This one over here?
Spasmodic Sauce: Yes, yes.
Doctor Pangolin: Okay, let me copy this dependencies map and change it up a little bit. Parentheses 2. And so, what we want to do is just mention one package that does not exist in, in the list, which would be something like that. Okay. And then we can try this and that should return the empty list. And currently it is not— it is returning like a full list, not an empty list. So let me change this to dependencies 2. Okay, now it's working as expected.
Spasmodic Sauce: So you still would want that even though that dependency is not on this dependencies list, we would still want to add it, right?
Doctor Pangolin: Uh, you're saying that even because this, like, IP package does not have any— like, it's not in this list, we still want to—
Spasmodic Sauce: Yes, let's say we want to still add it. What would be the, the logic change here?
Doctor Pangolin: Okay, in that case, then we would just continue over here and not explore its dependencies. So instead of a return, we could have like a continue.
Spasmodic Sauce: Okay, so let's run it, run the code again.
Doctor Pangolin: Let's see what we— okay, and we want this to show up as well, like we want IP to show up as well?
Spasmodic Sauce: Yes, we do.
Doctor Pangolin: We want to ignore it. Okay.
Spasmodic Sauce: No, that's great. Okay. Yeah, okay. This is a pretty good working solution. Okay, awesome.
Doctor Pangolin: Great.
Spasmodic Sauce: Good job. Let's move on to the second question. So just taking notes here. The next part that we want to do is we want to basically 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. We want to include each package exactly once and each dependency must appear before the package requiring it. And then also you can assume that there's like, like no cycles here, but this is kind of roughly the shape that we would want.
Doctor Pangolin: Um, so, okay, let me read this real quick.
Spasmodic Sauce: Yes. Great.
Doctor Pangolin: So, okay, we have the same parameters, same return, uh, but this time the order matters and I want to include the target, which is the first package, um, or not the first package, but target is— yeah, target. Include all direct and indirect. Indirect meaning like nested dependencies, correct?
Spasmodic Sauce: Yes.
Doctor Pangolin: Okay, include each package exactly once, so no duplicates. Every dependency must appear before pack the package requiring it. So the installation order is what matters here, and you may assume there are no cycles. Okay. All right. Okay.
Spasmodic Sauce: So how would we go about implementing this?
Doctor Pangolin: Okay. Um, Okay, API and UI. All right, so what I'm thinking here is that we can— well, first let me look at the first solution and see what went— like, why this solution won't work. So we have our dependency for app, which is API, UI. API's dependencies are database and auth. UI's are just auth. And then auth has no dependencies. So, like, a viable order for this would have been auth first, database— I'm also on the top line 14. Auth first, then database.
Spasmodic Sauce: Oh, okay.
Doctor Pangolin: Okay, yeah, then UI, for example, then API, and that would be our— and then we would do app. Is that the, like, a correct installation order?
Spasmodic Sauce: That should be. I listed the one in the bottom, but it should be—
Doctor Pangolin: Oh, okay, I see now. Database, auth, API, UI. Yeah, looks— yeah, looks like both of these work. Let me just copy that down here. So yeah, so we want to be able to put the packages that have no dependencies first in our installation order. Then from there, we can add in all of the packages that were dependent on these packages. So what we can do is that once we have our, our list of packages, which we can get from our find_dependencies, find_dependencies method, what we can do is track the— okay, here, let me write this out. Auth, database, UI. How did I choose auth and database first? Because we first started with app. Then I went into API, I saw all of API's dependencies, which are database and auth. Then I went into all of database and auth's dependencies, which were just nothing, for example. And then we looked at UI, which had auth. Okay, so from the find_dependencies method, we get a comprehensive list of all of the dependencies excluding target. So we have to add target to that list. Now we have a list of all of the packages that we need to order. Now we can see all of the dependencies of each of the packages that we need to order. By calling this find— like dependent— by calling this dependencies map and getting the length of the list. So that way we know how many dependencies each package has. From there, we can queue up all of the packages which have no dependencies and to have those first in our ordering. From there, we can start to create a sample, like, installation order or a viable installation order and only enqueue packages or, like, child dependencies of packages when their dependency list shrinks to 0. And we're going to mark the dependency list not by using the entire list, but just by keeping a count. So we can keep a count of all the dependencies, and we can decrement that count based off of when we process one of that package's dependencies. Okay, let me write that out a little bit now. So, what we're going to do is we're going to get dependencies list. We're going to map each dependency, dependency to its count of dependencies. We're going to call this, uh, like in-degree. Then we're going to enqueue all packages with no dependencies, go through the queue, and we're going to, um, decrement the in-degree of packages with this package as a dependency.
Doctor Pangolin: Okay, but how are we getting this? How are we going to be able to decrement the in-degree of packages with in-degree of children of this package? Like, for example, if we process database, how do we know that API is in database? Sorry, that database is in the API dependencies. So, what we can do also before that is create a reverse mapping. of dependencies to what they are dependent on. Is that a good way of putting it?
Spasmodic Sauce: Mm-hmm.
Doctor Pangolin: Create a mapping of dependencies to their predecessor. I guess we'll call it predecessor. No, that's not a good way of putting it. This is a package and this is its dependency. So maybe we could call it like parent or something like that. So we're also going to have to do that, create parent mapping where we map dependencies to their parent— parents to all their parents. Is it parents or children? Database has no dependencies, but API is dependent on database. All packages map dependencies to all packages dependent on them. Okay, so it'd be more like a children mapping, mapping dependencies to packages that are dependent on them.
Doctor Pangolin: Okay, so we go through this queue, we're going to decrement the in-degree of the packages with in-degree of children of this package, children of this package using our child mapping. And then we're going to enqueue— actually, we're just— this, this part comes down here. Enqueue all— no, no, this is separate. This is the queue part. And then we're going to enqueue packages or child packages if their in-degree drops to 0. Okay, and then by the end we're going to get our final mapping from there. How does that sound? I know I was going on for a bit.
Spasmodic Sauce: Um, no, okay, let's see. This is an interesting approach. Let's, um, can you— so given the example above, can you walk through like the pseudocode that you wrote and see and kind of just showcase to me how it would work?
Doctor Pangolin: Yeah, sure. So first things first, we're going to like take all of the dependencies. Oh, actually, this, this comes first. We're going to get our dependencies list of app. So, that's going to be our comprehensive list of each of the— here, let me just copy this right here. Get dependencies, this is going to return this. And then we have to add target, which is going to be app. Okay.
Then we're going to create a children mapping where we map each of these dependencies to the packages that are dependent on them. So, UI is going to be mapped to app, auth is going to be mapped to— let me just correct this here— to app. Then, we're going to have auth is mapped to API and UI. Oops. API and UI. And then we're going to keep track of the in-degree. We map each dependency to its count of dependencies. So same thing as, as here. So database is going to be 0, auth is going to be 0, UI is going to be 1. API is going to be 2, and so on. And now we're going to enqueue all packages with no dependencies. We're going to start with database and auth. Go through the queue, we're going to decrement the in-degree of all the children of this package. So then when we look at database, what does database map to? Well, database maps to API. So now API has 1 remaining. So this 2 is going to go to 1. Did that make sense over there?
Spasmodic Sauce: Um, this maps to 1.
Doctor Pangolin: Wait, can you go through this one more time?
Spasmodic Sauce: Sorry, I just want to make sure I'm following.
Doctor Pangolin: Yeah, sure. Sure. So we go through the queue, right? So first thing is database, and we look at the, um, the packages that are dependent on database, which would just be API. Like, for example, over here, this would be database maps to API.
Spasmodic Sauce: Okay.
Doctor Pangolin: And then API's in-degree would drop to 1, which would mean that it still has one more dependency needed before it can be enqueued before it can be enqueued. So that's not explored. Instead, we go to the next one. So then now we just have auth in our queue. From auth, we are going to decrement UI. So UI is going to become 0, and then API is going to become 0. So now both of these, UI and API, are going to become enqueued. And then we look at all of their dependencies and all their dependencies and so on, and that should create the ordering.
Spasmodic Sauce: Okay, this makes— this seems reasonable. Let's, uh, let's implement this.
Doctor Pangolin: Okay, sounds good. So let me go ahead over here. This is going to be installation_order. It's going to take in— it's going to take in dependencies and a target. Dependencies and target. All right, first thing is that we get our dependency list, so dependencies_list equals get— we can just call it the method that we used, find_dependencies, find_dependencies(dependencies, target)— and then we're going to add target itself.
Okay. Um, so that is our list. Now we have to use this list and map it. So we have to create the child mapping, map each dependency to documents dependent on it.
Spasmodic Sauce: Okay.
Doctor Pangolin: So, we can do this by going through each of the dependencies. Okay, let me copy this here.
Spasmodic Sauce: Just letting you know, we have roughly about 8 to 9 minutes left. So, yeah, just continue.
Doctor Pangolin: Got it. All right, children is going to be this. We're going to go through for dependency in dependencies_list. And there should be a key for each one. But for each dependency, we're going to go through our dependency map for that dependency.
Spasmodic Sauce: Okay.
Doctor Pangolin: And then we're going to add that child to the children map. So children of dependency equals or children of map dependencies to all the packages dependent on them. So this child, which should really be parent, dot append the dependency itself. So this will point all of these. So UI will point to app. API will point to app. Okay, that makes sense.
Now we have to get our in-degree. So degree is also going to be a map, and we're going to go through the same thing here where we're going to go through the Actually, we can just get the list, so we can do in-degree[dp] = len(dependencies[dp]). So this will get the length of that dependency list and set it equal to the in-degree for that dependency. That is good.
Next, we're going to— we also have to keep track of our queue, and we're going to want to— we can do it in this step over here where we append to our queue if the in-degree equals 0. So if in-degree == 0, equals 0, and we can just append that package. All right, so now we start off with all of our— like, our queue is seeded with these 0 dependency packages. And then we're going to go through our queue. We also have to have our result list, which is going to be install order. And then when we pop from our queue, we're going to add to the install order.
And in the end, we're going to return our install order. All right, so while queue, we're going to pop from our queue. So package is going to be queue.pop_left. I just realized that above I did not use pop. I used— I mean, I didn't use pop_left, I used pop, which likely caused that, um, discrepancy in ordering. Let me just change that real quick.
Spasmodic Sauce: Yeah, okay.
Doctor Pangolin: Okay, so package equals queue.pop_left, and then we're going to add this package to our to our install order. install_order.append(package). Okay. And then we are going through each of the children of this. Go through the queue, decrement the in-degree of all the children of this package. So So, we're going to go through, so for child in children of package, in-degree[child] -= 1. If in-degree[child] equals 0, then we're going to want to add it to our queue. Okay, and then yeah, I think that should handle going through the rest. And yeah, let me try this with a quick test case just to make sure there's nothing— hello?
Spasmodic Sauce: Oh, sorry. Yeah, whoops, just It just disconnected for some reason. I'm back.
Doctor Pangolin: Okay. Yeah, sounds good. I'm just gonna run a quick test for this to make sure there's nothing crazy out of order. Let me just copy a test from above. Print installation_order(dependencies, app). All right. Okay, so we have an exception here, KeyError database.
Spasmodic Sauce: So yeah, what's this issue?
Doctor Pangolin: All right, so in our child, this is on line 134, 115. All right, so What we're doing here is we're creating that child mapping. We're mapping all dependencies to the packages dependent on them. Okay, so we go through all of the— I'll just call this packages. We're overusing dependencies. For each package in dependency_list, we look at the dependencies of that package. And then we map those to this. Okay, we can just use a default dict of list. Okay, and—
Spasmodic Sauce: Okay.
Doctor Pangolin: Over here I can do the same thing. Default— actually, that one should be okay. All right. 15 over here. And package. Okay, so this is printing the order database, uh, auth, API, UI, which is a valid installation order for this. Okay, so should we try some other test cases?
Spasmodic Sauce: Yeah, what are some other edge cases here?
Doctor Pangolin: Okay, so one other edge case could be, um— Hello?
Spasmodic Sauce: Yeah, I'm still here.
Doctor Pangolin: Okay, yeah, I accidentally exited out. Okay, so you asked about other edge cases, right? So another edge case could be where we have kind of like what we were talking about before. So there could be apps, like there could be target packages with no dependencies, meaning like, like we have an empty dependency map, or we can have an empty, um, yeah, an empty result. So actually what we can do is we're calling this function findDependencies, so we can also work from there and see that if this list is empty, then we're just going to want to return the target itself, which actually might not be true.
Spasmodic Sauce: Right.
Doctor Pangolin: Because it could depend that— it could be valid that an app has no dependencies on it, in which case we would just want to return the app itself. Okay. So, what we can do is that If dependencies[target], so that means that there are dependencies, and not dependencies_list, which means that this returned null, then we're going to want to return an empty list.
Spasmodic Sauce: Sure, okay.
Doctor Pangolin: Okay, um, otherwise If we can also just do this, like, if not dependencies[target], then we can just return target like that.
Spasmodic Sauce: Okay, no, this is good. This is a good working solution. Uh, I think we're gonna pause here and just talk about, like, I guess, some high-level like ideas and then get some feedback and then, yeah, conclude the interview. But this was good. This was actually a very nice implementation of, I believe it's Caine's algorithm, but—
Doctor Pangolin: Yeah.
Spasmodic Sauce: Or Kahn's topological sort algorithm. But this is good.
Doctor Pangolin: What would you expect the runtime to be here?
Spasmodic Sauce: Oh, for this installation order method?
Doctor Pangolin: Yes.
Doctor Pangolin: I believe it would be O. You explore all the vertices and edges between dependencies.
Spasmodic Sauce: Okay, yeah, that makes sense. And what about space complexity?
Doctor Pangolin: Okay, space restoring My bad, I exited again. You asked about the space complexity, right?
Spasmodic Sauce: Yeah.
Doctor Pangolin: So each of these, I think it's going to be V plus E as well.
Spasmodic Sauce: Yeah, that tracks.
Doctor Pangolin: So we don't have to implement this part, but I just wanted to get a sense of how you would think. Um, what is the— like, if you were to track, if you were to calculate cycle detection, how would you go about doing this? Again, we don't have to implement this, we can just talk this part out loud.
Doctor Pangolin: Yeah, so the key thing with cycle detection is that we are visiting a node which, um, which has like— are you talking about specifically for, for this algorithm or for the previous method?
Spasmodic Sauce: No, for this one.
Doctor Pangolin: Uh, like let's say if you get into a situation where, um, like one of the packages, uh, downstream, uh, needs like another package upstream.
Doctor Pangolin: Right, right, right. Um, yeah, I think the thing there is that we could keep track of a visiting set which would show us which, um, which dependencies are currently being explored. And if we have to revisit a dependency that has already like been explored, then we know that like that's already being explored. Then we can tell that there's a cycle going on there.
Spasmodic Sauce: Right. So then you would need to basically keep track of, you know, in this current path that you're exploring, what has already been explored down this, this current traversal.
Doctor Pangolin: Right.
Spasmodic Sauce: Okay, great. Yeah, this is good. So just some meta feedback here. Yeah, you did well. I think the first solution, the way you implemented it, was great.
The way you were able to think about edge cases and get to a working solution, all solid. I know that that second edge case, uh, you were implement— you were able to implement the, the, you know, the fix relatively quickly. I did have to prompt a little bit, but again, not like— still great, like, and not like a big issue there.
Spasmodic Sauce: Again, this Kahn's topological sort algorithm that you implemented, the fact that you got to a working solution here is very impressive, and you were able to think through the edge cases. And even when I was asking you questions about cycle detection, you were able to, you know, answer like where you would implement them. And again, I think for many tech companies, um, like you're able to— as long as you can get through the meat of the problem and answer kind of like the follow-ups about like where you would update your code, I think that would be like, that's like kind of what, what is all required at least from all the times that I've done interviews at some of these FAANG companies. Um, so again, that's great.
I think one piece of constructive advice here is that this installation order solution, again, great that you were able to implement this, but there's actually a much simpler solution here that you can directly leverage.
Doctor Pangolin: Mm-hmm.
Spasmodic Sauce: Which is, uh, just plain DFS. So if you actually just like, you know, have like— instead of using like a queue, and very similarly to your first method, instead of using a queue, if you use a stack, like it would effectively get you the right order and like would be— would take a lot less implementation time. So like in this case,
Doctor Pangolin: Mm-hmm.
Spasmodic Sauce: You would be able to get through part 2 and then also potentially have a solution for part 3 where you would definitely be a, like, a shoo-in for getting into the next round.
I think, you know, again, this is not— I'm not saying this more as like your solution is wrong or you took a wrong approach. I think it's like, had you had gone to that, it, it literally is almost not verbatim, but like a one-line change from your first solution of like, instead of using a queue, if you use a stack, like being able to be—
Doctor Pangolin: Oh, okay.
Spasmodic Sauce: You know, like as long as I keep appending to the top of the stack of any of the dependencies that I see, anything that comes after it, we would have to basically take off the stack first anyways. Does that make sense?
Doctor Pangolin: Yeah, that makes sense. I should have probably tried to talk about the trade-offs between BFS and DFS. Maybe that could have helped.
Spasmodic Sauce: Yeah. Again, just to make sure, you did well, but I think if you had, you like thought about kind of this like, okay, do I need to implement a little bit more of, you know, like a more technically savvy solution when the problem potentially has an easier solution where it's like you can literally leverage that code that you wrote for your first one and then change like, you know, the queue part to a stack and it would effectively have like the same result.
And I encourage you to try it, you know.
Doctor Pangolin: Mm-hmm.
Spasmodic Sauce: After, um, and, you know, get us to the desired result. And then when you can land that piece, then we can go into part 3 and part 4 of the problem where, you know, can get you bonus points with, with the interviewer, right?
Doctor Pangolin: Yeah, got it, got it.
Spasmodic Sauce: But yeah, great stuff. Any questions for me before we end the interview?
Doctor Pangolin: Um, anything else stand out to you, like coding quality-wise, or like anything else that, like me specifically, you think that I would benefit from?
Spasmodic Sauce: I— sorry, the mouse is sensitive. I'm back. Sorry, you were asking?
Doctor Pangolin: Yeah, I was saying, um, like, what, what did you— like, what were you able to tell from me?
Like, what do you think that I need to focus on?
Um, maybe like coding-wise, or like, yeah, for the variables and all that stuff. I know I kind of like— my thought process, even talking through dependencies, packages, like, like, uh, interchanging those 2 terminologies. Like anything that felt kind of sloppy or anything like that?
Spasmodic Sauce: Yeah, yeah, very good question. I'm glad that you're, you know, I think a lot of folks won't ask that type of question.
I think from your code quality perspective, I think for the most part it's pretty readable. I would avoid, you know, I think when you are getting into like abbreviations and stuff like that where it's like, like you're using the letter Q and like obviously Q stands for queue, so it's like fine, like I think the way you named your variables and the way you wrote your comments, everything is fine. I don't think there's anything there.
I think for any block of code that you write, underneath the while loop, I think maybe having just a one-line statement of, hey, this is what I would expect to kind of do, or this is kind of what we expect here, being like, okay, walk through queue here, or something like that.
I think it's just a very easy way for like the interviewers to kind of follow along of like what is like the chunk of like the function that you're working on currently.
The one piece of advice that I did see, like your initial check around for your first function of like if not dependencies or target not in dependencies, where like what happens if like the target doesn't exist? Like again, right, like not a huge deal breaker, but like when you initially added that first check of like if not target or not dependencies, or like, I think like your or target not in dependencies case would have solved that, right?
Doctor Pangolin: Right.
Spasmodic Sauce: So, it's like there's no need to bloat up like the if statement when you're like— I think you should use if statements sparingly because they can oftentimes really like add a bunch of like branches to the code that are not necessary.
Um, so, you know, I, I think in that case, if you had read it through and being like, okay, like does this check already account for it or do I need to add it? I think that's something that I would say is something that maybe you could work on.
Doctor Pangolin: Got it.
Spasmodic Sauce: But yeah, I think everything else, like your comments beforehand, your code quality, I think that's fine. The fact that you were able to reuse the same function, you know, from part 1 and part 2, I think is also a great signal.
Yeah, I think what I could tell about you, if I had to guess, I would say you're probably past the entry-level engineering bar, maybe around the mid-level engineer.
Doctor Pangolin: Nice, great. Yeah, that's kind of what I'm targeting too. So yeah, that's a good read and like that's kind of reassuring to know that I'm kind of fitting in that range.
Spasmodic Sauce: Right, absolutely. And again, like a senior engineer, last piece of advice, like would probably have implemented like the DFS or like the DFS algorithm right away and kind of could have saved them some, some time. But that's, I guess that's how you level up and, and, and get better, right?
Doctor Pangolin: Yep, yep, got it.
Spasmodic Sauce: But yeah, great stuff. Any questions for me before we end the interview?
Doctor Pangolin: Um, anything else stand out to you, like coding quality-wise, or like anything else that, like me specifically, you think that I would benefit from?
Spasmodic Sauce: I— sorry, the mouse is sensitive. I'm back. Sorry, you were asking?
Doctor Pangolin: Yeah, I was saying, um, like, what, what did you— like, what were you able to tell from me?
Like, what do you think that I need to focus on?
Um, maybe like coding-wise, or like, yeah, for the variables and all that stuff. I know I kind of like— my thought process, even talking through dependencies, packages, like, like, uh, interchanging those 2 terminologies. Like anything that felt kind of sloppy or anything like that?
Spasmodic Sauce: Yeah, yeah, very good question. I'm glad that you're, you know, I think a lot of folks won't ask that type of question.
I think from your code quality perspective, I think for the most part it's pretty readable. I would avoid, you know, I think when you are getting into like abbreviations and stuff like that where it's like, like you're using the letter Q and like obviously Q stands for queue, so it's like fine, like I think the way you named your variables and the way you wrote your comments, everything is fine. I don't think there's anything there.
I think for any block of code that you write, underneath the while loop, I think maybe having just a one-line statement of, hey, this is what I would expect to kind of do, or this is kind of what we expect here, being like, okay, walk through queue here, or something like that.
I think it's just a very easy way for like the interviewers to kind of follow along of like what is like the chunk of like the function that you're working on currently.
The one piece of advice that I did see, like your initial check around for your first function of like if not dependencies or target not in dependencies, where like what happens if like the target doesn't exist? Like again, right, like not a huge deal breaker, but like when you initially added that first check of like if not target or not dependencies, where like, I think like your or target not in dependencies case would have solved that, right?
Doctor Pangolin: Right.
Spasmodic Sauce: So, it's like there's no need to bloat up like the if statement when you're like— I think you should use if statements sparingly because they can oftentimes really like add a bunch of like branches to the code that are not necessary. Um, so, you know, I, I think in that case, if you had read it through and being like, okay, like does this check already account for it or do I need to add it? I think that's something that I would say is something that maybe you could work on.
Doctor Pangolin: Got it.
Spasmodic Sauce: But yeah, I think everything else, like your comments beforehand, your code quality, I think that's fine. The fact that you were able to reuse the same function, you know, from part 1 and part 2, I think is also a great signal.
Yeah, I think what I could tell about you, if I had to guess, I would say you're probably past the entry-level engineering bar, maybe around the mid-level engineer.
Doctor Pangolin: Nice, great. Yeah, that's kind of what I'm targeting too. So yeah, that's a good read and like that's kind of reassuring to know that I'm kind of fitting in that range.
Spasmodic Sauce: Right, absolutely. And again, like a senior engineer, last piece of advice, like would probably have implemented like the DFS or like the DFS algorithm right away and kind of could have saved them some, some time. But that's, I guess that's how you level up and, and, and get better, right?
Doctor Pangolin: Yep, yep, got it.
Spasmodic Sauce: But yeah, great stuff. Any questions for me before we end the interview?
Doctor Pangolin: Anything else stand out to you, like coding quality-wise, or like anything else that, like me specifically, you think that I would benefit from?
Spasmodic Sauce: I— sorry, the mouse is sensitive. I'm back. Sorry, you were asking?
Doctor Pangolin: Yeah, I was saying, um, like, what, what did you— like, what were you able to tell from me?
Like, what do you think that I need to focus on?
Um, maybe like coding-wise, or like, yeah, for the variables and all that stuff. I know I kind of like— my thought process, even talking through dependencies, packages, like, like, uh, interchanging those 2 terminologies. Like anything that felt kind of sloppy or anything like that?
Spasmodic Sauce: Yeah, yeah, very good question. I'm glad that you're, you know, I think a lot of folks won't ask that type of question.
I think from your code quality perspective, I think for the most part it's pretty readable. I would avoid, you know, I think when you are getting into like abbreviations and stuff like that where it's like, like you're using the letter Q and like obviously Q stands for queue, so it's like fine, like I think the way you named your variables and the way you wrote your comments, everything is fine. I don't think there's anything there.
I think for any block of code that you write, underneath the while loop, I think maybe having just a one-line statement of, hey, this is what I would expect to kind of do, or this is kind of what we expect here, being like, okay, walk through queue here, or something like that.
I think it's just a very easy way for like the interviewers to kind of follow along of like what is like the chunk of like the function that you're working on currently.
The one piece of advice that I did see, like your initial check around for your first function of like if not dependencies or target not in dependencies, where like what happens if like the target doesn't exist? Like again, right, like not a huge deal breaker, but like when you initially added that first check of like if not target or not dependencies, where like, I think like your or target not in dependencies case would have solved that, right?
Doctor Pangolin: Right.
Spasmodic Sauce: So, it's like there's no need to bloat up like the if statement when you're like— I think you should use if statements sparingly because they can oftentimes really like add a bunch of like branches to the code that are not necessary.
Um, so, you know, I, I think in that case, if you had read it through and being like, okay, like does this check already account for it or do I need to add it? I think that's something that I would say is something that maybe you could work on.
Doctor Pangolin: Got it.
Spasmodic Sauce: But yeah, I think everything else, like your comments beforehand, your code quality, I think that's fine. The fact that you were able to reuse the same function, you know, from part 1 and part 2, I think is also a great signal.
Yeah, I think what I could tell about you, if I had to guess, I would say you're probably past the entry-level engineering bar, maybe around the mid-level engineer.
Doctor Pangolin: Nice, great. Yeah, that's kind of what I'm targeting too. So yeah, that's a good read and like that's kind of reassuring to know that I'm kind of fitting in that range.
Spasmodic Sauce: Right, absolutely. And again, like a senior engineer, last piece of advice, like would probably have implemented like the DFS or like the DFS algorithm right away and kind of could have saved them some, some time. But that's, I guess that's how you level up and, and, and get better, right?
Doctor Pangolin: Yep, yep, got it.