Amazon interview question

Given an unsorted array and two numbers, find the minimum distance between them. For example, if the array is {1,2, 10, 2, 3, 5, 2, 1, 5} distance between 2 and 5 is 1.

Comments

  1. //this code returns 999 if the elements are not found
    //space =o(1) time =o(n)
    #include

    using namespace std;

    int find_distance(int* arr,int num1,int num2,int len)
    {
    int ptr1=0;
    int ptr2=0;
    int srch_ptr=0;
    int min_distance=1000;
    int found=0;
    while(srch_ptr<len && ptr1<len)
    {
    while(arr[ptr1]!=num1 && srch_ptr<len && ptr1<len)
    {
    ptr1++;
    srch_ptr++;
    }

    while(arr[srch_ptr]!=num2 && srch_ptr<len)
    {
    srch_ptr++;
    if(arr[srch_ptr]==num1)
    {
    ptr1=srch_ptr;
    }
    if(arr[srch_ptr]==num2)
    {
    ptr2=srch_ptr;
    int distance=ptr2-ptr1;
    //cout<<ptr1<< " "<<ptr2<<endl;
    if(distance<min_distance)
    {
    min_distance=distance;
    }
    break;
    }
    }
    srch_ptr++;
    ptr1=srch_ptr;
    }
    return min_distance-1;
    }


    int main()
    {
    int arr[]={0,5,1,2,3,4,6};
    int len=sizeof(arr)/sizeof(arr[0]);
    int ans=find_distance(arr,2,5,len);
    cout<<ans;
    return 0;


    }

    ReplyDelete
  2. @priyaranjan cud plz chk if the code is correct... i hav my interview scheduled in few days...

    ReplyDelete
  3. @ankit here is my code please check and can reply back if any prob:

    int minDist(int[] arr, int x, int y){

    int mindist = MAX, currdist = MAX;
    int curr_x = -1, curr_y = -1, min_x = -1, min_y = -1;

    for(int i=0; i<arr.length(); i++){

    if (arr[i]== x)
    curr_x = i;
    else if(arr[i] == y)
    curr_y = i;

    if(curr_x != -1 && curr_y != -1){
    currdist = Math.abs(curr_x - curr_y);
    if(currdist < mindist){
    mindist = currdist;
    min_x = curr_x;
    min_y = curr_y;
    }
    }
    }
    return mindist;
    }

    Time: O(n)

    ReplyDelete
  4. @priyaranjan lol.... i asked u ti find bug in my piece of code...nyways

    elegant code ... but wat shd be the op of this test case??
    {1,2, 10, 2,5, 2, 5}

    0 or 1??

    ReplyDelete
  5. @ankit it should be 1 and sorry your code was looking huge so i couldn't debug..:)

    ReplyDelete

Post a Comment

Popular posts from this blog