Solve substring and worker assignment

Quick Overview

This pair of problems evaluates competencies in string processing and multiplicity handling as well as scheduling and resource-allocation for interval tasks, testing the ability to choose and apply appropriate data structures while managing time and space complexity.

Company: Lyft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

The interview included two algorithm problems: 1. Shortest covering substring: Given two strings s and t, return the shortest contiguous substring of s that contains every character in t with at least the same multiplicity. If no such substring exists, return an empty string. 2. Minimum worker assignment: You are given a list of jobs, where each job has a start time and a duration. A job occupies the half-open interval [start, start + duration). Assign every job to a worker so that no worker is assigned overlapping jobs, and use the minimum possible number of workers. Return the worker assigned to each job in the original input order.

Overview: This pair of problems evaluates competencies in string processing and multiplicity handling as well as scheduling and resource-allocation for interval tasks, testing the ability to choose and apply appropriate data structures while managing time and space complexity.

Part 1: Shortest Covering Substring

Given two strings s and t, return the shortest contiguous substring of s that contains every character in t with at least the same multiplicity. For example, if t = 'AABC', the substring must contain at least two 'A' characters, one 'B', and one 'C'. If there are multiple shortest valid substrings, return the one that appears first in s. If no such substring exists, return an empty string.

Constraints

0 <= len(s), len(t) <= 200000
Characters are case-sensitive.
The answer should account for repeated characters in t.
If t is empty, return an empty string.

Examples

Input: ('ADOBECODEBANC', 'ABC')

Expected Output: 'BANC'

Explanation: 'BANC' is the shortest substring containing A, B, and C.

Input: ('bbaa', 'aba')

Expected Output: 'baa'

Explanation: The substring must contain two 'a' characters and one 'b'.

Hints

Keep a frequency map of the characters required from t.
Use a sliding window: expand the right side until the window is valid, then shrink the left side as much as possible.

Part 2: Minimum Worker Assignment

You are given a list of jobs, where each job is represented as [start, duration]. Job i occupies the half-open interval [start, start + duration), so a job ending at time x does not overlap a job starting at time x. Assign every job to a worker so that no worker is assigned overlapping jobs, while using the minimum possible number of workers. Return the worker assigned to each job in the original input order. For deterministic output, use 0-based worker IDs and follow this rule: process jobs in increasing start time, breaking ties by original input index. Whenever multiple workers are free, reuse the smallest-numbered available worker. If no worker is free, create a new worker with the next unused ID.

Constraints

0 <= len(jobs) <= 200000
0 <= start <= 10^9
0 <= duration <= 10^9
Each job is a pair [start, duration].
Intervals are half-open: [start, start + duration).

Examples

Input: [[0, 5], [1, 2], [6, 1]]

Expected Output: [0, 1, 0]

Explanation: The second job overlaps the first, so it needs a different worker. The third job can reuse worker 0.

Input: [[0, 3], [3, 2], [5, 1]]

Expected Output: [0, 0, 0]

Explanation: Because intervals are half-open, each job starts exactly when the previous one is free.

Hints

Sort the jobs by start time, but remember each job's original index so you can rebuild the answer.
Use one min-heap for busy workers by end time and another min-heap for currently available worker IDs.