Drills

You're given a list of prices and a budget. Return whether any two distinct items add up to exactly the budget. The list is not sorted, and you scan it once.

You're handing out wristbands at a door, reading ID numbers one by one as people arrive. Return the first ID that you've already let in earlier — the first repeat, by arrival order. The IDs are not sorted, and you only get to read the line once, front to back.

Versions 1..n shipped in order, and at some point one bad commit broke the build — every version from that point on is also broken. You have a slow checker isBad(v) and want to find the first broken version. Each check is expensive, so you want to minimize the number of checks.

You're handed an array of weights that is already sorted in increasing order, plus a target. Return whether any two of them add up to exactly the target, using no extra storage. Because it's sorted, a smaller weight sits to the left and a larger one to the right.

You're given a pile of event timestamps in no particular order and a window k. Return whether any two events happened within k of each other. The timestamps arrive jumbled, and a close pair could be anywhere in the pile.

You're given a string of brackets using three kinds — round (), square [], and curly {}. Return whether they're validly nested: every closer matches the most recently opened bracket of its kind, and nothing is left open at the end. So "([])" is valid but "([)]" is not.

You have a singly linked list: each node only knows the next node, and you cannot jump to position k or read the length up front. Some buggy code may have made a later node point back to an earlier one, forming a loop. Return whether following next from the head eventually cycles forever instead of reaching an end, using only constant extra memory.

Given a list of distinct items, return every possible subset — including the empty set and the full set. Notice the shape: the subsets of the whole list are just the subsets of the remaining items, each taken twice — once without the first item, once with it added in. So the problem contains a smaller version of itself, and you solve it by reducing to a list with one fewer item until nothing is left.

You have an unlimited supply of coins in a few fixed denominations, say {1, 2, 5}. Given an amount, return the number of distinct ways to make exactly that amount. Order doesn't matter, so 1+2 and 2+1 count as the same way. The same smaller amounts keep coming up as you work toward the total, and the answer for a big amount is built from the answers for smaller amounts.

You're dropped into a grid maze with walls and open cells. From any cell you may step to an up/down/left/right neighbor, and every step costs the same. Return the minimum number of steps to reach the exit from the start, or report that it's unreachable. Each move has equal cost, and you want the shortest path measured in number of moves.

You have a list of daily rainfall amounts. Find the length of the shortest contiguous run of days whose rainfall adds up to at least a target amount, or report that no such run exists. The days must be back-to-back, and all the amounts are positive.

A wall of lockers is labeled with numbers. Every number appears exactly twice except for a single number, which appears once. Return that lone number. You may use only constant extra memory, and each pair of equal numbers should cancel out.

Patients arrive at an ER over time, each tagged with an urgency number. After every arrival you must immediately treat the single most urgent patient waiting, then keep going as new patients keep arriving. Return the order in which patients are treated. The set of waiting patients keeps changing, and you repeatedly need the most urgent one right now.

People keep becoming friends one pair at a time. After all the friendships are added, count how many separate friend groups exist, where being friends (even friends-of-friends) puts people in the same group. New connections keep merging groups together over time.

You have a map of cities connected by flights, and each flight has its own price. Starting from your city, find the cheapest total price to reach your home city. Each flight has a different cost, and you want the lowest total cost, not the fewest flights.