Expedia Interview Question for Java Developers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
3
of 3 vote

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.

char getFirstNonRepetitiveChar(String str) {
  int[] seen = new int[256];
  // if seen[i] == 0 -> character wasn't seen
  // if seen[i] == -1 -> character was seen more than once
  // else seen[i] == the index that character was seen at

  for (int i=0; i<str.length(); ++i) {
    char c = str.charAt(i);
    if (seen[c] == 0) { // hasn't been see yet
      seen[c] = i; // save the index
    } else if (seen[c] != -1) { // has been see once
      seen[c] = -1;
    } // has already been seen more than once
  }
  // find min in the list such that min != -1 or 0
  int min = -1;
  for (int i=0; i<seen.length; ++i) {
    if (seen[i] != 0 && seen[i] != -1) {
      // for readability sake
      if (min == -1 || seen[i] < min) {
        min = seen[i];
      }
    }
  }
  return (min != -1) ? str.charAt(min) : '';
}

- Anonymous April 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
    }
}

- nandkarthik March 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
}

- rishi March 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Conceptually, your ch[] array *is* a hashtable...

- david.rebatto@gmail.com April 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Agreed.

- nandkarthik April 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- rishi March 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

will above work for 2 1 3 3 4 4. Looking at code it returns first small non repeating character which is wrong.

- N April 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}
}

- Suarez April 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}


}
}

- sreenivasulu May 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// 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;
}

}


}

- Rajesh J May 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

String s1 = "abaaaabcab";

for(int l=0;l<s1.length();l++){
char ch = s1.charAt(l);
if(s1.indexOf(ch)==s1.lastIndexOf(ch)){
System.out.println("Char--->"+ch);
}
}

- Anonymous May 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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));
	}

- intel3 October 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
			}
		}
	}

- Tarun Trehan July 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

String str = "aabbcfcddeeg";
		char[] chararr = str.toCharArray();
		for(int i=0;i<chararr.length;i++) {
			if(str.lastIndexOf(chararr[i]) == str.indexOf(chararr[i])) {
				System.out.println("Non repeating char ::"+chararr[i]);
				break;
			}

}

- purani86 August 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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'
}

- sreemana@buffalo.edu March 30, 2012 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More