CODEWITHSUNDEEP
javahashmap
Bob Doe
Bob Doe

Reputation: 41

Is it possible to find the first instance of a value from a Hashmap within the same loop?

Ok so I have an interview coding problem, and the problem states that in one loop I must find the first instance of a non repeating character. So for example if the string was "abcab" it would return c since a and b repeat.

I have the following which iterates through the entire string, and inputs the amount of characters that occur into a hash map, and it works.

private static  boolean findFirstCharacter(String s) {
     HashMap<Character, Integer> map = new HashMap<Character, Integer>();

       for(int i = 0; i < s.length(); i++) {
           char c = s.charAt(i);
            if(!map.containsKey(c)){
                map.put(c,1);

            }else{
               int value =  map.get(c);
               value++;
               map.put(c,value);


            }



        }


}

Now obviously I can just iterate again and find the first instance where the key has a value of 1, but It must be one loop. Is there anyway to do this given what I have or am I approaching this incorrectly?

Upvotes: 1

Views: 1082

Answers (4)

Andreas
Andreas

Reputation: 159086

Here is one way to do it in a single loop.

The method can handle Unicode characters from the supplementary planes, and has been modified to return the first non repeating character, instead of a boolean.

Note: The code requires Java 8+.

private static String findFirstCharacter(String s) {
    Set<Integer> singles = new LinkedHashSet<>(), duplicates = new HashSet<>();
    s.codePoints().forEach(ch -> {
        if (! duplicates.contains(ch) && ! singles.add(ch)) {
            singles.remove(ch);
            duplicates.add(ch);
        }
    });
    return (singles.isEmpty() ? null : new String(new int[] { singles.iterator().next() }, 0, 1));
}

Test

System.out.println(findFirstCharacter("abcab"));
System.out.println(findFirstCharacter("abcbca"));
System.out.println(findFirstCharacter("😀😈😍😀😈"));

Output

c
null
😍

Upvotes: 5

Timothy Truckle
Timothy Truckle

Reputation: 15622

The tricky part is that you need to filter out chracters with multiple occurence.

Your approach of counting the occurrences forces a second iteration over the map to filter the results.

Also you don't meet the requierment since you don't remember the actual index of the character.

I would do this with an extra collection like that (not tested):

 Collection<Character> seenCharacters = new HashSet<>();
 Map<Character, Integer> map = new HashMap<>();
 for(Character c : s.toCharArray()){
   if(seenCharacters.contains(c)){  // at least second occurrence
     map.remove(c); 
   } else {                         // first occurence
     seenCharacters.add(c);
     map.put(c,s.indexOf(c));
   }
 }

Of cause you have to do an aditional iteration over the result map for output (since System.out.println(map); is a hidden iteration).

But how do you identify the first nonrepeating character without an additional loop? – Holger

Sorry, missed that part.

to get that we change seenCharacters from Collection and HashSet to List and ArrayList.

 List<Character> seenCharacters = new ArrayList<>();

After the loop we cheat:

 seenCharacters.retainAll(map.keySet()); // hidden iteration
 retun seenCharacters.isEmpty()?
            ' ':
            seenCharacters.get(0);

But wait, we are not required to output the position, so we do not need the Map which makes it much easier ...

 List<Character> seenCharacters = new ArrayList<>();
 List<Character> singleCharacters = new ArrayList<>();
 for(Character c : s.toCharArray()){
   if(seenCharacters.contains(c)){  // at least second occurrence
     singleCharacters.remove(c); 
   } else {                         // first occurence
     seenCharacters.add(c);
     singleCharacters.add(c);
   }
 }
 retun singleCharacters.isEmpty()?
            ' ':
            singleCharacters.get(0);

Upvotes: 0

Holger
Holger

Reputation: 298143

The key point is to use a LinkedHashSet to hold all unique characters, which remembers the insertion order, hence, allows to retrieve the first one:

// better method name would be findFirstUniqueCharacter
private static char findFirstCharacter(String s) {
    HashSet<Character> unique = new LinkedHashSet<>(), seen = new HashSet<>();
    for(int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if(seen.add(c)) unique.add(c); else unique.remove(c);
    }
    return unique.isEmpty()? '_': unique.iterator().next();
}

seen.add(c) only adds the character if it is not contained in the Set and returns whether it has added it. It’s the often forgotten contract of all collections to return whether they have added the element, which together with the contract of Set makes additional contains checks obsolete.

So if seen.add(c) was successful, we add the character to the set of unique characters, otherwise, we remove it.

At the end of the loop, unique contains all remaining unique characters in the encounter order, so we can simply return its first element.

Upvotes: 4

Leviand
Leviand

Reputation: 2805

A possible and elegant solution could be done with this (required java 8)

private static  boolean findFirstCharacter(String s) {
    List<String> listChars = Arrays.asList(s.split(""));
    Map<String, Long> map = listChars.stream().collect(Collectors.groupingBy(c -> c, Collectors.counting()));

    for(String key : map.keySet()) {
        if(map.get(key) == 1) {
            System.out.println("Result: " + key);
            return true;
        }
    }
    return false;
}

Upvotes: 0

Related Questions