Design data structure that support Insert,remove(), findMiddle(), deleteMiddle() operation in O(1)


Asked In: AmazonIntuitAdobe

You need to design a data structure which support below operation in O(1) time complexity
1) Insert() which adds an element to the data structure
2) remove() which removes an element from the data structure
3) findMiddle() which will return middle element
4) deleteMiddle() which will delete the middle element.

Example:

Insert(1)  --- O(1) time complexity 
Insert(2)
Insert(3)
findMiddle() – 2 in O(1) time complexity
Insert(4)
Insert(5)
deleteMiddle() - remove 3 in O(1) time complexity
remove(5) – in O(1) time complexity

Problem level: Medium