← Visa Interview Insights

Visa·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
Apr 2026

Summary

Visa SWE interview with a DP problem that looked familiar but had a twist that threw me off more than I'd like to admit.

Questions Asked (1)

Q1

You're given an array of binary strings and two integers m and n. Find the largest subset of those strings where the total number of zeros is at least m and the total number of ones is at least n. Each string can only be used once. Return the maximum subset size.

Algorithms & Data Structures
Author's notes

I recognized the 2D knapsack shape right away from LeetCode 474 and started setting up the DP table almost on autopilot.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Recognize this as a 0/1 knapsack variant where each string has a cost of (zeros, ones) and a value of 1. Use dynamic programming with a 2D state (i, j) representing the maximum number of strings that can be selected with at least i zeros and j ones. Iterate through each string and update the DP table in reverse order to avoid reusing the same string.

Pro tip: Clarify that 'at least' means we can cap the counts at m and n to keep the DP dimensions small, and mention that the time complexity is O(L * m * n) where L is the number of strings. This shows you understand optimization and edge cases.

1. Understand the problem and identify the pattern

Restate the problem: select a subset of strings to maximize size such that total zeros ≥ m and total ones ≥ n. Recognize it as a 0/1 knapsack problem with two cost dimensions.

2. Define the DP state and transition

Let dp[i][j] be the maximum number of strings that can be chosen with at least i zeros and j ones. For each string, update dp in reverse order: dp[min(m, i+zeros)][min(n, j+ones)] = max(dp[i][j] + 1, ...).

3. Initialize and handle base cases

Initialize dp[0][0] = 0 and all other states to -infinity (or 0 if we consider 'at least' as satisfying from the start). Actually, since we need at least m zeros and n ones, we can initialize dp[0][0] = 0 and others to -1 to represent unreachable.

4. Iterate through strings and update DP

For each string, count zeros and ones. Then iterate i from m down to 0 and j from n down to 0, and update dp[min(m, i+zeros)][min(n, j+ones)] = max(dp[min(m, i+zeros)][min(n, j+ones)], dp[i][j] + 1) if dp[i][j] is valid.

5. Return the result and analyze complexity

The answer is dp[m][n] (or the maximum over all states that meet the requirement). Time complexity O(L * m * n), space O(m * n).

Key Points to Mention

  • 0/1 knapsack with two cost dimensions (zeros and ones)
  • Dynamic programming state definition: dp[i][j] = max strings with at least i zeros and j ones
  • Reverse iteration to avoid reusing the same string
  • Capping counts at m and n to keep DP dimensions small
  • Time and space complexity analysis: O(L * m * n) time, O(m * n) space
  • Edge cases: empty array, strings with no zeros or ones, m or n zero

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