Feature #2: Copy Connections
Explore how to clone a graph representing Facebook user connections for use on Instagram’s servers. Learn to use depth-first traversal and hash maps to duplicate nodes without revisiting, managing uni- and bi-directional edges efficiently. Understand the time and space complexities involved in the process.
We'll cover the following...
Description
After identifying every user’s friend circles, we need to duplicate this data to Instagram’s servers so it can be easily accessed and modified there as well. As the user’s name can be the same, so every user on Facebook gets assigned a unique id. Each Facebook user’s connections are represented and stored in a graph-like structure. We will first have to make an exact copy of this structure before storing it on Instagram’s servers.
Let’s say we want to duplicate the data for the following users:
For each user, we’ll be provided with a node and its information. This node will point to other nodes, and from that one node, we need to reach and make an exact clone of every other node. An edge between two nodes means that they are friends with each other. A bi-directional edge means that ...