Lyft software engineer interviews cover algorithms, data structures, system design, and coding problems drawn from real interview rounds.
[time, id, user, type, value], where time and value...Input: Array of stringss and t, return the shortest contiguous substring of s that contains every character in t, including its multiplicity. For example, if t contains two A characters, a valid substring must contain at least two A characters.Characters are case-sensitive, and their order in t does not constrain their order in the substring. If multiple valid substrings have the same minimum length, return the one with the smallest starting index in s. Return "" if no valid substring exists or if t is empty.Implement an algorithm that runs in O(len(s) + len(t)) time, including construction of the returned string. Do not enumerate every substring.Function or class signaturemin_window(s: str, t: str) -> str{"s": "ADOBECODEBANC", "t": "ABC"}Output:"BANC"Explanation:
"BANC", beginning at index 9, contains A, B, and C. No substring of length three contains all three required characters, so length four is optimal.Example 2:Input:{"s": "AAABBAAC", "t": "AABC"}Output:"BAAC"Explanation: A valid window needs two copies of
A, one B, and one C. The substring at indices 4 through 7 is "BAAC", satisfying all four required occurrences. Its length equals len(t), so no shorter answer is possible.Constraints:0 <= len(s), len(t) <= 200000.A–Z and a–z.s arrives as a one-pass stream and cannot be reread. Return the best window's inclusive start and exclusive end indices rather than its contents. Can you process the stream in O(len(s) + len(t)) total time using O(len(t)) auxiliary space, even when an arbitrarily long run of irrelevant characters appears?Sign up for free to access walkthroughs, AI-generated questions, and more.
Get Started Free