Interview Question - Amazon - Help!
Anonymous User
381

You are given two arrays - both sorted and a distance d.
The numbers in array1 and array2 are both distinct ( no overlap )
eg -
Array1 - 0,2,4,9,11,13,14,16,18
Array2 - 5, 8, 19
d = 6
You have to return total count where element of Array1 and Array2 are within distance d.
Pick smaller array.

  1. taking element at index 0 of Array2.
    stRange = 5-5 = 0;
    enRange = 5+5 = 10;
    now do binary seach to get number of elements withing range 0-10 --> 0,2,4,9
    we get back 4
    add to result.
    Result = 4;
  2. taking element at index 1 of Array2.
    stRange = 8-5 = 3;
    enRange = 8+5 = 13;
    now do binary seach to get number of elements withing range 3-13 --> 4,9,11,13
    we get back 4
    add to result.
    Result = 4+4 = 8;
    3)taking element at index 2 of Array2.
    stRange = 19-5 = 14;
    enRange = 19+5 = 24;
    now do binary seach to get number of elements withing range 14-24 --> 14,16,18
    we get back 2
    add to result.
    Result = 4+4+3 = 11;
    Answer -- 11

I was able to talk the algo out, but the binary search to find range, I couldn't. Can someone tell me how you find the number of elements within the range. It should return 0, if that range is not to be found.

Comments (2)