Katkat
Back

Implement Refactoring Assessment Features

Luma AISoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to manage stateful data with temporal versioning and reconstruct valid paths in a graph while ensuring data integrity under constraints.

Part 1: Versioned Key-Value Store

Design a data structure VersionedKV that supports storing values at specific timestamps.

Implement the following methods:

  • put(key, value, timestamp): Stores a value at a specific timestamp. If a value exists at that timestamp, overwrite it.
  • get(key, timestamp): Returns the value at the specified timestamp. If no exact match exists, return the value associated with the largest timestamp less than or equal to the provided timestamp.
  • delete(key, timestamp): Ensures that any get operation at or after this timestamp for this key returns null until a new put occurs.
  • scan(prefix, timestamp): Returns a list of keys starting with prefix that are active at the given timestamp, sorted lexicographically.

Part 2: Path Reconstruction

Given a set of directed edges representing dependencies [u, v] (meaning v depends on u), and a starting node start_node, reconstruct the complete dependency chain. If a cycle is detected, return an empty list. If multiple valid paths exist, return the one where the path length is maximized.

Constraints

  • timestamp is a positive integer.
  • prefix is a string.
  • The graph may contain thousands of nodes; ensure your solution is efficient (avoid exponential recursion).

Example 1

put("config", "v1", 10), put("config", "v2", 20), get("config", 15) -> Returns "v1".

Example 2

Edges: [[A, B], [B, C], [A, C]]. start_node = A. A valid path is [A, B, C].

Hints

Hint 1

For the versioned store, use a TreeMap for each key to store pairs, allowing efficient floorKey lookups.

Hint 2

To handle deletions in the versioned store, treat a deletion as a special value type (e.g., a tombstone) in the version history.

Hint 3

For path reconstruction, use Depth First Search with memoization to track visited states and find the longest path in the Directed Acyclic Graph.

Follow-up questions

  • How would you optimize the `scan` operation if the number of keys grows to millions?
  • How does your solution handle concurrency if multiple threads perform `put` and `delete` operations simultaneously?
  • If the dependency graph were not a DAG, how would you modify the path reconstruction to find the longest path in a graph with cycles?