Parse URL query parameters with repeated and nested keys

A web service receives HTTP GET requests. The part of the URL after the first ? is the query string. Write a parser that turns it into a dictionary.

Part 1: flat parameters

Implement parse_query(url: str) -> dict[str, str | list[str]].

• The query string runs from just after the first ? to the first # (or the end). If there is no ?, return {}.
• Parameters are separated by &. Skip empty pieces, such as the gap in a=1&&b=2 or a trailing &.
• Each parameter splits on its first =. Everything after it is the value, even if it contains more =. A parameter with no = has the value "". Drop a parameter whose key is empty.
• If a key appears once, map it to its string value. If it appears more than once, map it to a list of all its values, in the order they appear.
• Decode keys and values after splitting: + is a space, and %XX (two hex digits) is one byte. Read the resulting bytes as UTF-8. Leave a % that is not followed by two hex digits unchanged.

Do not use urllib.parse or a similar library.

Example 1

parse_query("https://shop.example/list?size=m&color=red&color=blue&gift")
-> {"size": "m", "color": ["red", "blue"], "gift": ""}

Example 2

parse_query("/find?q=caf%C3%A9+near+me&redirect=/home?tab=2&note=50%25")
-> {"q": "café near me", "redirect": "/home?tab=2", "note": "50%"}

Part 2: nested keys

Implement parse_nested(url: str) -> dict with the same rules, plus bracket keys:

• a[b][c]=v stores v at result["a"]["b"]["c"], creating dicts as needed.
• A key that ends in [], such as tags[]=v, appends v to the list at result["tags"].
• A key whose brackets do not close normally is a plain key.
• If a key would need a node to be both a value and an object (for example a=1 and then a[b]=2), raise ValueError.

Example 3

parse_nested("/s?filter[price][max]=90&filter[city]=Lisbon&ids[]=4&ids[]=7")
-> {"filter": {"price": {"max": "90"}, "city": "Lisbon"}, "ids": ["4", "7"]}

Constraints

• The URL is at most 10^5 characters.
• Aim for time linear in the length of the URL.

Reconstructed from the reported question; details may differ from what interviewers ask.