Distributed Machine Cluster Count and Topology

You are given a tree structure where each node represents a machine in a distributed cluster. Machines can only communicate with their direct parent or children via asynchronous message passing. The problem asks you to implement a receiveMessage() function that enables the cluster to count its own nodes, map the full tree topology, and handle duplicate or failed messages idempotently. Problem Description You have a tree structure. Each node in the tree is a machine in a cluster. Each machine can only talk to its parent and its children by sending messages. You need to build a system that uses messages to learn facts about the cluster. Available Methods Every machine can use two methods: sendAsyncMessage(nodeId: str, message: str) This is a provided API. You do not need to write it. Assume it works correctly. When you send a message to a machine, that machine automatically runs its receiveMessage() function. receiveMessage(fromNodeId: str, message: str) You must write this function. fromNodeId: The ID of the machine sending the message (this is None or null if the message comes from outside the cluster). message: The text content of the message. Node Details Each machine (node) has: A unique nodeId. A link to its parent (this is None or null for the root node). A list of children (IDs of machines it can talk to). Rules: Machines can only talk to their direct parent or direct children. Siblings (brothers/sisters) cannot talk directly to each other. The root node has parent = None. Leaf nodes have an empty children list []. Task 1: Count Nodes Write the code for receiveMessage() to count how many machines are in the cluster. Task Requirements The process starts when the root node gets a message. Every machine must work with its children to count the nodes below it. Only the root node prints the final number. Leaf nodes should answer immediately. You can decide what the messages look like. How to Solve It ** receiving a count request:** If the node is a leaf: Send "1" back to the parent immediately. If the node has children: Start the count at 1 (count yourself). Send a request to all children. Wait for them to answer. When receiving a count response (a number) from a child: Add the child's number to your total. Mark that child as "finished." When all children have answered: Send the final total to your parent (or print it if you are the root). Example Flow Tree structure: Root (1) / \ 2 3 / \ \ 4 5 6 Steps: 1. Root gets: receiveMessage(null, "count") 2. Root sends "count" to children [2, 3] 3. Node 2 sends "count" to children [4, 5] 4. Node 3 sends "count" to children [6] 5. Nodes 4, 5, 6 (leaves) reply with "1" 6. Node 2 gets replies, adds them up: 1 (self) + 1 + 1 = 3. Sends "3" to Root. 7. Node 3 gets reply, adds them up: 1 (self) + 1 = 2. Sends "2" to Root. 8. Root gets replies, adds them up: 1 (self) + 3 + 2 = 6. Root prints "6". Special Cases Root is a leaf: The cluster has only 1 machine. Print "1" immediately. Message order: Messages might arrive at different times. Message types: You must know the difference between a "count request" and a "number response." Task 2: Map the Cluster Update your receiveMessage() code to return the structure (topology) of the whole tree. Mapping Requirements The root starts the process. Each machine gathers the structure of its own subtree from its children. Only the root node prints the final map. The output format should be clear, like: String: "1(2(3[]))" JSON: {"node": "1", "children": [{"node": "2", "children": []}]} Mapping Approach Use new message types: "topology" (request) and "topologyResponse" (answer). When receiving a "topology" request: If leaf: Send back your ID and an empty list. If internal: Forward the request to all children and wait. When receiving responses from children: Save the data from each child. When all children have answered: Create your own structure: {"node": myID, "children": [child_data]}. Send this to your parent (or print if root). Message Format Example You can use simple strings: Request: "topology" Response: "topologyResponse|{nodeId}|{children_data}" Expected Output For the tree in Task 1: 1(2(4[],5[]),3(6[])) Or using JSON: { "node": "1", "children": [ { "node": "2", "children": [ {"node": "4", "children": []}, {"node": "5", "children": []} ] }, { "node": "3", "children": [ {"node": "6", "children": []} ] } ] } Task 3: Handling Failures Interviewer Question: "Messages might fail or send twice. How do you make sure we don't count the same node twice?" Key Concepts Idempotency: Doing the same action multiple times should not change the result. Deduplication: Remembering which messages you already finished. Request IDs: Giving every request a unique name. Solution Approach Use a Set to remember the IDs of requests you have already handled. class Node: def __init__(self, node_id, children, parent): self.node_id = node_id self.children = children self.parent = parent self.processed_requests = set() # Remembers request IDs self.pending_responses = {} def receiveMessage(self, fromNodeId, message): # Get the ID from the message request_id = extract_request_id(message) # If we already did this, stop if request_id in self.processed_requests: return # Mark as done self.processed_requests.add(request_id) # Continue with normal logic... Other Options Sequence Numbers: Keep track of the order of messages. Caching: Save the answer. If the parent asks again, send the saved answer. Timeout: If a child takes too long, ask again. Code Solution for Task 1 Here is a reference implementation for counting the machines. from typing import List class Node: def __init__(self, node_id: str, children: List[str], parent: str): self.node_id = node_id self.children = children # List of child node IDs self.parent = parent # Parent node ID or None self.total_count = 0 self.pending_children = [] def sendAsyncMessage(self, node_id: str, message: str): """Provided API - do not implement""" pass def receiveMessage(self, fromNodeId: str, message: str): """Your implementation - count machines""" # Case 1: Start request (from outside/root) if fromNodeId is None: if not self.children: # Root is a leaf - print now print("1") else: # Root has children - start counting self.total_count = 1 # Count myself self.pending_children = self.children.copy() for child in self.children: self.sendAsyncMessage(child, "COUNT_REQUEST") # Case 2: Request from parent elif fromNodeId == self.parent: if not self.children: # Leaf node - reply with 1 self.sendAsyncMessage(self.parent, "1") else: # Internal node - ask children self.total_count = 1 # Count myself self.pending_children = self.children.copy() for child in self.children: self.sendAsyncMessage(child, "COUNT_REQUEST") # Case 3: Response from a child elif fromNodeId in self.children: # Ignore duplicate answers if fromNodeId not in self.pending_children: return # Add child's count child_count = int(message) self.total_count += child_count self.pending_children.remove(fromNodeId) # Check if all children answered if not self.pending_children: if self.parent is None: # Root node - print result print(str(self.total_count)) else: # Internal node - send to parent self.sendAsyncMessage(self.parent, str(self.total_count)) # Reset for next time self.total_count = 0 Important Logic State Management: We use variables like total_count and pending_children to remember what we are waiting for. Message Types: We handle "COUNT_REQUEST" differently than numeric strings. Edge Cases: Root node has no children. Leaf nodes reply instantly. Reset State: We clear total_count at the end so the machine can be used again. Code Solution for Task 2 class Node: def __init__(self, node_id: str, children: List[str], parent: str): self.node_id = node_id self.children = children self.parent = parent self.topology_responses = {} self.pending_topology_children = [] def receiveMessage(self, fromNodeId: str, message: str): # Handle requests if message == "TOPOLOGY_REQUEST": if fromNodeId is None or fromNodeId == self.parent: if not self.children: # Leaf node response = f"TOPOLOGY|{self.node_id}|[]" if self.parent: self.sendAsyncMessage(self.parent, response) else: print(f"{self.node_id}") # Root leaf else: # Internal node - ask children self.pending_topology_children = self.children.copy() for child in self.children: self.sendAsyncMessage(child, "TOPOLOGY_REQUEST") # Handle responses elif message.startswith("TOPOLOGY|"): parts = message.split("|", 2) child_node_id = parts[1] child_structure = parts[2] if child_node_id in self.pending_topology_children: self.topology_responses[child_node_id] = child_structure self.pending_topology_children.remove(child_node_id) # All children answered if not self.pending_topology_children: # Build the string children_str = ",".join([ f"{child_id}{self.topology_responses[child_id]}" for child_id in self.children ]) topology = f"{self.node_id}({children_str})" if self.parent is None: # Root - print result print(topology) else: # Send to parent response = f"TOPOLOGY|{self.node_id}|({children_str})" self.sendAsyncMessage(self.parent, response) # Reset state self.topology_responses = {} Test Cases Test Case 1: Simple Tree 1 / \ 2 3 Count: 3 Topology: 1(2[],3[]) Test Case 2: Unbalanced Tree 1 / 2 / 3 Count: 3 Topology: 1(2(3[])) Test Case 3: Complete Tree 1 / \ 2 3 / \ / \ 4 5 6 7 Count: 7 Topology: 1(2(4[],5[]),3(6[],7[])) Test Case 4: Single Node 1 Count: 1 Topology: 1 Important Notes No Threading: This problem is about logic, not real parallel processing. Formats: You can choose your own message format (JSON, strings, etc.). State: Be careful to reset your variables after a request is finished. Common Errors Forgetting yourself: Each node must add 1 to the total count (for itself). Root issues: The root handles fromNodeId = None differently. Duplicates: Not checking if a child already answered. Confusion: Mixing up "Ask for count" messages with "Here is the count" messages. Dirty State: Not resetting the counters, causing bugs on the second run. Tips for Success Draw a small tree and explain the message flow out loud. Discuss why you chose strings or JSON for messages. For Task 3, focus on the idea of unique IDs rather than writing perfect code. Ask questions about edge cases (e.g., "What if the cluster is empty?").