First question was on binary search in which you were given two arrays and an integer d. You had to find count of all pairs such that arr[j] - arr[i]

Question

First question was on binary search in which you were given two arrays and an integer d. You had to find count of all pairs such that arr[j] - arr[i] <= d where i is pointer on first array and j is pointer on second array.

Accepted Answer

Count pairs in two arrays with difference less than or equal to d.

Sort both arrays in ascending order.
Initialize count to 0.
For each element in the first array, find the largest index in the second array such that arr[j] - arr[i] <= d.
Add the count of pairs for that element to the total count.
Return the total count.
Example: arr1 = [1, 3, 5], arr2 = [2, 4, 6], d = 2. Answer is 3 (pairs are (1, 2), (1, 4), (3, 2)).

Accepted Answer

def count_pairs(arr1, arr2, d):

arr1.sort()

arr2.sort()

count = 0

for x in arr1:

low, high = 0, len(arr2) - 1

while low <= high:

mid = (low + high) // 2

if arr2[mid] - x <= d:

low = mid + 1

else:

high = mid - 1

count += low

return count

# Example usage

arr1 = [1, 3, 5]

arr2 = [2, 4, 6]

d = 2

result = count_pairs(arr1, arr2, d)

print(result) # Output: 6

First question was on binary search in which you were given two arrays and an integer d. You had to find count of all pairs such that arr[j] - arr[i] <= d where i is pointer on first array and j is pointer on second array.

Top Amazon Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern

Top HR questions asked in Amazon Software Developer Intern

First question was on binary search in which you were given two arrays and an integer d. You had to find count of all pairs such that arr[j] - arr[i] &lt;= d where i is pointer on first array and j is pointer on second array.

Top Amazon Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern

Top HR questions asked in Amazon Software Developer Intern

First question was on binary search in which you were given two arrays and an integer d. You had to find count of all pairs such that arr[j] - arr[i] <= d where i is pointer on first array and j is pointer on second array.