Geek Culture
Published in

Geek Culture

Multisource BFS for your FAANG coding interviews

This is a neat little trick to optimize your code and reach peak performance

BFS goes level by level. There is no reason we can’t add multiple nodes (gates) to the first level. There’s your hint. Try to work this out for yourself before proceeding

Important Points

  1. BFS Refresher- Traditional BFS starts with a single source i.e, a single node at level 1 (distance 0). Let’s look at the logic for BFS for distance mapping
Initialize queue Q
Initialize array d[N] = [INF]*len(Nodes) #for distances from source
Q.enqueue(a)
distance = 0
d[a] = 0
while Q is not empty:
n = Q.dequeue
distance = distance + 1
for each neighbor n_i of n:
if d[n_i] is infinity:
d[n_i] = distance
Q.enqueue(n_i)
  1. Multi-Source BFS- As the name suggests, we change the sources. The source node is the original node we start from (a in the pseudo code). If we have multiple starting locations for our BFS, there is nothing stopping us from appending all those locations into our starting queue. Everything else is usual.
  2. If you’re confused- If this is confusing you, feel to take a breather. Consider your vanilla BFS. Once you have populated your queue with the neighbors of your source, you can basically treat the queue as a list of sources starting on the subgraph. This is because graphs and BFS are inherently recursive. The only difference between the vanilla and a multi-source BFS is that the latter has a populated queue at time/distance 0. This is one of the coolest properties of recursive structures. Even more complex variants of a simple recursive structure can be reduced to your simple structure easily. This is why recursive code is often called elegant. There’s a cool topic to bring up at parties where you’re surrounded by nerds.
  3. Code for you- If you’re having trouble with this concept, it might be helpful to see how it is implemented. Here you can see the Python code for the Microsoft favorite question, Rotting Oranges, which we covered here. Try to break the code into different chunks to differentiate it into steps. This will help you build up your familiarity with this idea.
from collections import deque
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
rotten_orange = deque()
minutes = 0
fresh_orange = 0

rows, cols = len(grid), len(grid[0])

for r in range(rows):
for c in range(cols):
orange = grid[r][c]
if orange == 2:
rotten_orange.append((r,c))
elif orange == 1:
fresh_orange += 1

directions = [(1,0), (-1,0), (0, 1), (0,-1)]
while rotten_orange and fresh_orange > 0:
minutes += 1

for _ in range(len(rotten_orange)):
r, c = rotten_orange.popleft()
for dr, dc in directions:
row = r + dr
col = c + dc
if row >= 0 and row < rows and col >= 0 and col < cols and grid[row][col] == 1:
fresh_orange -= 1
grid[row][col] = 2
rotten_orange.append((row, col))

return minutes if fresh_orange == 0 else -1
Photo by Alina Grubnyak on Unsplash

Reach out to me

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Devansh- Machine Learning Made Simple

Deep Insights about Artificial Intelligence (AI), Machine Learning, Software Engineering, and the Tech Industry. Follow me to come out on top