PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

This multi-part question evaluates algorithmic problem-solving and practical implementation skills, covering grid geometry and distance metrics for nearest-item queries, expression parsing and nested evaluation for a command-based calculator, and time-indexed data structure design for versioned key-value storage in the Coding & Algorithms domain.

  • medium
  • Snowflake
  • Coding & Algorithms
  • Software Engineer

Solve three coding rounds

Company: Snowflake

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given three independent interview-style coding tasks. ## 1) Nearest cake/person in a 2D grid You are given an `m x n` grid of integers: - `1` = cake - `0` = person Assume at least one cake and at least one person exist. ### 1A. Minimum distance between any cake and any person Compute the minimum Manhattan distance between any person cell and any cake cell. - Manhattan distance between `(r1,c1)` and `(r2,c2)` is `|r1-r2| + |c1-c2|`. - **Output:** an integer minimum distance. ### 1B. Which cake does a given person eat? Each person will eat the **closest** cake (by Manhattan distance). You are given the position (or index) of one specific person, and you must return which cake that person will eat. Additional guarantees: 1. For any fixed person, there is no tie between their closest cakes. 2. For any fixed cake, there is no tie between its closest people. These guarantees imply the assignment is deterministic (no ambiguous choices). - **Input:** the grid and a target person location `(rp, cp)` (known to be a `0`). - **Output:** the cake location `(rc, cc)` that this person eats. ## 2) Implement a simple command-based calculator You are given a list of strings `commands`, each command being one of: - `"ADD x"` - `"SUB x"` - `"MULT x"` - `"DIV x"` where `x` is an integer (may be negative). Start with an accumulator value `acc = 0`. Process commands in order, updating `acc` each time. `DIV` should use truncation toward zero (like integer division in many languages). - **Output:** the final `acc` after all commands. ### Follow-up (nested computation) Extend the calculator to support nested expressions inside a command, e.g. operands can themselves be expressions, such as: - `"ADD (MULT 3 (ADD 2 5))"` Define a clear grammar and evaluate the expression correctly. ## 3) Design an in-memory time-indexed key-value store Implement an in-memory store supporting: - `set(key, value, timestamp)` - `get(key, timestamp)` → returns the value associated with `key` at the greatest timestamp `t'` such that `t' <= timestamp`. If none exists, return an empty value. Assume: - `key` and `value` are strings - `timestamp` is an integer - Multiple values can be set for the same key at different timestamps You should design data structures and implement these operations efficiently.

Quick Answer: This multi-part question evaluates algorithmic problem-solving and practical implementation skills, covering grid geometry and distance metrics for nearest-item queries, expression parsing and nested evaluation for a command-based calculator, and time-indexed data structure design for versioned key-value storage in the Coding & Algorithms domain.

Part 1: Minimum Distance Between Any Cake and Any Person

You are given a 2D grid where `1` represents a cake and `0` represents a person. The grid contains at least one cake and at least one person. Return the minimum Manhattan distance between any cake cell and any person cell. Manhattan distance between `(r1, c1)` and `(r2, c2)` is `|r1-r2| + |c1-c2|`. The key interview insight is to reason about the fact that every cell is either a cake or a person.

Constraints

  • 1 <= m, n
  • Each grid cell is either 0 or 1
  • At least one cell is 0 and at least one cell is 1

Examples

Input: [[1, 0]]

Expected Output: 1

Explanation: The two cells are adjacent, so the minimum Manhattan distance is 1.

Input: [[1], [0]]

Expected Output: 1

Explanation: The cake and person are vertically adjacent.

Input: [[1, 1, 1], [1, 1, 1], [0, 0, 0]]

Expected Output: 1

Explanation: Cells on the boundary between the top region and bottom region are adjacent.

Input: [[1, 1, 1], [1, 0, 1], [1, 1, 1]]

Expected Output: 1

Explanation: The center person is adjacent to cakes on all four sides.

Hints

  1. If both values exist somewhere in the grid, think about any path from a cake cell to a person cell using up/down/left/right moves.
  2. Along such a path, there must be a first place where the value changes from 1 to 0 or from 0 to 1.

Part 2: Find Which Cake a Given Person Eats

You are given a 2D grid where `1` represents a cake and `0` represents a person. A specific person at location `(rp, cp)` will eat the cake with the smallest Manhattan distance to them. You are guaranteed that this person has a unique closest cake. Return the coordinates of the cake that person eats.

Constraints

  • 1 <= m, n
  • Each grid cell is either 0 or 1
  • There is at least one cake in the grid
  • The target location is a person cell
  • The target person has a unique closest cake

Examples

Input: ([[1, 0, 0], [0, 0, 1], [0, 0, 0]], (2, 1))

Expected Output: (1, 2)

Explanation: Distances from (2, 1) are 3 to (0, 0) and 2 to (1, 2), so the person eats the cake at (1, 2).

Input: ([[1, 0, 0]], (0, 2))

Expected Output: (0, 0)

Explanation: There is only one cake, so it must be chosen.

Input: ([[0, 1], [0, 0]], (1, 0))

Expected Output: (0, 1)

Explanation: The only cake is at (0, 1), at distance 2.

Input: ([[1, 0, 1], [0, 0, 0], [0, 1, 0]], (1, 1))

Expected Output: (2, 1)

Explanation: Distances are 2 to (0, 0), 2 to (0, 2), and 1 to (2, 1), so the closest cake is (2, 1).

Hints

  1. Only cake cells matter for the answer, so scan the grid and evaluate the Manhattan distance to each cake.
  2. Keep track of the smallest distance seen so far and the cake coordinates that produced it.

Part 3: Simple Command-Based Calculator

You are given a list of calculator commands. Start with `acc = 0` and process each command in order. A command is one of: `ADD x`, `SUB x`, `MULT x`, or `DIV x`, where `x` is an integer and may be negative. Division must truncate toward zero. Return the final accumulator value.

Constraints

  • 0 <= len(commands) <= 100000
  • -10^9 <= x <= 10^9
  • Every command is one of ADD, SUB, MULT, DIV
  • DIV commands never use 0 as the divisor

Examples

Input: ['ADD 5', 'MULT 3', 'SUB 4', 'DIV 2']

Expected Output: 5

Explanation: 0 -> 5 -> 15 -> 11 -> 5.

Input: ['SUB -7', 'DIV 2']

Expected Output: 3

Explanation: 0 - (-7) = 7, then 7 / 2 truncates toward zero to 3.

Input: []

Expected Output: 0

Explanation: No commands means the accumulator stays 0.

Input: ['ADD 10', 'DIV -3']

Expected Output: -3

Explanation: 10 / -3 is -3.333..., which truncates toward zero to -3.

Hints

  1. Parse each command into an operation and an integer operand.
  2. Python's `//` floors for negatives, so implement truncation toward zero carefully.

Part 4: Evaluate Nested Prefix Calculator Expressions

Write a calculator that evaluates nested prefix-style expressions with the operators `ADD`, `SUB`, `MULT`, and `DIV`. Division truncates toward zero. Use this grammar: `expr := integer | '(' OP expr expr ')'`. To mirror the original accumulator-based calculator, also allow a top-level shorthand `OP expr`, which means `(OP 0 expr)`. Examples: `'ADD (MULT 3 (ADD 2 5))'` evaluates to `21`, and `'(SUB (MULT 2 10) (DIV 9 2))'` evaluates to `16`.

Constraints

  • 1 <= len(expression) <= 100000
  • Operators are ADD, SUB, MULT, DIV
  • Integer literals may be negative
  • The input expression is syntactically valid
  • No division by zero occurs

Examples

Input: 'ADD (MULT 3 (ADD 2 5))'

Expected Output: 21

Explanation: This is shorthand for `(ADD 0 (MULT 3 (ADD 2 5)))`, so the result is 0 + 21 = 21.

Input: '(SUB (MULT 2 10) (DIV 9 2))'

Expected Output: 16

Explanation: `(MULT 2 10) = 20`, `(DIV 9 2) = 4`, so the result is 20 - 4 = 16.

Input: 'SUB -5'

Expected Output: 5

Explanation: Top-level shorthand means `0 - (-5) = 5`.

Input: '(DIV (SUB 0 7) 3)'

Expected Output: -2

Explanation: `(SUB 0 7) = -7`, and -7 / 3 truncates toward zero to -2.

Input: '42'

Expected Output: 42

Explanation: A plain integer is already a complete expression.

Hints

  1. First tokenize the string by separating `(` and `)` from other tokens.
  2. A recursive descent parser works naturally because each parenthesized expression has exactly one operator and two subexpressions.

Part 5: Time-Indexed Key-Value Store

Implement a time-indexed key-value store in function form. You will receive a list of operations and must process them in order. A `set` operation stores a string value for a string key at a given integer timestamp. A `get` operation asks for the value of a key at the greatest timestamp `t'` such that `t' <= timestamp`. If no such value exists, return an empty string. Your function should return the results of all `get` operations in order.

Constraints

  • 1 <= len(operations) <= 200000
  • Keys and values are strings
  • Timestamps are integers
  • For each key, `set` operations arrive in nondecreasing timestamp order

Examples

Input: [('set', 'foo', 'bar', 1), ('get', 'foo', 1), ('get', 'foo', 3), ('set', 'foo', 'baz', 4), ('get', 'foo', 4), ('get', 'foo', 5)]

Expected Output: ['bar', 'bar', 'baz', 'baz']

Explanation: Gets return the latest value at or before the requested timestamp.

Input: [('get', 'a', 10), ('set', 'a', 'x', 5), ('get', 'a', 4), ('get', 'a', 5)]

Expected Output: ['', '', 'x']

Explanation: The first get has no data, the second is before the first set timestamp, and the third matches timestamp 5.

Input: [('set', 'love', 'high', 10), ('set', 'love', 'low', 20), ('get', 'love', 5), ('get', 'love', 10), ('get', 'love', 15), ('get', 'love', 20), ('get', 'love', 25)]

Expected Output: ['', 'high', 'high', 'low', 'low']

Explanation: Queries before 10 return empty, then the latest value at or before the query time is returned.

Input: [('set', 'a', 'x', 1), ('set', 'b', 'y', 2), ('get', 'b', 1), ('get', 'a', 2), ('get', 'b', 2)]

Expected Output: ['', 'x', 'y']

Explanation: Each key is tracked independently.

Hints

  1. Store each key's history in timestamp order so you can binary search it during `get`.
  2. For a query time `t`, you need the rightmost timestamp less than or equal to `t`.
Last updated: Apr 19, 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 a JSON Parser - Snowflake (hard)
  • Solve Matrix and Array Distance Problems - Snowflake (medium)
  • Solve Array Distance and Wiki Navigation - Snowflake (medium)
  • Implement Document Predicate APIs - Snowflake (medium)
  • Find Shortest Wiki Click Path - Snowflake (medium)