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.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Snowflake.

What role is this question designed for?

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

Solve three coding rounds | Snowflake Coding Question

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.

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.

Loading coding console...

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.

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

Only cake cells matter for the answer, so scan the grid and evaluate the Manhattan distance to each cake.
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

Parse each command into an operation and an integer operand.
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

First tokenize the string by separating `(` and `)` from other tokens.
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

Store each key's history in timestamp order so you can binary search it during `get`.
For a query time `t`, you need the rightmost timestamp less than or equal to `t`.