16. storing data log

Problem

You run an e-commerce website and want to record the last N order ids in a log. Implement a data structure to accomplish this, with the following API:

• record(order_id): adds the order_id to the log
• get_last(i): gets the i-th last element from the log. i is guaranteed to be smaller than or equal to N. You should be as efficient with time and space as possible.

How to implement

I had little experience to use Data-Base. So, I came up with using hash table or list. Since hash table is fast to access the value, I'm trying to use hash table corresponding to dictionary type in python . Now, I assume recording only order_id.

At first, we consider record(order_id) method. This method is devided to 2 processes. First, looking up the oldest id. Second, overwriting the id with new order id. To implement these operation, keys of hash table, that stores id logs, is assigned the position to. Concretely, log[position] = id where the position contain from 0 to N-1. If a new order come, the DB overwrites the oldest with the new, by log[oldest] = new_id.

Finally, let's consider get_last(i) method.Here I assume last means new. Roughly, to get i-th id from the last, we should access oldest - i. Note that the limit of the data-structure storing is N, and oldest - i may be smaller than 0. In that case, it's no problem in python, but I don't want to deal with minus element and I implement a little confusingly.

Implement

class log():
    def __init__(self, N):
        self.oldest = None
        self.hash = {} # note that hash has at most N logs
        self.N = N

    def record(self, order_id):
        self.hash[self.oldest] = order_id
        self.oldest += 1
        self.oldest %= self.N

    def get_last(self, i):
        target = (self.oldest - i + self.N)%self.N # (self.oldest - i)%self.N works well, but I don't want to deal with minus element  
        return self.hash[target]