Katkat
Back

Design a constrained cache and secure string validator

RobinhoodSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question tests the ability to implement a thread-safe, size-constrained cache (LRU-like) and robust string validation logic for identifying malformed or potentially malicious input strings.

Part 1: Thread-Safe Fixed-Size Cache

Design a thread-safe, fixed-size cache that stores key-value pairs (string, string). When the cache reaches its capacity, it should evict the least recently accessed item. Provide a class SecureCache with the following interface:

class SecureCache:
    def __init__(self, capacity: int):
        # Initialize cache with a fixed capacity
        pass

    def put(self, key: str, value: str) -> None:
        # Add/update the key-value pair
        pass

    def get(self, key: str) -> Optional[str]:
        # Return value if present, else None, updating access time
        pass

Part 2: Secure Validator

Implement a function is_valid_address(address: str) -> bool that validates an address string based on the following constraints:

  1. The length must be between 5 and 100 characters.
  2. The string must not contain special characters except spaces, periods, and commas.
  3. The string must not contain common injection patterns such as 'DROP TABLE', 'SELECT', or ''.

Example

# Cache Example
cache = SecureCache(2)
cache.put("A", "123 Main")
cache.put("B", "456 Oak")
cache.get("A") # Returns "123 Main"
cache.put("C", "789 Pine") # Evicts "B"

# Validation Example
is_valid_address("123 Main St, Apt 4") # Returns True
is_valid_address("123 alert(1)") # Returns False

Constraints

  • The SecureCache must handle high concurrency.
  • The validator should be case-insensitive for injection patterns.
  • Consider edge cases like empty strings or extremely long inputs.

Hints

Hint 1

Use a combination of a hash map for O(1) access and a doubly linked list to track access order for the cache.

Hint 2

For thread safety, consider using a reentrant lock (RLock) to ensure operations on the cache internal structure remain atomic.

Hint 3

For the validator, use a blocklist of forbidden strings combined with a regex or character set check for the length and allowed characters.

Follow-up questions

  • How would you modify the cache to handle expiration timestamps for each key?
  • If this cache were deployed in a distributed environment across multiple servers, what synchronization challenges would you face?
  • How could you improve the validator to handle unicode characters or international address formats?