Yatra.com Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
I guess...you could do it using binary search tree(or set if u wanted to use inbuild lib) with total complexity < O(n) ~ O(lg n)
Lets take two variables as
first_non_repetative=-infinity and second_non_repetative=-inifinity
take one element at a time and try to insert it in a binary search tree..so now if at any moment you get a collision(get same data in BST) (for a no say x)then don't insert it rather do
if(first_non_repetative == -infinity)
{
first_non_repetative = x;
}
else if(first_non_repetative!=x && second_non_repetative==-infinity)
{
second_non_repetative = x
return ///that would be the ans
}
PSEUDO CODE
=================
1) Iterate through elements of the array from the beginning and put them in hash table, key being array element and 1 as the value
2) If the next value in the array is already there , increase the value of that key by 1
3) Once all the array elements are added in hash table, iterate the array again from the beginning to find the value of each key.
4) Find the second key whose value is 1.
import java.io.*;
public class str1
{
public static void main(String a[])
{
int[] ar={3,4,3,4,4,3,2,4,1,9,8};
int[] a1=new int[100];
int i,c=1,j,f=0,m=0,k=0;
for(i=0;i<11;i++)
{ c=1;
for(j=i+1;j<11;j++)
{
for(k==0;k<11;k++)
{
if(ar[i]==ar[j]&&ar[j]!=a1[k])
{
c++;
k++;
}
}
if(c!=1)
a1[k]=ar[i];
System.out.println("the c is"+c);
System.out.println("the no is"+a1[k]);
if(c==1)
f++;
if(f==2)
m=ar[i];
}
System.out.println("the 2nd no is"+m);
}
}
Using a bitmap takes one pass of the array to find this
- Anonymous January 24, 2012