Lyft Interview Guide

You are given a grid of oranges, some fresh, some rotten. Rotten oranges contaminate adjacent fresh oranges; find the minimum time until all oranges are rotten.

Design a key-value store that supports storing values associated with timestamps. You should be able to retrieve the value for a given key at the latest timestamp less than or equal to a given time.

Implement a function to read characters from a file using a provided read4 API, but the read function can be called multiple times, so you need to handle internal buffering.

Find the smallest substring within a larger string that contains all the characters of a target string. You need to locate the minimum window that satisfies this condition.

Design a stack that supports push, pop, top, peekMax, and popMax operations, all in O(1) time complexity where possible. The challenge lies in efficiently tracking and retrieving the maximum value within the stack.

Transform a sorted linked list into a balanced binary search tree. The tree's structure should reflect the sorted order of the list.

Determine if a given binary tree is a complete binary tree. A complete binary tree has all levels filled except possibly the last, which is filled from left to right.

Compress a given string by replacing consecutive repeating characters with the character followed by the count of repetitions. If the compressed string isn't shorter, return the original.

You have K sorted lists of numbers. Find the smallest range [min, max] that includes at least one number from each of the K lists.

Determine if a car, with a limited capacity, can complete a series of passenger pick-up and drop-off requests without exceeding its capacity at any point. You're given the number of passengers for each trip, the start location, and the end location.

Find all the shortest transformation sequences from a start word to an end word, using a dictionary of valid words. You can only change one letter at a time.

Precompute a matrix to efficiently calculate the sum of elements within any rectangular region of a given 2D matrix. You'll then handle multiple queries for different rectangular regions.

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. You need to implement a stack with an additional function to efficiently get the minimum value.

Given a string of digits, find the number of ways to decode it as a sequence of letters based on a simple mapping. Each digit can represent a letter, and pairs of digits can also represent a letter.

Given an unsorted array of integers, find the length of the longest consecutive elements sequence. These consecutive numbers do not need to be adjacent in the original array.

You have two jugs with different capacities. Can you measure a specific target amount of water using only these jugs and a water source?

Find the length of the longest substring within a given string that contains no repeating characters. The substring must be contiguous.

You are given a list of meeting time intervals. Determine the minimum number of conference rooms required to accommodate all the meetings without any overlap.

You're given boxes containing candies, some locked initially. Determine the maximum number of candies you can collect by strategically using keys found in open boxes to unlock others.

Design a data structure that efficiently stores a set of strings and allows for prefix-based searches. Implement methods to insert strings, search for complete words, and check if any word starts with a given prefix.