CareerCup

I think about make two array of size 256, one to record the order of characters, and the other is to record the number each character appears

char getUniqueCharacter()
{
int counter[256]={0};
char order[256]={0};

int i=0;
while(hasNext())
{
char tmp=getNext();
if(counter[tmp]==0)
order[i++]=tmp;
counter[tmp]++;

}

for(int j=0;j<256;j++)
{
char tmp=order[j];
if(tmp!='#')
{
if(counter[tmp]==1)
return tmp;
}
}

return '#';
}


O(n) runtime

When they say its a stream you need to think of an object that holds its states and stream usually means one character at a time, this is a rough solution, you can complete on your own.

Public Class UniqueCharacter
{
	private InputStream is;
	private char uniqueChar = '#';
	private Map<char, char> chars = new Map();


	Public UniqueCharacter(InputStream is)
	{
		this.is = is;
	}
	public char getUniqueCharacter()
	{

		if (is.hasNext())
		{
			char tempChar = is.getNext();
			if (chars .put(tempChar, tempChar) == null)
			{
				//if its not already the hashmap
				this.uniqueChar = tempChar;

				//returns the unique character so far
				return tempChar;
			}
		}
		else
		{
			//returns the unique character so far
			return this.uniqueChar;
		}

	}



}

Create a 256 sized array. Assign "order" to the corresponding slot for a character if it is 0 and -1 otherwise. In the end, the min positive value will represent the first unique character.

Code in Python

def firstUnique():
    count = [0] * 256
     order = 1
     while hasNext():
         next = ord(getNext())
         if count[next] == 0:
               count[next] = order
               order += 1
          else:
               count[next] = -1

     firstUniq = -1
     for i in range(256):
          if count[i] > 0 and (firstUniq == -1 or count[firstUniq] > count[i]):
               firstUniq = i
     
     return chr(firstUniq) #Assume there's at least one uniq character

The solution to this problem is very simple. Just put each new character encountered as key in a LinkedHashMap and inititalize the value with 1.While reading the character from stream each time you encounter the character already present as key in hashmap, remove that key value pair. After the end of stream is read, the first key present in hashmap with value 1 will be the required character. Program would somewhat look like this:

public class CharacterReader
{
	InputStream ins ;
	public CharacterReader(InputStream ins)
	{
		this.ins = ins;
  	}
	public char getUniqueCharacter()
	{
		Map<Character,Integer> map = new LinkedHashMap<Character,Integer>();
		while(ins.hasNext())
		{
			char ch = ins.getNext()
			if (map.get(ch)!=null)
			{
				map.put(ch,1);
			}
			else
			{
				map.remove(ch);
			}
		}
		if(map.size() == 0)
		return '#';
		else
		{
			Set<Character> s = map.keySet();
			Iterator<Character> iter = s.iterator();
			return map.get(iter.next());
		}
 	}
}

Note: Assuming input stream have only alphabate, there is no special charcter or symbols.

char getUniqueCharacter(STREAM *in)
{
    int cunt=0, position;
    MinHeap MnHip; // Contains only once appeariance charcter
    int map[256] = {-1}; //This will map charcter to MeanHeap Table.
    int FLAG[256] = {0};
    char ch='\0';
    while(hasNext(in)){
        ch = getNext(in);
	if(FLAG[ch] == 0){/*Charcter comes 1st time*/
            position = MnHip.insert(ch, cunt);
	    map[ch] = position;
	    FLAG[ch] = 1;
	    cunt++;
	}else{/*Charcter comes 2nd time*/
	    position = map[ch];
	    if(position<=256){ /*This means char present in Heap else deleted because of more than once repetation*/
	        MnHip.delete(ch, position);
	        map[ch] = 300;//Max size of Heap is 256
	    }
	}
    }//while()
    if(MnHip.root) return MnHip.root;
    else return '#';
}

Data Strucure Use: Min Heap

T(N) = N*Log(256) //256 is number of unique char, N is length of input stream

public char findUnique(Iterator<Stream> st){
int map = new int[256];
int k = 0;
while(st.hasNext()){
k++;
char c = st.getNext();
if(map[c] == 0) map[c] = k;
else if(map[c] > 0) map[c] = -1;
}

int min = Integer.MAXINTEGER;
char mind = '#';

for(int i=0;i<256;i++){
if(map[i]>0 && map[i] < min){
min = map[i];
mind = char(i);
}
}
return mind;
}

public static char getUniqueCharacter(Stream is) {
Map <String, String> map = new HashMap<String, String>();
while (is.hasNext()) {
String next = String.valueOf(is.getNext());
if (map.containsKey(next)) {
map.put(next, "duplicate");
}
else {
map.put(next, "unique");
}
}

for (Map.Entry<String, String> entry : map.entrySet()) {
if("unique".equals(entry.getValue())) {
return entry.getKey().charAt(0);
}
}
return '#';
}

We can use a LinkedHashMap and use contains method to check if the new character already exists or not(this is done in constant time)...if it exists then we can remove that key else add that key to LinkedHashMap.This way since the linkedHashMap maintains the order you get the first element in O(n) time....Also code is much cleaner just about 10 lines.....

Here my solution (assuming simple 1-byte chars from 0 to 255 and undefinite length stream):

public char findUnique(Stream stream){
		int[] counters = new int[256];
		int[] pos = new int[256];
		for(int i=0;i<pos.length;i++) pos[i] = -1;
		int index = 0;
		while(stream.hasNext()) {
			int idx = stream.getNext();
			if(counters[idx]==0) pos[index++]=idx; 			
			counters[idx] = counters[idx]>0?2:1;
		}
		for(int i=0;i<index;i++){
			if(counters[pos[i]]==1) return (char)pos[i];
		}
		return '#';
	}

Here my code:

public static void main(String[] args) {
		long initial = System.currentTimeMillis();
		AmazonTest test = new AmazonTest();
		
		List<Character> list = new ArrayList<Character>();
		List<Character> excludedList = new ArrayList<Character>();

		while (test.hasNext()) {
			
			Character item = test.getNext();
			
			if (list.contains(item)) {
				list.remove(item);
				excludedList.add(item);
			}
			else {
				if (!excludedList.contains(item)) {
					list.add(item);
				}
			}
			
		}
		if (!list.isEmpty()) {
			System.out.println(list.get(0));
		}
		else {
			System.out.println("No repeted value found");
		}
		System.out.println("time=" + (System.currentTimeMillis() - initial));
	}