Merge Nested Dictionaries Iteratively
Company: Chicago
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Take-home Project
Given a list of Python dictionaries, merge them into a single dictionary **without using recursion**.
Rules:
- Process the dictionaries from left to right.
- If a key appears in only one dictionary, keep that key-value pair.
- If the same key appears in multiple dictionaries:
- when both values are dictionaries, merge those dictionaries using the same rules;
- otherwise, the value from the later dictionary overrides the earlier one.
- You may assume keys are strings.
Example:
- Input:
- `[{"a": 1, "b": {"x": 2}}, {"b": {"y": 3}, "c": 4}, {"b": {"x": 5}}]`
- Output:
- `{"a": 1, "b": {"x": 5, "y": 3}, "c": 4}`
Implement a function that returns the merged dictionary using an iterative approach.
Quick Answer: This question evaluates a candidate's skill in iterative data structure manipulation and handling of nested dictionary merging semantics, including conflict resolution and value overriding.
Merge dictionaries left-to-right, recursively merging nested dictionaries but implemented with an explicit stack.
Examples
Input: ([{'a': 1, 'b': {'x': 2}}, {'b': {'y': 3}, 'c': 4}, {'b': {'x': 5}}],)
Expected Output: {'a': 1, 'b': {'x': 5, 'y': 3}, 'c': 4}
Explanation: Prompt example.
Input: ([{'a': {'x': 1}}, {'a': 2}],)
Expected Output: {'a': 2}
Explanation: Later non-dict overrides.