> For the complete documentation index, see [llms.txt](https://lei-d.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lei-d.gitbook.io/leetcode/facebook.md).

# facebook

## Q1

Given a list A of objects and another list B which is identical to A except that one element is removed, find that removed element.

### Solution 1: if there are no duplicates in the list

Convert list A and B to sets, find element in A set but not in B set.

Time complexity: O(n), because searching in set is O(1).

Space complexity: O(n)

Disadvantage of this solution is if there are duplicates in the list, when we convert to set, we will loss the duplicates. Then this solution is wrong.

```python
def findDeleted(A, B)
    diff = list(set(A) - set(B))
    return diff[0]
```

### Solution 2: if elements in A and B are numbers

Sum up all the elements in A and B, and the difference between sumA and sumB will be the deleted element.

```python
def findDeleted(A, B)
    sumA, sumB = 0, 0
    for i in A:
        sumA += i
    for j in B:
        sumB += j
    return sumA - sumB
```

### Solution 3: Use dictionary to store the frequency of B, and search each element in A

```python
def findDeleted(A, B)
    dic = {}
    for j in B:
        dic[j] = dic.get(j, 0) + 1
    for i in A:
        if dic.get(i) is None OR dic.get(i) == 0:
            return i
        else:
            dic.get(i) -= 1
```