Google Interview Question

Design an LRU (Least Recently Used) Cache and explain its time complexity for insertion, deletion, and retrieval operations.