Interview Question Software Engineer in Tests
Not sure if there is a O(n) algo to solve this.
Otherwise, one can always sort the input and find the duplicate element in O(n log n).
ok... i can give an O(nlog n) solution too...
public int findUniqueData(data[i], data[j]){
j=i+1;
if(data[i]==data[j]){
int flag[i]=1;//set a flag if it is not unique
findUniqueData(data[i], data[j]);//recursive call
i++;
}
elseif(data[i]!=data[j]&&flag[i]!=1){
return data[i];
}
}
List of character is known (fixed in number ). iterate over string and find the frequency of character if it is 1 break the loop
time complexity O(n)
#define NUM_CHARS 256
char findUnique(char *searchString) {
int charCounter[NUM_CHARS];
for(int i=0; i<NUM_CHARS; i++)
charCounter[i] = 0;
for(i=0; searchString[i]; i++)
charCounter[searchString[i]]++;
for(i=0; searchString[i]; i++)
if(charCounter[searchString[i]] == 1)
break;
return searchString[i];
}
int unique(string s){
int a=0,b=0,x;
for(int i=0;i<(int)s.length();++i){
x=s[i]-'a';
if(a&(1<<x)) b|=1<<x;
else a|=1<<x;
}
x=(a&b);
for(int i=0;i<(int)s.length();++i) { if(!(a&(1<<(s[i]-'a'))) ) return i; }
return -1;
}
this works if the string has 'a'-'z'.
im sorry , if(!(a&(1<<(s[i]-'a'))) ) return i; shud be changed to
if(!(x&(1<<(s[i]-'a'))) ) return i;
logic is actually simple, set the (char-'a')th bit in a for the first tym the char appears in the string.
if it appears second tym, set the same bit in b.
now x=a&b has the corresponding (char-'a') bits set if the char is duplicated in the string. so return the first char where (x&1<<(char-'a') fails :)
Your approach brings no merit. It's just an alternative of using bit vector. Your solution assumes (without justification) that string is made of [a,z] only. What about UNICODE char set, which has 2^16 chars.
public int returnFirstUnique(int data[]){ int n=data.length; int unique; for(int i=0;i<n-2;i++){ for(int j=i+1;j<n;j++){ if(data[i]!=data[j]){ unique=1;} else{ unique=-1; break;} }//end the inner loop if unique>0{return unique;} }//end the outer loop }this runs O(n^2) times worst case
- olivebranch March 16, 2011please correct me if i am wrong... Thanks, olivebranch!