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

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


```text
3-------1
|        \
|         2
|         /
5--------4
```

```text
1-------5
|        \
|         3
|         /
2--------4
```

```text
1-------2
|        \
|         3
|         /
5--------4
```

```text
1-------2
|        \
|         5
|         /
3--------4
```

Which graph is made from the given adjacency list?

[[2, 5], [1, 3], [2, 4], [3, 5], [1, 4]]


Which graph is made from the given adjacency list?
[[2, 5], [1, 3], [2, 4], [3, 5], [1, 4]]

[[2, 6], [3, 5], [2, 4], [1, 3], [4, 6], [1, 5]]

[[2, 8], [2, 4], [1, 3], [3, 5], [4, 6], [5, 7], [1, 7], [6, 8]]

[[1, 7], [1, 3], [2, 4], [3, 5], [4, 6], [5, 7], [6, 8], [2, 8]]

[[2, 8], [1, 3], [2, 4], [3, 5], [4, 6], [5, 7], [6, 8], [1, 7]]

Which adjacency list is made using the given graph?
```
1-------8------7-------6      
|                      |
|                      |
2-------3------4-------5
```



Which adjacency list is made using the given graph?
<pre><code>1-------8------7-------6 
| |
| |
2-------3------4-------5
</code></pre>

Which adjacency list is made using the given graph?

```text
        1
      /   \
     /     \
    /       \
   2 - - - - 3
```


Which adjacency list is made using the given graph?
<pre><code class="language-text"> 1
 / \
 / \
 / \
 2 - - - - 3
</code></pre>

Clone Graph

Clone Graph

# 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 `CloneGraph.java` in the following coding playground.


import java.util.*;

public class CloneGraph{

    public static Node clone(Node root) {

        // Replace this placeholder return statement with your code
        return root;
    }
}

import java.util.*;

class Node {
 int data;
 List<Node> neighbors;

 public Node(int data) {
 this.data = data;
 this.neighbors = new ArrayList<Node>();
 }
}

class Node:
  def __init__(self, d):
    self.data = d
    self.neighbors = []

from Node import *

def clone(root):
    
    # Replace this placeholder return statement with your code
    
    return root

Help me debug only the function Clone Graph . . 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 clone function and the other function(s) invoked in it/them. Do not review extra/helper files or functions not invoked in the solution function clone. 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 clone. 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 clone. 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

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
        """
        def create_graph(data):
            if len(data) == 0:
                return Node(1)
            nodes = []
            for i in range(len(data)):
                nodes.append(Node(i+1))
            
            for i, node in enumerate(nodes):
                for neighbor in data[i]:
                    node.neighbors.append(nodes[neighbor-1])
            return nodes[0] 

        def create_2D_list(root):
            queue = [root]
            visited = {}
            graph = []
            node_index = {}

            while queue:
                node = queue.pop(0)
                neighbors = []

                for neighbor in node.neighbors:
                    neighbors.append(visited.get(neighbor, neighbor).data)
                    if neighbor not in visited and neighbor not in queue:
                        visited[neighbor] = neighbor
                        queue.append(neighbor)

                neighbors.sort()

                if node not in node_index:
                    node_index[node] = len(graph)
                    graph.append([node.data, neighbors])
                else:
                    graph[node_index[node]][1] = neighbors

            graph.sort(key=lambda x: x[0])
            
            return [sublist[1] for sublist in graph]

        def clone_helper(root, nodes_completed):
            if root == None:
                return None

            cloned_node = Node(root.data)
            nodes_completed[root] = cloned_node

            for p in root.neighbors:
                x = nodes_completed.get(p)
                if not x:
                    cloned_node.neighbors += [clone_helper(p, nodes_completed)]
                else:
                    cloned_node.neighbors += [x]
            return cloned_node

        def clone(root):
            nodes_completed = {}
            return clone_helper(root, nodes_completed)

        # multiple outputs will be added at each index respectively for a single test_case
        expected_outputs = []
        inp = self.__inputs[0]
        grp = create_graph(inp)
        expected1 = clone(grp)
        expected = create_2D_list(expected1)
        # store the 1st expected output that should be displayed to the user 
        expected_outputs.append(expected)
        actual1 = self.__actual_outputs[0]
        #actual = create_2D_list(actual1)

        if json.dumps(expected) == json.dumps(actual1):
            self.__edu_result.store_result(expected_outputs, TestCaseResult.PASS)
        else:
            self.__edu_result.store_result(expected_outputs, TestCaseResult.FAIL)

        return self.__edu_result

import java.util.*;

public class Main{
 public static Node createGraph(int[][] data) {
 if(data.length == 0){
 return new Node(1);
 }
 Node[] nodes = new Node[data.length];
 for (int i = 0; i < data.length; i++) {
 nodes[i] = new Node(i + 1);
 }

 for (int i = 0; i < data.length; i++) {
 for (int neighbor : data[i]) {
 nodes[i].neighbors.add(nodes[neighbor - 1]);
 }
 }
 return nodes[0];
 }

 public static List<List<Integer>> create2DList(Node root) {
 // Initialize a queue for breadth-first traversal
 Queue<Node> queue = new LinkedList<Node>();
 queue.add(root);
 // Initialize a HashMap to keep track of visited nodes
 HashMap<Node, Node> visited = new HashMap<Node, Node>();
 // Initialize a 2D List to store the graph
 List<List<Integer>> graph = new ArrayList<List<Integer>>();
 // Initialize a HashMap to store the index of each node
 HashMap<Node, Integer> nodeIndex = new HashMap<Node, Integer>();
 // Perform breadth-first traversal
 while (!queue.isEmpty()) {
 // Get the next node in the queue
 Node node = queue.remove();
 // Create a new List to store the neighbors of the current node
 List<Integer> neighbors = new ArrayList<Integer>();
 // Iterate through the neighbors of the current node
 for (Node neighbor : node.neighbors) {
 // Append the neighbor's value to the List of neighbors
 neighbors.add(visited.getOrDefault(neighbor, neighbor).data);
 // Add the neighbor to the queue if it hasn't been visited yet
 if (!visited.containsKey(neighbor) && !queue.contains(neighbor)) {
 visited.put(neighbor, neighbor);
 queue.add(neighbor);
 }
 }
 // Sort the List of neighbors
 Collections.sort(neighbors);
 // Append the current node's value and its neighbors to the 2D List
 if (!nodeIndex.containsKey(node)) {
 int index = graph.size();
 nodeIndex.put(node, index);
 List<Integer> sublist = new ArrayList<Integer>();
 sublist.add(node.data);
 sublist.addAll(neighbors);
 graph.add(sublist);
 }
 }
 // Sort the graph by node value
 Collections.sort(graph, new Comparator<List<Integer>>() {
 public int compare(List<Integer> a, List<Integer> b) {
 return a.get(0) - b.get(0);
 }
 });
 List<List<Integer>> result = new ArrayList<List<Integer>>();
 for (List<Integer> sublist : graph) {
 List<Integer> sub = new ArrayList<>(sublist.subList(1, sublist.size()));
 result.add(sub);
 }
 return result;
 }
 public static boolean compareAddresses(Node original, Node cloned) {
 Queue<Node> originalQueue = new LinkedList<>();
 Queue<Node> clonedQueue = new LinkedList<>();
 Set<Node> visited = new HashSet<>();

 originalQueue.add(original);
 clonedQueue.add(cloned);

 while (!originalQueue.isEmpty() && !clonedQueue.isEmpty()) {
 Node originalNode = originalQueue.poll();
 Node clonedNode = clonedQueue.poll();

 if (!visited.contains(originalNode)) {
 visited.add(originalNode);
 if (System.identityHashCode(originalNode) == System.identityHashCode(clonedNode)) {
 return true;
 // System.out.println("Original Node " + originalNode.data + ": " + System.identityHashCode(originalNode) + " || Cloned Node " + clonedNode.data + ": " + System.identityHashCode(clonedNode) + " || Address Equal");
 // System.out.println("---------------------------------------------------------------------------------------------");
 }
 originalQueue.addAll(originalNode.neighbors);
 clonedQueue.addAll(clonedNode.neighbors);
 }
 }
 return false;
 }
 public static List<List<Integer>> clone(TwoDArray twoD) {
 Node root = createGraph(twoD.arr);
 Node res = CloneGraph.clone(root);
 boolean flg = compareAddresses(root, res);
 if(flg){
 System.out.println("The graph is not properly cloned.");
 return new ArrayList<List<Integer>>();
 }
 List<List<Integer>> result = create2DList(res);
 return result;
 }
}

clone_graph.yaml

testcases:
  - name: "testcase 1"
    inputs:
    - 1 : [[2, 3], [1, 3], [1, 2]]
    output: 
    - 1 : [[2, 3], [1, 3], [1, 2]]
  - name: "testcase 2"
    inputs:
    - 1 : [[2, 5], [1, 3], [2, 4], [3, 5], [1, 4]]
    output: 
    - 1 : [[2, 5], [1, 3], [2, 4], [3, 5], [1, 4]]
  - name: "testcase 3"
    inputs:
    - 1 : [[2], [1]]
    output: 
    - 1 : [[2], [1]]
  - name: "testcase 4"
    inputs:
    - 1 : [[2, 6], [1, 3], [2, 4], [3, 5], [4, 6], [1, 5]]
    output: 
    - 1 : [[2, 6], [1, 3], [2, 4], [3, 5], [4, 6], [1, 5]]
  - name: "testcase 5"
    inputs:
    - 1 : [[2, 8], [1, 3], [2, 4], [3, 5], [4, 6], [5, 7], [6, 8], [1, 7]]
    output: 
    - 1 : [[2, 8], [1, 3], [2, 4], [3, 5], [4, 6], [5, 7], [6, 8], [1, 7]]
  

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 check_values(array):
 for row in array:
 for value in row:
 if value > 100 or value < 1:
 return False
 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 # Not a valid 2D array if it's empty or contains non-list elements
 
 for row in arr:
 if any(elem is None or isinstance(elem, bool) for elem in row):
 return False # Not a valid 2D array if any element in a row is None
 if not all(isinstance(elem, int) for elem in row):
 return False # Not a valid 2D array if any element in a row is not an integer
 
 return True # Valid 2D array
 
 def is_valid_graph(adjacency_list):
 if not adjacency_list:
 return True, ""

 num_nodes = len(adjacency_list)
 nodes = [Node(i + 1) for i in range(num_nodes)]
 visited = set()
 isolated_node_count = 0

 for i, node in enumerate(nodes):
 if i + 1 in visited:
 continue # Skip nodes that have already been visited
 
 if not adjacency_list[i]:
 isolated_node_count += 1
 visited.add(i + 1)
 continue
 
 for neighbor_index in adjacency_list[i]:
 if neighbor_index < 1 or neighbor_index > num_nodes:
 return False, "Invalid neighbor index"
 neighbor = nodes[neighbor_index - 1]

 # Check for undirected edges
 if neighbor == node:
 return False, "Self-loops are not allowed"

 if neighbor not in node.neighbors:
 node.neighbors.append(neighbor)

 # Check if the reverse undirected edge needs to be added
 if node not in neighbor.neighbors:
 neighbor.neighbors.append(node)

 # Check if the reverse edge is present for undirected connections
 if i + 1 not in adjacency_list[neighbor_index - 1]:
 return False, "Missing reverse edge for undirected connection"

 visited.add(i + 1)

 # Check if each node has a unique data value
 unique_data_values = set(node.data for node in nodes)
 if len(unique_data_values) != num_nodes:
 return False, "Not all nodes have unique data values"

 # Check for connectedness using BFS
 if not bfs(nodes[0], visited, num_nodes):
 return False, "Not all nodes are connected"

 # If all nodes are not visited, or there are isolated nodes, the graph is invalid
 if len(visited) != num_nodes or isolated_node_count > 1:
 return False, "Not all nodes are connected or there are isolated nodes"
 
 if len(adjacency_list) > 1 and len(adjacency_list[len(adjacency_list)-1]) == 0:
 return False, "Graph is not connected"

 return True, ""

 def bfs(start_node, visited, num_nodes):
 queue = [start_node]
 while queue:
 current_node = queue.pop(0)
 if current_node.data not in visited:
 visited.add(current_node.data)
 queue.extend(neighbor for neighbor in current_node.neighbors)
 
 # Check if all nodes are visited
 return len(visited) == num_nodes


 # inputs can be accessed using self.__inputs starting from 0 to len(self.__inputs) - 1
 adj_list = self.__inputs[0]
 # inputs can be accessed using self.__inputs starting from 0 to len(self.__inputs) - 1
 if not is_valid_2d_array(adj_list):
 self.store_result ("Not a valid 2D Integer array", ValidationFunction.FAIL)
 elif not (0 <= len(adj_list) <= 100):
 self.store_result ("expected graph to have 0 <= size <= 100", ValidationFunction.FAIL)
 elif not (check_values(adj_list)):
 self.store_result("graph must consist of values from 1 to 100 only", ValidationFunction.FAIL)
 elif not is_valid_graph(adj_list)[0]:
 self.store_result(is_valid_graph(adj_list)[1], ValidationFunction.FAIL)
 
 else:
 self.store_result("", ValidationFunction.PASS)
class Node:
 def __init__(self, d):
 self.data = d
 self.neighbors = []

Graphs

Trie

Custom Data Structures

Conclusion

Clone Graph

Statement

Examples

Understand the problem

Figure it out!

Try it yourself