Amazon Interview Question
Software Engineer / DevelopersTeam: Kindle-Periodicals
Country: India
Interview Type: In-Person
Complexity for this algorithm is O(n^2).
It can be done in O(n) with space complexity O(n)....
Need to create an array of size "N"(as given) say it b[ ]
if given array is a[ ] then we can do like this...
for(i=0;i<N;i++)
{
}
Sorry for previous incomplete code...
for(i=0;i<=N;i++)
b[i]=-1;
for(i=0;i<=N;i++)
{
if (a[i]<=N)
b(N-a[i])=a[i];
}
for(i=0;i < N/2; i++)
{
if(a[i] != -1 and a[N-i]!= -1)
prinftf("Pair:%d,%d\n",a[i],a[N-i]);
}
In the last for loop:
you mean
if(b[i] != -1 and b[N-i]!= -1)
prinftf("Pair:%d,%d\n",b[i],b[N-i]);
void findPairs(int[]a,int n){
Map<Integer,Integer>map=new HashMap<Integer,Integer>();
for(int i=0;i<a.length;i++){
Integer c=map.get(a[i]);
if(c==null)
map.put(a[i], 1);
else
map.put(a[i], c+1);
}
for(int i=0;i<a.length;i++){
int delta=n-a[i];
Integer c=map.get(delta);
if(c!=null)
if(delta==a[i]){
if(c>=2)
System.out.println(a[i]+","+delta);
}
else
System.out.println(a[i]+","+delta);
}
}
First sort the array
- NaiveCoder March 18, 2012void Pair(int a[],int n,int sum)
{
int i=0;
int j=n-1;
while(i<j)
{
if(a[i]+a[j] <sum)
i++;
else if(a[i]+a[j]>sum)
j--;
else
{
printf("%d %d\n",a[i],a[j]);
int k=j-1;
while(a[i]+a[k]==sum)
{
printf("%d %d\n",a[i],a[k]);
k--;
}
i++;
}
}