Quick Overview

This question evaluates Python programming proficiency, algorithm design, data structure selection and justification, modular coding practices, unit testing, and time/space complexity analysis.

Design and implement a Python solution

Company: Anthropic

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Design and implement a solution in Python for a problem specified by the interviewer. Outline your approach and chosen data structures, justify key design decisions and trade-offs, write clean modular code, provide unit tests and sample runs, and analyze the time and space complexity. You may use Google Colab for development and execution.

Quick Answer: This question evaluates Python programming proficiency, algorithm design, data structure selection and justification, modular coding practices, unit testing, and time/space complexity analysis.

Design and implement a time-aware key-value store. You are given a list of operations to process in order. A set operation stores a value for a key at a given timestamp. A get operation asks for the value of a key at the greatest timestamp less than or equal to the requested timestamp. If no such value exists, return an empty string. Return the results of all get operations in order. To keep each operation easy to represent across languages, timestamps are provided as decimal strings and should be parsed as integers.

Constraints

  • 0 <= len(operations) <= 200000
  • 1 <= len(key) <= 100
  • 0 <= len(value) <= 100
  • 1 <= int(timestamp) <= 10^9
  • For each individual key, set operation timestamps appear in nondecreasing order in the input.
  • If multiple set operations for the same key use the same timestamp, the latest one in operation order should be returned for that timestamp.

Examples

Input: ([['set', 'foo', 'bar', '1'], ['get', 'foo', '1'], ['get', 'foo', '3'], ['set', 'foo', 'bar2', '4'], ['get', 'foo', '4'], ['get', 'foo', '5']],)

Expected Output: ['bar', 'bar', 'bar2', 'bar2']

Explanation: At timestamps 1 and 3, the latest value for 'foo' is 'bar'. After setting 'bar2' at timestamp 4, queries at 4 and 5 return 'bar2'.

Input: ([['get', 'x', '10'], ['set', 'x', 'a', '5'], ['get', 'x', '4'], ['get', 'x', '5']],)

Expected Output: ['', '', 'a']

Explanation: The first query happens before any value is stored for 'x'. The query at timestamp 4 is before the first stored timestamp 5. The query at timestamp 5 returns 'a'.

Hints

  1. Store a separate timestamp history for each key instead of scanning all operations for every get.
  2. Because timestamps for each key are stored in sorted order, binary search can find the latest timestamp not greater than the query time.

Loading coding console...