Find The Duplicates using binarySearch python

Question

I got this interview question from Pramp. You can find it online through their website: https://www.pramp.com/challenge/15oxrQx6LjtQj9JK9XlA

Find The Duplicates

Given two sorted arrays arr1 and arr2 of passport numbers, implement a function findDuplicates that returns an array of all passport numbers that are both in arr1 and arr2. Note that the output array should be sorted in an ascending order.

Let N and M be the lengths of arr1 and arr2, respectively. Solve for two cases and analyze the time & space complexities of your solutions: M ≈ N - the array lengths are approximately the same M ≫ N - arr2 is much bigger than arr1.

Example:

input: arr1 = [1, 2, 3, 5, 6, 7], arr2 = [3, 6, 7, 8, 20]

output: [3, 6, 7] # since only these three

def find_duplicates(arr1, arr2):
    output = []

    for val in arr1:
        if b_search(arr2, val):
            output.append(val)

    return output


def b_search(A, value):
    lower_ind = 0
    upper_ind = len(A) - 1

    while lower_ind <= upper_ind:
        middle_ind = lower_ind + (upper_ind - lower_ind) // 2

        if A[middle_ind] == value:
            return value
        elif A[middle_ind] > value:
            upper_ind = middle_ind - 1
        elif A[middle_ind] < value:
            lower_ind = middle_ind + 1
    return False


#I also tested it against the test cases, and it passed all of the test cases.

# Input: [1, 2, 3, 5, 6, 7], [3, 6, 7, 8, 20]

print(find_duplicates([1, 2, 3, 5, 6, 7], [3, 6, 7, 8, 20]))
# Output: [3,6,7]



Test Case #1
Input: [11], [11],
Expected: [11],
Actual: [11]
Test Case #2
Input: [1,3,5,9], [2,4,6,10],
Expected: [],
Actual: []
Test Case #3
Input: [1,2,3,5,6,7], [3,6,7,8,20],
Expected: [3,6,7],
Actual: [3, 6, 7]
Test Case #4
Input: [1,2,3,5,6,7], [7,8,9,10,11,12],
Expected: [7],
Actual: [7]
Test Case #5
Input: [10,20,30,40,50,60,70,80], [10,20,30,40,50,60],
Expected: [10,20,30,40,50,60],
Actual: [10, 20, 30, 40, 50, 60]
Test Case #6
Input: [10,20,30,40,50,60,70], [10,20,30,40,50,60,70],
Expected: [10,20,30,40,50,60,70],
Actual: [10, 20, 30, 40, 50, 60, 70]

Answer 1

• Given that len(arr1) == n and len(arr2) == m, the bisection method has a \$O(n \log m)\$ time complexity. Notice that it is important which array is scanned, and which is bisected. You really want arr1 to be shorter than arr2 (do you see why?).

• That said, in case M ≈ N the bisection method has \$O(n \log n)\$ time complexity. However in this case you can achieve \$O(n)\$. The same linear algorithm applied to the general case yields \$O(n + m)\$. Picking the right one (\$O(n \log m)\$ vs \$O(n + m)\$) is the core of the question as I see it.

  I intentionally do not spell the linear algorithm out. It is quite simple.

• Returning value from b_search misses an opportunity to optimize further. Notice that both arrays are sorted, therefore you don't need to search the entire arr2 again and again: you are only interested in values to the right of where the last search ended.

  Consider instead returning an index. It should not be an index of the element found, but one that partitions arr2 into strictly smaller, and larger or equal than val. A bisect module conveniently provides a bisect_left method:

      from bisect import bisect_left
  
      def find_duplicates(arr1, arr2):
          output = []
          index = 0
          for val in arr1:
              index = bisect_left(arr2, val, index)
              if arr2[index] == val:
                  output.append(val)