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.

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.

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']]

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.

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.

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.

Loading coding console...