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 Meta.

What role is this question designed for?

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

Solve tree diameter and grid path problems

Q: Solve tree diameter and grid path problems

This question evaluates understanding of graph algorithms and pathfinding, covering tree diameter computation and grid shortest-path problems as well as enumeration of simple paths, and requires skills in traversal techniques, combinatorial reasoning, and time/space complexity analysis.

You are interviewing for a software engineer / ML intern role and are given the following algorithmic problems.

Question 1: Longest Path in a Tree

You are given a tree, i.e., a connected, undirected, acyclic graph with $n$ nodes labeled from 1 to $n$ , and $n - 1$ edges.

Each edge is unweighted (or equivalently has weight 1).

Task:

Find the length of the longest path between any two nodes in the tree. The length of a path is defined as the number of edges on that path.

Input:
- An integer $n$ , the number of nodes.
- A list of $n - 1$ edges, each edge given as a pair $(u, v)$ indicating an undirected edge between nodes $u$ and $v$ .
Output:
- A single integer: the maximum number of edges on any simple path between two nodes in the tree.

You should describe an algorithm (no need to provide code) and analyze its time and space complexity.

Assume $1 \le n \le 10^5$ , so the algorithm must be close to linear time.

Question 2: Shortest Path in an Obstacle Grid (and All Paths)

You are given an $n \times n$ grid representing a 2D map. Each cell is either free or blocked:

0 means the cell is free.
1 means the cell is blocked (an obstacle) and cannot be stepped on.

You start in the top-left cell (0, 0) and want to reach the bottom-right cell (n - 1, n - 1).

From any cell, you may move one step at a time in the four cardinal directions:

Up: (r - 1, c)
Down: (r + 1, c)
Left: (r, c - 1)
Right: (r, c + 1)

You may only move to cells that are within bounds and free (0).

Part A: Shortest Path Length

Task:

Find the length (in number of steps) of the shortest path from (0, 0) to (n - 1, n - 1).

If there is no valid path, return -1 .
Input:
- An integer $n$ (e.g., up to a few hundred).
- An $n \times n$ matrix grid of 0s and 1s.
Output:
- A single integer: the minimum number of steps needed to reach (n - 1, n - 1) from (0, 0) , or -1 if impossible.

Describe the algorithm you would use and analyze its time and space complexity.

Part B (Follow-up): Enumerate All Paths

Now, suppose we want to find all possible paths from (0, 0) to (n - 1, n - 1) under the same movement and obstacle rules.

Describe an approach to enumerate all distinct simple paths (paths that do not revisit any cell).
Discuss:
- How you would represent each path in memory.
- The time and space complexity in terms of $n$ and the number of valid paths $K$ .
- Any practical limitations when $n$ is moderately large and/or when there may be exponentially many paths.

You may assume $n$ is small enough that, in principle, all paths could be generated for the sizes considered (e.g., in a whiteboard or interview setting), but you should still comment on scalability and limitations.

You are interviewing for a software engineer / ML intern role and are given the following algorithmic problems.

Question 1: Longest Path in a Tree

You are given a tree, i.e., a connected, undirected, acyclic graph with $n$ nodes labeled from 1 to $n$ , and $n - 1$ edges.

Each edge is unweighted (or equivalently has weight 1).

Task:

Find the length of the longest path between any two nodes in the tree. The length of a path is defined as the number of edges on that path.

Input:
- An integer $n$ , the number of nodes.
- A list of $n - 1$ edges, each edge given as a pair $(u, v)$ indicating an undirected edge between nodes $u$ and $v$ .
Output:
- A single integer: the maximum number of edges on any simple path between two nodes in the tree.

You should describe an algorithm (no need to provide code) and analyze its time and space complexity.

Assume $1 \le n \le 10^5$ , so the algorithm must be close to linear time.

Question 2: Shortest Path in an Obstacle Grid (and All Paths)

You are given an $n \times n$ grid representing a 2D map. Each cell is either free or blocked:

0 means the cell is free.
1 means the cell is blocked (an obstacle) and cannot be stepped on.

You start in the top-left cell (0, 0) and want to reach the bottom-right cell (n - 1, n - 1).

From any cell, you may move one step at a time in the four cardinal directions:

Up: (r - 1, c)
Down: (r + 1, c)
Left: (r, c - 1)
Right: (r, c + 1)

You may only move to cells that are within bounds and free (0).

Part A: Shortest Path Length

Task:

Find the length (in number of steps) of the shortest path from (0, 0) to (n - 1, n - 1).

If there is no valid path, return -1 .
Input:
- An integer $n$ (e.g., up to a few hundred).
- An $n \times n$ matrix grid of 0s and 1s.
Output:
- A single integer: the minimum number of steps needed to reach (n - 1, n - 1) from (0, 0) , or -1 if impossible.

Describe the algorithm you would use and analyze its time and space complexity.

Part B (Follow-up): Enumerate All Paths

Now, suppose we want to find all possible paths from (0, 0) to (n - 1, n - 1) under the same movement and obstacle rules.

Describe an approach to enumerate all distinct simple paths (paths that do not revisit any cell).
Discuss:
- How you would represent each path in memory.
- The time and space complexity in terms of $n$ and the number of valid paths $K$ .
- Any practical limitations when $n$ is moderately large and/or when there may be exponentially many paths.

Solve tree diameter and grid path problems

Quick Overview

Question 1: Longest Path in a Tree

Question 2: Shortest Path in an Obstacle Grid (and All Paths)

Part A: Shortest Path Length

Part B (Follow-up): Enumerate All Paths

Submit Your Answer

Solve tree diameter and grid path problems

Quick Overview

Question 1: Longest Path in a Tree

Question 2: Shortest Path in an Obstacle Grid (and All Paths)

Part A: Shortest Path Length

Part B (Follow-up): Enumerate All Paths

Submit Your Answer