DSA / Graphs Interview Questions 2026

Implement Dijkstra's algorithm using a Fibonacci heap. Compare amortized complexity with a binary heap and explain when the Fibonacci heap is actually slower in practice despite the better theoretical bound.

Implement a topological sort for a directed acyclic graph. Then extend it to detect cycles and explain how this maps to dependency resolution in build systems like Bazel.

Given a social graph, find all users within K hops of a given user. Implement BFS with a visited set. Then discuss how you would scale this to Meta's 3 billion user graph using partitioning.

Given Meta's social graph, find all friend-of-friend recommendations for a user that are not already friends. Discuss BFS at scale, how to prune the search space, and how to rank recommendations by mutual friend count efficiently.

Given a 2D grid of 0s and 1s, count the number of islands. Then extend: find the largest island, and then explain how you would solve this for a streaming grid that changes in real time using a Union-Find structure.

Given a city map as a weighted graph, find the shortest travel time from a driver's current location to all potential passenger pickup points simultaneously. How does Dijkstra's multi-source variant solve this?

Given a directed graph representing service dependencies, detect all strongly connected components and explain how this maps to identifying circular dependencies in a microservices architecture.

Given a social graph, find the shortest chain of mutual connections between two users (like LinkedIn's "degrees of connection"), and explain how bidirectional BFS improves performance over a single-direction BFS at this scale.

Given a directed graph representing category hierarchies in an e-commerce catalog, find the shortest path between two categories. Explain BFS vs Dijkstra for unweighted vs weighted graphs.