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.
Given an integer n, write a function that returns count of trailing zeroes in n!. Examples: Input: n = 5 Output: 1 Factorial of 5 is 20 which has one trailing 0. Input: n = 20 Output: 4 Factorial of 20 is 2432902008176640000 which has 4 trailing zeroes. Input: n = 100 Output: 24
//this code returns 999 if the elements are not found
ReplyDelete//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;
}
@priyaranjan cud plz chk if the code is correct... i hav my interview scheduled in few days...
ReplyDelete@ankit here is my code please check and can reply back if any prob:
ReplyDeleteint 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)
@priyaranjan lol.... i asked u ti find bug in my piece of code...nyways
ReplyDeleteelegant code ... but wat shd be the op of this test case??
{1,2, 10, 2,5, 2, 5}
0 or 1??
@ankit it should be 1 and sorry your code was looking huge so i couldn't debug..:)
ReplyDelete