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 Onsite rounds at Lyft.

What role is this question designed for?

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

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.

Quick Answer: 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'.

Input: ('abdcab', 'ab')

Expected Output: 'ab'

Explanation: There are two shortest valid windows of length 2; return the earlier one.

Input: ('a', 'aa')

Expected Output: ''

Explanation: s does not contain enough copies of 'a'.

Input: ('abc', '')

Expected Output: ''

Explanation: An empty target requires no characters, so return the empty string.

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.

Input: [[2, 4], [2, 1], [3, 2], [7, 1]]

Expected Output: [0, 1, 1, 0]

Explanation: Two workers are enough. Jobs are processed by start time, and the smallest free worker ID is reused.

Input: []

Expected Output: []

Explanation: No jobs means no assignments.

Input: [[1, 0], [1, 0], [1, 1]]

Expected Output: [0, 0, 0]

Explanation: Zero-duration jobs occupy no time, so the same worker can be reused immediately.

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.

Quick Overview