← Flipkart questions

Topological sort

Filed under Flipkart · Also reported at ClearTrip, Happiest Mind, Innovaccer, Magnitude Software, Moonfrog Labs, Nielsen, OYO, Paytm and 1 more

Free read 2 of 3

Confirm graph representation and check if the graph is guaranteed to be a DAG.

The question

Given a directed acyclic graph (DAG), return a linear ordering of its vertices such that for every directed edge u -> v from vertex u to vertex v, u comes before v in the ordering.

Constraints

  • The graph is represented as an adjacency list.
  • The graph is guaranteed to be a Directed Acyclic Graph (DAG).
  • Number of vertices V <= 10^5, Edges E <= 2 * 10^5.

Examples

Input
n = 6, edges = [[5, 2], [5, 0], [4, 0], [4, 1], [2, 3], [3, 1]]
Output
[4, 5, 2, 3, 1, 0]
Why
Vertex 4 and 5 have in-degree 0. Processing them leads to a valid topological order.

Approach

  1. Confirm graph representation and check if the graph is guaranteed to be a DAG.

Tips

  • What they are testing: Tested on cycle detection, disconnected components, and single-node graphs.
  • Common mistake: Failing to check for cycles in graphs that are not guaranteed to be DAGs.

Related Flipkart questions

Collected from public candidate posts and coding forums. Updated Nov 2026.