← Amazon Interview Insights

Amazon·Data Scientist·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
Jul 2026

Summary

Amazon Data Scientist interview with a coding question built around graph traversal. Pretty algorithmic for a DS role, but not shocking given Amazon's bar.

Questions Asked (1)

Q1

Given an adjacency list representing a directed acyclic graph, write a Python function that returns the length of the longest path in terms of number of nodes.

Algorithms & Data Structures
Author's notes

I knew DFS was the right move but fumbled a bit on where to add memoization.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the problem and edge cases, then explain that the longest path in a DAG can be found using dynamic programming with topological sorting or DFS with memoization. Write clean Python code, analyze time and space complexity, and test with examples.

Pro tip: Mention that the graph is a DAG, so no cycles, and that topological order ensures we process nodes in dependency order. Also, note that the longest path can be computed in O(V+E) time, which is optimal.

1. Clarify the problem

Confirm that the adjacency list represents a DAG, that path length is the number of nodes, and that the graph may be disconnected. Ask about input size and edge cases.

2. Choose an approach

Decide between topological sort with DP or DFS with memoization. Both are O(V+E). Explain the chosen method and why it works for DAGs.

3. Implement the solution

Write Python code for the chosen approach. For topological sort, compute in-degrees, use a queue, and update distances. For DFS, use recursion with memoization to compute the longest path from each node.

4. Analyze complexity

State that time complexity is O(V+E) and space complexity is O(V+E) for storing the graph and auxiliary arrays. Mention that this is optimal for this problem.

5. Test with examples

Walk through a small example, including a disconnected graph, to verify correctness. Discuss potential pitfalls like recursion depth and handling of isolated nodes.

Key Points to Mention

  • DAG property ensures no cycles, so longest path is well-defined and can be computed in linear time.
  • Topological sorting provides a linear ordering where each node appears before its descendants, enabling DP.
  • Dynamic programming: for each node, longest path = 1 + max(longest path of successors).
  • DFS with memoization avoids redundant computations and handles disconnected components.
  • Time and space complexity: O(V+E) time, O(V+E) space.
  • Edge cases: empty graph, single node, multiple components, and nodes with no outgoing edges.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.