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 Verkada.

What role is this question designed for?

This question is commonly asked for Frontend Engineer candidates at Verkada during technical interviews.

Implement a recency cache and min-coins DP

Quick Overview

This question evaluates data structure design and algorithmic problem-solving skills, focusing on an LRU-style recency cache and a dynamic programming minimum-coin change problem, and tests knowledge of efficient state management and optimization under constraints.

PracHub

Questions Coaches Learning Guides Interview Prep

Quick Overview

medium
Verkada
Coding & Algorithms
Frontend Engineer

Implement a recency cache and min-coins DP

Company: Verkada

Role: Frontend Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

The algorithm round covered two coding problems: 1. Design a fixed-capacity in-memory key-value cache that evicts the least recently accessed item when full. Implement: - `Cache(int capacity)` - `int get(int key)` which returns `-1` if the key does not exist - `void put(int key, int value)` Both operations should run in O(1) average time. 2. Given a list of positive coin denominations and a target amount, return the minimum number of coins needed to form exactly that amount. If the amount cannot be formed, return `-1`. You may use each denomination any number of times.

Quick Answer: This question evaluates data structure design and algorithmic problem-solving skills, focusing on an LRU-style recency cache and a dynamic programming minimum-coin change problem, and tests knowledge of efficient state management and optimization under constraints.

Least Recently Used Cache

Simulate get and put on a fixed-capacity cache, returning outputs for get operations.

Constraints

capacity >= 0

Examples

Input: (2, [('put', 1, 1), ('put', 2, 2), ('get', 1), ('put', 3, 3), ('get', 2), ('get', 3)])

Expected Output: [1, -1, 3]

Explanation: Evicts least recently accessed key.

Input: (0, [('put', 1, 1), ('get', 1)])

Expected Output: [-1]

Explanation: Zero capacity cache.

Input: (1, [('put', 1, 1), ('put', 1, 2), ('get', 1)])

Expected Output: [2]

Explanation: Updating existing key refreshes it.

Hints

A production O(1) solution uses a hash map plus doubly linked list.

Minimum Coins for a Target Amount

Return the fewest coins needed to make amount using unlimited positive denominations, or -1 if impossible.

Constraints

coins are positive integers
amount >= 0

Examples

Input: ([1, 2, 5], 11)

Expected Output: 3

Explanation: 5+5+1.

Input: ([2], 3)

Expected Output: -1

Explanation: Impossible amount.

Input: ([1], 0)

Expected Output: 0

Explanation: Zero amount.

Input: ([3, 7], 14)

Expected Output: 2

Explanation: Two 7-value coins.

Hints

dp[x] is the minimum coins needed for amount x.

Last updated: Jun 27, 2026