How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Snowflake.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Snowflake during technical interviews.

Implement topological sort and tree boundary traversal

Q: Implement topological sort and tree boundary traversal

These tasks evaluate core competencies in directed graph algorithms (topological ordering and cycle detection) and binary tree traversals (boundary identification and leaf enumeration), testing understanding of dependency modeling and traversal patterns.

You are given two separate coding tasks.

Problem A — Order courses with prerequisites

You have n courses labeled 0..n-1 and a list of prerequisite pairs prerequisites, where each pair [a, b] means to take course a, you must first take course b.

Task: Return any valid ordering of all courses that satisfies prerequisites. If it is impossible (because of a cycle), return an empty list.

Input:

n (integer)
prerequisites (list of pairs)

Output:

A list of length n representing a valid order, or [] if no order exists.

Constraints (typical):

1 ≤ n ≤ 10^5
0 ≤ len(prerequisites) ≤ 2*10^5

Notes:

Implement the algorithm yourself (e.g., topological sort).
Be prepared to write a few basic tests (e.g., cycle case, disconnected graph).

Problem B — Boundary traversal of a (complete/balanced) binary tree

You are given the root of a binary tree. The tree is guaranteed to be complete and balanced (interview variant constraint), but your solution may work for any binary tree.

Define the boundary of the tree in anti-clockwise order as:

The root (once).
The left boundary (excluding leaves): from root.left going downward, always taking the next boundary node.
All leaf nodes from left to right.
The right boundary (excluding leaves): from root.right going downward, collected top-down but output bottom-up .

Task: Return a list of node values in boundary order, with no duplicates.

Input:

root of a binary tree

Output:

List of integers representing the boundary traversal.

Edge cases to consider:

Single-node tree
Root has only one child
Trees where left/right boundary paths include missing children (even if the interview variant says complete)

Complexity target:

Time O(N) , space O(H) (recursion) or O(N) worst case depending on implementation.

You are given two separate coding tasks.

Problem A — Order courses with prerequisites

You have n courses labeled 0..n-1 and a list of prerequisite pairs prerequisites, where each pair [a, b] means to take course a, you must first take course b.

Task: Return any valid ordering of all courses that satisfies prerequisites. If it is impossible (because of a cycle), return an empty list.

Input:

n (integer)
prerequisites (list of pairs)

Output:

A list of length n representing a valid order, or [] if no order exists.

Constraints (typical):

1 ≤ n ≤ 10^5
0 ≤ len(prerequisites) ≤ 2*10^5

Notes:

Implement the algorithm yourself (e.g., topological sort).
Be prepared to write a few basic tests (e.g., cycle case, disconnected graph).

Problem B — Boundary traversal of a (complete/balanced) binary tree

You are given the root of a binary tree. The tree is guaranteed to be complete and balanced (interview variant constraint), but your solution may work for any binary tree.

Define the boundary of the tree in anti-clockwise order as:

The root (once).
The left boundary (excluding leaves): from root.left going downward, always taking the next boundary node.
All leaf nodes from left to right.
The right boundary (excluding leaves): from root.right going downward, collected top-down but output bottom-up .

Task: Return a list of node values in boundary order, with no duplicates.

Input:

root of a binary tree

Output:

List of integers representing the boundary traversal.

Edge cases to consider:

Single-node tree
Root has only one child
Trees where left/right boundary paths include missing children (even if the interview variant says complete)

Complexity target:

Time O(N) , space O(H) (recursion) or O(N) worst case depending on implementation.

Implement topological sort and tree boundary traversal

Quick Overview

Problem A — Order courses with prerequisites

Problem B — Boundary traversal of a (complete/balanced) binary tree

Comments (0)

Implement topological sort and tree boundary traversal

Quick Overview

Problem A — Order courses with prerequisites

Problem B — Boundary traversal of a (complete/balanced) binary tree

Comments (0)