Frontend School

Bot Communication Network Reachability

DSA
easy

Bot Communication Network Reachability

Easy
Graph
BFS
DFS
Reachability

Overview

Zerodha operates a sophisticated network of automated trading bots that communicate critical information and alerts. Efficient and reliable propagation of these alerts is paramount. This problem asks you to determine if an alert originating from a specific bot can reach another designated monitoring bot through the established communication channels.

What you need to do / Task

Implement the function canBotReach which determines if an alert originating from a startBot can successfully propagate to a targetBot within the given communication network.

Input & output

Your function will receive the following parameters:

  • numBots: An integer representing the total number of bots in the network, indexed from 0 to numBots - 1.
  • connections: A 2D array of integers, where each inner array [u, v] signifies that bot u can send information directly to bot v. These connections are directed.
  • startBot: An integer representing the bot from which the alert originates.
  • targetBot: An integer representing the bot that needs to receive the alert.

The function should return true if targetBot is reachable from startBot, and false otherwise.

Clarifications

  • Bots are 0-indexed, meaning bot IDs range from 0 to numBots - 1.
  • You can assume startBot and targetBot will always be valid bot IDs within the 0 to numBots - 1 range.
  • An alert originating from startBot can always reach startBot itself.

Examples

1

Example 1

Input:

numBots = 4, connections = [[0,1],[1,2],[2,3]], startBot = 0, targetBot = 3

Output:

true

Note:

Bot 0 can send to 1, 1 to 2, and 2 to 3. So, 0 -> 1 -> 2 -> 3, alert reaches target.

2

Example 2

Input:

numBots = 4, connections = [[0,1],[2,3]], startBot = 0, targetBot = 3

Output:

false

Note:

Bot 0 can only reach bot 1. Bot 3 is in a separate component reachable from bot 2.

3

Example 3

Input:

numBots = 3, connections = [[0,1],[1,0]], startBot = 0, targetBot = 0

Output:

true

Note:

An alert from startBot can always reach startBot itself.

4

Example 4

Input:

numBots = 5, connections = [[0,1],[0,2],[1,3],[2,4],[3,4]], startBot = 0, targetBot = 4

Output:

true

Note:

Multiple paths exist: 0 -> 2 -> 4, or 0 -> 1 -> 3 -> 4. Target is reachable.

Constraints

Constraints & assumptions

  • 1 <= numBots <= 1000
  • 0 <= connections.length <= 5000
  • 0 <= u, v < numBots for all [u, v] in connections.
  • startBot and targetBot will always be valid bot indices.
  • Connections are directed; if [u, v] exists, it does not imply [v, u] exists.
  • There will be no duplicate connections or self-loops (e.g., [u, u]) in the input connections array.

What interviewers evaluate

  • Correctness of the graph traversal algorithm (BFS or DFS).
  • Optimal time and space complexity for the given constraints.
  • Clarity and readability of the code structure.
  • Proper handling of visited states to prevent infinite loops and redundant computation.

Loading editor...