# What Changed Overnight

> Schema from yesterday vs today. Something changed.

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

Domain: Python · Difficulty: medium · Seniority: L4 · Asked in: Google

## Problem

A migration ran overnight, and you have the table's columns from before it (`old_schema`) and after (`new_schema`), each a list of `{'name', 'type'}` dicts. Return which columns were added, which were removed, and which kept their name but changed type.

## Example 1

Input:

```
new_schema = [{"name":"id","type":"BIGINT"},{"name":"age","type":"INT"},{"name":"phone","type":"VARCHAR"}], old_schema = [{"name":"id","type":"INT"},{"name":"email","type":"VARCHAR"},{"name":"age","type":"INT"}]
```

Output:

```
{"added":["phone"],"removed":["email"],"type_changed":[{"name":"id","new_type":"BIGINT","old_type":"INT"}]}
```

## Example 2

Input:

```
new_schema = [{"name":"zip","type":"VARCHAR"},{"name":"city","type":"VARCHAR"},{"name":"id","type":"BIGINT"},{"name":"score","type":"FLOAT"}], old_schema = [{"name":"id","type":"INT"},{"name":"city","type":"TEXT"},{"name":"country","type":"VARCHAR"}]
```

Output:

```
{"added":["score","zip"],"removed":["country"],"type_changed":[{"name":"city","new_type":"VARCHAR","old_type":"TEXT"},{"name":"id","new_type":"BIGINT","old_type":"INT"}]}
```

## Worked solution and explanation

### Why this problem exists in real interviews

This is column-by-column matching wearing a schema-drift costume. The trap: almost everyone walks the two lists and compares them position-by-position, which reports every column as added and removed the moment someone reorders them. The real skill is indexing each schema by name first, then doing set math on the keysets so order stops mattering and the whole thing runs O(n+m) instead of O(n*m).

---

### Break down the requirements

#### Step 1: Index both schemas by column name

Build a dict mapping column name to column type for each schema. This is the move that makes ordering irrelevant and lookups O(1).

#### Step 2: Find added and removed columns

Columns whose names are in new but not old are added; the reverse are removed. Subtracting the two keysets gives both directly. Sort each name list ascending.

#### Step 3: Find columns with changed types

For names present in both keysets, compare their types and emit a {'name', '`new_type`', '`old_type`'} dict for each mismatch, walked in sorted name order so the result is already ordered.

---

### The solution

**Name-indexed schema comparison**

```python
def schema_diff(new_schema, old_schema):
    new_map = {col['name']: col['type'] for col in new_schema}
    old_map = {col['name']: col['type'] for col in old_schema}
    new_names = set(new_map)
    old_names = set(old_map)
    added = sorted(new_names - old_names)
    removed = sorted(old_names - new_names)
    type_changed = []
    for name in sorted(new_names & old_names):
        if new_map[name] != old_map[name]:
            type_changed.append({
                'name': name,
                'new_type': new_map[name],
                'old_type': old_map[name],
            })
    return {
        'added': added,
        'removed': removed,
        'type_changed': type_changed,
    }
```

> **Time and Space Complexity**
>
> **Time:** O(n + m) where n and m are the column counts in each schema.
> 
> Space: O(n + m) for the indexed maps and result.

> **Interviewers Watch For**
>
> Do you index by column name before comparing? The candidates who reach for nested loops or positional comparison are the ones who quietly ship a diff that explodes on a harmless column reorder.

> **Common Pitfall**
>
> Treating a column reorder as schema drift. The problem cares about names and types, not positions. Indexing by name naturally ignores ordering; a positional zip of the two lists does not.

---

## Common follow-up questions

- How would you detect column renames? _(Tests heuristic matching: same type, similar position, only one candidate.)_
- What if schemas had nullable flags and default values? _(Tests extending the comparison to additional column attributes.)_
- How would you auto-generate ALTER TABLE statements from the diff? _(Tests translating diff categories to DDL: ADD COLUMN, DROP COLUMN, ALTER COLUMN TYPE.)_
- What if there were hundreds of schema versions to compare? _(Tests pairwise diff chaining or baseline comparison strategies.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/what_changed_overnight)
- [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). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.