Katkat
Back

Deep Equality of Two Records

UberSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to recursively compare two complex, nested data structures while handling different types like dictionaries, lists, and primitives.

Deep Equality of Two Records

Implement a function are_deeply_equal(obj1, obj2) that determines if two objects are structurally and value-equivalent. The objects can contain primitives (integers, strings, booleans, null), lists, and dictionaries.

Two objects are considered equal if:

  1. They are of the same type.
  2. For primitives, their values are identical.
  3. For lists, they have the same length and elements at corresponding indices are deeply equal.
  4. For dictionaries, they contain the same keys, and the values associated with each key are deeply equal.

Function Signature

def are_deeply_equal(obj1, obj2) -> bool:

Examples

Example 1:

# Input
obj1 = {"a": [1, 2], "b": {"c": 3}}
obj2 = {"a": [1, 2], "b": {"c": 3}}
# Output: True

Example 2:

# Input
obj1 = [1, {"x": 2}]
obj2 = [1, {"x": 3}]
# Output: False

Constraints

  • Objects can be nested to an arbitrary depth.
  • Dictionaries are unordered: {'a': 1, 'b': 2} is equal to {'b': 2, 'a': 1}.
  • You do not need to handle circular references in this version of the problem.

Edge Cases

  • Empty lists [] vs empty lists [] (True).
  • Empty dictionaries {} vs {} (True).
  • Mixed types (e.g., 1 vs "1" should be False).

Hints

Hint 1

Start by checking if the types of obj1 and obj2 are the same; if not, return False immediately.

Hint 2

For dictionaries, check if the set of keys is identical before recursing into the values.

Hint 3

For lists, iterate through indices and use a loop or recursion to compare the items at each position.

Follow-up questions

  • How would you modify your solution to handle circular references (e.g., a list that contains itself)?
  • What is the time complexity of your solution in terms of the total number of nodes in the data structures?
  • If the dictionaries were extremely large, would checking 'keys' via set conversion affect performance?