Solve tree diameter and grid path problems

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.

1. Describe an approach to enumerate all distinct simple paths (paths that do not revisit any cell).
2. 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.