Unit 11 Session 2 Advanced (Click for link to problem statements)
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?
|x_i - x_j| + |y_i - y_j|.HAPPY CASE
Input: outposts = [[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]]
Output: 20
Explanation: The minimum total cost to connect the outposts is 20. We calculate the cost using Manhattan distances and find the minimum spanning tree.
EDGE CASE
Input: outposts = []
Output: 0
Explanation: No outposts are present, so the total cost is 0.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 Connecting Points or Minimum Spanning Tree problems, we want to consider the following approaches:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Use Prim's algorithm to find the minimum cost to connect all outposts. Treat the outposts as nodes in a graph, where the edges between nodes represent the Manhattan distance between outposts. Prim's algorithm will help find the minimum spanning tree that connects all nodes.
1) Initialize a priority queue to store (cost, node) pairs, starting from outpost 0.
2) Use a set to track the visited outposts.
3) Initialize the total cost to 0.
4) While not all outposts are visited:
a) Pop the minimum cost node from the priority queue.
b) If the node has been visited, skip it.
c) Add the node to the visited set and add its cost to the total cost.
d) For all unvisited neighboring nodes, calculate the Manhattan distance and push the distance and node to the priority queue.
5) Return the total cost once all outposts are connected.⚠️ Common Mistakes
Implement the code to solve the algorithm.
import heapq
# Helper function to calculate Manhattan distance
def manhattan_distance(p1, p2):
return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
# Function to find the minimum cost to connect all outposts
def prepare_winter_roads(outposts):
n = len(outposts)
if n == 0:
return 0
# Initialize variables
total_cost = 0
visited = set()
min_heap = [(0, 0)] # (cost, index) starting from outpost 0
# Dijkstra-like approach to find the minimum spanning tree
while len(visited) < n:
cost, u = heapq.heappop(min_heap)
if u in visited:
continue
# Add this outpost to the visited set and accumulate the cost
visited.add(u)
total_cost += cost
# Check all other outposts and calculate the distance to add to the heap
for v in range(n):
if v not in visited:
dist = manhattan_distance(outposts[u], outposts[v])
heapq.heappush(min_heap, (dist, v))
return total_costReview the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Example 1:
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Assume n is the number of outposts.
O(n^2 log n) due to calculating the distance between all pairs and pushing them into the priority queue.O(n) for storing visited nodes and the priority queue.