PracHub
QuestionsPremiumLearningGuidesInterview PrepNEWCoaches
|Home/Coding & Algorithms/Microsoft

Build a time-based key-value store

Last updated: Mar 29, 2026

Quick Overview

This question evaluates understanding of time-versioned data structures and efficient temporal lookup within associative mappings, focusing on storing and retrieving multiple values per key across timestamps.

  • medium
  • Microsoft
  • Coding & Algorithms
  • Software Engineer

Build a time-based key-value store

Company: Microsoft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## Problem Design a data structure that stores multiple values for the same key at different timestamps, and can retrieve the most recent value as of a given timestamp. Implement a class `TimeMap` with the following operations: - `set(key, value, timestamp)` - Stores the string `value` for string `key` at integer `timestamp`. - `get(key, timestamp) -> string` - Returns the value associated with `key` at the **largest timestamp `t` such that `t <= timestamp`**. - If there is no such timestamp for the key, return an empty string `""`. ### Notes / Constraints (typical) - `key` and `value` are strings. - `timestamp` is a positive integer. - `set` calls for the same key may be given in increasing timestamp order (state your assumption; if not guaranteed, handle it). - Target complexity: about **O(log m)** per `get`, where `m` is the number of stored timestamps for that key.

Quick Answer: This question evaluates understanding of time-versioned data structures and efficient temporal lookup within associative mappings, focusing on storing and retrieving multiple values per key across timestamps.

Related Interview Questions

  • Return Top K Open Businesses - Microsoft (hard)
  • Implement Memory Allocation and In-Memory Records - Microsoft (medium)
  • Implement K-Means and Detect Divisible Subarrays - Microsoft (medium)
  • Sort Three Categories In Place - Microsoft (medium)
  • Retain Top K Elements - Microsoft (medium)
Microsoft logo
Microsoft
Oct 14, 2025, 12:00 AM
Software Engineer
Technical Screen
Coding & Algorithms
5
0

Problem

Design a data structure that stores multiple values for the same key at different timestamps, and can retrieve the most recent value as of a given timestamp.

Implement a class TimeMap with the following operations:

  • set(key, value, timestamp)
    • Stores the string value for string key at integer timestamp .
  • get(key, timestamp) -> string
    • Returns the value associated with key at the largest timestamp t such that t <= timestamp .
    • If there is no such timestamp for the key, return an empty string "" .

Notes / Constraints (typical)

  • key and value are strings.
  • timestamp is a positive integer.
  • set calls for the same key may be given in increasing timestamp order (state your assumption; if not guaranteed, handle it).
  • Target complexity: about O(log m) per get , where m is the number of stored timestamps for that key.

Comments (0)

Sign in to leave a comment

Loading comments...

Browse More Questions

More Coding & Algorithms•More Microsoft•More Software Engineer•Microsoft Software Engineer•Microsoft Coding & Algorithms•Software Engineer Coding & Algorithms
PracHub

Master your tech interviews with 7,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.