PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

This question evaluates understanding of data structures and API design for hierarchical (nested) key-value stores, covering operations such as set/get/delete, child iteration, flattening to dot paths, optional type safety, and serialization.

  • Medium
  • Lyft
  • Coding & Algorithms
  • Software Engineer

Implement a nested key-value store

Company: Lyft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Design and implement a nested key–value store that supports set(path, value), get(path), and delete(path), where path is dot-delimited (e.g., "a.b.c"). Support creating intermediate nodes, overwriting existing values, and returning clear errors for missing paths. Add: ( 1) an iterator to list immediate children under a prefix; ( 2) a method to flatten the structure into a single-level map using dot paths; ( 3) optional type checking to prevent incompatible overwrites. Provide expected time and space complexity for each operation and explain how you would serialize/deserialize the structure.

Quick Answer: This question evaluates understanding of data structures and API design for hierarchical (nested) key-value stores, covering operations such as set/get/delete, child iteration, flattening to dot paths, optional type safety, and serialization.

Part 1: Basic Nested Key-Value Store

Implement a nested key-value store that supports three operations on dot-delimited paths: 'set(path, value)', 'get(path)', and 'delete(path)'. Missing intermediate nodes must be created automatically during 'set'. A path may store a value and still have children, so after setting 'a' you may still set 'a.b'. 'delete(path)' removes the entire subtree rooted at that path. Process a list of operations and return one result per operation.

Constraints

  • 0 <= len(operations) <= 10^4
  • Each path is a non-empty dot-delimited string with no empty segments
  • Values are Python literals such as int, str, bool, float, or None
  • delete(path) removes the whole subtree at that path

Examples

Input: [('set', 'a.b.c', 5), ('get', 'a.b.c'), ('delete', 'a.b.c'), ('get', 'a.b.c')]

Expected Output: ['OK', 5, 'OK', 'ERROR: Path not found']

Explanation: Basic create, retrieve, delete, then verify the path is gone.

Input: [('set', 'x', 1), ('set', 'x', 7), ('get', 'x')]

Expected Output: ['OK', 'OK', 7]

Explanation: Setting an existing path overwrites its old value.

Input: [('set', 'a', 1), ('set', 'a.b', 2), ('get', 'a'), ('get', 'a.b'), ('delete', 'a'), ('get', 'a.b')]

Expected Output: ['OK', 'OK', 1, 2, 'OK', 'ERROR: Path not found']

Explanation: A node can hold a value and also have children. Deleting 'a' removes the whole subtree.

Input: [('delete', 'z')]

Expected Output: ['ERROR: Path not found']

Explanation: Edge case: deleting a missing path should return a clear error.

Hints

  1. Treat each path segment as one step in a tree or trie.
  2. To support both 'a' and 'a.b', store a node's value separately from its children.

Part 2: List Immediate Children Under a Prefix

Extend the nested key-value store with a 'children(prefix)' operation. It should return the immediate child names directly under the given prefix, not full paths. For example, if the store contains 'a.b' and 'a.c.d', then 'children("a")' returns ['b', 'c']. The empty prefix '' refers to the root. If the prefix path does not exist, return 'ERROR: Path not found'. Return child names sorted lexicographically for deterministic output.

Constraints

  • 0 <= len(operations) <= 10^4
  • Paths for 'set' and 'delete' are non-empty dot-delimited strings with no empty segments
  • The empty prefix '' is allowed only for 'children' and means the root
  • A node may have both a direct value and child nodes

Examples

Input: [('set', 'a.b', 1), ('set', 'a.c.d', 2), ('children', 'a'), ('children', 'a.c')]

Expected Output: ['OK', 'OK', ['b', 'c'], ['d']]

Input: [('set', 'z', 1), ('set', 'a.b', 2), ('children', '')]

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

Input: [('set', 'a', 1), ('children', 'x')]

Expected Output: ['OK', 'ERROR: Path not found']

Input: [('set', 'a.b', 1), ('children', 'a.b')]

Expected Output: ['OK', []]

Input: [('set', 'a.b', 1), ('delete', 'a.b'), ('children', '')]

Expected Output: ['OK', 'OK', []]

Input: [('set', 'a', 1), ('set', 'a.b', 2), ('children', 'a')]

Expected Output: ['OK', 'OK', ['b']]

Input: [('set', 'a', 1), ('set', 'a.b', 2), ('delete', 'a.b'), ('children', '')]

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

Input: [('delete', 'x.y'), ('children', '')]

Expected Output: ['ERROR: Path not found', []]

Hints

  1. After walking to the node for the prefix, you only need its direct children dictionary.
  2. Sort the child names before returning them so the result is deterministic.

Part 3: Flatten a Nested Key-Value Store

You are given set/delete operations for a nested key-value store whose keys are dot-delimited paths. Build the final store, then flatten it into a single dictionary whose keys are full dot paths. Only nodes with direct stored values should appear in the output. Intermediate nodes created only to hold children must not appear. A node may still appear in the flattened result even if it also has children.

Constraints

  • 0 <= len(operations) <= 10^4
  • Each set path is a non-empty dot-delimited string with no empty segments
  • If delete(path) is called on a missing path, it has no effect
  • Values are Python literals such as int, str, bool, float, or None

Examples

Input: [('set', 'a.b', 1), ('set', 'c', 2)]

Expected Output: {'a.b': 1, 'c': 2}

Explanation: Two stored paths become two flat entries.

Input: [('set', 'a', 1), ('set', 'a.b.c', 3)]

Expected Output: {'a': 1, 'a.b.c': 3}

Explanation: A node can keep its own value and also have descendants.

Input: [('set', 'x.y', 5), ('set', 'x.y', 7), ('delete', 'x'), ('set', 'z', 0)]

Expected Output: {'z': 0}

Explanation: Overwriting changes the value, and deleting 'x' removes the entire subtree.

Input: [('delete', 'missing')]

Expected Output: {}

Explanation: Edge case: deleting a missing path does nothing.

Input: []

Expected Output: {}

Explanation: Edge case: an empty store flattens to an empty dictionary.

Hints

  1. Build the store as a tree, then do a DFS while carrying the current path segments.
  2. Do not emit intermediate nodes unless they were explicitly assigned a value.

Part 4: Optional Type Checking for Overwrites

Implement a nested key-value store with an optional strict overwrite mode. You will receive a boolean 'strictMode' and a list of operations. When 'strictMode' is True, overwriting an existing value at the same exact path is allowed only if the new value has the exact same Python type as the old value, meaning 'type(old) is type(new)'. If the types differ, reject the write with 'TYPE_ERROR' and keep the old value unchanged. When 'strictMode' is False, all overwrites are allowed. A node may store a value and still have children. 'delete(path)' removes the entire subtree rooted at that path.

Constraints

  • 0 <= len(operations) <= 10^4
  • Each path is a non-empty dot-delimited string with no empty segments
  • Type checking applies only when overwriting an existing direct value at the same path
  • Use exact Python type equality, so int and bool are considered different

Examples

Input: (True, [('set', 'a', 1), ('set', 'a', 2), ('get', 'a')])

Expected Output: ['OK', 'OK', 2]

Explanation: Strict mode still allows overwrites when the type stays the same.

Input: (True, [('set', 'a', 1), ('set', 'a', 'hello'), ('get', 'a')])

Expected Output: ['OK', 'TYPE_ERROR', 1]

Explanation: Changing the type at the same path is rejected in strict mode.

Input: (False, [('set', 'a', 1), ('set', 'a', 'hello'), ('get', 'a')])

Expected Output: ['OK', 'OK', 'hello']

Explanation: When strict mode is off, incompatible overwrites are allowed.

Input: (True, [('set', 'x.y', 1), ('delete', 'x.y'), ('set', 'x.y', 'now string'), ('get', 'x.y')])

Expected Output: ['OK', 'OK', 'OK', 'now string']

Explanation: Deleting a path removes its old type history because the node is gone.

Input: (True, [('get', 'missing')])

Expected Output: ['ERROR: Path not found']

Explanation: Edge case: reading from a missing path should fail clearly.

Hints

  1. After reaching the target node for a 'set', compare the existing value's exact type with the new value's exact type only if the node already stores a value.
  2. If a write fails with 'TYPE_ERROR', do not modify the stored value.
Last updated: Apr 30, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ 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.

Related Coding Questions

  • Implement Grid Spread and Transactional Store - Lyft (hard)
  • Assign Minimum Workers to Jobs - Lyft (medium)
  • Solve substring and worker assignment - Lyft (medium)
  • Implement Cache and Key-Value Store - Lyft (medium)
  • Implement command-driven in-memory key-value database - Lyft (Medium)