Problem Statement
Design an online chat system that supports user management, friend connections, private messaging, and group chat functionality.
Constraints and Assumptions
- Text conversations only (no media)
- User operations:
- Add, remove, update users
- Manage friend lists
- Send, approve, reject friend requests
- Chat types:
- Private 1-1 chat
- Group chat with multiple participants
- No scaling concerns initially (single server)
Design Overview
The chat system uses several interconnected classes:
- UserService: Manages all users and friend requests
- User: Represents a chat user with friends and conversations
- Chat: Abstract base class for all chat types
- PrivateChat: One-on-one conversation
- GroupChat: Multi-user conversation
- Message: Individual message in a chat
- AddRequest: Friend request with status tracking
- RequestStatus: Enum for friend request states
This design uses the Mediator pattern where UserService acts as a central coordinator for user interactions, and the Composite pattern where different chat types share a common interface.
Implementation
UserService Class
Central service for managing users and relationships:
class UserService(object):
def __init__(self):
self.users_by_id = {} # key: user id, value: User
def add_user(self, user_id, name, pass_hash): # ...
def remove_user(self, user_id): # ...
def add_friend_request(self, from_user_id, to_user_id): # ...
def approve_friend_request(self, from_user_id, to_user_id): # ...
def reject_friend_request(self, from_user_id, to_user_id): # ...
User Class
Represents a user with all their social connections:
class User(object):
def __init__(self, user_id, name, pass_hash):
self.user_id = user_id
self.name = name
self.pass_hash = pass_hash
self.friends_by_id = {} # key: friend id, value: User
self.friend_ids_to_private_chats = {} # key: friend id, value: private chats
self.group_chats_by_id = {} # key: chat id, value: GroupChat
self.received_friend_requests_by_friend_id = {} # key: friend id, value: AddRequest
self.sent_friend_requests_by_friend_id = {} # key: friend id, value: AddRequest
def message_user(self, friend_id, message): # ...
def message_group(self, group_id, message): # ...
def send_friend_request(self, friend_id): # ...
def receive_friend_request(self, friend_id): # ...
def approve_friend_request(self, friend_id): # ...
def reject_friend_request(self, friend_id): # ...
Chat Hierarchy
Abstract base class and concrete implementations:
from abc import ABCMeta
class Chat(metaclass=ABCMeta):
def __init__(self, chat_id):
self.chat_id = chat_id
self.users = []
self.messages = []
class PrivateChat(Chat):
def __init__(self, first_user, second_user):
super(PrivateChat, self).__init__()
self.users.append(first_user)
self.users.append(second_user)
class GroupChat(Chat):
def add_user(self, user): # ...
def remove_user(self, user): # ...
Message Class
Represents individual messages:
class Message(object):
def __init__(self, message_id, message, timestamp):
self.message_id = message_id
self.message = message
self.timestamp = timestamp
Friend Request Classes
Manage friend connection requests:
from enum import Enum
class AddRequest(object):
def __init__(self, from_user_id, to_user_id, request_status, timestamp):
self.from_user_id = from_user_id
self.to_user_id = to_user_id
self.request_status = request_status
self.timestamp = timestamp
class RequestStatus(Enum):
UNREAD = 0
READ = 1
ACCEPTED = 2
REJECTED = 3
Key Design Patterns
UserService acts as a mediator coordinating interactions between users:
┌──────────────┐
│ UserService │ (Mediator)
│ │
│ Coordinates: │
│ - User CRUD │
│ - Friend req │
└──────────────┘
↓
┌──────────────┐
│ User A │ ←→ Friend Request ←→ User B
│ User C │
└──────────────┘
Composite Pattern
Different chat types share a common interface:
┌──────────────┐
│ Chat │ (Abstract)
│ - users │
│ - messages │
└──────────────┘
↑
│ extends
┌───┴───┐
│ │
┌──────┐ ┌────────┐
│Private│ │Group │
│Chat │ │Chat │
└──────┘ └────────┘
Observer Pattern (Implicit)
Users maintain references to their chats and can be notified of new messages:
friend_ids_to_private_chats: Maps friends to conversationsgroup_chats_by_id: Tracks group memberships
System Workflows
Friend Request Flow
User A UserService User B
│ │ │
│ send_friend_request() │ │
├───────────────────────────>│ │
│ │ create AddRequest │
│ │ (status: UNREAD) │
│ ├───────────────────────────>│
│ │ │
│ │ approve_friend_request() │
│ │<───────────────────────────┤
│ │ │
│ │ update AddRequest │
│ │ (status: ACCEPTED) │
│ │ │
│<───────────────────────────┤ add to friends_by_id │
│ add to friends_by_id │───────────────────────────>│
Private Chat Flow
User A User B
│ │
│ Check if private chat exists │
│ with User B in │
│ friend_ids_to_private_chats │
│ │
│ If not, create PrivateChat │
│ Add to both users' mappings │
│ │
│ message_user(friend_id, message) │
├──────────────────────────────────────────────────>│
│ │
│ Create Message object │
│ Add to PrivateChat.messages[] │
Group Chat Flow
User A creates GroupChat
│
├─> Add User A to GroupChat.users[]
│
├─> User A invites User B
│ └─> Add User B to GroupChat.users[]
│ └─> Add GroupChat to User B's group_chats_by_id
│
├─> User A invites User C
│ └─> Add User C to GroupChat.users[]
│ └─> Add GroupChat to User C's group_chats_by_id
│
└─> Any user can message_group(group_id, message)
└─> Message added to GroupChat.messages[]
Data Structure Design
User Relationships
The User class uses multiple dictionaries to efficiently manage relationships:
# Fast O(1) friend lookup
friends_by_id = {
user_id_1: User(...),
user_id_2: User(...)
}
# Map friend to their private chat
friend_ids_to_private_chats = {
user_id_1: PrivateChat(...),
user_id_2: PrivateChat(...)
}
# Track all group conversations
group_chats_by_id = {
chat_id_1: GroupChat(...),
chat_id_2: GroupChat(...)
}
Complexity Analysis
| Operation | Time Complexity | Notes |
|---|
| add_user() | O(1) | Hash map insertion |
| remove_user() | O(n) | Remove from all friends’ lists |
| send_friend_request() | O(1) | Create and store request |
| approve_friend_request() | O(1) | Update status, add to friends |
| message_user() | O(1) | Append to chat messages |
| message_group() | O(1) | Append to chat messages |
Most operations are O(1) due to hash map lookups. The exception is remove_user(), which requires iterating through friends to remove bidirectional references.
Design Considerations
Advantages
- Clear separation: Users, chats, and messages are distinct entities
- Bidirectional relationships: Both users maintain friend and chat references
- Flexible chat types: Easy to add new chat types (e.g., channels, threads)
- Request lifecycle: Clear states for friend requests
Friend Request States
UNREAD → READ → ACCEPTED
→ REJECTED
Potential Improvements
- Message delivery: Add read receipts, delivery status, typing indicators
- Online status: Track user presence (online, away, offline)
- Message history: Implement pagination for loading older messages
- Search: Full-text search across messages and users
- Notifications: Push notifications for new messages and friend requests
- Encryption: End-to-end encryption for private messages
- Media support: Images, videos, files, voice messages
- Message reactions: Emojis, likes, replies
- User blocking: Prevent unwanted interactions
- Admin controls: Moderation tools for group chats
- Scalability: Distribute users across servers, use message queues
- Persistence: Database backend for storing users and messages
- WebSocket support: Real-time message delivery
- Rate limiting: Prevent spam and abuse
