optimizing the data structure implementation

Question

There is a stream of random characters coming like 'a''b''c''a'... and so on. At any given point in time when I query I need to get the first non repeating character. For example, for the input "abca", 'b' should be returned since a is repeated and the first non repeating character is 'b'.

There needs to be two methods, one for inserting and one for querying.

My solution is to have a linkedList to store the incoming stream characters. While I get the next character, I just compare with all the current characters and if present I will not insert into the end of linkedlist, else I will insert at the end. By this approach, the query will take O(1) since I will get the first element on the linkedlist and insert will take O(n) since I need to compare from the first element till the last element in the worst case.

Is there any better performing way?

• biziclop: That depends on what you mean by a better approach. There are always trade-offs, for example you can store your incoming characters both in a list and a hash table. You use the list to keep track of the order of characters and the hash table for checking whether a character has been encountered before. You've improved your time performance at the expense of space. Is that an improvement overall? It depends what you're after.

Answer 1

Either you haven't explained your algorithm well or it won't return the correct result. In the example a b a, would your algorithm return a (because it is the first element in the linked list)?

Anyway, here is a modification that improves performance. The idea is to use a hash map from characters to (doubly) linked list nodes. This map can be used to determine if a character has already been inserted and to get to the required node quickly. We should allow a null value for the map target (instead of the list node) to express a character that has ocurred more than once already.

The insertion method works as follows:

Check if the map contains the current character (O(1)). If not, add it to the end of the list and add a reference to the map (O(1)).

If the character is already in the map: Check if the pointed to node is null (O(1)). If so, just ignore it. If it is not, remove the pointed to node from the list and update the reference to a null value (O(1)).

Overall, a O(1) operation.

The query works as in your previous solution.

Here is a C# implementation. It's basically a 1:1 translation of the above explanation:

class StreamAnalyzer
{
 LinkedList<char> characterList = new LinkedList<char>();
 Dictionary<char, LinkedListNode<char>> characterMap 
 = new Dictionary<char, LinkedListNode<char>>();
 public void AddCharacter(char c)
 {
 LinkedListNode<char> referencedNode;
 if (characterMap.TryGetValue(c, out referencedNode))
 {
 if(referencedNode != null)
 {
 characterList.Remove(referencedNode);
 characterMap[c] = null;
 }
 }
 else
 {
 var node = new LinkedListNode<char>(c);
 characterList.AddLast(node);
 characterMap.Add(c, node);
 }
 }
 public char? GetFirstNonRepeatingCharacter()
 {
 if (characterList.First == null)
 return null;
 else
 return characterList.First.Value;
 }
}

• zilcuanu: Can you please explain your solution with sample code?