How to Find The Perfect Match? [3 Solutions For Interview Question]

Solution #1: Naive O(N2) Solution

Suppose we have a list of numbers A with N items. You can quickly iterate over all possible pairs in the list and check whether their sum equals to target. If we found such pairs, return their indexes; otherwise, we return None.

How can we find all possible pairs in a list?

The first observation is that any possible pair can be represented by the tuple (x,y)if 0≤x<N and 0≤y<N. Suppose a=A[x] and b=A[y], then we can represent the numbers a and b as the tuple (x,y). In other words, we can map the pair a and b by their corresponding positions in the list.

Well, It seems a straightforward task.

def findPerfect(numbers: List[int], target: int) -> Union[Tuple[int,int],None]:
    def ArePerfect(aa: int , bb: int, target: int) -> bool:
        return target == (aa+bb)

    size = len(numbers)
    for xx in range(0,size):
        for yy in range(0,size):
            if ArePerfect(numbers[xx], numbers[yy], target):
                return (xx,yy)
    return None  

We have N2 possible pairs to check. In other words, the algorithm runtime is O(N2)

Solution #2: Fixing the Solution 1

Well, We are in the right direction to solve this Facebook interview question. But there is bug in the above solution. Can you find it?

The error is that while any possible pair can be represented by the tuple (x,y) if 0≤x<N and 0≤y<N, the opposite is not valid. That is, not all tuples (x,y) where 0≤x<N and 0≤y<N maps to a valid pair. If x=y, the tuple (x,y) does not map to a valid pair. Why? if x=y then we have a pair with the same item, however, we want to find two different items in the list. Let’s fix it to eliminate the pairs from the form (x,x):

def findPerfect(numbers: List[int], target: int) -> Union[Tuple[int,int],None]:
    def ArePerfect(aa: int , bb: int, target: int) -> bool:
        return target == (aa+bb)

    size = len(numbers)
    for xx in range(0,size):
        for yy in range(0,size):
            if xx != yy and ArePerfect(numbers[xx], numbers[yy], target):
                return (xx,yy)
    return None  

Now, the solution is correct. We now check only N(N-1) pairs. But the algorithm runtime is still O(N2). Can you improve it?

Solution #3: Sum Operator is Symmetric

In our case we there is no importance to the order of the numbers. We all know that the sum operator is symmetric, in other words a+b=b+a, Therefore if the pair represented by the pair represented by tuple (x,y) is perfect match to target, then the pair represented by(y,x) is also perfect match to target.

Let’s update our observation: We need to check all tuples (x,y) where 0≤x<N and x+1≤y<N. In other words, all the tuples where y is smaller than x. This way, we will check all valid pairs at least once and only once. First, we eliminate the invalid pairs from the form (x,x). second, we eliminate the valid (p,q) where p>q since we will check this pair when we process the tuple (q,p)

Let’s update the the code:

def findPerfect(numbers: List[int], target: int) -> Union[Tuple[int,int],None]:

    def ArePerfect(aa: int , bb: int, target: int) -> bool:
        return target == (aa+bb)

    for xx in range(0,len(numbers)):
        for yy in range(xx+1,len(numbers)):
            if ArePerfect(numbers[xx], numbers[yy], target):
                return (xx,yy)
    return None 

We decrease the numbers of pairs we need to N(N-1)/2 pairs. We optimize the checking but it is still O(n^2) algorithm.

Conclusions For Perfect Match Facebook Interview Question

In the last operation, we use the observation that the sum operator is symmetric. However, not all the operators are symmetric. Suppose we change the definition: We say that the numbers, a and b, are a perfect match to target if ab = target. This claim does not hold anymore. For example: 23=8 while 3²=9.

We decrease the numbers of pairs, we need to check by using the symmetric property observation. However, the algorithm runtime is still O(N^2). The naive solution works, However, There is better solution to this Facebook interview question, Can you find another observation about what we want to find in the list and improve the runtime of the solution?