Navan·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jul 2026

Summary

Did a technical phone screen for a software engineer role at Navan. The whole session was basically one problem that looked simple on the surface but had a real constraint twist that forced you to think carefully about space complexity and update order.

Questions Asked (1)

Implement a Pascal's Triangle-style DP problem where dp[i][j] = dp[i-1][j-1] + dp[i-1][j], but the 2D array causes an out-of-memory error. Solve it using O(N) space with a 1D rolling array, and explain why you must update right-to-left instead of left-to-right.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I started with the 2D approach out of habit and the interviewer stopped me pretty quickly to say it would OOM.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, explain the OOM issue with the 2D DP and propose reducing space to O(N) by using a 1D array that represents the current row. Then, describe the update rule and emphasize that iterating right-to-left is crucial to avoid overwriting values needed for the current row's computation. Finally, justify the time complexity remains O(N^2) and discuss trade-offs.

Pro tip: Mention that the right-to-left update is a common pattern in DP space optimization, and relate it to the 0/1 knapsack problem to show broader understanding.

1. Identify the problem

Explain that the 2D DP array causes O(N^2) space, leading to out-of-memory for large N. State the goal: reduce space to O(N).

2. Propose 1D rolling array

Introduce using a 1D array dp of size N+1, where dp[j] represents the current row's j-th element. Initialize dp[0] = 1 and update in place.

3. Derive update rule

Show that for each row i from 1 to N, we update dp[j] = dp[j] + dp[j-1] for j from i down to 1. This uses the previous row's values stored in dp[j] and dp[j-1].

4. Explain right-to-left necessity

Emphasize that updating left-to-right would overwrite dp[j-1] before it's used for dp[j], causing incorrect results. Right-to-left preserves the previous row's values.

5. Analyze complexity and trade-offs

State that time complexity remains O(N^2) and space is O(N). Discuss that this is optimal for space without changing time, and mention potential edge cases.

Key Points to Mention

Space complexity reduction from O(N^2) to O(N)
In-place update of 1D array
Right-to-left iteration to avoid overwriting
Time complexity remains O(N^2)
Connection to 0/1 knapsack DP optimization
Handling of edge cases (e.g., N=0, N=1)

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