cswork / libraryOpen practice workspace

Coding questions · Meta

Solve shipping capacity and expression insertion

This combined prompt evaluates algorithmic problem-solving skills: the first problem tests array partitioning and capacity planning under ordering and resource constraints, and the second tests combinatorial expression generation, tokenization, and numeric edge-case handling in digit strings.

Problem A: Minimum shipping capacity

You are given an array weights where weights[i] is the weight of the i-th package. Packages must be shipped in order (you cannot reorder). You have D days to ship all packages.

Each day, you load a contiguous prefix of the remaining packages onto the ship, up to the ship's capacity C. The total weight loaded that day cannot exceed C.

Task: Return the minimum integer capacity C that allows shipping all packages within D days.

Input:

  • weights: array of positive integers
  • D: positive integer

Output:

  • Minimum feasible ship capacity C

Example:

  • weights = [1,2,3,4,5,6,7,8,9,10], D = 5 → output 15

Constraints (typical):

  • 1 <= len(weights) <= 1e5
  • 1 <= weights[i] <= 1e5
  • 1 <= D <= len(weights)

Problem B: Insert +, -, or concatenate to hit target

You are given a string s consisting only of digits (e.g., "123") and an integer target.

You may insert between any two adjacent digits one of:

  • '+'
  • '-'
  • nothing (concatenate digits into a multi-digit number)

This forms an arithmetic expression evaluated left-to-right with normal integer addition/subtraction.

Task: Return all distinct expressions (as strings) that evaluate to target.

Rules / edge cases:

  • A number token cannot have leading zeros (e.g., "05" is invalid), except the token "0" itself.
  • You must use the digits in s in order; you cannot reorder or skip digits.

Input:

  • s: digit string
  • target: integer

Output:

  • List of expression strings that evaluate to target (order not important)

Example:

  • s = "123", target = 6 → ["1+2+3"]
  • s = "105", target = 5 → ["10-5"] (but not "1+0+5" if it doesn't match)

Constraints (typical):

  • 1 <= len(s) <= 10~12 (small enough to allow backtracking)
  • Result count may be large; return all that exist

Minimum Shipping Capacity

Return the smallest ship capacity that can deliver packages in order within D days.

Constraints

  • weights are positive
  • 1 <= D <= len(weights)

Examples

Example 1

Input: ([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5)
Output: 15

Explanation: Classic example.

Example 2

Input: ([3, 2, 2, 4, 1, 4], 3)
Output: 6

Explanation: Capacity 6 works.

Hints

  1. Binary-search capacity and greedily count how many days it needs.

Insert Plus or Minus to Hit Target

Insert +, -, or nothing between digits to form all expressions that evaluate to target.

Constraints

  • s contains digits
  • multi-digit tokens cannot start with 0

Examples

Example 1

Input: ('123', 6)
Output: ['1+2+3']

Explanation: 1+2+3 hits 6.

Example 2

Input: ('105', 5)
Output: ['10-5']

Explanation: Concatenation is allowed without leading zero tokens.

Hints

  1. Backtrack over the next token, then add it with + or -.