Solve shipping capacity and expression insertion
Company: Meta
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## 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
Quick Answer: 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.
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
Input: ([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5)
Expected Output: 15
Explanation: Classic example.
Input: ([3, 2, 2, 4, 1, 4], 3)
Expected Output: 6
Explanation: Capacity 6 works.
Input: ([5], 1)
Expected Output: 5
Explanation: Single package.
Input: ([1, 2, 3], 3)
Expected Output: 3
Explanation: One package per day.
Hints
- 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
Input: ('123', 6)
Expected Output: ['1+2+3']
Explanation: 1+2+3 hits 6.
Input: ('105', 5)
Expected Output: ['10-5']
Explanation: Concatenation is allowed without leading zero tokens.
Input: ('00', 0)
Expected Output: ['0+0', '0-0']
Explanation: Leading-zero concatenation is not allowed.
Input: ('12', 5)
Expected Output: []
Explanation: No expression hits target.
Hints
- Backtrack over the next token, then add it with + or -.