Practice/Microsoft/Design a graph-based system

Design a graph-based system

Object Oriented DesignMust

Problem

Design and implement a social network graph system that models relationships between users and groups. The system should support two primary node types: User nodes and Group nodes. Users can be friends with other users (bidirectional relationship), and users can be members of groups (directional relationship from user to group).

Your implementation should provide a flexible, extensible architecture that can easily accommodate additional node types and relationship types in the future. The system must efficiently store and query these relationships.

Requirements

1. Node Types: Implement at least two node types (User and Group) with a common base class or interface
2. Edge Management: Create an edge structure that can represent different relationship types (friendship between users, membership in groups)
3. Bidirectional Friendships: When a friendship is added between two users, both should recognize each other as friends
4. Directional Memberships: Group memberships are directional (user belongs to group)
5. Query Operations: Support querying a user's friends and a group's members
6. Extensibility: Design should allow easy addition of new node types and edge types
7. Data Integrity: Prevent duplicate edges and handle invalid node references gracefully

Constraints

• Node IDs are unique strings with length between 1 and 100 characters
• The network can contain up to 10,000 nodes total
• Each user can have up to 500 friends
• Each user can belong to up to 100 groups
• Each group can have up to 1,000 members
• All operations should be efficient (add: O(1) amortized, query: O(E) where E is the number of edges for that node)

Examples

Example 1: Basic Friendship Network

` Operations: network.add_user("Alice") network.add_user("Bob") network.add_user("Charlie") network.add_friendship("Alice", "Bob") network.add_friendship("Bob", "Charlie")

Query: network.get_friends("Alice") Output: ["Bob"]

Query: network.get_friends("Bob") Output: ["Alice", "Charlie"] `

Example 2: Group Memberships

` Operations: network.add_user("David") network.add_user("Emma") network.add_group("Engineering") network.add_group("ProductManagement") network.add_membership("David", "Engineering") network.add_membership("Emma", "Engineering") network.add_membership("Emma", "ProductManagement")

Query: network.get_group_members("Engineering") Output: ["David", "Emma"]

Query: network.get_group_members("ProductManagement") Output: ["Emma"] `

Example 3: Mixed Relationships

` Operations: network.add_user("Frank") network.add_user("Grace") network.add_group("Designers") network.add_friendship("Frank", "Grace") network.add_membership("Frank", "Designers") network.add_membership("Grace", "Designers")

Query: network.get_friends("Frank") Output: ["Grace"]

Query: network.get_group_members("Designers") Output: ["Frank", "Grace"] `