CareerCup

// ZoomBA
def single_pass( string ){
   l = list()
   set( string.value ) ->{
     if ( $.item @ $.partial ){
       l -=  $.item 
     }else{
       l += $.item 
     }
     $.item // is the key 
   }
   empty(l) ? 'Nothing' : l[0] 
}

This question is really straight forward if more than one passes are allowed. The following are the approaches for more than one passes:

1) Brute Force: Simple O(N^2) solution, compare each character with all the remaining characters.
2) Using a Hashtable: O(N) solution, populate the Hashtable (lets say HashMap) in the first pass. The HashMap contains the character and the count of the character occurrences.
In the second pass, we can look at the count in the HashMap and figure out the the first unrepeated.

Single Pass Solution:
Use a combination of HashMap<Character, DoublyLinkedList> and Doubly Linked List.
1) If the character is not present in the HashMap, we add the a node to the doubly linked list and to the HashMap.
2) If the character is already present in the HashMap and has occurred only one time before (count of occurrences of character maintained in a different HashMap), we delete the node from the doubly linked list.
3) If the character is already present in the HashMap and has occurred more than one time before simply update the count in the HashMap that maintains the count.

Maintain the head of the doubly linked list in a separate reference throughout the pass, the value of this node will be the first unrepeated character.

Solution for the single pass HashMap and Doubly Linked List proposal:

public Character getFirstUnrepeatedCharacter(String inputString)
	{
		if(inputString==null)
			return null;
		
		int inputLength = inputString.length();
		
		if(inputLength<=0)
			return null;
		
		Map<Character,DoublyListNode> charHash = new HashMap<Character,DoublyListNode>();
		Map<Character,Integer> charCountHash = new HashMap<Character,Integer>();
		
		DoublyListNode firstUnrepeatedChar = null;
		DoublyListNode lastUnrepeatedChar = null;
		Character currentChar;
		DoublyListNode refCharNode;
		Integer currentCharCount;
		
		for(int charIndex=0; charIndex<inputLength; charIndex++)
		{
			currentChar = inputString.charAt(charIndex);
			refCharNode = charHash.get(currentChar);
			
			if(refCharNode==null)
			{
				DoublyListNode nodeToBeAdded = new DoublyListNode(currentChar);
				firstUnrepeatedChar = addDoublyNodeToList(firstUnrepeatedChar, lastUnrepeatedChar, nodeToBeAdded);
				lastUnrepeatedChar = nodeToBeAdded;
				charHash.put(currentChar, nodeToBeAdded);
				charCountHash.put(currentChar, 1);
			}
			
			else
			{
				currentCharCount = charCountHash.get(currentChar);
				if(currentCharCount==1)
				{
					firstUnrepeatedChar = removeDoublyNodeFromList(firstUnrepeatedChar, lastUnrepeatedChar, refCharNode);
					if(lastUnrepeatedChar == refCharNode)
					{
						lastUnrepeatedChar = lastUnrepeatedChar.prev;
					}
				}
				
				charCountHash.put(currentChar, currentCharCount+1);
			}
			
			DoublyListNode current = firstUnrepeatedChar;
			
			while(current!=null)
			{
				current = current.next;
			}
		}
		
		if(firstUnrepeatedChar==null)
			return null;
		
		return firstUnrepeatedChar.element;
	}



	private DoublyListNode removeDoublyNodeFromList(DoublyListNode firstUnrepeatedChar,
			DoublyListNode lastUnrepeatedChar, DoublyListNode refCharNode) {
		if(firstUnrepeatedChar == refCharNode)
		{
			if(firstUnrepeatedChar.next==null)
			{
				firstUnrepeatedChar=null;
				lastUnrepeatedChar=null;
			}
			else
			{
				firstUnrepeatedChar = firstUnrepeatedChar.next;
			}
		}
		
		else
		{
			if(lastUnrepeatedChar != refCharNode)
			{
				refCharNode.next.prev = refCharNode.prev;
			}
			refCharNode.prev.next = refCharNode.next;	
		}
		
		return firstUnrepeatedChar;	
	}

	private DoublyListNode addDoublyNodeToList(DoublyListNode firstUnrepeatedChar,
			DoublyListNode lastUnrepeatedChar, DoublyListNode nodeToBeAdded) {
		
		if(firstUnrepeatedChar==null)
		{
			firstUnrepeatedChar = nodeToBeAdded;
		}
		
		else
		{
			lastUnrepeatedChar.next = nodeToBeAdded;
			nodeToBeAdded.prev = lastUnrepeatedChar;
		}
		
		return firstUnrepeatedChar;
	}

class DoublyListNode
{
	char element;
	DoublyListNode next;
	DoublyListNode prev;
	
	DoublyListNode(char element)
	{
		this.element=element;
	}
}

Just maintain vector<pair<char, bool>> and map<char, int>.

char firstChar(string s) {
    vector<pair<char, bool> > v;
    map<char, int> m;
    for (size_t i = 0; i < s.length(); i++) {
        if (m.find(s[i]) != m.end())
            v[m[s[i]]].second = false;
        else {
            m[s[i]] = v.size();
            v.push_back({s[i], true});
        }
    }
    for (auto p : v) {
        if (p.second)
            return p.first;
    }
    return '#';
}

This is my solution passing only once in the array (string whatever) but using a queue to control de first unique:

package problems;

import java.util.*;

/**
 * Created by fsantos on 2/10/17.
 */
public class Prob153 {
    public static void findFirstUnique(int[] arr) {
        Queue<Integer> queue = new ArrayDeque<>();
        Map<Integer, Integer> freqMap = new HashMap<>();

        for (int i = 0; i < arr.length; i++) {
            Integer c = freqMap.get(arr[i]);
            if (c == null) {
                freqMap.put(arr[i], 1);
                queue.add(arr[i]);
            } else {
                freqMap.put(arr[i], c + 1);

                if (queue.peek() == arr[i])
                    queue.remove();
            }
        }

        boolean found = false;

        while (!queue.isEmpty()) {
            Integer x = queue.remove();
            Integer c = freqMap.get(x);

            if (c == 1 && !found) {
                System.out.println(x);
                // Guarantee to purge to queue
                found = true;
            }
        }
    }

    public static void main(String[] args) {
        findFirstUnique(new int[] {1, 2, 3, 1});
    }
}

Output:

2

Should just need a HashMap and if you traverse from end to front (still just one pass), the last unseen char is the answer. O(l) time and space where l is length of string.