Solve three coding rounds

Q: Solve three coding rounds

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Loading...

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:

For any fixed person, there is no tie between their closest cakes.
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.