Katkat
Back

Solve substring and worker assignment

LyftSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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.

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.