2
\$\begingroup\$

Consider a large list of 4 character strings.

For example: ['P0BH', 'LF3J', 'MA1Y', 'STSM', '8Y74', 'JWBD']

I want to add a new string in the following precise manner:

If the new string already exists in the given list, delete the old value from the list and prepend the new string to the front of the list. For example, if the string 'MA1Y' was added, then the output list would look like this: ['MA1Y', 'P0BH', 'LF3J', 'STSM', '8Y74', 'JWBD']. If the new string does not exist in the list, then just prepend the new string to the front. For example, if the string 'FSH7' was added, then the output list would look like this: ['FSH7', 'P0BH', 'LF3J', 'MA1Y', 'STSM', '8Y74', 'JWBD'].

There is one other caveat: the algorithm must run in constant time complexity. I don't care about space complexity.

Naturally, I have already implemented a solution, which is given below. I believe it runs in constant time complexity, but I would like that we improve it or redesign something better. My understanding is that a map has constant time deletion, membership testing and assignment.

Does the addTicker method in my tickerMap class run in constant time?

If my algorithm is poor, please let me know.

import random
import string

class tickersMap:
    def __init__(self, tickersList):
        self.Map = {t:i for i, t in enumerate(tickersList)}
        self.firstIndex = 0

    def addTicker(self, newTicker):
        if newTicker in self.Map:
            print('exists')
            del self.Map[newTicker]
            self.Map[newTicker] = self.firstIndex - 1
            self.firstIndex -= 1
        else:
            self.Map[newTicker] = self.firstIndex - 1
            self.firstIndex -= 1

    def listTickers(self):
        # This is O(n) but is only required for printing 
        return sorted(self.Map, key=self.Map.get)



if __name__ == "__main__":     

    tickersList = [''.join(random.choice(string.ascii_uppercase + string.digits) for _ in range(4)) for __ in range(6)]

    newTickers = [''.join(random.choice(string.ascii_uppercase + string.digits) for _ in range(4)) for __ in range(3)]

    newTickers.insert(0,tickersList[3])
    newTickers.insert(3,tickersList[2])

    print('Starting ticker list:', tickersList)
    tMap = tickersMap(tickersList)

    for newTicker in newTickers:

        print('\nCurrent map:', tMap.Map)

        print('Want to add:', newTicker)

        tMap.addTicker(newTicker)

        print('New map', tMap.Map)

        newTickersList = tMap.listTickers()

        print('New ticker list:', newTickersList)
\$\endgroup\$
  • \$\begingroup\$ Cross-posted on Stack Overflow \$\endgroup\$ – Mast Sep 25 '17 at 16:06
  • 1
    \$\begingroup\$ listTickers() is O(n lg n), not O(n), due to the sorting. Also, why do you del self.Map[newTicker] and re-add it, rather than just changing the value? \$\endgroup\$ – Snowbody Sep 25 '17 at 17:49
8
\$\begingroup\$

You can accomplish this using the standard collections.OrderedDict. According to the docs:

Deleting an entry and reinserting it will move it to the end.

By default, the presentation will be in insertion order. For you, that is reversed, so you will want to reverse the ordering when you iterate (using .keys() or .items()).

Update

To use the ordered dictionary, you'll have to import collections (unless you're using python3.6, where I think dictionaries become ordered by default- check that).

So:

import collections

od = collections.OrderedDict()

def insert(ticker, price):
    '''
    Insert a ticker->price pair. If ticker is already stored, move it
    to the end (last updated). 
    '''
    if ticker in od:
        del od[ticker]

    od[ticker] = price

def each_ticker():
    '''Return ticker symbols in reverse order of insertion'''
    return reversed(od.keys())

def each_ticker_price():
    '''Return (ticker, price) pairs in reverse order of insertion'''
    return reversed(od.items())


insert('AAPL', 100)
insert('MSFT', 200)
insert('GOOG', 300)
insert('AAPL', 400)
insert('MSFT', 350)

for name, price in each_ticker_price():
    print(name, "trading at", price)

Output is:

$ python test.py
MSFT trading at 350
AAPL trading at 400
GOOG trading at 300
\$\endgroup\$
  • \$\begingroup\$ How do I use the ordered dict class? \$\endgroup\$ – Pii Sep 25 '17 at 19:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.