Expedia Interview Question
Java DevelopersCountry: United States
Interview Type: Phone Interview
If we use the HashTable in Java. It is synchronized and It doesn't maintain the order in which we enter. So, use a LinkedHashMap instead.
public class FirstRepetitiveElementInList {
public static void main(String [] args) {
String text = "youtube facebook google amazon youtube google facebook";
List<String> wordList = Lists.newArrayList(text.split(" "));
HashMap<String, Integer> stringCounter = Maps.newLinkedHashMap();
for(String word: wordList) {
if(stringCounter.containsKey(word)) {
stringCounter.put(word, stringCounter.get(word) + 1);
}
else {
stringCounter.put(word, 1);
}
}
String nonRepetitiveString = getFirstNonRepetitiveElement(stringCounter);
if(nonRepetitiveString == null) {
System.out.println("Not exists");
}
else {
System.out.println(nonRepetitiveString);
}
}
private static String getFirstNonRepetitiveElement(HashMap<String, Integer> stringCounter) {
for(String key: stringCounter.keySet()) {
if(stringCounter.get(key).equals(1)) {
return key;
}
}
return null;
}
}
I think we dont need to use so hash table ...
this code may work..
char GetFirstNonRepititiveChar(char* str1)
{
int nLen = strlen(str1);
char retChar = NULL;
char ch[256];
memset(ch,0,nLen);
for(int i = 0; i < nLen; i++)
{
//Get Ncount inceremet and then restore
int val = ch[str1[i]];
val++;
ch[str1[i]] = val;
}
for(int i = 0; i < nLen; i++)
{
int val = ch[str1[i]];
if(val == 1)
{
retChar = str1[i];
break;
}
}
return retChar;
}
I think this code may work
char GetFirstNonRepititiveChar(char* str1)
{
int nLen = strlen(str1);
char retChar = NULL;
char ch[256];
memset(ch,0,nLen);
for(int i = 0; i < nLen; i++)
{
//Get Ncount inceremet and then restore
int val = ch[str1[i]];
val++;
ch[str1[i]] = val;
}
for(int i = 0; i < nLen; i++)
{
int val = ch[str1[i]];
if(val == 1)
{
retChar = str1[i];
break;
}
}
return retChar;
}
public static void search(String str) {
char[] look = str.toCharArray();
int[] seen = new int[256];
for(int i=0;i<look.length;i++){
if(seen[look[i]]==0){
seen[look[i]]=1;
}
else
seen[look[i]]=-1;
}
for(int i=0;i<seen.length;i++){
if(seen[i]==1){
System.out.println("First repeating char is "+ (char)i);
break;
}
}
}
Below code works. Please comment if Im using anything unnecessarily.
public class FirstNonRepetitiveChar{
public static void main(String args[]){
String str = args[0];
char chars[] = str.toLowerCase().toCharArray();
boolean notFound=true;
StringBuffer alreadyCheckedChars = new StringBuffer();
for(int i=0; i<chars.length; i++){
char currentChar=chars[i];
System.out.println("currentChar:" + chars[i]);
//alreadyCheckedChars.append(currentChar);
for(int j= 0; j<chars.length; j++){
System.out.println("currentChar:" + currentChar + " & chars["+j+"]:" + chars[j]);
if( i!=j && currentChar==chars[j]){
notFound=false;
break;
}
}
if(notFound){
System.out.println("FirstNonRepetitiveChar in " + str + " is " + currentChar);
break;
}
notFound=true;
}
}
}
// Here the array cset_[256] is the character set initialized to "0".
void firstNonRep( unsigned char* s )
{
unsigned int slen = strlen( (const char*)s );
unsigned char* si = s;
unsigned char ch;
while( *si != '\0' )
{
ch = *si;
cset_[ ch ]++;
si++;
}
for( unsigned int i=0; i<slen; i++ )
{
ch = s[i];
if( cset_[ch] == 1 )
{
printf( "First non rep is:%c in string: %s\n", ch, s );
return;
}
}
}
Here is what I thought of make two ArrayList: one unique and one duplicate. Once found in unique list move that to duplicate list
private static void nonRepeatingCharacter(String str) {
ArrayList<Character> includeList = new ArrayList<Character>();
ArrayList<Character> excludeList = new ArrayList<Character>();
char[] look = str.toCharArray();
for(Character i : look){
if(!excludeList.contains(i)){
if(includeList.contains(i)){
includeList.remove(i);
excludeList.add(i);
}else{
includeList.add(i);
}
}
}
System.out.println(includeList.get(0));
}
Simpler way to solve using substring and comparison.
public static void main(String[] args) {
String inputStr = "atbBQidcdedefghh";
for(int i = 0 ; i < inputStr.length() ; i++ )
{
String readChr = (new Character(inputStr.charAt(i)).toString());
String subStr = new String(inputStr.substring(i+1,inputStr.length()));
if(subStr.indexOf(readChr)!=-1)
{
System.out.println("The First repeating character is-->"+readChr);
break;
}
}
}
Use a hash table.
Iterate through every character in the string and insert into the hash table with key = character and value = count.
No re-iterate through the string checking the values in the hash table for each character. The first element with count = 1 should be your first non-repeated character.
// Assume you have an ASCII coded string
char first_non_rep(char* string, int length)
{
static int hash_table[256];
int i=0;
for (i = 0;i<length;i++)
{
hash_table[string[i]]++;
}
for (i=0;i<length;i++)
{
if (hash_table[string[i]]==1)
return string[i];
}
return '\0'
}
My understanding of this question is that repeating characters don't have to be next to eachother. e.g. the first non-repetitive character in this: "abaaaabc" is c.
- Anonymous April 25, 2012