Implement a nested key-value store

Q: Implement a nested key-value store

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.

Q: 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.

Q: What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Lyft.

Q: What role is this question designed for?

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

Question

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.

PracHub · Accepted Answer

def solution(operations):
    class Node:
        __slots__ = ('children', 'has_value', 'value')
        def __init__(self):
            self.children = {}
            self.has_value = False
            self.value = None

root = Node()

def parts(path):
        return path.split('.') if path else []

def traverse(path, create=False):
        node = root
        for seg in parts(path):
            if seg not in node.children:
                if not create:
                    return None
                node.children[seg] = Node()
            node = node.children[seg]
        return node

def delete_path(path):
        segs = parts(path)
        if not segs:
            return False

node = root
        stack = []
        for seg in segs:
            if seg not in node.children:
                return False
            stack.append((node, seg))
            node = node.children[seg]

parent, last = stack[-1]
        del parent.children[last]

for parent, seg in reversed(stack[:-1]):
            child = parent.children[seg]
            if child.has_value or child.children:
                break
            del parent.children[seg]

return True

results = []
    for op in operations:
        kind = op[0]
        if kind == 'set':
            _, path, value = op
            node = traverse(path, True)
            node.has_value = True
            node.value = value
            results.append('OK')
        elif kind == 'get':
            _, path = op
            node = traverse(path, False)
            if node is None or not node.has_value:
                results.append('ERROR: Path not found')
            else:
                results.append(node.value)
        elif kind == 'delete':
            _, path = op
            if delete_path(path):
                results.append('OK')
            else:
                results.append('ERROR: Path not found')
        else:
            results.append('ERROR: Unknown operation')

return results

def solution(operations):
    class Node:
        __slots__ = ('children', 'has_value', 'value')
        def __init__(self):
            self.children = {}
            self.has_value = False
            self.value = None

root = Node()

def parts(path):
        return path.split('.') if path else []

def traverse(path, create=False):
        node = root
        for seg in parts(path):
            if seg not in node.children:
                if not create:
                    return None
                node.children[seg] = Node()
            node = node.children[seg]
        return node

def delete_path(path):
        segs = parts(path)
        if not segs:
            return False

node = root
        stack = []
        for seg in segs:
            if seg not in node.children:
                return False
            stack.append((node, seg))
            node = node.children[seg]

parent, last = stack[-1]
        del parent.children[last]

for parent, seg in reversed(stack[:-1]):
            child = parent.children[seg]
            if child.has_value or child.children:
                break
            del parent.children[seg]

return True

results = []
    for op in operations:
        kind = op[0]
        if kind == 'set':
            _, path, value = op
            node = traverse(path, True)
            node.has_value = True
            node.value = value
            results.append('OK')
        elif kind == 'delete':
            _, path = op
            if delete_path(path):
                results.append('OK')
            else:
                results.append('ERROR: Path not found')
        elif kind == 'children':
            _, prefix = op
            node = root if prefix == '' else traverse(prefix, False)
            if node is None:
                results.append('ERROR: Path not found')
            else:
                results.append(sorted(node.children.keys()))
        else:

Quick Overview

Solution

Hints

Part 2: List Immediate Children Under a Prefix

Constraints

Examples

Solution

Hints

Part 3: Flatten a Nested Key-Value Store

Constraints

Examples

Solution

Hints

Part 4: Optional Type Checking for Overwrites

Constraints

Examples

Solution

Hints

Quick Overview