Learn and practice the Graphs, Tries, and Custom Data Structures patterns to solve coding interview problems.

Educative-99 in Java: Accelerate Your Coding Interview Prep

Proficiency in advanced data structures is a marker of a highly experienced engineer, and interviewers use such questions to finetune how they grade candidates. This module teaches you the use of two advanced data structures—graphs and tries—to solve relatively complex problems. To solve problems with very specific requirements that may not be handled by standard data structures, we gain experience in the advanced skill of the design, implementation, and efficient use of custom data structures.

Advanced Data Structures

# Statement

A network of `n` nodes labeled $1$ to $n$ is provided along with a list of travel times for directed edges represented as $times[i]=(x_i​, \space y_i, \space t_i​)$, where $x_i$​ is the source node, $y_i$​ is the target node, and $t_i$​ is the delay time from the source node to the target node.

Considering we have a starting node, `k`, we have to determine the minimum time required for all the remaining $n - 1$ nodes to receive the signal. Return $-1$ if it's not possible for all $n - 1$ nodes to receive the signal.

**Constraints:**

- $1 \leq$ `k` $\leq$ `n` $\leq$ $100$
- $1 \leq$ `times.length` $\leq$ $6000$
- `times[i].length` $== 3$
- $1 \leq x, y \leq$ `n`
- $x$ $!=$ $y$
- $0 \leq t \leq 100$
- Unique pairs of $(x, y)$, which means that there should be no multiple edges

# Examples
 

# Understand the problem

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

What is the minimum time it takes for all the `n` nodes to receive the signal?

times = [[3, 1, 1], [2, 3, 1], [2, 4, 1]]  
n = 4  
k = 2

What is the minimum time it takes for all the <code>n</code> nodes to receive the signal?
times = [[3, 1, 1], [2, 3, 1], [2, 4, 1]] 
n = 4 
k = 2

What is the minimum time it takes for all the `n` nodes to receive the signal?

times = [[2, 1, 1], [1, 3, 1], [3, 4, 2], [5, 4, 2]]  
n = 5  
k = 1

What is the minimum time it takes for all the <code>n</code> nodes to receive the signal?
times = [[2, 1, 1], [1, 3, 1], [3, 4, 2], [5, 4, 2]] 
n = 5 
k = 1

What is the minimum time it takes for all the `n` nodes to receive the signal?

times = [[1, 2, 1], [2, 3, 1], [3, 4, 1]]   
n = 4  
k = 1

What is the minimum time it takes for all the <code>n</code> nodes to receive the signal?
times = [[1, 2, 1], [2, 3, 1], [3, 4, 1]] 
n = 4 
k = 1

Network Delay Time

Network Delay Time

# Figure it out!
We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

# Try it yourself

Implement your solution in the following coding playground.

#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>
#include <unordered_set>

int networkDelayTime(std::vector<std::vector<int>>& times, int n, int k) {

 // Replace this placeholder return statement with your code
 
 return -1;
}

import java.util.*;

class NetworkDelay {
    public static int networkDelayTime(int[][] times, int n, int k) {

        // Replace this placeholder return statement with your code    
        return -1;
    }
}

Help me debug only the function Network Delay Time . . I don't need the corrected code.I don't want explanations or code review. Just provide me the exact and to-the-point error that helps me run the code successfully on the test cases provided.

Please help me understand why this code failed for the last failed test case. Don't give me the corrected code. . If yes, then Just provide me the exact and to-the-point error that helps me run the code successfully on the test cases provided.

Your current task is to review only the networkDelayTime function and the other function(s) invoked in it/them. Do not review extra/helper files or functions not invoked in the solution function networkDelayTime. Do not review the code of data structures objects instantiated like a binary tree, linked list, trie, union find, etc., in the solution functions. Just review the solution/algorithm function of the problem. Also, Answer the following questions: Is the Graphs pattern used? Take your time and review the code.

Please provide a brief time complexity analysis of the function networkDelayTime. While calculating time complexity, include the time complexity of built-in Java functions invoked by the code. The Answer should be to the point and in a few lines.

Please provide a brief Space complexity analysis of the function networkDelayTime. While calculating space complexity, include the space complexity of built-in Java functions invoked by the code. Do not include the space used for the input parameters and the space used for just returning an output(not used as a scratch space). The Answer should be to the point and in a few lines

TwoDArray

#include <string>

using namespace std;

class TwoDArray : public DataStructure
{

 // define class attributes

private:
 void generateError(string data)
 {
 cerr << "TwoDArray is not parsable: " << data;
 exit(-1);
 }

public:
 std::vector<vector<int>> val;

 TwoDArray()
 {
 // constructor
 }
 TwoDArray(std::vector<vector<int>> v)
 {
 this->val = v;
 // constructor
 }
 
 // return value will be passed to user program
 void *construct(string new_value, int typeOfDs)
 {
 json j_complete = json::parse(new_value);
 std::vector<std::vector<int>> temp = j_complete;
 this->val = temp;
 // cout << this->val.size();
 return this;
 // parse test case in json string 'value' to your desired data structure
 }

 // input param contains return value of user program
 string traverse(void *input, int typeOfDs)
 {
 TwoDArray * custom_ds =(TwoDArray *)input; 
 json result = (json)(custom_ds->val);
 return result.dump();
 // convert your data structure 'input' to a json string representing a test case output
 }

 // override operator<< for your data structure if required
};

import ds_v1.DataStructure.DataStructure;
import java.util.*;
import java.io.IOException;
import com.fasterxml.jackson.databind.ObjectMapper;
public class TwoDArray extends DataStructure {

 // define class attributes
 int [][] arr={{}};
 private void generateError(String data) {
 System.err.println("MyCustomDS is not parsable: " + data);
 System.exit(-1);
 }

 public TwoDArray() {
 // constructor
 }
 public TwoDArray(int[][] data) {
 arr = copy(data);
 }

 public String toString() {
 // override toString() for your data structure
 return Arrays.deepToString(arr);
 }

 // return value will be passed to user program
 @Override
 public TwoDArray construct(String new_value, Integer type_of_ds) {
 int[][] data={{}};
 try {
 ObjectMapper mapper = new ObjectMapper();
 data = mapper.readValue(new_value, int[][].class);
 
 } catch (IOException e) {
 e.printStackTrace();
 }
 return new TwoDArray(data);

 }

 // input param contains return value of user program
 @Override
 public String traverse(Object input, Integer type_of_ds) {
 // convert your data structure 'input' to a json string representing a test case output
 return input.toString();
 }
 public static int[][] copy(int[][] src) {
 if (src == null) {
 return null;
 }
 
 int[][] copy = new int[src.length][];
 for (int i = 0; i < src.length; i++) {
 copy[i] = Arrays.copyOf(src[i], src[i].length);
 }
 
 return copy;
 }

}

def evaluate_results(self) -> object:
        """
        self.__inputs is the list of inputs that are passed as input to function
        self.__actual_output is a list of outputs that is produced by the learner's code
        return : self.__edu__result object
        """

        from queue import PriorityQueue
        from collections import defaultdict

        def network_delay_time(times, n, k):
            adjacency = defaultdict(list)
            for src, dst, t in times:
                adjacency[src].append((dst, t)) 

            pq = PriorityQueue()
            pq.put((0, k)) 
            visited = set() 
            delays = 0   
            
            while not pq.empty():
                time, node = pq.get()
            
                if node in visited:
                    continue
                
                visited.add(node)  
                delays = max(delays, time) 
                neighbours = adjacency[node]

                for neighbour in neighbours:
                    neighbour_node, neighbour_time = neighbour
                    if neighbour_node not in visited:
                        new_time =  time + neighbour_time
                        pq.put((new_time, neighbour_node))
        
            if len(visited) == n:
                return delays

            return -1

        expected_outputs = [] 
        expected = network_delay_time(self.__inputs[0], self.__inputs[1],self.__inputs[2])
        actual_output = self.__actual_outputs[0]
        

        if expected == actual_output:
            expected_outputs.append(expected)
            self.__edu_result.store_result(expected_outputs, TestCaseResult.PASS)
        else:
            expected_outputs.append(expected)
            self.__edu_result.store_result(expected_outputs, TestCaseResult.FAIL)

        return self.__edu_result

public class Main{
    public static Integer sum (TwoDArray input_1, Integer input_2, Integer input_3) {
        return NetworkDelay.networkDelayTime(input_1.arr, input_2, input_3);
    }
}

network_delay_time (1).yaml

testcases:
  - name: "testcase 1"
    inputs:
    - 1 : [[1, 2, 5], [1, 3, 10], [1, 4, 15]]
    - 2 : 4
    - 3 : 1
    output: 
    - 1 : 15
  - name: "testcase 2"
    inputs:
    - 1 : [[1, 2, 1], [2, 3, 1], [3, 4, 1]]
    - 2 : 4
    - 3 : 1
    output: 
    - 1 : 3
  - name: "testcase 3"
    inputs:
    - 1 : [[1, 2, 5], [2, 3, 10], [2, 4, 15]]
    - 2 : 4
    - 3 : 1
    output: 
    - 1 : 20
  - name: "testcase 4"
    inputs:
    - 1 : [[1, 2, 5], [1, 3, 5], [1, 4, 5], [2, 4, 5], [3, 4, 5]]
    - 2 : 4
    - 3 : 1
    output: 
    - 1 : 5
  - name: "testcase 5"
    inputs:
    - 1 : [[1, 2, 1], [2, 3, 2], [3, 4, 3], [4, 1, 4]]
    - 2 : 4
    - 3 : 2
    output: 
    - 1 : 9

def sum(input_1, input_2):
    return input_1+input_2

def validate_inputs(self) -> None:
 """
 self.__inputs is the list of inputs that are passed as input to function
 store the result using the self.store_result(error_msg, status)
 return : void
 """

 def three_length(times):
 for time in times:
 if len(time) != 3:
 return True


 def xy_validity(times, n):
 for time in times:
 if not 1 <= time[0] <= n or not 1 <= time[1] <= n:
 return True


 def t_validity(times):
 for time in times:
 if not 0 <= time[2] <= 100:
 return True


 def x_not_equal_to_y(times):
 for time in times:
 if time[0] == time[1]:
 return True


 def unique_pairs(times):
 xy = []
 for time in times:
 xy.append((time[0], time[1]))

 if len(xy) != len(list(set(xy))):
 return True


 def is_valid_2d_array(arr):
 if not isinstance(arr, list) or not all(isinstance(row, list) for row in arr):
 return False

 for row in arr:
 if any(elem is None or isinstance(elem, bool) for elem in row):
 return False
 if not all(isinstance(elem, int) for elem in row):
 return False

 return True

 times = self.__inputs[0]
 n = self.__inputs[1]
 k = self.__inputs[2]

 if not is_valid_2d_array(times):
 self.store_result ("'times' should be a 2D integer array", ValidationFunction.FAIL)
 elif three_length(times):
 self.store_result ("'times[i]' should have three values [x,y,t]", ValidationFunction.FAIL)
 elif not 1 <= k <= n <= 100:
 self.store_result ("'k' should be in the range (1 <= k <= n <= 100)", ValidationFunction.FAIL)
 elif not 1 <= len(times) <= 6000:
 self.store_result ("'times' length should be in the range [1,6000]", ValidationFunction.FAIL)
 elif xy_validity(times, n):
 self.store_result ("'x,y' should be in the range [1,n]", ValidationFunction.FAIL)
 elif t_validity(times):
 self.store_result ("'t' should be in the range [1,100]", ValidationFunction.FAIL)
 elif x_not_equal_to_y(times):
 self.store_result ("x should not be equal to y", ValidationFunction.FAIL)
 elif unique_pairs(times):
 self.store_result ("'times' should not have multiple edges from 'x' to 'y'", ValidationFunction.FAIL)
 else:
 self.store_result("", ValidationFunction.PASS)

Try to solve the Network Delay Time problem.

Graphs

Trie

Custom Data Structures

Conclusion

Network Delay Time

Statement

Examples

Understand the problem

Figure it out!

Try it yourself