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.
[AMAZON] Vertical sum of nodes
Given a Binary Tree, find vertical sum of the nodes that are in same vertical line. Print all sums through different vertical lines. Examples: 1 / \ 2 3 / \ / \ 4 5 6 7 The tree has 5 vertical lines Vertical-Line-1 has only one node 4 => vertical sum is 4 Vertical-Line-2: has only one node 2=> vertical sum is 2 Vertical-Line-3: has three nodes: 1,5,6 => vertical sum is 1+5+6 = 12 Vertical-Line-4: has only one node 3 => vertical sum is 3 Vertical-Line-5: has only one node 7 => vertical sum is 7 So expected output is 4, 2, 12, 3 and 7
//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