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 Technical Screen rounds at OpenAI.

What role is this question designed for?

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

Implement KV store and plan type conversions

Quick Overview

This question evaluates proficiency in designing scalable, time-versioned key-value data structures and in graph-based shortest-path planning for costed type conversions, assessing algorithmic thinking, complexity analysis, and robustness under large-scale constraints in the Coding & Algorithms domain.

Company: OpenAI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Part 1 — Versioned key-value store: Implement a data structure with set(key, value, t) and get_at(key, t) that returns the value for key whose timestamp is the greatest <= t (or None if none). Timestamps are integers and may arrive out of order. Optimize both time and space for up to 1e5 keys and 1e6 operations. Explain your data structures, complexity, and edge cases (duplicate timestamps per key, missing keys, very large t, memory). Provide working code for core methods. Part 2 — Type conversion planning: Given primitive types and directed conversion rules (from, to, cost), answer Q queries (source_type, target_type) by returning the minimum total cost to transform source to target, or -1 if impossible. Types <= 1e4, rules <= 1e5, queries <= 1e5. Explain algorithm choices (e.g., Dijkstra on demand vs preprocessing), complexity, path reconstruction, and how to handle dynamic updates to rules.

Quick Answer: This question evaluates proficiency in designing scalable, time-versioned key-value data structures and in graph-based shortest-path planning for costed type conversions, assessing algorithmic thinking, complexity analysis, and robustness under large-scale constraints in the Coding & Algorithms domain.

Part 1: Versioned Key-Value Store

Design a versioned key-value store that processes operations in order. Each 'set' operation stores a string value for a key at an integer timestamp. Each 'get' operation asks for the value of that key whose timestamp is the greatest value less than or equal to the query timestamp, considering only versions inserted by earlier operations. Timestamps may arrive out of order. If the same key is set multiple times at the same timestamp, the newest value overwrites the old one. Return the answers for all 'get' operations in order. To keep the return type simple, return the string 'None' when no version exists.

Constraints

0 <= len(ops) <= 10^6
All four input lists have the same length
There can be up to 10^5 distinct keys
Timestamps are integers in the range [0, 10^9]
Stored values are non-empty strings and will never be the literal string 'None'

Examples

Input: (['set','set','get','set','get','get'], ['a','a','a','a','a','a'], ['x','y','','z','',''], [5,10,7,6,6,100])

Expected Output: ['x','z','y']

Explanation: The query at time 7 sees version (5,'x'). After setting timestamp 6 to 'z', the query at time 6 returns 'z'. The final query returns the latest version at or before 100, which is 'y' at timestamp 10.

Input: (['get','set','get','get'], ['m','m','m','m'], ['','v','',''], [4,5,4,5])

Expected Output: ['None','None','v']

Explanation: Before any set, the key is missing. After setting at timestamp 5, a query for time 4 still has no valid version, while time 5 returns 'v'.

Input: (['set','set','get','set','get','get'], ['a','a','a','b','b','a'], ['old','new','','x','',''], [3,3,3,2,2,10])

Expected Output: ['new','x','new']

Explanation: The second set for key 'a' uses the same timestamp and overwrites the old value. Key 'b' is independent.

Input: ([], [], [], [])

Expected Output: []

Explanation: Edge case: no operations means no output.

Hints

A hash map alone is not enough because each key needs fast predecessor queries by timestamp.
Think of keeping one ordered structure per key, where insert and 'greatest timestamp <= t' can both be done in logarithmic time.

Part 2: Type Conversion Planning

You are given primitive types numbered from 0 to n - 1 and directed conversion rules (from_type, to_type, cost). For each query (source_type, target_type), return the minimum total cost required to convert the source to the target, or -1 if it is impossible. All costs are non-negative. The queries are given as a batch, so you may reuse work across queries.

Constraints

1 <= n <= 10^4
0 <= len(rules) <= 10^5
0 <= len(queries) <= 10^5
0 <= u, v, source, target < n
0 <= cost <= 10^9

Examples

Input: (5, [(0,1,2),(1,2,3),(0,2,10),(2,3,1)], [(0,2),(0,3),(3,0),(4,4)])

Expected Output: [5,6,-1,0]

Explanation: 0->2 is cheaper through 1. 0->3 is 0->1->2->3. There is no path from 3 to 0. A type always converts to itself at cost 0.

Input: (3, [(0,1,5),(0,1,2),(1,2,4),(0,2,10)], [(0,1),(0,2),(2,2)])

Expected Output: [2,6,0]

Explanation: There are duplicate rules from 0 to 1; the cheapest one should be used. Then 0->1->2 costs 6, which beats the direct edge of cost 10.

Input: (2, [], [(0,1),(1,1)])

Expected Output: [-1,0]

Explanation: Edge case: with no rules, only source == target queries have cost 0.

Input: (6, [(0,5,7),(1,5,3),(2,1,1),(2,5,20),(3,2,2)], [(0,5),(2,5),(3,5),(4,5)])

Expected Output: [7,4,6,-1]

Explanation: For target 5, 2 reaches 5 more cheaply through 1, and 3 reaches 5 through 2 and 1.

Hints

If many queries share the same source, one shortest-path run can answer all of them; the same idea works with shared targets on the reversed graph.
Because all costs are non-negative, Dijkstra's algorithm is appropriate, and you can stop early once all nodes needed for the current group of queries are settled.

Quick Overview