Amazon Interview Question
Software Engineer in TestsTeam: Chennai
Country: India
Interview Type: Phone Interview
int a[LENGTH];
for(i=0; i<LENGTH;i++)
{
if( 1== abs(a[i]-a[i+1]))
printf("%d %d",a[i],a[i+1]);
else
continue;
}
Time Copmplexity = O(n)
People have got the question wrong, I think.
The array could be {4,7,6,9,3}
4 and 3 are adjacent with difference 1.
For this version, use a hashtable, and given a[i], check if a[i] -1 and a[i]+1 are already there.
The question doesn't mention a 'circular' array!
Even if the array were circular, the O(N) solution can easily be fixed by extending the indices (and proper index mod) in the loop or an extra step outside the loop to check for the last-first element pair.
Using a hashtable for this problem appears, to me at least, to be a horrible idea.
No shams. You misunderstand the intrepreation of this question.
The difference 1 is defining what adjacent means.
They are not looking for a[i] and a[i+1] such that |a[i] - a[i+1]| = 1.
They are looking for i and j such that |a[i] - a[j]| = 1. For this version, hashtable is perfect.
Otherwise the problem is utterly trivial.
#include<stdio.h>
#include<conio.h>
main()
{
int i , j, a[20], n;
printf("entr the size of array ");
scanf("%d", &n);
printf("enter the element");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<n;i++)
{
j=i+1;
if((a[i]-a[j]==1)||(a[j]-a[i]==1))
{
printf("%d%d",a[i],a[j]) ;
}
else
printf(" there are such pairs of elements whose difference is equal to1 ");
}
getch();
}
Since you have to traverse the entire array atleast once, Time Complexity : O(n)
- Anonymous January 08, 2014