Minimize total distance to a store

Q: Minimize total distance to a store

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.

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.

Q: What difficulty level is this interview question?

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

Q: What role is this question designed for?

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

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

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

Comments (0)