Daily Coding Problem - 16

day-16.py

"""
This problem was asked by Twitter.

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 ith 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.
"""
# Implementation of circular queue
class CircularQueue:
    def __init__(self, N):
        # Create an empty initially
        self.N = N
        self.queue = N * [None]
        self.start = -1
        self.end = -1
 
    def insert(self, val):
        # If circular queue is empty
        if self.start == -1 and self.end == -1:
            self.start += 1
            self.end += 1
            self.queue[self.end] = val
        else:
            self.end = (self.end + 1) % self.N
            self.queue[self.end] = val
            self.start = (self.start + 1) % self.N

    def get_last(self, i):
        if self.end - i + 1< 0:
            index = self.start + i - 1
            return queue[index]
        else:
            return index[self.end - i + 1]