Set Equality - Determine If Two Collections Contain Identical Elements

Question

## Round 1 - Coding

## Problem

Implement a function that checks whether two input sequences contain exactly the same elements with the same frequencies (i.e., are equal as multisets), without using built-in set or Counter types.

```python
def are_equal_multisets(a: list, b: list) -> bool:
    # Return True if a and b contain exactly the same elements
    # with the same counts, regardless of order.
    # Do NOT use set(), Counter(), or sorted().
    ...
```

```
Example:
are_equal_multisets([1, 2, 2, 3], [3, 2, 1, 2]) -> True
are_equal_multisets([1, 2, 3],    [1, 2, 2])    -> False
are_equal_multisets([],           [])            -> True
are_equal_multisets(["a", "b"],   ["b", "a"])   -> True
```

**Extension:** Implement `set_difference(a, b)` that returns elements in `a` not in `b` (multiset difference).

```python
set_difference([1,2,2,3], [2,3]) -> [1, 2]
```

## Follow-ups

1. What is the time and space complexity of your approach?
2. Can you solve this in O(n) time for integer inputs?
3. How would you handle unhashable element types (e.g. lists inside lists)?
4. How does your solution change if elements have a defined ordering (so you can sort)?

Set Equality - Determine If Two Collections Contain Identical Elements

Question Details

Full Details

Topics

More from Pinterest