CODEWITHSUNDEEP
algorithmdata-structures
zilcuanu
zilcuanu

Reputation: 3715

optimizing the data structure implementation

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?

Upvotes: 0

Views: 55

Answers (1)

Nico Schertler
Nico Schertler

Reputation: 32587

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

Upvotes: 3

Related Questions