Using the online code editor, create a data structure that does the following:
1 - Has a max size of elements
2 - When attempting to add a new element, if the element will exceed the structure max size, remove the oldest accessed element to make room for the new element.

Question

Using the online code editor, create a data structure that does the following:
1 - Has a max size of elements
2 - When attempting to add a new element, if the element will exceed the structure max size, remove the oldest accessed element to make room for the new element.

aj · Accepted Answer

Use Linked List to implement this.
Each node stores value and points to next element. 
When try to insert after max_size, Update head and tail pointers as follows
head = head.next;
tail.next = newNode
tail = newNode
Insertion takes o(1)

Python · Answer

class cache():
  
  def __init__(self, size):
    self.size=size
    print('The cache is initilized with max size', size)
    self.kvtable={}
    self.orderlist=[]


  def put(self, k,v):
    l=len(self.kvtable)
    if l >= self.size and k not in self.kvtable:
      rk=self.orderlist.pop(0)
      del self.kvtable[rk]
    if k in self.kvtable:
      idx=self.orderlist.index(k)
      del self.orderlist[idx]
    self.orderlist.append(k)  
    self.kvtable[k]=v

  def get(self, k):
    if k in self.kvtable:
      idx=self.orderlist.index(k)
      del self.orderlist[idx]
      self.orderlist.append(k)
      return self.kvtable[k]
    else:
      return -1
 
c=cache(2)
c.put(1,1)
print(c.kvtable, c.orderlist)
c.put(2,2)
print(c.kvtable, c.orderlist)
c.put(1,3)
print(c.kvtable, c.orderlist)
c.put(3,4)
print(c.kvtable, c.orderlist)
out=c.get(2)
print(c.kvtable, c.orderlist, out)
out=c.get(1)
print(c.kvtable, c.orderlist, out)

Amazon

Amazon Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches