Solve substring and worker assignment
Company: Lyft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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
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.