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: [[1],[2],[3],[]]
Output: true
EDGE CASE
Input: [[2], [], [1]]
Output: false
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.
To apply a graph algorithm for this problem, here are things we want to consider are:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Use a stack to store previous operator/operand combinations and compute the answer as we go.
⚠️ Common Mistakes
Implement the code to solve the algorithm.
class Solution(object):
def canVisitAllRooms(self, rooms):
seen = [False] * len(rooms)
seen[0] = True
stack = [0]
#At the beginning, we have a todo list "stack" of keys to use.
#'seen' represents at some point we have entered this room.
while stack: #While we have keys...
node = stack.pop() # get the next key 'node'
for nei in rooms[node]: # For every key in room # 'node'...
if not seen[nei]: # ... that hasn't been used yet
seen[nei] = True # mark that we've entered the room
stack.append(nei) # add the key to the todo list
return all(seen) # Return true iff we've visited every room
class Solution {
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
boolean[] seen = new boolean[rooms.size()];
seen[0] = true;
Stack<Integer> stack = new Stack();
stack.push(0);
// at the beginning, we have a todo list "stack" of keys to use.
while (!stack.isEmpty()) { // While we have keys...
int node = stack.pop(); // Get the next key 'node'
for (int nei: rooms.get(node)) // For every key in room # 'node'...
if (!seen[nei]) { // ...that hasn't been used yet
seen[nei] = true; // mark that we've entered the room
stack.push(nei); // add the key to the todo list
}
}
for (boolean v: seen) // if any room hasn't been visited, return false
if (!v) return false;
return true;
}
}
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.
O(N + K)
, where N
is the number of rooms and K
is the number of Keys.
O(N)
since we are using a list to store the visited rooms list.