Deep Equality of Two Records
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Deep Equality of Two Records
You are given two records (think of them as instances of a `struct` / `class` / nested object). Write a function that decides whether the two records are **deeply equal** — that is, they represent the same data, field by field, all the way down through any nested structure.
Each record is a JSON-like value built from the following kinds of values:
- a **scalar**: an integer, a string, a boolean, or `null`
- a **list**: an ordered sequence of values (each element is itself any of these kinds)
- an **object**: an unordered mapping from string keys to values (each value is itself any of these kinds)
Two values are deeply equal when **all** of the following hold:
1. They are the same kind (scalar vs. list vs. object).
2. **Scalars** are equal only when they have the same type *and* the same value. `1` (integer) is **not** equal to `"1"` (string), `true` is **not** equal to `1`, and `0` is **not** equal to `false`. `null` equals only `null`.
3. **Lists** are equal only when they have the same length *and* each pair of elements at the same index is deeply equal. **Order matters**: `[1, 2]` is not equal to `[2, 1]`.
4. **Objects** are equal only when they have exactly the same set of keys *and* the value under each key is deeply equal in both objects. **Key order does not matter**: `{"a": 1, "b": 2}` equals `{"b": 2, "a": 1}`.
Return `true` if the two records are deeply equal, and `false` otherwise.
### Input
Two values `a` and `b`, each a JSON-decoded value (scalar, list, or object/dictionary) using your language's native types.
### Output
A boolean: `true` if `a` and `b` are deeply equal under the rules above, otherwise `false`.
### Examples
**Example 1**
```
a = {"name": "Ada", "skills": ["go", "rust"], "active": true}
b = {"active": true, "name": "Ada", "skills": ["go", "rust"]}
```
Output: `true` (same keys and values; object key order is ignored).
**Example 2**
```
a = {"id": 1, "tags": ["x", "y"]}
b = {"id": 1, "tags": ["y", "x"]}
```
Output: `false` (list order differs).
**Example 3**
```
a = {"count": 1}
b = {"count": "1"}
```
Output: `false` (integer `1` vs. string `"1"` — different scalar types).
**Example 4**
```
a = {"meta": {"v": 1, "nested": [null, {"k": false}]}}
b = {"meta": {"nested": [null, {"k": false}], "v": 1}}
```
Output: `true`.
### Constraints
- The total number of values across both records (counting every scalar, list, object, and nested element) is at most $10^5$.
- Nesting depth is at most $1000$.
- Object keys are strings; there are no duplicate keys within a single object.
- The two inputs are independent — they may differ in kind at the top level (e.g. one a list, one an object), in which case the answer is `false`.
Quick Answer: This coding question tests a software engineer's ability to implement recursive structural comparison across nested, heterogeneous data types. It evaluates practical understanding of type-strict equality, recursive traversal, and the distinction between ordered and unordered collections — core competencies commonly assessed in algorithm-focused interviews.
You are given two records (think of them as instances of a `struct` / `class` / nested object). Write a function `deep_equal(a, b)` that decides whether the two records are **deeply equal** — that is, they represent the same data, field by field, all the way down through any nested structure.
Each record is a JSON-like value built from the following kinds of values:
- a **scalar**: an integer, a string, a boolean, or `null`
- a **list**: an ordered sequence of values (each element is itself any of these kinds)
- an **object**: an unordered mapping from string keys to values (each value is itself any of these kinds)
Two values are deeply equal when **all** of the following hold:
1. They are the same kind (scalar vs. list vs. object).
2. **Scalars** are equal only when they have the same type *and* the same value. `1` (integer) is **not** equal to `"1"` (string), `true` is **not** equal to `1`, and `0` is **not** equal to `false`. `null` equals only `null`.
3. **Lists** are equal only when they have the same length *and* each pair of elements at the same index is deeply equal. **Order matters**: `[1, 2]` is not equal to `[2, 1]`.
4. **Objects** are equal only when they have exactly the same set of keys *and* the value under each key is deeply equal in both objects. **Key order does not matter**: `{"a": 1, "b": 2}` equals `{"b": 2, "a": 1}`.
Return `true` if the two records are deeply equal, and `false` otherwise.
### Input
Two values `a` and `b`, each a JSON-decoded value (scalar, list, or object/dictionary) using your language's native types.
### Output
A boolean: `true` if `a` and `b` are deeply equal under the rules above, otherwise `false`.
### Constraints
- The total number of values across both records (counting every scalar, list, object, and nested element) is at most 10^5.
- Nesting depth is at most 1000.
- Object keys are strings; there are no duplicate keys within a single object.
- The two inputs are independent — they may differ in kind at the top level (e.g. one a list, one an object), in which case the answer is `false`.
Constraints
- The total number of values across both records is at most 10^5.
- Nesting depth is at most 1000.
- Object keys are strings; no duplicate keys within a single object.
- The two inputs may differ in kind at the top level, in which case the answer is false.
- Scalars must match in both type and value: int != string, bool != int, null == null only.
Examples
Input: ({"name": "Ada", "skills": ["go", "rust"], "active": True}, {"active": True, "name": "Ada", "skills": ["go", "rust"]})
Expected Output: True
Explanation: Same keys and values; object key order is ignored, so the records are deeply equal.
Input: ({"id": 1, "tags": ["x", "y"]}, {"id": 1, "tags": ["y", "x"]})
Expected Output: False
Explanation: List order matters: ["x", "y"] != ["y", "x"].
Input: ({"count": 1}, {"count": "1"})
Expected Output: False
Explanation: Integer 1 vs string "1" — different scalar types, so not equal.
Input: ({"meta": {"v": 1, "nested": [None, {"k": False}]}}, {"meta": {"nested": [None, {"k": False}], "v": 1}})
Expected Output: True
Explanation: Deeply nested objects with key order swapped at the inner level still match.
Input: (True, 1)
Expected Output: False
Explanation: Boolean true is not equal to integer 1 — different scalar types.
Input: (0, False)
Expected Output: False
Explanation: Integer 0 is not equal to boolean false — different scalar types.
Input: (None, None)
Expected Output: True
Explanation: null equals null.
Input: (None, False)
Expected Output: False
Explanation: null only equals null, not the boolean false.
Input: ([1, 2], [2, 1])
Expected Output: False
Explanation: Lists differ in element order.
Input: ({"a": 1}, {"a": 1, "b": 2})
Expected Output: False
Explanation: Different key sets — the second object has an extra key b.
Input: ([], {})
Expected Output: False
Explanation: An empty list and an empty object are different kinds, so not equal.
Input: ({}, {})
Expected Output: True
Explanation: Two empty objects have the same (empty) key set and are deeply equal.
Input: ([1, [2, [3, None]]], [1, [2, [3, None]]])
Expected Output: True
Explanation: Deeply nested identical lists are equal.
Input: ("hello", "hello")
Expected Output: True
Explanation: Identical string scalars are equal.
Hints
- First classify each value into a 'kind': null, bool, int, string, list, or object. Two values can only be equal if their kinds match — so a list is never equal to an object, and an int is never equal to a string.
- Watch the bool/int trap: in many languages a boolean compares equal to an integer (true == 1, false == 0). The spec forbids this, so distinguish bool as its own kind BEFORE checking int.
- Recurse: lists compare element-by-element in order (length must match first); objects compare by checking both have the same number of keys and that every key in one exists in the other with a deeply-equal value.