Pick the most items within two limits: A Sample Coding Interview Solution

The coding question

You're given a list of strings made of 0s and 1s, and two numbers m and n. Return the most strings you can pick so the total number of 1s is at most m and the total number of 0s is at most n.

Ask a few questions first

Ask	What we'll assume
Can I pick the same string twice?	No. Each string in the list can be picked once. Duplicates in the list are separate strings.
Which limit is which?	m caps the 1s and n caps the 0s, like the question says. Double-check, because the well-known version swaps them.
How big can things get?	Up to about 600 strings, and m and n up to 100.
Can strings be empty?	We'll say no, each has at least one character.

A couple of examples

Input	Output
strs = ["10", "0001", "111001", "1", "0"], m = 3, n = 5	4 ("10", "0001", "1", "0")
strs = ["10", "0", "1"], m = 1, n = 1	2 ("0" and "1")
strs = ["111", "1000", "1000"], m = 1, n = 6	1

Start with brute force

Try every subset of strings, add up its 1s and 0s, and keep the biggest subset that fits.

Cost: O(2^L × L) for L strings. Fine for 20 strings, hopeless for 600.

A better way

This is the 0/1 knapsack problem with two budgets instead of one. Each string costs some 1s and some 0s, and every string is worth 1.

So use dynamic programming: best[a][b] is the most strings we can pick using at most a ones and b zeros. For each string, either skip it or take it, which means best[a - ones][b - zeros] + 1.

We only need one 2D table if we fill it from big budgets down to small. Going downward means the cells we read haven't been updated for this string yet, so no string gets used twice.

Make a table best of size (m + 1) by (n + 1), all zeros.
For each string, count its ones and zeros.
For a from m down to ones, and b from n down to zeros, set best[a][b] to the larger of itself and best[a - ones][b - zeros] + 1.
Return best[m][n].

The code

solution.pypython

def most_strings(strs, m, n):
    # best[ones][zeros] = most strings we can pick using at most
    # that many 1s and 0s, from the strings seen so far.
    best = [[0] * (n + 1) for _ in range(m + 1)]
    for s in strs:
        ones = s.count("1")
        zeros = len(s) - ones
        # Go from high budgets down, so each string is used at most once.
        for a in range(m, ones - 1, -1):
            for b in range(n, zeros - 1, -1):
                best[a][b] = max(best[a][b], best[a - ones][b - zeros] + 1)
    return best[m][n]

	Cost	Why
Time	O(L × m × n + total length)	Each string touches the whole table once, after counting its characters
Space	O(m × n)	One table, reused for every string

Test it

Walk through one of the examples out loud, then check the cases that tend to break things:

An empty list returns 0.
A string that needs more 1s than m on its own is never picked, because its loop range is empty.
m = 0 still lets you pick all-zero strings.
Duplicate strings each count once, so ["0", "0"] with n = 2 gives 2.

Common mistakes

Mixing up m and n. Say out loud which one is the 1s budget.
Looping budgets upward, which lets one string be counted many times.
Going greedy by shortest string first. It often works, but not always, since a short string can use the scarce kind of character.
Building a 3D table indexed by string too, then running out of memory. It works, but the 2D version is what they're hoping to see.

Follow-up questions

What if each string had a different value?

Replace the + 1 with that string's value. Everything else stays the same.

Can you return which strings to pick?

Keep the 3D table, or record a decision per string and budget, then walk back from best[m][n].

What if there were three limits?

Add another dimension. The cost grows with each budget, so it only works while they stay small.

How the time adds up

Minutes	What you're doing
0–5	Ask questions and agree on examples
5–10	Brute force over subsets
10–20	Spot the knapsack and set up the table
20–35	Write the code
35–40	Test with the examples and edge cases
40–45	Follow-up questions

Key concepts used here

Dynamic programmingSolve each subproblem once and reuse the answer.

We wrote this sample solution ourselves. Practice Loop is independent and isn't affiliated with or endorsed by Amazon.