RetailMeNot | OA | Suitable Locations in Neighborhood
Eels
722
Graph TheoryRetailMeNotMatrixBreadth-First SearchInterview

A is NxM matrix. 0 indicates empty plot, 1 indicates house.
We need to place a store in a neighborhood.
The store must be max K distance from each house.
The Store must be placed at an empty plot.

How many suitable locations are present?

Test Cases

[
   {
   	input: {
   		K: 2,
   		A: [
   			[0, 0, 0, 0],
   			[0, 0, 1, 0],
   			[1, 0, 0, 1],
   		],
   	},
   	output: 2,
   },
   {
   	input: {
   		K: 1,
   		A: [
   			[0, 1],
   			[0, 0],
   		],
   	},
   	output: 2,
   },
   {
   	input: {
   		K: 4,
   		A: [
   			[0, 0, 0, 1],
   			[0, 1, 0, 0],
   			[0, 0, 1, 0],
   			[1, 0, 0, 0],
   			[0, 0, 0, 0],
   		],
   	},
   	output: 8,
   },
]

My Solution

This passed the example test cases, though is probably wrong for hidden cases (since I didn't get a call back after this round 😅).

/**
*
* @param {number} K Maximum distance
* @param {number[][]} A Matrix representing neighborhood
* @returns {number} number of suitable locations
*/
function matrixSuitableLocations(K, A) {
   const houses = []

   const N = A.length
   const M = A[0].length

   for (let i = 0; i < N; i++) {
   	for (let j = 0; j < M; j++) {
   		const cell = A[i][j]
   		if (cell === 1) {
   			houses.push([i, j])
   		}
   	}
   }
   const housesNumber = houses.length
   let visitedCheck = 0
   while (houses.length) {
   	const house = houses.pop()
   	const queue = new Queue()
   	let stepsRemaining = K + 1
   	queue.enqueue({
   		position: house,
   		stepsRemaining,
   	})

   	stepLoop: while (queue.size()) {
   		let {position, stepsRemaining} = queue.dequeue()
   		const [i, j] = position
   		if (A[i] === undefined || A[i][j] === undefined) {
   			continue stepLoop
   		}
   		if (A[i][j] === visitedCheck) {
   			A[i][j]--
   		}

   		if (!stepsRemaining) break stepLoop

   		stepsRemaining--

   		queue.enqueue({
   			position: [i - 1, j],
   			stepsRemaining,
   		})
   		queue.enqueue({
   			position: [i, j - 1],
   			stepsRemaining,
   		})
   		queue.enqueue({
   			position: [i, j + 1],
   			stepsRemaining,
   		})
   		queue.enqueue({
   			position: [i + 1, j],
   			stepsRemaining,
   		})
   	}
   	visitedCheck--
   }

   let result = 0

   for (let i = 0; i < N; i++) {
   	for (let j = 0; j < M; j++) {
   		const cell = A[i][j]
   		if (cell === -housesNumber) {
   			result++
   		}
   	}
   }

   return result
}
Comments (0)