Rubrik Software Engineer Phone Screen Questions

## Problem Given app dependencies, determine a valid installation order or detect circular dependencies. ## Likely LeetCode equivalent Similar to LC 207 Course Schedule. ## Tags graph, topological_sort, rubrik

## Problem Implement a fixed-capacity circular buffer queue that supports `enqueue`, `dequeue`, `peek`, and `is_full`/`is_empty` operations. When full, the enqueue operation should overwrite the oldest element (ring buffer semantics). The buffer should be O(1) for all operations. ```python class BufferQueue: def __init__(self, capacity: int): ... def enqueue(self, item) -> None: ... def dequeue(self): # returns item or raises if empty def peek(self): # returns next item without removing def is_full(self) -> bool: ... def is_empty(self) -> bool: ... def __len__(self) -> int: ... ``` **Example:** ``` bq = BufferQueue(3) bq.enqueue(1); bq.enqueue(2); bq.enqueue(3) bq.is_full() -> True bq.enqueue(4) # overwrites oldest: [2,3,4] bq.dequeue() -> 2 bq.dequeue() -> 3 bq.is_empty() -> False ``` ## Follow-ups 1. How do you distinguish a full buffer from an empty buffer when using only head and tail pointers (the classic off-by-one problem)? 2. What is the difference between overwrite-on-full semantics and block-on-full semantics, and where is each used? 3. How would you make this thread-safe for a single producer and single consumer without a mutex (lock-free SPSC queue)? 4. How is this data structure used in audio/video streaming pipelines (e.g., jitter buffers)?

## Problem Compute total file sizes in a directory tree structure, summing sizes recursively through subdirectories. ## Likely LeetCode equivalent No confident LC match. ## Tags binary_tree, recursion, rubrik, filesystem

## Problem Design a leaderboard system for a multiplayer game that supports: updating a player's score, querying a player's current rank (1-indexed, rank 1 = highest score), and fetching the top K players. Scores can only increase. ```python class GameRanking: def __init__(self): ... def add_score(self, player_id: str, score: int) -> None: ... def get_rank(self, player_id: str) -> int: ... def top_k(self, k: int) -> list[tuple[str, int]]: ... # top_k returns [(player_id, score)] sorted by score desc ``` **Example:** ``` gr = GameRanking() gr.add_score("Alice", 500) gr.add_score("Bob", 800) gr.add_score("Carol", 800) gr.add_score("Alice", 300) # Alice total = 800 (if cumulative) or 500 gr.get_rank("Alice") -> 2 or 3 depending on design gr.top_k(2) -> [("Bob",800),("Carol",800)] or similar ``` **Clarify:** Does `add_score` replace the score or add to it? ## Follow-ups 1. How would you implement `get_rank` efficiently -- what data structure supports O(log n) rank queries (e.g., sorted set, order-statistics tree)? 2. How does Redis's ZSET (sorted set) solve this problem in production, and what are its rank/score query commands? 3. What is the time complexity of your top_k query, and how does it change if scores are bounded integers (e.g., 0-10000)? 4. How would you shard the leaderboard across multiple servers for 100 million players?

## Problem Given two integer arrays `A` and `B`, find the pair `(a, b)` where `a` is from `A` and `b` is from `B` such that `|a - b|` is minimized. Return the pair and the difference. ```python def smallest_difference( A: list[int], B: list[int] ) -> tuple[int, int, int]: # (a, b, difference) pass ``` **Example:** ``` A = [1, 3, 15, 11, 2] B = [23, 127, 235, 19, 8] -> (11, 8, 3) # |11-8| = 3, smallest possible A = [-1, 5, 10, 20, 28, 3] B = [26, 134, 135, 15, 17] -> (28, 26, 2) ``` ## Round 1 - Coding Solve with a two-pointer approach after sorting both arrays. ## Follow-ups 1. What is the time complexity of the two-pointer approach vs. brute force? Why does sorting enable the two-pointer technique here? 2. If there are multiple pairs with the same minimum difference, how do you return all of them? 3. How would you solve this if elements are floating-point numbers (with precision concerns)? 4. Extend the problem: find the triplet `(a, b, c)` from three arrays minimizing `|a - b| + |b - c|`.

## Problem Implement a key-value store that supports snapshot and rollback operations. ## Likely LeetCode equivalent Similar to LC 1146 Snapshot Array. ## Tags hash_table, design, rubrik, snapshot

## Problem Implement a function that expands `${VARIABLE}` placeholders in a template string using a provided variable map. Undefined variables should raise an error. Nested expansions (a variable whose value contains another `${...}`) should be recursively resolved up to a max depth. ```python def expand_variables( template: str, variables: dict[str, str], max_depth: int = 10 ) -> str: pass ``` **Example:** ``` variables = {"NAME": "Alice", "GREETING": "Hello, ${NAME}!", "CITY": "NYC"} expand_variables("${GREETING} From ${CITY}.", variables) -> "Hello, Alice! From NYC." expand_variables("Hi ${UNKNOWN}", variables) -> raises KeyError or UndefinedVariableError # Cycle: A -> "${B}", B -> "${A}" -> raises RecursionDepthError after max_depth ``` ## Follow-ups 1. How do you detect cycles in variable expansion, and what error do you raise? 2. How would you support default values with `${VAR:-default}` syntax (similar to bash)? 3. What is the difference between eager expansion (expand everything at parse time) and lazy expansion (expand at use time)? 4. How would you make the function safe against injection attacks if variable values come from untrusted user input?