Visa·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

May 2026

Summary

Visa SWE interview with a dynamic programming problem that flips the usual constraint, which threw me off more than I expected for something that looks like a classic knapsack variant.

Questions Asked (1)

Given an array of binary strings and two integers m and n, find the size of the largest subset where the total number of zeros is at least m and the total number of ones is at least n. Each string can be used at most once.

Algorithms & Data Structures

Author's notes

I jumped straight to 2D DP because it looks exactly like the 0/1 knapsack problem on zeros and ones.

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 is an item with a cost of (zeros, ones) and a value of 1. Use dynamic programming with a 2D state dp[i][j] representing the maximum subset size achievable with exactly i zeros and j ones, iterating through each string and updating the DP table in reverse to avoid reusing items. Finally, return the maximum value in the DP table for all states where zeros >= m and ones >= n.

Pro tip: Clarify that the DP table can be sized (m+1) x (n+1) by capping counts at m and n, which reduces time and space complexity. Also mention that if the problem asks for 'at least', you can either track exact counts and take the max over the valid region, or modify the DP to track 'at least' directly by saturating counts.

1. Understand the problem and identify the pattern

Restate the problem: each string has a cost (zeros, ones) and value 1; we need to maximize the number of strings such that total zeros >= m and total ones >= n. Recognize this as a 2D 0/1 knapsack problem.

2. Define the DP state and recurrence

Let dp[i][j] be the maximum number of strings that can be chosen with exactly i zeros and j ones. For each string with z zeros and o ones, update dp[i][j] = max(dp[i][j], dp[i-z][j-o] + 1) for i from m down to z and j from n down to o.

3. Handle 'at least' constraints

Since the requirement is 'at least m zeros and at least n ones', after filling the DP table, the answer is the maximum value of dp[i][j] for all i >= m and j >= n. Alternatively, cap the counts at m and n during DP to directly compute the answer.

4. Implement and optimize

Initialize dp with 0 (or -infinity for unreachable states) and iterate through strings. Use a 2D array of size (m+1) x (n+1) and update in reverse order to avoid using the same string multiple times. Time complexity O(L * m * n) where L is number of strings.

5. Test with examples and edge cases

Walk through a small example to verify correctness. Consider edge cases: no valid subset, strings with zero zeros or ones, and large m/n relative to total counts.

Key Points to Mention

Dynamic programming approach with 2D state (zeros, ones) and value as subset size.
0/1 knapsack variant: each item can be used at most once, so iterate in reverse.
Time and space complexity: O(L * m * n) time, O(m * n) space, where L is number of strings.
Handling 'at least' constraints by either taking max over valid region or capping counts.
Optimization: cap zeros and ones at m and n to reduce state space.
Edge cases: empty array, strings with no zeros/ones, and when no subset satisfies the condition.

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