Hash map merge

Merge two dictionaries deeply, combining values and preserving structure.

dictionaries recursion merging nested-data

Implement the function `merge_dicts(d1, d2)` that merges two dictionaries into a new dictionary according to the following rules:

- If a key exists in both dictionaries and both corresponding values are dictionaries, merge them recursively.
- If a key exists in both dictionaries and the values are not both dictionaries, the value from `d2` overrides the value from `d1`.
- Keys that exist in only one dictionary appear in the result with their original value.
- The original dictionaries must not be modified.
- The order of keys in the result is not important.

Example:
- `merge_dicts({'a': 1, 'b': {'x': 10}}, {'b': {'y': 20}, 'c': 3})` returns `{'a': 1, 'b': {'x': 10, 'y': 20}, 'c': 3}`.

You may assume that all values are either dictionaries, numbers, strings, booleans, `None`, lists, or other hashable immutable types. The function should handle arbitrarily nested dictionaries.

Constraints

- Input dictionaries are non-empty? (Not guaranteed; handle empty.)
- Depth can be arbitrarily large; recursion is fine for typical test cases.
- Complexity: O(N) where N is the total number of keys across both dictionaries, because each key is visited once.

Example

>>> merge_dicts({'a': 1, 'b': {'x': 10}}, {'b': {'y': 20}, 'c': 3})
{'a': 1, 'b': {'x': 10, 'y': 20}, 'c': 3}
>>> merge_dicts({}, {'a': 1})
{'a': 1}
>>> merge_dicts({'a': {'b': 2}}, {'a': 2})
{'a': 2}

15 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Try using a for loop over the union of keys from both dictionaries.

When both values are dictionaries, the result for that key is merge_dicts(v1, v2).

Start with a copy of d1 to avoid modifying the original.

For keys present only in d2, directly assign them.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.