0

Fill a weekly work schedule to an exact hour total

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Fill a weekly work schedule to an exact hour total

Companies: Snowflake

Difficulty: Medium

Problem statement

A week's work plan is written as a 7-character string pattern, one character per day. A digit (0-9) is a day whose hours are already set. A ? is a day that is still open.

Implement:

def find_schedules(work_hours: int, day_hours: int, pattern: str) -> list[str]

Replace every ? with a digit from 0 to day_hours so that the seven digits sum to exactly work_hours. Return every valid schedule as a 7-character string, in ascending lexicographic order. Return an empty list if none exists. Digits already in the pattern never change.

Constraints

  • len(pattern) == 7
  • 0 <= day_hours <= 8
  • 0 <= work_hours <= 56

Example 1

work_hours = 24, day_hours = 4, pattern = "08??840"
-> ["0804840", "0813840", "0822840", "0831840", "0840840"]

The fixed days sum to 20, so the two open days must share 4 hours, each at most 4.

Example 2

work_hours = 10, day_hours = 3, pattern = "1111111"
-> []

There are no open days and the fixed days sum to 7, not 10.

Approach

Clarify first. The input is a 7-character pattern of digits and ?, a weekly total work_hours, and a per-day cap day_hours for the open days. Pin down:

  • What to return. Every way to fill the ? days so the week sums to exactly work_hours, as full 7-character strings, sorted in ascending order. An empty list if there is no way.
  • Fixed days are fixed. A digit already in the pattern is never changed, even if it is larger than day_hours.
  • Range of a ?. Each open day takes 0..day_hours hours. Because every value is a single digit, string order equals numeric order day by day, so generating values from small to large gives sorted output for free.

Reduce the problem. Subtract the fixed digits from work_hours. Call the result need and the number of ? days k. If need < 0 or need > k * day_hours, the answer is empty. Otherwise the task is: list every sequence of k numbers in 0..day_hours that sums to need.

Brute force. Try all (day_hours + 1)^k fillings and keep those with the right sum. With k = 7 and day_hours = 8 that is 9^7, about 4.8 million candidates. It works for one call, but most of the work is wasted on fillings that can never reach the target.

Backtracking with pruning. Fill the open days left to right. Before giving the current day h hours, check that the remaining days can still absorb what is left:

0 <= need - h <= (days_left - 1) * day_hours

So h runs from max(0, need - (days_left - 1) * day_hours) to min(day_hours, need). With this bound, every branch we enter leads to at least one valid schedule. No work is wasted: the cost is proportional to the size of the output.

Invariant. At each step, need is the number of hours still to place, and 0 <= need <= days_left * day_hours. When days_left reaches 0, need is 0 and the current fill is a valid schedule. Values are tried in ascending order at every position, so results come out in lexicographic order.

Code

from __future__ import annotations


def find_schedules(work_hours: int, day_hours: int, pattern: str) -> list[str]:
    """All fillings of '?' in `pattern` (each 0..day_hours) whose digits sum to work_hours.

    Results are in ascending lexicographic order.
    """
    if len(pattern) != 7:
        raise ValueError("pattern must have 7 characters")
    if not all(c == "?" or c.isdigit() for c in pattern):
        raise ValueError("pattern may contain only digits and '?'")

    fixed = sum(int(c) for c in pattern if c != "?")
    open_slots = [i for i, c in enumerate(pattern) if c == "?"]
    need = work_hours - fixed
    k = len(open_slots)

    if need < 0 or need > k * day_hours:
        return []

    chars = list(pattern)
    results: list[str] = []

    def fill(slot: int, remaining: int) -> None:
        days_left = k - slot
        if days_left == 0:
            results.append("".join(chars))  # remaining is 0 by the invariant
            return
        rest_cap = (days_left - 1) * day_hours
        low = max(0, remaining - rest_cap)
        high = min(day_hours, remaining)
        for h in range(low, high + 1):
            chars[open_slots[slot]] = str(h)
            fill(slot + 1, remaining - h)
        chars[open_slots[slot]] = "?"

    fill(0, need)
    return results


def count_schedules(work_hours: int, day_hours: int, pattern: str) -> int:
    """Number of valid schedules, without listing them (follow-up)."""
    need = work_hours - sum(int(c) for c in pattern if c != "?")
    k = pattern.count("?")
    if need < 0:
        return 0
    ways = [1] + [0] * need  # ways[s]: fillings of the slots so far that sum to s
    for _ in range(k):
        nxt = [0] * (need + 1)
        prefix = 0
        for s in range(need + 1):
            prefix += ways[s]
            if s - day_hours - 1 >= 0:
                prefix -= ways[s - day_hours - 1]
            nxt[s] = prefix
        ways = nxt
    return ways[need]


if __name__ == "__main__":
    # Need 4 across two days capped at 4.
    assert find_schedules(24, 4, "08??840") == ["0804840", "0813840", "0822840", "0831840", "0840840"]
    # Need 1 across four days capped at 2.
    assert find_schedules(3, 2, "??2??00") == ["0020100", "0021000", "0120000", "1020000"]
    assert find_schedules(10, 3, "1111111") == []
    assert find_schedules(7, 3, "1111111") == ["1111111"]
    assert count_schedules(56, 8, "???????") == 1
    assert find_schedules(56, 8, "???????") == ["8888888"]
    assert find_schedules(0, 8, "???????") == ["0000000"]
    assert find_schedules(57, 8, "???????") == []
    assert find_schedules(4, 8, "9??????") == []          # fixed digit already too high
    for wh, dh, p in [(24, 4, "08??840"), (3, 2, "??2??00"), (20, 5, "???????"), (9, 3, "1?2?3??")]:
        assert count_schedules(wh, dh, p) == len(find_schedules(wh, dh, p))
        out = find_schedules(wh, dh, p)
        assert out == sorted(out) and len(set(out)) == len(out)
    print("ok")

Complexity

Let k be the number of ? days (at most 7), d = day_hours, and R the number of valid schedules.

  • find_schedules: the pruning means every branch reaches a result, so the recursion tree has at most k nodes per result. Time is O(R * k) to build the tree plus O(R * 7) to join the strings, which is O(R) for a fixed week. Space is O(k) for the recursion plus O(R * 7) for the output.
  • Worst case for R: below (d + 1)^k, because the sum is fixed. For k = 7, d = 8 the largest answer (need 28) has 273,127 strings, so output size dominates everything.
  • count_schedules: O(k * need) time with a sliding-window prefix sum, O(need) space.

Test cases

  • work_hours = 24, day_hours = 4, pattern = "08??840": fixed days sum to 20, need 4 across 2 days → ["0804840", "0813840", "0822840", "0831840", "0840840"].
  • work_hours = 3, day_hours = 2, pattern = "??2??00": need 1 across 4 days → ["0020100", "0021000", "0120000", "1020000"].
  • No ? and the sum matches: 7, 3, "1111111" → ["1111111"].
  • No ? and the sum differs: 10, 3, "1111111" → [].
  • Every day open at the cap: 56, 8, "???????" → ["8888888"].
  • Every day open at zero: 0, 8, "???????" → ["0000000"].
  • Target above the maximum: 57, 8, "???????" → [].
  • A fixed digit already exceeds the target: 4, 8, "9??????" → [].
  • day_hours = 0: every ? becomes 0; the answer is one schedule if the fixed digits sum to work_hours, else empty.
  • Ordering check: the output is strictly increasing and has no duplicates.

Follow-ups

  1. Only count the schedules. Output can reach hundreds of thousands of strings. Counting is a bounded-compositions problem: DP over days where ways[s] is the number of fillings summing to s, updated with a sliding-window sum in O(need) per day (count_schedules above). Inclusion-exclusion gives a closed form too.
  2. Return the k-th schedule in sorted order, or page through results. Combine the two: at each open day, for h from low to high, count how many completions start with h (DP on remaining days and remaining hours). Skip whole blocks until the k-th falls inside one. O(k * d) per query after an O(k * need) table, no listing.
  3. Stream instead of building a list. Turn fill into a generator so callers can stop early or write to a file. Memory drops to O(k).
  4. Per-day caps or minimums. Replace the single day_hours with lo[i] and hi[i] for each open day. The pruning bound becomes a suffix sum of hi (and of lo for the lower side); the rest is unchanged.
  5. Longer horizons or multi-digit hours. For a 30-day month or hours above 9, the string order no longer matches numeric order once values have different widths. Define the output format (padded fields or lists of ints) and sort by tuple; the pruned backtracking still runs in output-proportional time.

Interviewer expectations

Mid-level (L4)

  • Asks whether fixed digits can exceed day_hours and how results are ordered.
  • Subtracts the fixed hours first and returns early when the target is out of range.
  • Writes a correct backtracking solution that yields sorted output, and tests the no-? and all-? cases.

Senior (L5)

  • Adds the "remaining days can still absorb it" bound and explains why it makes the work proportional to the output.
  • States complexity in terms of output size, and points out that output size, not search, is the real limit.
  • Offers the counting DP when asked "how many" and checks it against the list length.

Staff (L6+)

  • Moves to streaming, pagination and k-th-result ranking without materializing the list, and explains the API changes this implies.
  • Generalizes to per-day ranges and other horizons while keeping one pruning rule.
  • Discusses where a real scheduler would differ: constraints across days (rest days, max consecutive hours) that need state in the DP rather than a single remaining-hours number.

Sign in to comment, vote or remix.