# The Hostile Takeover

> One dict eats another.

Canonical URL: <https://datadriven.io/problems/the_hostile_takeover>

Domain: Python · Difficulty: medium · Seniority: L4

## Problem

Given two dicts base and override, recursively merge: if a key exists in both AND both values are dicts, recurse. Otherwise override's value replaces base's value. Keys only in base are kept; keys only in override are added. Do not mutate inputs.

## Worked solution and explanation

### Why this problem exists in real interviews

This tests **recursive deep merge without mutation**, a pattern critical in configuration management and immutable data processing. It probes recursion, type checking, and the discipline to avoid side effects.

---

### Break down the requirements

#### Step 1: Copy the base dict

Start with a shallow copy of the base to avoid mutating the original.

#### Step 2: Iterate override keys and decide: recurse or overwrite

If both values are dicts, merge recursively. Otherwise, the override value replaces the base value.

#### Step 3: Return the merged result

Keys from both dicts are preserved; override wins on conflicts.

---

### The solution

**Immutable recursive deep merge**

```python
def deep_merge(base: dict, override: dict) -> dict:
    merged = dict(base)
    for key, value in override.items():
        if key in merged and isinstance(merged[key], dict) and isinstance(value, dict):
            merged[key] = deep_merge(merged[key], value)
        else:
            merged[key] = value
    return merged
```

> **Time and Space Complexity**
>
> **Time:** O(n) where n is the total number of keys across all nesting levels.
> 
> **Space:** O(n) for the merged output plus O(d) recursion stack where d is the maximum depth.

> **Interviewers Watch For**
>
> Whether the function is pure (no mutation of inputs). Test this by verifying `base` is unchanged after the call.

> **Common Pitfall**
>
> Using `base.update(override)` at any level. This mutates `base` and clobbers nested dicts.

---

## Common follow-up questions

- What if lists should be concatenated instead of replaced? _(Tests adding an `isinstance(value, list)` branch with `+` concatenation.)_
- How would you handle this iteratively? _(Tests using a stack of (base_dict, override_dict) pairs.)_
- What if you need a three-way merge? _(Tests `deep_merge(deep_merge(base, env), local)` chaining.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_hostile_takeover)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.