← Flexport Interview Insights

Flexport·Software Engineer·Technical Phone Screen·Intermediate

IntermediateRejected
May 2026

Summary

First round coding interview at Flexport for a software engineer role. The problems themselves weren't unreasonable but the test setup was a mess and I ran out of time building trees by hand. Rejection came back within 30 minutes, and now I'm sitting on a 6-month freeze before I can try again.

Questions Asked (1)

Q1

Solve the House Robber III problem: given a binary tree where each node has a value, find the maximum amount you can collect without robbing two directly connected nodes.

Algorithms & Data Structures
Author's notes

The problem itself is fine, classic tree DP.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a post-order DFS that returns two values per node: the max loot if you rob this node (node value + grandchildren's non-rob values) and if you don't (max of children's rob/non-rob values). At the root, return the max of the two. This bottom-up DP avoids redundant computation and runs in O(n) time.

Pro tip: Clarify that 'directly connected' means parent-child edges, so you can't rob a node and its immediate children. Mention that the DP state is local to each node, making it a classic tree DP problem.

1. Clarify problem and constraints

Confirm that robbing a node means you cannot rob its immediate children, but grandchildren are allowed. Ask about tree size, value ranges, and whether recursion depth is a concern.

2. Define DP state

For each node, define two values: rob[node] = max loot if robbing this node, and notRob[node] = max loot if not robbing this node. These represent the optimal substructure.

3. Derive recurrence

rob[node] = node.val + notRob[left] + notRob[right]; notRob[node] = max(rob[left], notRob[left]) + max(rob[right], notRob[right]). This ensures no two adjacent nodes are robbed.

4. Implement post-order DFS

Traverse the tree recursively, returning a pair (rob, notRob) for each subtree. At the root, return max(rob[root], notRob[root]).

5. Analyze complexity and edge cases

Time O(n), space O(h) for recursion stack. Handle empty tree (return 0), single node (return its value), and skewed trees (consider iterative DFS if recursion depth is an issue).

Key Points to Mention

  • Tree DP with two states per node: rob vs. not rob
  • Post-order traversal to compute children before parent
  • Recurrence relation: rob = node.val + notRob(left) + notRob(right); notRob = max(rob, notRob) for each child
  • Time complexity O(n) and space complexity O(h) due to recursion stack
  • Handling edge cases: empty tree, single node, and skewed tree (potential stack overflow)
  • Comparison with naive approach (exponential) and why DP is necessary

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