Denmin Group Interview Question
Software Engineer / Developerswe need not to scan entire string, we will stop when there is a repetition, and we will start scan again. complexity O(k) where k=position of first repeated char
private char findIt(String s)
{
boolean[] bit = new boolean[26];
int index=-1;
for(int i=0;i<s.length();i++){
char c = s.charAt(i);
if (bit[c-97]==true){
index=i;
bit[c-97]=false; // reset it back to false, so now we have first group of non repetitive chars
break;
}
else
bit[c-97]=true;
}
if (index==-1) System.out.println("no repet");
for (int j=0;j<index;j++){
char cc = s.charAt(j);
if (bit[cc-97]==true)
return cc;
}
return 0;
}
Use a hashMap. Maxm 26 keys will be required.
- A May 23, 2010Scan the string and put count corresponding to chars in hashmap.
Now scan the string again and get values from hashmap for chars and return when count == 1.
Any better approach??