Why Use Python Ordered Dictionary?

An ordered dictionary offers same time complexity as the standard dict.

The implementation is simple:

  • Keep two dictionaries and a doubly-linked list of keys.
  • The DLL maintains order.
  • One dict maps key => DLL node
  • Other dict maps key => value

Implementation details

https://github.com/python/cpython/blob/3.7/Lib/collections/init.py#L129

Example

Problem: Find the first non-repeating char in a string.

def firstUniqChar(self, s):
        """
        :type s: str
        :rtype: int
        """
        if len(s) == 0:
            return -1

        d = collections.OrderedDict()
        
        for index, c in enumerate(s):
            if c in d:
                d[c][0] += 1
            else:
                d[c] = [1, index]
        
        for k in d:
            if d[k][0] == 1:
                return d[k][1]
        
        return -1

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.