PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

This question evaluates implementation skills in data structures and algorithms, covering time-based versioning and TTL in an in-memory key-value store, dependency resolution and evaluation in an expression interpreter, and parsing plus streaming processing of matrix data.

  • hard
  • Instacart
  • Coding & Algorithms
  • Software Engineer

Implement store, evaluator, and parser

Company: Instacart

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

The interview included several independent coding problems: 1. Implement an in-memory key-value store. Start with basic put/get operations, then extend it with per-key expiration using TTL, and finally support queries for the value of a key at any past timestamp. 2. Implement an expression evaluator with variable assignment and references. Statements may include forms such as `A = 5`, `B = A`, `C = B - 10`, and simple expressions using `+` and `-`. Resolve dependencies and compute final values. 3. Parse a text file containing matrices. In the basic version, return the value at a requested row and column from a single matrix. In the extended version, the file contains multiple matrices, each preceded by a string key; return a mapping from each key to the value at the requested coordinates. Discuss how to process the file in a streaming way instead of loading the entire file into memory.

Quick Answer: This question evaluates implementation skills in data structures and algorithms, covering time-based versioning and TTL in an in-memory key-value store, dependency resolution and evaluation in an expression interpreter, and parsing plus streaming processing of matrix data.

Part 1: In-Memory Key-Value Store with Basic Put/Get

Design a simple in-memory key-value store. You are given a sequence of operations. A `put` operation stores or overwrites an integer value for a string key. A `get` operation returns the current value for a key, or `None` if the key does not exist. Return the results of all `get` operations in order.

Constraints

  • 0 <= len(operations) <= 200000
  • Keys are non-empty strings.
  • Values are integers.
  • A later `put` for the same key overwrites the previous value.

Examples

Input: [('put', 'a', 1), ('get', 'a'), ('get', 'b')]

Expected Output: [1, None]

Explanation: Key 'a' was stored with value 1. Key 'b' was never stored.

Input: [('put', 'x', 10), ('put', 'x', 20), ('get', 'x')]

Expected Output: [20]

Explanation: The second put overwrites the first value.

Input: [('get', 'z'), ('put', 'z', 5), ('get', 'z')]

Expected Output: [None, 5]

Explanation: The first get happens before the key exists.

Input: []

Expected Output: []

Explanation: No operations means no get results.

Hints

  1. A hash map/dictionary gives constant-time average lookup and update.
  2. You only need to append to the answer list when you see a `get` operation.

Part 2: In-Memory Key-Value Store with TTL Expiration

Extend the key-value store to support per-key expiration. Each stored value has a TTL (time to live). A value written at time `t` with TTL `ttl` is valid for timestamps in the half-open interval `[t, t + ttl)`. If a key is queried outside that interval, return `None`. If a key is overwritten, the previous value is discarded and does not come back after the new value expires.

Constraints

  • 0 <= len(operations) <= 200000
  • 0 <= timestamp <= 10^9
  • 0 <= ttl <= 10^9
  • Operation timestamps are non-decreasing.
  • Overwriting a key replaces its previous value and expiration.

Examples

Input: [('put', 1, 'a', 10, 5), ('get', 1, 'a'), ('get', 5, 'a'), ('get', 6, 'a')]

Expected Output: [10, 10, None]

Explanation: The value is valid for timestamps 1 through 5, but not at 6.

Input: [('put', 1, 'x', 10, 10), ('put', 4, 'x', 99, 1), ('get', 4, 'x'), ('get', 5, 'x'), ('get', 6, 'x')]

Expected Output: [99, None, None]

Explanation: The second write overwrites the first and expires at time 5.

Input: [('put', 2, 'k', 7, 0), ('get', 2, 'k')]

Expected Output: [None]

Explanation: TTL 0 means the value is never visible.

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

Expected Output: [None]

Explanation: Missing keys return None.

Hints

  1. For each key, store both the value and its expiration time.
  2. A value is active only when `query_time < expire_time`.

Part 3: Historical Key-Value Store Queries

Build a versioned key-value store with TTL and historical lookups. A `put` operation writes a value for a key at a timestamp with a TTL. A `get` operation asks what value that key had at a specified past timestamp. If multiple writes exist for a key, the newest write at or before the query timestamp is the one that matters. Older values do not reappear after a newer write expires.

Constraints

  • 0 <= len(operations) <= 200000
  • 0 <= timestamp, query_timestamp <= 10^9
  • 0 <= ttl <= 10^9
  • `put` timestamps are non-decreasing.
  • A newer write hides older ones permanently, even after it expires.

Examples

Input: [('put', 1, 'a', 10, 5), ('put', 4, 'a', 20, 10), ('get', 'a', 2), ('get', 'a', 4), ('get', 'a', 14)]

Expected Output: [10, 20, None]

Explanation: At time 2 the first write is active, at time 4 the second write is active, and at time 14 the second write has expired.

Input: [('put', 1, 'x', 5, 10), ('put', 3, 'x', 8, 2), ('get', 'x', 2), ('get', 'x', 4), ('get', 'x', 5), ('get', 'x', 6)]

Expected Output: [5, 8, None, None]

Explanation: The later write at time 3 overwrites the earlier one and expires at time 5. The old value does not come back.

Input: [('put', 10, 'a', 1, 5), ('get', 'a', 9), ('get', 'b', 100)]

Expected Output: [None, None]

Explanation: One query is before the first write; the other asks for a missing key.

Input: [('put', 7, 'k', 3, 0), ('get', 'k', 7)]

Expected Output: [None]

Explanation: A write with TTL 0 is never active, even at its own timestamp.

Hints

  1. Keep a per-key history of write timestamps in sorted order.
  2. For a historical lookup, binary search for the latest write with time <= query_timestamp.

Part 4: Expression Evaluator with Variable References

You are given assignment statements that define variables using integers, previously or later defined variables, and the operators `+` and `-`. Evaluate every variable and return its final integer value. Each variable is assigned exactly once. Expressions are valid, acyclic, and use space-separated tokens, such as `A = 5`, `B = A`, `C = B - 10`, or `D = A + C + 2`.

Constraints

  • 1 <= len(statements) <= 100000
  • Each variable is assigned exactly once.
  • All referenced variables are defined somewhere in the input.
  • There are no cyclic dependencies.
  • Tokens in expressions are separated by spaces.

Examples

Input: ['A = 5', 'B = A', 'C = B - 10', 'D = A + C + 2']

Expected Output: {'A': 5, 'B': 5, 'C': -5, 'D': 2}

Explanation: Evaluate dependencies transitively: B depends on A, C depends on B, and D depends on A and C.

Input: ['B = A + 3', 'A = 7']

Expected Output: {'B': 10, 'A': 7}

Explanation: Definitions may appear out of order, so you must resolve references.

Input: ['A = -5', 'B = A - -3']

Expected Output: {'A': -5, 'B': -2}

Explanation: Negative integer literals are allowed.

Input: ['X = 0']

Expected Output: {'X': 0}

Explanation: Single-variable input is the simplest valid case.

Hints

  1. Think of each variable as a node whose value may depend on other variables.
  2. DFS with memoization avoids recomputing the same variable many times.

Part 5: Matrix File Parser for Single Value Lookup

A text file contains a single matrix of integers. Each non-empty line represents one row, and integers in a row are separated by spaces. Given the file contents as a string and a 0-based row and column, return the integer at that position. If the requested row or column is out of bounds, return `None`. Solve it in a way that could be adapted to stream the file line by line instead of loading the whole matrix structure.

Constraints

  • 0 <= number of rows <= 100000
  • 0 <= target_row, target_col <= 10^9
  • Each non-empty row contains space-separated integers.
  • Blank lines may appear and should be ignored.

Examples

Input: ('1 2 3\n4 5 6\n7 8 9', 1, 2)

Expected Output: 6

Explanation: Row 1, column 2 contains 6.

Input: ('1 2\n\n3 4', 1, 0)

Expected Output: 3

Explanation: Blank lines are ignored, so the second non-empty row is '3 4'.

Input: ('1 2\n3 4', 2, 0)

Expected Output: None

Explanation: Row index 2 is out of bounds.

Input: ('', 0, 0)

Expected Output: None

Explanation: An empty file contains no values.

Input: ('10 20', 0, 2)

Expected Output: None

Explanation: Column index 2 is out of bounds for the only row.

Hints

  1. You do not need to build the whole matrix if you only want one cell.
  2. Count non-empty rows until you reach the target row, then parse only that line.

Part 6: Parser for Multiple Keyed Matrices

A text file contains multiple matrices. Each matrix begins with a key line ending in `:` such as `A:` or `sales_q1:`. The following non-empty lines, until the next key line, are rows of that matrix with space-separated integers. For a given 0-based row and column, return a dictionary mapping every key to the value at those coordinates in its matrix, or `None` if that matrix does not have that cell. Aim for a line-by-line solution that only keeps minimal state, as if the file were being streamed.

Constraints

  • 0 <= number of matrices <= 100000
  • 0 <= target_row, target_col <= 10^9
  • Keys are unique and end with `:` in the file.
  • Matrix rows contain space-separated integers.
  • Blank lines may appear and should be ignored.

Examples

Input: ('A:\n1 2\n3 4\n\nB:\n5 6\n7 8', 0, 1)

Expected Output: {'A': 2, 'B': 6}

Explanation: Both matrices have a value at row 0, column 1.

Input: ('X:\n1\n\nY:\n9 8 7', 1, 0)

Expected Output: {'X': None, 'Y': None}

Explanation: Neither matrix has a second row.

Input: ('m1:\n\n10 20 30\n40 50 60\n\nm2:\n7 8\n9 10\n11 12', 2, 1)

Expected Output: {'m1': None, 'm2': 12}

Explanation: Only m2 has a third row, and column 1 there is 12.

Input: ('', 0, 0)

Expected Output: {}

Explanation: An empty file contains no matrices.

Input: ('Solo:\n1 2 3', 0, 5)

Expected Output: {'Solo': None}

Explanation: The requested column is out of bounds.

Hints

  1. You only need the current key, the current row index within that matrix, and the answer map.
  2. When you enter a new matrix, initialize its answer to `None` in case the requested cell never appears.
Last updated: Jun 12, 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

  • Fix the Broken Search Filter in a Book Catalog API - Instacart (medium)
  • Find Largest Adjacent Stock Price Change - Instacart (medium)
  • Implement an In-Memory File Storage System - Instacart (medium)
  • Evaluate an arithmetic expression - Instacart (medium)
  • Decode an encoded string - Instacart (medium)