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

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Robinhood during technical interviews.

Design a constrained cache and secure string validator

Quick Overview

This question evaluates proficiency in data structures and algorithms (constrained cache design), concurrent programming, complexity analysis, and secure input parsing for address classification, with emphasis on robustness, failure modes, and security-aware validation.

Company: Robinhood

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

## Part A — Constrained cache (LRU-like) Design an in-memory cache that supports the following operations: - `get(key) -> value | null` - `put(key, value) -> void` ### Functional requirements - The cache has a fixed capacity `C` (number of entries). When inserting into a full cache, evict an entry based on a well-defined policy (e.g., least-recently-used). - `get` and `put` should be efficient (target amortized \(O(1)\)). ### Security/robustness requirements (discuss + implement) - **High concurrency:** multiple threads may call `get/put` concurrently. Describe and/or implement a thread-safe approach. - **Abuse scenarios:** discuss how the cache behaves under: - extremely hot keys (contention), - key-spamming (many unique keys), - intentionally malformed/oversized keys or values. - **Failure handling:** define behavior for null/empty keys, capacity \(C \le 0\), memory pressure, and unexpected exceptions. ## Part B — Secure string validation (IP-like) Write a function `classifyAddress(s: string) -> "IPv4" | "IPv6" | "Neither"`. ### Core rules (typical IPv4/IPv6 validation) - IPv4: four decimal segments separated by `.`, each `0..255`, no leading `+/-`, no extra spaces; handle leading zeros per your chosen policy but state it clearly. - IPv6: eight hex segments separated by `:`, each `1..4` hex chars (`0-9`, `a-f`, `A-F`). ### Security constraints (must address) - **Bypass resistance:** your parser must not accept inputs that can trick naive implementations (e.g., hidden whitespace, mixed separators, Unicode lookalikes, overflow like `9999999999`, empty segments, trailing separators). - **Performance under abnormal traffic:** avoid worst-case blowups (e.g., pathological long strings). State time and space complexity and any length limits you enforce. Return the classification string for each input.

Quick Answer: This question evaluates proficiency in data structures and algorithms (constrained cache design), concurrent programming, complexity analysis, and secure input parsing for address classification, with emphasis on robustness, failure modes, and security-aware validation.

Part 1: Robust LRU Cache Simulator

Implement the core logic of a constrained in-memory cache using the Least Recently Used (LRU) eviction policy. The task is single-threaded, but your design should reflect robust system behavior: capacity limits must prevent unbounded growth, invalid inputs must not crash the cache, and malformed operations should be ignored safely. For this problem, each operation is either ['put', key, value] or ['get', key]. A successful get or put on an existing key makes that key the most recently used. When inserting into a full cache, evict the least recently used entry. Robustness rules: if capacity <= 0, the cache is disabled; all puts are ignored and every get returns 'NULL'. Keys are valid only if they are non-empty ASCII strings of length 1..16 containing only letters, digits, or underscore. Values are valid only if they are printable ASCII strings of length 1..32 and are not equal to the reserved token 'NULL'. Invalid puts are ignored. Invalid gets return 'NULL'. Malformed operations and unknown commands are ignored.

Constraints

0 <= len(operations) <= 200000
capacity may be any integer; if capacity <= 0, the cache is disabled
Valid keys: ASCII letters, digits, underscore only; length 1..16
Valid values: printable ASCII; length 1..32; value cannot be 'NULL'
Target average time per valid get/put: O(1)

Examples

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

Expected Output: ['1', 'NULL', '3']

Explanation: After getting 'a', it becomes most recent, so inserting 'c' evicts 'b'.

Input: (0, [['put', 'x', '9'], ['get', 'x']])

Expected Output: ['NULL']

Explanation: Capacity 0 disables the cache, so puts are ignored and every get misses.

Input: (2, [['put', '', '1'], ['put', 'abcdefghijklmnopq', 'X'], ['put', 'good_1', 'A'], ['noop', 'x'], ['get', ''], ['get', 'good_1']])

Expected Output: ['NULL', 'A']

Explanation: Empty and oversized keys are invalid, so only ('good_1', 'A') is stored.

Input: (2, [['put', 'a', '1'], ['put', 'b', '2'], ['put', 'a', '9'], ['put', 'c', '3'], ['get', 'a'], ['get', 'b'], ['get', 'c']])

Expected Output: ['9', 'NULL', '3']

Explanation: Updating 'a' refreshes its recency, so 'b' is evicted when 'c' is inserted.

Hints

Use a hash map for O(1) lookup and an order structure to track recency.
Be explicit about which inputs are ignored and which get operations should still produce 'NULL'.

Part 2: Secure IP Address Classifier

Write a strict parser that classifies a string as 'IPv4', 'IPv6', or 'Neither'. Security matters: your parser must reject inputs that naive implementations often accept by mistake, including hidden whitespace, mixed separators, empty segments, trailing separators, Unicode lookalike punctuation, and oversized numeric chunks. IPv4 rules: exactly four decimal segments separated by '.', each segment must contain only digits, must be in the range 0..255, and leading zeros are not allowed unless the segment is exactly '0'. IPv6 rules: exactly eight segments separated by ':', each segment must contain 1 to 4 hexadecimal characters (0-9, a-f, A-F). The shorthand '::' is not allowed in this problem. To avoid pathological behavior on abnormal traffic, reject impossible lengths early.

Constraints

s may contain arbitrary Unicode characters
If len(s) == 0 or len(s) > 39, return 'Neither' immediately
IPv4 must have exactly 4 parts; IPv6 must have exactly 8 parts
No spaces, tabs, newlines, or other whitespace are allowed anywhere
No IPv6 compression ('::') is allowed

Examples

Input: '172.16.254.1'

Expected Output: 'IPv4'

Explanation: Four valid decimal segments, each within 0..255.

Input: '2001:0db8:85a3:0000:0000:8A2E:0370:7334'

Expected Output: 'IPv6'

Explanation: Eight valid hexadecimal groups, each length 1..4.

Input: '01.1.1.1'

Expected Output: 'Neither'

Explanation: Leading zeros are rejected for IPv4 unless the segment is exactly '0'.

Input: '172.16.254.1 '

Expected Output: 'Neither'

Explanation: Hidden or trailing whitespace must not be accepted.

Input: ''

Expected Output: 'Neither'

Explanation: Empty input is not a valid address.

Hints

Check for whitespace, non-ASCII characters, and mixed separators before validating segments.
For IPv4, verify segment length and digit-only content before converting to an integer.

Quick Overview