Round 1
Questions: Given the social graph of a person, find all the nth connections of the person. The task is to find all the nth-level connections of a given person in a social graph. The graph is represented as an undirected graph where:
- Each person (node) can have one or more direct connections (edges) to other people.
- The graph is stored using an adjacency list (in Python, represented as a dictionary where keys are nodes, and values are lists of connected nodes).
The objective is to find all individuals who are at the nth degree of separation from a given person in the graph.
Approach: The BFS algorithm explores the graph level by level starting from the source node (in this case, the given person). This ensures that we can accurately find all connections that are exactly n levels away from the source.
Solution Outline:
- Initialize BFS:
- Start from the given person (node).
- Use a queue to store nodes to be explored, along with the current level (starting from 0 for the source node).
- Maintain a visited set to avoid revisiting nodes and cycle.
- Explore Nodes Level by Level.
For each node, process its neighbors, and for each unvisited neighbor, enqueue it with the next level. Stop once the queue reaches level n and collect all the nodes at level n.
After BFS completes, gather all nodes that are exactly n levels away from the source.
Candidate's Approach
The candidate chose to implement the BFS algorithm to explore the social graph. They initialized the BFS with the source node and maintained a queue to track the nodes to be explored along with their levels. The candidate ensured that nodes were not revisited by using a visited set. They successfully collected all nodes that were exactly n levels away from the source after completing the BFS traversal.
Interviewer's Feedback
No feedback provided.