How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Maximize weighted subsequence pairs with wildcards

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

You are given a string `s` of length `n` consisting only of characters `'0'`, `'1'`, and `'!'`. Each `'!'` can be replaced by either `'0'` or `'1'`. For the final binary string, define: - `count10` = number of index pairs `(i, j)` with `i < j`, `s[i] = '1'`, `s[j] = '0'` (a subsequence pair, not necessarily adjacent). - `count01` = number of index pairs `(i, j)` with `i < j`, `s[i] = '0'`, `s[j] = '1'`. Given integers `x` and `y`, the total “error” is: `error = x * count10 + y * count01`. Return the maximum possible `error` over all replacements of `'!'`, modulo `1_000_000_007`. Example: `s = "101!1"` (with given `x, y`).

Quick Answer: This question evaluates combinatorial counting, string manipulation, and optimization under constraints, along with handling large-number results via modular arithmetic.

Part 1: Maximize weighted subsequence pair errors with wildcards

You are given a string s containing only '0', '1', and '!'. Each '!' must be replaced by either '0' or '1'. After all replacements, consider every pair of indices (i, j) with i < j: - if the characters form 01, that pair contributes x errors - if the characters form 10, that pair contributes y errors These are subsequence pairs, not substrings, so the two characters do not need to be adjacent. Return the maximum total number of errors possible after replacing all '!'. Because the answer can be large, return it modulo 10^9 + 7.

Constraints

1 <= len(s) <= 2000
s contains only '0', '1', and '!'
1 <= x, y <= 10^9

Examples

Input: ("101!1", 3, 2)

Expected Output:

Input: ("!", 5, 7)

Expected Output:

Input: ("!!", 4, 7)

Expected Output:

Input: ("1!!0", 2, 5)

Expected Output:

Input: ("101!1", 3, 2)

Expected Output: 15

Input: ("!", 5, 7)

Expected Output: 0

Input: ("!!", 4, 7)

Expected Output: 7

Input: ("1!!0", 2, 5)

Expected Output: 20

Input: ("10", 3, 8)

Expected Output: 8

Input: ("!!!", 6, 2)

Expected Output: 12

Input: ("000111", 4, 9)

Expected Output: 36

Hints

Process the string from left to right. When you place the current bit, its contribution depends only on how many 0s and 1s already exist before it.
For a prefix, you do not need the exact assignments of previous wildcards. It is enough to know how many of them were turned into 1s and the best score for that count.

Part 2: Maximize protected population by moving security units left once

There are n cities in a line, indexed from 1 to n. - population[i] is the population of city i + 1 in 0-based Python indexing. - unit is a binary string of length n. - unit[i] == '1' means city i + 1 initially has one security unit. Each security unit may either: - stay in its current city, or - move exactly one city to the left A unit can be moved at most once, and a unit in the first city cannot move left. After all moves, a city is considered protected if it has at least one unit. If multiple units end in the same city, that city still counts only once. Return the maximum total population of protected cities.

Constraints

1 <= n == len(population) == len(unit) <= 2 * 10^5
0 <= population[i] <= 10^9
unit contains only '0' and '1'

Examples

Input: ([10, 5, 8, 9, 6], "01101")

Expected Output:

Input: ([4, 7, 2], "000")

Expected Output:

Input: ([6, 2, 9], "110")

Expected Output:

Input: ([3, 9, 4], "011")

Expected Output:

Input: ([2, 8, 1, 7], "0101")

Expected Output:

Input: ([1000000000, 0], "11")

Expected Output: 1000000000

Input: ([5], "1")

Expected Output: 5

Input: ([10, 1, 1, 10], "0110")

Expected Output: 11

Hints

Consider each maximal consecutive block of 1s separately. Units from different blocks never need to interact.
If a block of k consecutive units starts at position l > 1 and ends at r, those k units can protect any k cities inside the interval [l-1, r].

Quick Overview

This question evaluates combinatorial counting, string manipulation, and optimization under constraints, along with handling large-number results via modular arithmetic.