Evaluate the Bracket Pairs of a String

Evaluate the Bracket Pairs of a String

What is this problem about?

In the Evaluate the Bracket Pairs of a String coding problem, you are given a string that contains keys enclosed in parentheses, such as (name). You are also given a dictionary (or a 2D array of key-value pairs). Your task is to replace every occurrence of a bracketed key with its corresponding value from the dictionary. If a key is not found in the dictionary, replace it with a question mark ?.

Why is this asked in interviews?

Google uses this problem to test basic string parsing and Hash Table interview pattern skills. It evaluates how efficiently you can extract substrings and perform lookups. It's a practical task that mimics template engine logic (like how variables are replaced in HTML templates). It checks if you can avoid O(N^2) string operations by using efficient string building techniques.

Algorithmic pattern used

The problem uses a One-pass String Parsing approach combined with a Hash Map.

1. Preprocessing: Store the knowledge base in a Hash Map for O(1) lookups.
2. Traversal: Iterate through the string character by character.
3. If you encounter (, start recording characters until you hit ).
4. Once you have the key, look it up in the map and append the value (or ?) to a result buffer.
5. For characters outside parentheses, append them directly.

Example explanation

String: hi (name), how is (place)? Knowledge: {"name": "bob", "place": "paris"}

1. Append "hi ".
2. Hit (: key is "name". Map has "bob". Append "bob".
3. Append ", how is ".
4. Hit (: key is "place". Map has "paris". Append "paris".
5. Append "?". Result: hi bob, how is paris?

Common mistakes candidates make

• String Concatenation: Using res += char in a loop in languages like Java or Python, which creates new string objects and results in O(N^2) time. Use a StringBuilder or a list of characters.
• Nested Brackets: Assuming brackets can be nested when the problem usually states they won't be (but it's good to clarify).
• Map Initialization: Re-creating the map multiple times or doing linear searches in the dictionary array.

Interview preparation tip

Always mention the difference between immutable and mutable strings. Using a StringBuilder (Java) or "".join(list) (Python) is a signal of a senior-level understanding of performance.