DSA Notes
HubAlgorithm vs Data Structure - Key DifferencesReal-World Applications of DSATime and Space Complexity OverviewWhat is DSA? Data Structures and AlgorithmsWhy Learn Data Structures and AlgorithmsAsymptotic Analysis - Understanding Algorithm GrowthBest, Average, and Worst Case AnalysisBig O Notation - Upper Bound AnalysisBig Omega Notation - Lower Bound AnalysisBig Theta Notation - Tight Bound AnalysisSpace Complexity - Memory AnalysisTime Complexity Examples and AnalysisArray Interview Problems and SolutionsArray Operations - Insert, Delete, SearchArray Rotation TechniquesArray Searching TechniquesArrays - Fundamental Data StructureDynamic Arrays - Flexible SizingMultidimensional Arrays - 2D and BeyondSliding Window Technique for ArraysAnagram Problems - Character RearrangementPalindrome Problems and SolutionsPattern Searching in StringsString Interview Problems CollectionString Matching Algorithms - Pattern SearchingString Operations - Concatenation, Substring, ManipulationString Data Structure - FundamentalsCircular Linked List - Ring StructureDoubly Linked List - Bidirectional TraversalLinked List Interview ProblemsLinked List - Data Structure FundamentalsLinked List Operations - Insert, Delete, ReverseReverse Linked List - Iterative and RecursiveSingly Linked List - Implementation and OperationsBalanced Parentheses - Stack ApplicationInfix, Prefix, Postfix Expressions - Stack ApplicationStack Implementation TechniquesStack Interview Problems and SolutionsStack Data Structure - LIFO PrincipleStack using Arrays - Static ImplementationStack using Linked Lists - Dynamic ImplementationCircular Queue - Efficient Space UsageDeque (Double Ended Queue)Priority Queue - Custom OrderingQueue Applications - Real-World Use CasesQueue Implementation - Array and Linked ListQueue Interview Problems and SolutionsQueue Data Structure - FIFO PrincipleAVL Tree - Self-Balancing Binary Search TreeBinary Search Tree (BST)Binary Tree - Structure and OperationsFenwick Tree (Binary Indexed Tree)Red-Black Tree - Another Balanced BSTSegment Tree - Range Query Data StructureTree Interview Problems CollectionTree Data Structure FundamentalsTree Traversals - Inorder, Preorder, Postorder, Level OrderHeap Data StructureHeap OperationsHeap Interview ProblemsMax-HeapMin-Heap Implementation and Use CasesPriority Queue using HeapBellman-Ford AlgorithmBreadth-First Search (BFS) AlgorithmDepth-First Search (DFS) AlgorithmDijkstra\Floyd-Warshall AlgorithmGraph Interview ProblemsGraph Data Structure FundamentalsGraph Representation MethodsKruskal\Minimum Spanning Tree (MST)Prim\Shortest Path Algorithms: Complete ComparisonTopological SortingUnion-Find (Disjoint Set Union)Separate ChainingCollision HandlingHash FunctionsHashing FundamentalsHashing Interview ProblemsOpen AddressingBubble Sort - Simple Sorting AlgorithmCounting Sort - Non-Comparison SortingHeap Sort - Heap Based SortingInsertion Sort - Build Sorted ArrayMerge Sort - Divide and ConquerQuick Sort - Partition Based SortingRadix Sort - Digit Based SortingSelection Sort - Selection Based SortingSorting Algorithms Comparison - Choosing the Right AlgorithmSorting Algorithms - Fundamentals and ConceptsBinary Search - Efficient SearchingInterpolation Search - Intelligent SearchingLinear Search - Sequential Search AlgorithmSearch Algorithms ComparisonSearching Algorithm Interview ProblemsTernary Search AlgorithmBacktracking with RecursionRecursion Fundamentals - Base Case and RecurrenceRecursion Problems and SolutionsRecursion Tree - Visualizing Function CallsRecursion vs Iteration - Comparing ApproachesTail Recursion - Optimization TechniqueDynamic Programming Interview ProblemsDynamic Programming FundamentalsFibonacci with Dynamic Programming0/1 Knapsack ProblemLongest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Matrix Chain MultiplicationMemoization (Top-Down Dynamic Programming)Tabulation (Bottom-Up Dynamic Programming)Activity Selection ProblemFractional KnapsackGreedy Interview ProblemsGreedy Algorithm FundamentalsHuffman Coding — Data Structures & AlgorithmsJob Sequencing with DeadlinesBacktracking FundamentalsBacktracking Practice ProblemsN-Queens ProblemRat in a MazeSubset GenerationSudoku SolverCodeforces Guide for Competitive ProgrammersCommon Competitive Programming TechniquesContest Strategies for Competitive ProgrammingCompetitive Programming IntroductionFast Input/Output for Competitive ProgrammingLeetCode Guide for Interview PreparationBit Manipulation - Advanced TechniquesBloom Filter - Probabilistic Data StructureComputational Geometry - Algorithms and TechniquesDisjoint Set Union (DSU) - Union FindRandomized Algorithms - Probabilistic ComputingSkip List - Probabilistic Balanced StructureSuffix Array - String IndexingTrie - Prefix Tree for Efficient SearchingAutocomplete System Using TrieLibrary Management System Using DSARoute Finder Using GraphsMini Search Engine ProjectSocial Network Analysis Using GraphsEssential Coding Patterns for InterviewsDSA Cheatsheet: Quick ReferenceEssential DSA Interview QuestionsFAANG DSA Sheet: Company-Specific Patterns and ProblemsProblem Solving Strategies for Coding InterviewsComplexity CheatsheetImportant Algorithms SummaryBest Practice Platforms for DSARecommended Books for DSA
Model social networks as graphs and implement BFS for degrees of separation, community detection, influence spread simulation, and simplified PageRank.
Why Graphs for Social Networks?
Social networks are graphs in disguise. Every person is a node, every friendship/follow is an edge. Facebook has 3 billion nodes and hundreds of billions of edges. The algorithms we learn in DSA class directly power features like "People You May Know," "Mutual Friends," and "Trending Topics."
In this project, we build a social network analyzer that answers real questions about network structure.
Building the Social Graph
Example
from collections import defaultdict, deque
import random
class SocialNetwork:
def __init__(self):
self.graph = defaultdict(set) # user -> set of friends
self.user_data = {} # user -> {name, interests, ...}
def add_user(self, user_id, name, interests=None):
self.user_data[user_id] = {
'name': name,
'interests': interests or []
}
if user_id not in self.graph:
self.graph[user_id] = set()
def add_friendship(self, user1, user2):
"""Undirected edge — mutual friendship."""
self.graph[user1].add(user2)
self.graph[user2].add(user1)
def get_friends(self, user_id):
return self.graph[user_id]
def mutual_friends(self, user1, user2):
"""Friends in common between two users."""
return self.graph[user1].intersection(self.graph[user2])
# Build a sample network
network = SocialNetwork()
users = [
("alice", "Alice", ["python", "music"]),
("bob", "Bob", ["java", "sports"]),
("carol", "Carol", ["python", "art"]),
("dave", "Dave", ["sports", "cooking"]),
("eve", "Eve", ["music", "art"]),
("frank", "Frank", ["python", "sports"]),
("grace", "Grace", ["music", "cooking"]),
]
for uid, name, interests in users:
network.add_user(uid, name, interests)
friendships = [
("alice", "bob"), ("alice", "carol"), ("alice", "eve"),
("bob", "dave"), ("bob", "frank"),
("carol", "eve"), ("carol", "frank"),
("dave", "frank"), ("dave", "grace"),
("eve", "grace"),
]
for u1, u2 in friendships:
network.add_friendship(u1, u2)
Feature 1: Degrees of Separation (BFS)
The famous "six degrees of separation" theory suggests any two people on Earth are connected by at most 6 intermediate acquaintances. BFS finds the shortest path between two users:
Example
def degrees_of_separation(self, source, target):
"""BFS to find shortest path between two users."""
if source == target:
return 0, [source]
visited = {source}
queue = deque([(source, [source])])
while queue:
current, path = queue.popleft()
for friend in self.graph[current]:
if friend == target:
return len(path), path + [target]
if friend not in visited:
visited.add(friend)
queue.append((friend, path + [friend]))
return -1, [] # Not connected
# Usage
distance, path = network.degrees_of_separation("alice", "grace")
print(f"Degrees: {distance}, Path: {' -> '.join(path)}")
# Output: Degrees: 2, Path: alice -> eve -> grace
Finding All Users Within K Degrees
Example
def users_within_k_degrees(self, source, k):
"""Find all users within k connections of source."""
visited = {source: 0}
queue = deque([(source, 0)])
while queue:
current, depth = queue.popleft()
if depth >= k:
continue
for friend in self.graph[current]:
if friend not in visited:
visited[friend] = depth + 1
queue.append((friend, depth + 1))
# Remove source and return with distances
del visited[source]
return visited
Feature 2: Community Detection (Connected Components)
Communities are clusters of densely connected users. A simple approach uses connected components; a more sophisticated one uses modularity-based detection:
Example
def find_communities_simple(self):
"""Find connected components (basic communities)."""
visited = set()
communities = []
for user in self.graph:
if user not in visited:
# BFS to find all users in this component
community = []
queue = deque([user])
visited.add(user)
while queue:
current = queue.popleft()
community.append(current)
for friend in self.graph[current]:
if friend not in visited:
visited.add(friend)
queue.append(friend)
communities.append(community)
return communities
def find_communities_label_propagation(self):
"""Label Propagation for overlapping community detection."""
# Each node starts with a unique label
labels = {user: user for user in self.graph}
for iteration in range(10): # Iterate until convergence
changed = False
users = list(self.graph.keys())
random.shuffle(users)
for user in users:
if not self.graph[user]:
continue
# Adopt the most common label among neighbors
neighbor_labels = [labels[n] for n in self.graph[user]]
from collections import Counter
most_common = Counter(neighbor_labels).most_common(1)[0][0]
if labels[user] != most_common:
labels[user] = most_common
changed = True
if not changed:
break
# Group users by label
communities = defaultdict(list)
for user, label in labels.items():
communities[label].append(user)
return list(communities.values())
Feature 3: Influence Spread Simulation
How far does information spread from a seed user? This simulates viral content:
Example
def simulate_influence_spread(self, seed_users, spread_probability=0.3, rounds=5):
"""Simulate how influence spreads through the network."""
activated = set(seed_users)
newly_activated = set(seed_users)
spread_history = [list(activated)]
for round_num in range(rounds):
next_activated = set()
for user in newly_activated:
for friend in self.graph[user]:
if friend not in activated:
# Each friend has a probability of being influenced
if random.random() < spread_probability:
next_activated.add(friend)
activated.update(next_activated)
newly_activated = next_activated
spread_history.append(list(next_activated))
if not next_activated:
break # No new activations
return {
'total_reached': len(activated),
'percentage': len(activated) / len(self.graph) * 100,
'rounds': len(spread_history) - 1,
'history': spread_history
}
Feature 4: Simplified PageRank
PageRank measures user importance based on who connects to them. A user connected to many important users is more important than one connected to few unimportant ones:
Example
def pagerank(self, damping=0.85, iterations=50):
"""Calculate PageRank for each user in the network."""
n = len(self.graph)
if n == 0:
return {}
# Initialize all ranks equally
ranks = {user: 1.0 / n for user in self.graph}
for _ in range(iterations):
new_ranks = {}
for user in self.graph:
# Sum of rank contributions from neighbors
rank_sum = 0
for friend in self.graph[user]:
# Friend contributes their rank divided by their degree
out_degree = len(self.graph[friend])
if out_degree > 0:
rank_sum += ranks[friend] / out_degree
# PageRank formula with damping
new_ranks[user] = (1 - damping) / n + damping * rank_sum
ranks = new_ranks
return ranks
# Usage
ranks = network.pagerank()
sorted_users = sorted(ranks.items(), key=lambda x: -x[1])
print("Most influential users:")
for user, rank in sorted_users:
print(f" {network.user_data[user]['name']}: {rank:.4f}")
Feature 5: Friend Recommendations
"People You May Know" — suggest friends based on mutual connections:
Example
def recommend_friends(self, user_id, top_k=5):
"""Recommend friends based on mutual friend count."""
scores = defaultdict(int)
for friend in self.graph[user_id]:
for friend_of_friend in self.graph[friend]:
if friend_of_friend != user_id and friend_of_friend not in self.graph[user_id]:
scores[friend_of_friend] += 1 # Count mutual friends
# Sort by mutual friend count
recommendations = sorted(scores.items(), key=lambda x: -x[1])
return [(uid, count) for uid, count in recommendations[:top_k]]
Complexity Summary
| Operation | Time | Space |
|---|---|---|
| Add user/friendship | O(1) | O(V + E) total |
| Degrees of separation | O(V + E) | O(V) |
| Find communities | O(V + E) | O(V) |
| PageRank (per iteration) | O(V + E) | O(V) |
| Friend recommendations | O(d²) where d = avg degree | O(V) |
Key Insights
- Social networks are sparse graphs — adjacency lists are far better than matrices
- BFS naturally answers "how far?" questions (degrees of separation)
- Community detection reveals clusters — useful for content recommendations
- PageRank is iterative — it converges after 20-50 rounds for most networks
- Real social networks follow power-law degree distributions — few users have many connections, most have few
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Social Network Analysis Using Graphs.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.
Search Terms
data-structures-algorithms, data structures & algorithms, data, structures, algorithms, projects, social, network
Related Data Structures & Algorithms Topics
Continue learning this concept
ProjectsAutocomplete System Using TrieBuild a real-time autocomplete system using a trie data structure with frequency ranking, prefix matching, and a complete Python implementation.ProjectsLibrary Management System Using DSABuild a library management system that demonstrates practical use of hash tables for book lookup, BST for sorted catalogs, queues for waitlists, stacks for undo operations, and linked lists for borrow history.ProjectsRoute Finder Using GraphsBuild a route-finding application using graph data structures, Dijkstra\ProjectsMini Search Engine ProjectBuild a mini search engine from scratch using an inverted index (hash map), TF-IDF scoring for relevance ranking, and a trie for autocomplete suggestions.Algorithm AnalysisAsymptotic Analysis - Understanding Algorithm GrowthUnderstand asymptotic analysis for analyzing algorithm behavior as input size grows infinitely.Algorithm AnalysisBest, Average, and Worst Case AnalysisAnalyze algorithms with best, average, and worst-case scenarios for comprehensive evaluation.