Implement store, evaluator, and parser

The Problem

You are tasked with building a core service for a real-time analytics engine. Implement a class AnalyticsStore that manages keys, their versioned values, and an expression evaluator for those values.

1. Key-Value Store with Versioning and TTL

Implement a store that supports:

• put(key, value, ttl_ms): Stores a value with an associated time-to-live.
• get(key, version): Retrieves the value at a specific version. If no version is provided, return the latest. If the key has expired, return null.

2. Expression Evaluator

Keys can contain expressions in the format "val(key_a) + val(key_b)". When you retrieve a key, if the value is an expression, resolve its dependencies recursively. If a dependency is missing or expired, the expression evaluation fails.

3. Matrix Parser

Implement a function parse_stream(stream) that processes a string of newline-separated rows representing a matrix of values. Some cells may be expressions. The input format is "1,2,val(a);3,4,5". Convert this stream into a structured 2D array representation.

Interface

class AnalyticsStore:
    def put(self, key: str, value: str, ttl_ms: int) -> None:
        pass

    def get(self, key: str, version: int = None) -> str:
        # Resolves expressions if needed
        pass

    def parse_stream(self, stream: str) -> list[list[str]]:
        # Processes matrix input
        pass

Constraints

• The store must handle up to 10,000 keys.
• Circular dependencies in expressions must be detected and return an error.
• Versioning is non-negative and monotonically increasing for each key.

Examples

store = AnalyticsStore()
store.put("a", "10", 5000)
store.put("b", "20", 5000)
store.put("c", "val(a) + val(b)", 5000)
print(store.get("c")) # Output: "30"