Minimize total distance to a store
Company: Ge
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## Question 1: Choose a CVS location to minimize total distance
You are given an `M x N` grid `grid` containing only `0` and `1`.
- `grid[r][c] = 1` means there is demand at cell `(r, c)` (e.g., a customer/home).
- `grid[r][c] = 0` means no demand.
- You may place **one** CVS store on **any** cell (including on a `1` cell).
- Distance is **Manhattan distance**:
\[ d((r_1,c_1),(r_2,c_2)) = |r_1-r_2| + |c_1-c_2| \]
**Goal:** Choose the store location that minimizes the **total distance** from every demand cell (`1`) to the store.
### Input
- `grid`: `M x N` matrix of 0/1.
### Output
- Return the **minimum possible total distance**.
### Notes
- If there are no `1`s, the minimum total distance is `0`.
- Be prepared to discuss a brute-force approach vs. an optimal approach.
---
## Question 2: Pick the best shop closing time
You are given a string `customers` of length `n` consisting only of `'Y'` and `'N'`.
- `customers[i] = 'Y'` means at hour `i` at least one customer arrives.
- `customers[i] = 'N'` means no customers arrive at hour `i`.
A shop chooses a **closing time** `t` where `t` is an integer in `[0, n]`:
- The shop is **open** during hours `[0, t-1]`.
- The shop is **closed** during hours `[t, n-1]`.
The **penalty** is:
- +1 for every hour the shop is **open** and `customers[i] = 'N'` (wasted open hour)
- +1 for every hour the shop is **closed** and `customers[i] = 'Y'` (missed customer hour)
**Task:** Return the **earliest** closing time `t` that achieves the **minimum penalty**.
### Input
- `customers`: string of `'Y'`/`'N'`
### Output
- Integer `t` (earliest minimizer).
Quick Answer: This pair of problems evaluates algorithmic problem-solving skills, focusing on spatial optimization with Manhattan distances for grid-based demand aggregation and sequential penalty minimization on binary time-series data, emphasizing reasoning about aggregation and trade-offs.
Minimize Total Manhattan Distance to a Store
Return the minimum total Manhattan distance from all demand cells to one chosen store cell.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([[1,0,0],[0,0,1],[0,1,0]],)
Expected Output: 4
Explanation: Median row/column.
Input: ([[0,0]],)
Expected Output: 0
Explanation: No demand.
Hints
- Use deterministic tie-breaking for prompts with multiple valid outputs.
- For design-style APIs, simulate operations with explicit inputs.
Earliest Best Shop Closing Time
Return the earliest closing time with minimum open/closed penalty.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ('YYNY',)
Expected Output: 2
Explanation: Classic example.
Input: ('NNN',)
Expected Output: 0
Explanation: Close immediately.
Input: ('YYY',)
Expected Output: 3
Explanation: Stay open until end.
Hints
- Use deterministic tie-breaking for prompts with multiple valid outputs.
- For design-style APIs, simulate operations with explicit inputs.