Data structures and algorithms

1.Two indexes that hit a target

Write pair_indexes(nums, target) for a list of integers. Return [i, j] with i < j and nums[i] + nums[j] == target. If several pairs work, pick the one with the smallest j, and for that j the smallest i. An element cannot pair with itself. Return [] if no pair exists.

2.Group anagrams

Write group_anagrams(words) for a list of lowercase strings. Two words belong together if one is a rearrangement of the other's letters. Return a list of groups. Inside a group keep words in input order, including duplicates. Order the groups by where their first word appears in the input. Return [] for an empty list.

3.Longest run without repeats

Write longest_unique(s) that returns the length of the longest contiguous substring of s in which no character appears twice. Characters are case-sensitive, and spaces count as characters. Return 0 for an empty string.

4.Smallest window covering letters

Write min_window(s, t) that returns the shortest contiguous substring of s containing every character of t, counting repeats (if t has two 'a', the window needs two 'a'). Matching is case-sensitive. If several shortest windows exist, return the leftmost. Return "" if no window works or t is empty.

5.Triples that sum to zero

Write zero_triples(nums) for a list of integers. Find every distinct triple of values [a, b, c] taken from three different positions with a + b + c == 0. Write each triple ascending, list each value combination once, and sort the result ascending (compare a, then b, then c). Return [] if none.

6.First and last position

Write first_last(nums, target) where nums is sorted ascending and may contain duplicates. Return [first, last], the lowest and highest index holding target. Return [-1, -1] if target is absent, including for an empty list. Aim for O(log n) with binary search.

7.Search a rotated sorted list

Write rotated_search(nums, target). nums holds distinct integers that were sorted ascending and then rotated at an unknown point, e.g. [5, 6, 1, 2, 3]. It may also be unrotated or empty. Return the index of target, or -1 if it is absent. Aim for O(log n).

8.Merge overlapping intervals

Write merge_intervals(intervals) for a list of [start, end] pairs with start <= end, in any order. Merge intervals that overlap or touch ([1, 3] and [3, 5] become [1, 5]). Return the merged list sorted by start. Return [] for an empty list.

9.Rooms needed for meetings

Write rooms_needed(meetings) for a list of [start, end] pairs with start < end. A meeting occupies its room from start up to but not including end, so one ending at 10 frees its room for one starting at 10. Return the minimum number of rooms so no two meetings share a room at the same time. Return 0 for an empty list.

10.Balanced brackets

Write is_balanced(s) that checks the brackets (), [] and {} in s. Every opener must be closed by the same kind, in the right nesting order. Characters that are not brackets are ignored. Return True or False; an empty string or one with no brackets is balanced.

11.Evaluate postfix expression

Write eval_rpn(tokens) for a valid postfix (reverse Polish) expression given as a list of strings. Tokens are integers (possibly negative, like "-3") or one of + - * /. Process tokens left to right with a stack: an operator pops the two most recent values, uses the older one as the left operand, and pushes the result. Division truncates toward zero, so -7 / 2 is -3. Return the final integer.

12.Reverse a list in groups

Write reverse_groups(values, k) for a Python list. Reverse it in consecutive blocks of k items, starting from the front. A final block with fewer than k items keeps its order. k is at least 1. Return a new list; an empty input returns [].

13.Tree level order

Write level_order(tree) for a binary tree written as nested lists: a node is [value, left, right], and a missing child is None. Return a list of levels from the root down, each level being its values from left to right. Return [] if tree is None.

14.Validate a BST in array form

Write is_valid_bst(values) for a binary tree stored as a list: the root is at index 0 and the children of index i are at 2i+1 and 2i+2; None marks a missing node, indexes past the end are missing, and any entries below a missing node are ignored. Return True if every node is greater than all values in its left subtree and less than all in its right (no duplicates allowed). An empty list is valid.

15.Shortest path in a grid

Write grid_steps(grid) where grid is a non-empty list of equal-length, non-empty strings; '.' is open and '#' is a wall. Starting at the top-left cell, move up, down, left or right through open cells. Return the fewest moves needed to reach the bottom-right cell, 0 if they are the same cell, and -1 if it cannot be reached or either corner is a wall.

16.Count islands

Write count_islands(grid) where grid is a list of equal-length strings of '1' (land) and '0' (water). Land cells that touch up, down, left or right belong to the same island; diagonal contact does not connect them. Return the number of islands. An empty list or a grid of empty strings has 0.

17.Order tasks by dependencies

Write task_order(graph) where graph maps each task name to the list of tasks that must come after it; every task appears as a key. Return all tasks in an order where each task precedes everything it points to. Whenever several tasks are ready, take the alphabetically smallest first. Return [] if a cycle makes this impossible.

18.Closest points to origin

Write k_closest(points, k) for a list of [x, y] integer points. Return the k points closest to (0, 0) by straight-line distance, nearest first. Break distance ties by smaller x, then smaller y. Duplicate points count separately. If k exceeds the number of points, return them all in that order; k = 0 returns [].

19.Most frequent words

Write top_k_words(words, k) for a list of lowercase words. Return the k distinct words that occur most often, ordered by count from highest to lowest; words with equal counts go in alphabetical order. If there are fewer than k distinct words, return them all in that order. An empty list returns [].

20.Count words by prefix

Write prefix_counts(words, queries). For each query string, count the words in words that start with it, counting duplicate words each time they appear. A word counts as starting with itself, and the empty query matches every word. Return a list of counts in query order.

21.Ways to climb with given steps

Write climb_ways(n, steps) where steps is a list of distinct positive step sizes. Count the ordered sequences of steps that add up to exactly n, so 1+2 and 2+1 are different. n = 0 has one way (take no steps). Return 0 if n cannot be reached.

22.Fewest coins for an amount

Write fewest_coins(coins, amount) where coins lists distinct positive denominations, each usable any number of times. Return the smallest number of coins whose values sum to exactly amount. Return 0 when amount is 0, and -1 if the amount cannot be made.

23.Edit distance

Write edit_distance(a, b) that returns the fewest single-character edits needed to turn string a into string b. An edit is inserting one character, deleting one character, or replacing one character with another; each costs 1. Comparison is case-sensitive. Either string may be empty.

24.Rob houses on a ring

Write ring_robber(values) for non-negative house values arranged in a circle, so the first and last houses are neighbours. Choose houses so that no two chosen houses are neighbours, and return the largest possible total. One house: return its value. No houses: return 0.

25.Split a string into words

Write can_split(s, words) that returns True if s can be cut into one or more consecutive pieces that are each in words, using any word as often as you like; otherwise False. Matching is exact and case-sensitive. An empty s returns True.

26.Unique permutations in order

Write unique_perms(nums) for a list of integers that may contain repeats. Return every distinct ordering of all the values, each as a list, with no ordering listed twice, sorted in ascending lexicographic order (compare first elements, then second, and so on). An empty list returns [[]].

27.Decode nested repeats

Write decode(s) for a string of lowercase letters where k[...] means the bracketed part repeated k times; k is a positive integer that may have several digits, and brackets can nest. Letters outside any brackets are copied as they are. The input is always well-formed. Return the expanded string; an empty s returns "".

28.Stack that reports its minimum

Write run_min_stack(ops) that simulates a stack. Each op is ["push", x], ["pop"], ["top"] or ["min"]. push adds x and outputs nothing; pop removes and outputs the top value; top outputs the top without removing it; min outputs the smallest value currently on the stack. On an empty stack, pop, top and min output None. Return the outputs in order.