LRU (Least Recently Used) Cache

Referring to LeetCode Q146 https://leetcode.com/problems/lru-cache/

Description

• LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
• int get(int key) Return the value of the key if the key exists, otherwise return -1.
• void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used
• The functions get and put must each run in O(1) average time complexity.

Data Structure Used

To satisfy the O(1) average time complexity for get and put,

Prerequisites

• Visual Studio Code extension ms-vscode.cpptools

• Xcode Command-line Tools / Xcode IDE

  • To install Xcode Command-line Tools: xcode-select --install
  • To install Xcode IDE: mas install Xcode

Test Environment

• Visual Studio Code 1.54.3 (Universal)

  • Commit: 2b9aebd5354a3629c3aba0a5f5df49f43d6689f8
  • Extension: ms-vscode.cpptools v1.2.2

• macOS 11.2.3

  $ uname -v
  Darwin Kernel Version 20.3.0: Thu Jan 21 00:06:51 PST 2021;
  root:xnu-7195.81.3~1/RELEASE_ARM64_T8101
  

• Xcode 12.4 (12D4e)

  $ clang --version
  Apple clang version 12.0.0 (clang-1200.0.32.29)
  Target: arm64-apple-darwin20.3.0
  Thread model: posix
  InstalledDir: /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin
  

Setup

Modify the settings.json in Visual Studio Code as shown below