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.

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.

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

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