How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Palo Alto Networks.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Palo Alto Networks during technical interviews.

Design an O(1) eviction cache | Palo Alto Networks Coding Question

Quick Overview

This question evaluates data structure and algorithmic design skills within the Coding & Algorithms domain, focusing on cache eviction policies and techniques for achieving average O(1) get/put operations. It is commonly asked to test reasoning about time and space complexity, handling of capacity and edge cases, and demonstrates a blend of conceptual understanding and practical application.

Design an O(1) eviction cache

Company: Palo Alto Networks

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Implement an in-memory key–value cache with fixed capacity that evicts the least recently used entry when full. Support get(key) -> value or -1 if missing, and put(key, value) to insert or update. Both operations must be average O( 1). Describe your data structures, sketch them on a whiteboard, and perform a dry run on the sequence: put(1, 10), put(2, 20), get ( 1), put(3, 30), get ( 2), put(4, 40), get ( 1), get ( 3), get ( 4). Explain time/space complexity and how you would handle edge cases (capacity=0, updates, frequent accesses).

Quick Answer: This question evaluates data structure and algorithmic design skills within the Coding & Algorithms domain, focusing on cache eviction policies and techniques for achieving average O(1) get/put operations. It is commonly asked to test reasoning about time and space complexity, handling of capacity and edge cases, and demonstrates a blend of conceptual understanding and practical application.

Implement a fixed-capacity least-recently-used (LRU) cache simulator. Given an integer capacity and a list of operations, process each operation in order. Supported operations are: ["get", key] which returns the value associated with key if present, otherwise -1, and marks the key as most recently used; and ["put", key, value] which inserts or updates the key with value and marks it most recently used. If inserting into a full cache, evict the least recently used key. Return a list of outputs for the get operations in the order they occur. Both operations must run in average O(1) time. If capacity is 0, puts have no effect and all gets return -1.

Constraints

0 <= capacity <= 100000
0 <= len(ops) <= 200000
Each op is either ["put", key, value] or ["get", key]
Keys and values are 32-bit signed integers (e.g., -1e9 <= key,value <= 1e9)
Average O(1) time for get and put
Updates to existing keys must refresh recency

Hints

Use a hash map from key to a node in a doubly linked list to achieve O(1) access and updates.
Maintain a doubly linked list ordered by recency: most recent at the head, least recent at the tail.
On get: if found, move the node to the head before returning its value.
On put: if key exists, update value and move to head; else insert a new node at head. If size exceeds capacity, remove the tail node and delete it from the map.
Sentinel head/tail nodes simplify insert/remove operations. Handle capacity=0 as a special case.

Last updated: Mar 29, 2026

Loading coding console...