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?
O(1)
time and O(1)
space. HAPPY CASE
Input: edges = [[1,2],[2,3],[4,2]]
Output: 2
Explanation: As shown in the figure above, node 2 is connected to every other node, so 2 is the center.
Input: edges = [[1,2],[5,1],[1,3],[1,4]]
Output: 1
EDGE CASE
Input: edges = [[1,2],[2,3]]
Output: 2
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, common solution patterns include:
Plan the solution with appropriate visualizations and pseudocode.
Approach #1:
General Idea: A valid start graph suggest that the center is connected to every edge, therefore we can get the center by seeing the comment element in the first 2 pairs.
Create 2 sets and return the common element between the two sets.
Approach #2:
General Idea: A valid start graph suggest that the center is connected to every edge, therefore we can get the center by seeing the comment element in the first 2 pairs.
If the first element in the edge pair is in the second pair, then this is the common element and therefore the center node. Else it is the second element.
⚠️ Common Mistakes
Implement the code to solve the algorithm.
Approach #1:
class Solution:
def findCenter(self, edges: List[List[int]]) -> int:
# Create 2 sets and return the common element between the two sets.
return (set(edges[0]) & set(edges[1])).pop()
Approach #2:
class Solution:
def findCenter(self, edges: List[List[int]]) -> int:
# If the first element in the edge pair is in the second pair, then this is the common element and therefore the center node. Else it is the second element.
return edges[0][0] if edges[0][0] == edges[1][0] or edges[0][0] == edges[1][1] else edges[0][1]
class Solution {
public int findCenter(int[][] e) {
// # If the first element in the edge pair is in the second pair, then this is the common element and therefore the center node. Else it is the second element.
return e[0][0] == e[1][0] || e[0][0] == e[1][1] ? e[0][0] : e[0][1];
}
}
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.
Assume V
represents the number of vertices.
Assume E
represents the number of edges.
Approach #1 & #2 Have the same time and space complexity: