Parse URL query parameters with repeated and nested keys

Clarify first. Ask what the result type is and how the edge cases behave, because that is most of the question. A reasonable contract:

• The query string is everything after the first ? and before the first #. No ? means no parameters.
• Pairs are separated by &. Empty pieces (a=1&&b=2, a trailing &) are skipped.
• Each pair splits on its first =, so a value may itself contain =. A key with no = maps to "". A pair with an empty key (=5) is dropped.
• A key seen once maps to a string. A key seen more than once maps to a list of its values in order.
• Keys and values are decoded after splitting: + becomes a space and %XX becomes a byte. The bytes are read as UTF-8. A % that is not followed by two hex digits stays as it is.

Order of operations is the key idea. Split on & and = first, then decode each piece. If you decode first, an encoded %26 turns into a real & and splits a value in two. Most bugs in this question come from getting that order wrong.

Brute force. Many candidates start with query.split("&") and pair.split("="). That breaks on expr=a=b (three pieces), on flag (one piece), and on empty pieces. Fixing it with partition("=") and a skip for empty pieces is the step from a first draft to a correct one. Calling urllib.parse.parse_qs is fine to mention, but the interviewer wants you to write the parser.

Repeated keys. Keep one dict. The first time you see a key, store the string. The second time, turn it into a list of two. After that, append. This keeps the common case (one value) simple for callers. Some teams prefer "always a list". Ask, and say that it is one line to change.

Percent decoding. Decode into a bytearray, not a str. S%C3%A3o is two bytes for one character, so you must collect bytes and decode them as UTF-8 at the end. Decoding each %XX with chr() gives the wrong text for any non-ASCII value.

Part 2: nested keys. Bracket keys describe a path: user[address][city]=SF sets root["user"]["address"]["city"], and tags[]=a appends to the list root["tags"]. Split the decoded key into segments, walk or create dicts for every segment except the last, then store the value at the last one with the same repeat rule. A key whose brackets do not close is treated as a plain key. Conflicts, such as a=1 then a[b]=2, raise ValueError instead of silently losing data.

Invariants. Every value in the flat result is a str or a non-empty list[str]. In the nested result, a node is a dict, a str, or a list[str], and a later pair never replaces a node of a different kind.

from typing import Union

Value = Union[str, list[str]]
HEX = "0123456789abcdefABCDEF"


def decode(s: str) -> str:
    """'+' -> space, %XX -> byte; bytes decoded as UTF-8. Bad escapes stay literal."""
    out = bytearray()
    i = 0
    while i < len(s):
        c = s[i]
        if c == "+":
            out.append(0x20)
            i += 1
        elif c == "%" and i + 2 < len(s) and s[i + 1] in HEX and s[i + 2] in HEX:
            out.append(int(s[i + 1:i + 3], 16))
            i += 3
        else:
            out.extend(c.encode("utf-8"))
            i += 1
    return out.decode("utf-8", errors="replace")


def query_pairs(url: str) -> list[tuple[str, str]]:
    """Split the query string into decoded (key, value) pairs, in order."""
    q = url.find("?")
    if q == -1:
        return []
    query = url[q + 1:].split("#", 1)[0]
    pairs: list[tuple[str, str]] = []
    for part in query.split("&"):
        if not part:
            continue                      # "a=1&&b=2" or trailing "&"
        raw_key, _, raw_val = part.partition("=")  # split on the FIRST '='
        key = decode(raw_key)
        if key:                           # "=5" has no key: skip it
            pairs.append((key, decode(raw_val)))
    return pairs


def parse_query(url: str) -> dict[str, Value]:
    """Part 1: flat keys; a repeated key collects its values in a list."""
    result: dict[str, Value] = {}
    for key, val in query_pairs(url):
        if key not in result:
            result[key] = val
        elif isinstance(result[key], list):
            result[key].append(val)
        else:
            result[key] = [result[key], val]
    return result


def split_key(key: str) -> list[str]:
    """'user[address][city]' -> ['user', 'address', 'city']; 'tags[]' -> ['tags', '']."""
    first = key.find("[")
    if first <= 0:
        return [key]
    parts = [key[:first]]
    i = first
    while i < len(key):
        close = key.find("]", i)
        if key[i] != "[" or close == -1:
            return [key]                  # malformed: treat the whole key as flat
        parts.append(key[i + 1:close])
        i = close + 1
    return parts


def parse_nested(url: str) -> dict:
    """Part 2: bracket keys build nested dicts; a trailing '[]' appends to a list."""
    root: dict = {}
    for key, val in query_pairs(url):
        path = split_key(key)
        append = len(path) > 1 and path[-1] == ""
        if append:
            path.pop()
        if "" in path:
            raise ValueError(f"'[]' may only end a key: {key!r}")
        node = root
        for seg in path[:-1]:
            child = node.setdefault(seg, {})
            if not isinstance(child, dict):
                raise ValueError(f"{key!r}: {seg!r} is already a value")
            node = child
        leaf = path[-1]
        old = node.get(leaf)
        if old is None:
            node[leaf] = [val] if append else val
        elif isinstance(old, dict):
            raise ValueError(f"{key!r}: {leaf!r} is already an object")
        elif isinstance(old, list):
            old.append(val)
        else:
            node[leaf] = [old, val]
    return root

Let n be the length of the URL.

• decode: O(len(s)) time and space.
• query_pairs and parse_query: O(n) time. Each character is scanned a constant number of times (find, split, partition, decode). Dict operations are O(1) on average, ignoring key hashing, which is linear in key length and so still O(n) in total. Space is O(n) for the pairs and the result.
• parse_nested: O(n) time. Each pair walks a path whose length is bounded by its key length. Space is O(n).

• parse_query("https://x.com/search?year=2019&genre=drama") returns {"year": "2019", "genre": "drama"}.
• No query string: parse_query("https://x.com/search") and parse_query("https://x.com/?") both return {}.
• Repeated key: "/p?id=1&id=2&id=3" returns {"id": ["1", "2", "3"]}.
• Key with no = and an empty value: "/p?flag&x=" returns {"flag": "", "x": ""}.
• Empty pieces: "/p?a=1&&b=2&" returns {"a": "1", "b": "2"}.
• Empty key: "/p?=5&c=3" returns {"c": "3"}.
• Value containing =: "/p?expr=a=b=c" returns {"expr": "a=b=c"}.
• Decoding: "/p?q=new+york&city=S%C3%A3o%20Paulo" returns {"q": "new york", "city": "São Paulo"}.
• Encoded separator and bad escapes: "/p?amp=a%26b&pct=100%&bad=%zz" returns {"amp": "a&b", "pct": "100%", "bad": "%zz"}.
• Fragment: "/p?a=1#frag?b=2" returns {"a": "1"}.
• A second ? belongs to the value: "/p?next=/q?x=1" returns {"next": "/q?x=1"}.
• Nested: "/p?user[name]=ann&user[address][city]=SF&tags[]=a&tags[]=b" returns {"user": {"name": "ann", "address": {"city": "SF"}}, "tags": ["a", "b"]}.
• Encoded brackets: "/p?tags%5B%5D=x" returns {"tags": ["x"]}.
• Unclosed bracket stays flat: "/p?a[b=1" returns {"a[b": "1"}.
• Conflict: "/p?a=1&a[b]=2" raises ValueError. "/p?a[][b]=1" raises ValueError.

• Build the URL back (serialize). Write to_query(params): percent-encode every byte outside the unreserved set (A-Z a-z 0-9 - _ . ~), emit one k=v per list item, and for nested input emit bracket paths. Discuss whether parse(serialize(x)) == x holds (it does for this contract, except that a one-item list comes back as a string unless you use k[]).
• Typed values and a schema. Callers want year as an int and tags as a list even with one value. Add a schema such as {"year": int, "tags": list[str]}. Parse to strings first, then coerce and report per-field errors. Keeping parsing and validation separate is the main point.
• Limits and hostile input. A public service should cap the number of pairs, the key length, and the nesting depth (for example 1,000 pairs, depth 5). It should also reject keys like __proto__ if the result feeds JavaScript. Without caps, a[a][a]... builds a deep structure from a short URL. Return an error, do not truncate silently.
• Streaming or very long query strings. For a body-size query (form posts), read the input in chunks and keep a small state machine (in key, in value, in % escape) instead of holding the whole string. The output is the same.
• Indexed arrays. Support items[0]=a&items[2]=c. Store a dict keyed by index while parsing, then convert to a list at the end. Decide whether gaps become None or are compacted, and cap the largest index so items[999999999] cannot allocate a huge list.

Mid-level (L4)

• Splits on & and the first =, and handles a missing ?, empty pieces, and a key with no value.
• Handles repeated keys and gets + and %XX decoding right, at least for ASCII.
• Tests the edge cases out loud, without being prompted.

Senior (L5)

• States the contract before coding and explains why decoding happens after splitting.
• Decodes to bytes and then UTF-8, and handles malformed % without crashing.
• Finishes the nested part with clear behavior on conflicts and malformed brackets, and keeps the code readable.

Staff (L6+)

• Frames the API choices (string or list, last-wins or collect, strict or lenient) and why one fits callers better.
• Raises limits, depth caps and parameter pollution as security issues, and explains how parsing differences between a proxy and an app can be exploited.
• Separates parsing, decoding and typed validation so each can change on its own.