Understand what the interviewer is asking for by using test cases and questions about the problem.
- Established a set (2-3) of test cases to verify their own solution later.
- Established a set (1-2) of edge cases to verify their solution handles complexities.
- Have fully understood the problem and have no clarifying questions.
- Have you verified any Time/Space Constraints for this problem?
HAPPY CASE
Input: n = 1, headID = 0, manager = [-1], informTime = [0]
Output: 0
Input: n = 4, headId = 2, manager = [3,3,-1,2], informTime = [0, 0, 162, 914]
Output: 1076
EDGE CASE
Input: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]
Output: 1
Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.
For graph problems, we want to consider the following approaches:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Use DFS to traverse the graph while calculating time at each step
1. We first convert the list to a graph
2. Then we use DFS to visit every note
3. We keep calculating the notifying time for each employee
4. we update the maximum time at each step
⚠️ Common Mistakes
employee_id
to list of subordinates.Implement the code to solve the algorithm.
class Solution(object):
def numOfMinutes(self, n, headID, managers, informTime):
graph = self.buildGraph(managers)
self.maxTime = 0
def dfs(source, currentTime):
# check if the source node is a non-manager
self.maxTime = max(self.maxTime, currentTime)
# explore the neighbors
for neighbor in graph[source]:
dfs(neighbor, currentTime + informTime[source])
dfs(headID, 0)
return self.maxTime
# we will build a Directed Graph : Manager -> Employee
def buildGraph(self, managers):
# Adjacency List
graph = defaultdict(list)
for employee, manager in enumerate(managers):
if manager != -1:
graph[manager].append(employee)
return graph
public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
Map<Integer, List<Integer>> graph = new HashMap<>();
for(int i = 0; i<manager.length; i++){
if(manager[i] == -1) {
continue;
}
graph.computeIfAbsent(manager[i], k-> new ArrayList()).add(i);
}
return dfs(headID, 0, graph, informTime);
}
// apply dfs
public int dfs(int headId, int time, Map<Integer,List<Integer>> graph, int[] informTime){
if(informTime[headId] == 0) {
return time;
}
int count = informTime[headId];
int val=Integer.MIN_VALUE;
for(int childId : graph.get(headId)){
val = Math.max(val, dfs(childId, time + count, graph, informTime));
}
return val;
}
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.