Implement an LRU Cache
Medium · Hashing · about 25 minutes
Asked at Amazon, Bloomberg, ByteDance, Cloudflare, Dropbox, Figma, Intel, Meta, Microsoft, MongoDB, NVIDIA, Qualcomm, Shopify, Snowflake, Walmart Global Tech, Hudson River Trading, AMD, Wayfair, Etsy, Asana, Notion, Datadog, GitLab, Broadcom, Arista Networks, Palo Alto Networks, CrowdStrike, Okta, Elastic, Vercel, Canva, Optiver, Epic Games, Unity, Anduril, SpaceX, Airtable, Toast, Samsung, Dell Technologies, Micron, Arm, Autodesk, Zscaler, Rubrik, Shopee, Flipkart, Zalando, Jump Trading, Susquehanna (SIG), Akamai.
Implement a Least Recently Used cache with a fixed capacity supporting get(key) and put(key, value) in O(1) time. When full, put evicts the least recently used key.