FastPrep
Problem · Tree

Radio Waves

Learn this problem
● HardSnowflakeINTERNOA
See Snowflake hiring insights

Problem statement

There is network of radio-wave devices which can transmit waves of integer frequencies of 1, 2 or 3 units. Two devices can receive messages directly if their transmission frequencies have an absolute difference of 1, at most. The network is given by a tree having network_nodes number of devices and network_nodes - 1 number of edges. The edges are numbered from 1 to network_nodes, in the form of two arrays, network_from, and network_to respectively. There is an undirected edge from network_from[i] to network_to[i] (1 ≤ i < network_nodes). There is also an array of frequency values, frequency, of size network_nodes.

Determine the longest distance between two devices that can transmit their message to each other. A device can transmit a message to another node if there is a simple path such that compatibility values of two consecutive devices differ by no more than once. If no device can transmit a message, return 0.

Note: The distance between two devices is defined as the number of edges in a simple path from one node to the other. A simple path is a sequence of devices from one node to another such that each consecutive device is connected by an edge and no node is used more than once in the sequence.

Function

radioWaves(network_nodes: int, network_from: int[], network_to: int[], frequency: int[]) → int

Examples

Example 1

network_nodes = 4network_from = [1, 2, 3]network_to = [2, 3, 4]frequency = [1, 3, 2, 1]return = 2
Example 1 illustration
The graph is labeled device:frequency. Check if a message can be passed for each pair of devices and distance.
  • (1, 2): The difference between frequencies, 1 and 3, is greater than 1. A message cannot be transmitted.
  • (1, 3): A message cannot be transmitted due to failure at (1, 2).
  • (1, 4): A message cannot be transmitted due to failure at (1, 2).
  • (2, 3): The difference in frequencies, 3 and 2, is 1. A message can be transmitted.
  • (2, 4): Differences are such that a message can be transmitted from 2->3 and 3->4. The distance is 2.
  • (3, 4): A message can be transmitted, and the distance is 1.
The longest path, and the answer, is 2.

Constraints

na

More Snowflake problems

drafts saved locally
public int radioWaves(int network_nodes, int[] network_from, int[] network_to, int[] frequency) {
    // write your code here
}
network_nodes4
network_from[1, 2, 3]
network_to[2, 3, 4]
frequency[1, 3, 2, 1]
expected2
checking account