Arrays, strings and hash tables

Most coding rounds open with an array or a string, and the first thing the interviewer checks is whether you know what your containers cost. "I'll put them in a set" is a strong start only if you can say why lookup is fast, when it isn't, and what you'd use if the keys had to stay in order. This lesson covers what happens inside a hash table, a Python list and a string, then the index moves behind many array and string questions: counting, two indices walking toward each other, writing from the back, and grid arithmetic.

How a hash table finds a key

A hash table (Python's dict and set, Java's HashMap) keeps its entries in an array of slots, often called buckets. To store a key, it runs a hash function that turns the key into a large integer, then reduces that integer to a slot number, for example the remainder after dividing by the number of slots. To find the key later, it repeats the computation and looks in that one slot.

Two different keys can land in the same slot. That is a collision, and every hash table has a plan for it. Some keep a short list of entries in each slot and search it. Others, including CPython's dict, probe other slots in a sequence worked out from the hash until they find the key or an empty slot. Either way, once the table gets too full it allocates a bigger array and reinserts everything, so a lookup checks only a few slots on average.

That gives the costs to quote, with n the number of entries:

The worst case happens when many keys collide: a poor hash function, or keys an attacker picked to collide, puts them all in one slot, and every lookup compares against all of them. Two more details come up in interviews. Hashing a string of length L costs O(L), and a lookup that lands on a matching hash also compares the strings, another O(L), so string keys cost O(L) per operation. CPython caches the hash on each string object, which doesn't help when an equal string arrives as a new object, such as one read from input or built by slicing. And keys must be hashable. Python's mutable built-ins (list, dict, set) aren't, which is why a list can't be a dict key; a tuple can, as long as everything inside it is hashable too: (1, [2]) is rejected.

A balanced binary search tree keeps its height near log n by rebalancing as it inserts and deletes. Choose it when order matters: keys come out sorted, and "the latest event at or before time t" is one O(log n) query. Python has no built-in tree map; a sorted list with the bisect module gives O(log n) search but O(n) insertion.

"I'll index the orders by customer id in a dict. Each lookup is O(1) on average, so n lookups cost O(n) expected time, plus O(n) space for the index. If you need the customers in sorted order, or a worst-case bound, I'd use a balanced tree at O(log n) per operation."

Lists grow, strings don't

A Python list is a dynamic array: one block of memory holding references side by side, with spare room at the end. Reading or writing a[i] is O(1). append is O(1) amortized: usually it takes a spare slot, and once in a while the block is full, so Python allocates a bigger one and copies everything across. Because each new block is larger by a constant factor, the copying averages out to a constant amount per append; Big O as you'd say it in an interview shows why. What isn't cheap: insert(0, x) and pop(0) shift every element, O(n), and x in some_list scans, also O(n).

Strings in Python and Java are immutable: nothing changes a string in place. s += ch builds a new string and copies the old one into it, so growing a string one character at a time can cost 1 + 2 + ... + n character copies, O(n²) for n characters. CPython sometimes avoids the copy, but you can't count on it, and an interviewer who spots the pattern will ask. Collect the pieces in a list and join once at the end (Java's equivalent is StringBuilder). Here, inserting thousands separators into a string of digits:

def group_digits(digits, sep=","):
    """'1234567' -> '1,234,567'"""
    parts = []
    for i, ch in enumerate(digits):
        if i > 0 and (len(digits) - i) % 3 == 0:
            parts.append(sep)
        parts.append(ch)
    return "".join(parts)

That is O(n) time and space for n digits. Slicing hides the same cost: s[1:] copies n - 1 characters, so a recursive function that passes s[1:] down spends O(n²) on copies alone. Pass an index instead. The interviewer's view of this mistake: a correct answer with a quadratic loop inside result += ..., from a candidate who quotes O(n) for it.

Counting with a dict or a fixed-size array

A count often turns "for each item, scan the rest" into one pass. Use a dict when you don't know the keys in advance or they're sparse: user ids, words, arbitrary integers. collections.Counter is a dict built for this. Here is the first log line that brings any user to their third failed login:

def first_lockout(failed_logins, limit=3):
    """failed_logins: user ids in time order. Return (index, user) for the
    attempt that first brings any user to `limit` failures, else None."""
    failures = {}
    for i, user in enumerate(failed_logins):
        failures[user] = failures.get(user, 0) + 1
        if failures[user] == limit:
            return i, user
    return None

With n log lines and u distinct users, that's O(n) time on average and O(u) space.

When the keys are small integers in a known range, a plain list beats a dict: no hashing, less memory, and the slots come out in key order for free. For lowercase letters, counts = [0] * 26 and counts[ord(ch) - ord("a")] += 1. The space is O(1) in the input size, since 26 slots don't grow with the string. Say so, because an interviewer may ask whether O(26) counts as constant; it does while the alphabet is fixed. If the input could hold any Unicode character, go back to a dict.

Two indices moving toward each other

Many array and string questions fall to an index at each end, each moving inward until a rule stops it. Neither index moves back, so the scan is O(n) time and O(1) extra space for n elements. Take a list of trail elevations: does it climb strictly to one top and then fall strictly, with at least one step on each side? Walk one index in from the left while the trail climbs and one in from the right while it climbs leftward, then check that they stopped at the same place:

def rises_then_falls(heights):
    """True if heights climb strictly to one top, then fall strictly."""
    n = len(heights)
    lo, hi = 0, n - 1
    while lo + 1 < n and heights[lo] < heights[lo + 1]:
        lo += 1                  # climb from the left
    while hi > 0 and heights[hi - 1] > heights[hi]:
        hi -= 1                  # climb from the right
    return 0 < lo == hi < n - 1

State what each index means: everything up to lo is a strict climb, and everything from hi on is a strict descent. The edge inputs then answer themselves. A flat top stops the two indices at different places, a trail that only climbs leaves hi at the last index, and an empty or one-point list fails 0 < lo. In other problems the indices move by turns: compare the two ends, move the one that can't be part of a better answer, and be ready to say why.

Writing from the back

When an in-place edit moves values to higher indices, loop from the back; when it moves them to lower indices, loop from the front. Either way, you never overwrite a value you haven't read yet. Say a fixed-length list holds the latest readings, newest first, and the interviewer wants new readings added at the front with O(1) extra space, the oldest falling off the end:

def push_front(history, new):
    """history and new are newest first. Shift history right by len(new)
    in place; the oldest readings fall off the end."""
    n = len(history)
    k = min(len(new), n)
    for i in range(n - 1, k - 1, -1):    # back to front
        history[i] = history[i - k]
    for i in range(k):
        history[i] = new[i]
    return history

That's O(n) time for n = len(history) and O(1) extra space. Outside an interview, collections.deque(maxlen=n) does this for you; the point here is the direction of the loop. What the interviewer sees when the first loop runs front to back: with one new reading, history[1] gets the old history[0], then history[2] copies history[1], which already holds that same value, and every shifted slot ends up equal. Removing values is the mirror case: a read index and a write index both move forward, and the writer never passes the reader.

Grids: index arithmetic and bounds

A grid with R rows and C columns is a list of R row lists, so cell (r, c) is grid[r][c], row first. Build it with [[0] * C for _ in range(R)]. The shorter [[0] * C] * R makes R references to one row, so setting one cell changes that column in every row, and the interviewer watches values appear where nothing wrote them.

Keep the four moves in one list, DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)], and test 0 <= nr < R and 0 <= nc < C before reading grid[nr][nc]. Python won't always save you: grid[-1] quietly reads the last row, so a missing check on the low side gives wrong answers, not an error.

To store a cell as one number, for a visited array, use i = r * C + c, and get the cell back with r, c = divmod(i, C). Both use C, the number of columns. Test on a grid that isn't square, such as 2 by 3; on a square grid, swapping R and C hides the bug.

Practicing with these questions

Before coding any question on this page, say your container and its cost in one sentence, as in the quote above, and name the index moves you expect to need. Then write it with a timer running. When you finish, check your quoted cost against the code line by line: a slice, an in on a list or a += on a string inside a loop is where O(n) quietly becomes O(n²). For more drills of the same shape, work through the Blind 75 arrays topic.