## 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).

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.

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.

What difficulty level is this interview question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Ge.

What role is this question designed for?

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

Minimize total distance to a store | Ge Interview Question

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).

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).

Minimize total distance to a store

Quick Overview

Question 1: Choose a CVS location to minimize total distance

Input

Output

Notes

Question 2: Pick the best shop closing time

Input

Output

Submit Your Answer

Minimize total distance to a store

Quick Overview

Question 1: Choose a CVS location to minimize total distance

Input

Output

Notes

Question 2: Pick the best shop closing time

Input

Output

Submit Your Answer