← Bank of America Interview Insights

Bank of America·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Apr 2026

Summary

Quant engineer interview with a matrix DP problem. Short and to the point, just one coding question from what I can tell.

Questions Asked (1)

Q1

Given a binary matrix, find the area of the largest square containing only 1s.

Algorithms & Data Structures
Author's notes

Classic DP problem, the kind you either know cold or fumble through.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use dynamic programming where dp[i][j] represents the side length of the largest square ending at (i, j). For each cell with a '1', set dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1, and track the maximum side length to compute the area.

Pro tip: Emphasize that this DP solution runs in O(m*n) time and O(n) space if optimized to a single row, which is crucial for large matrices in banking applications. Also, mention that you would clarify edge cases like empty matrix or all zeros before coding.

1. Clarify the problem and constraints

Ask about matrix dimensions, whether the matrix can be empty, and if the square must be axis-aligned. Confirm that the area is side length squared.

2. Define the DP state and recurrence

Let dp[i][j] be the side length of the largest square of 1s ending at (i, j). If matrix[i][j] == '1', dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1; else 0.

3. Initialize and iterate

Initialize a DP table (or two rows) with zeros. Iterate through the matrix, compute dp values, and keep track of the maximum side length seen.

4. Compute and return the area

After filling the DP table, the area is max_side * max_side. Return that value.

5. Analyze complexity and optimize

State that time complexity is O(m*n) and space can be optimized to O(n) by using a single row and a variable for the previous diagonal. Discuss trade-offs.

Key Points to Mention

  • Dynamic programming state definition and recurrence relation
  • Time and space complexity analysis (O(m*n) time, O(n) space optimized)
  • Handling edge cases: empty matrix, single row/column, all zeros
  • Optimization from O(m*n) space to O(n) space using a rolling array
  • Explanation of why the recurrence works (minimum of three neighbors plus one)
  • Potential follow-up: finding the largest rectangle instead of square

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