Practice Graphs Questions for DSA Coding Interviews

21. Word Ladder

Required Input:

hit' 
'cog' 
['hot', 'dot', 'dog', 'lot', 'log', 'cog']

Expected Output:

Code In Python

from collections import deque def word_ladder(beginWord, endWord, wordList): # Write your logic here pass # Prefilled input beginWord = "hit" endWord = "cog" wordList = ["hot", "dot", "dog", "lot", "log", "cog"] print(word_ladder(beginWord, endWord, wordList))

Run Code?

Click Run Button to view compiled output

22. Traveling Salesman Problem

Required Input:

[
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]

Expected Output:

Code In Python

def tsp(graph): # Write your logic here pass # Prefilled input graph = [ [0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0] ] print(tsp(graph))

Run Code?

Click Run Button to view compiled output

23. Maximum Flow

Required Input:

 [
    [0, 16, 13, 0, 0, 0],
    [0, 0, 10, 12, 0, 0],
    [0, 4, 0, 0, 14, 0],
    [0, 0, 9, 0, 0, 20],
    [0, 0, 0, 7, 0, 4],
    [0, 0, 0, 0, 0, 0]
]

Expected Output:

Code In Python

from collections import deque def max_flow(graph, source, sink): # Write your logic here pass # Prefilled input graph = [ [0, 16, 13, 0, 0, 0], [0, 0, 10, 12, 0, 0], [0, 4, 0, 0, 14, 0], [0, 0, 9, 0, 0, 20], [0, 0, 0, 7, 0, 4], [0, 0, 0, 0, 0, 0] ] source = 0 sink = 5 print(max_flow(graph, source, sink))

Run Code?

Click Run Button to view compiled output

24. Strongly Connected Components

Required Input:

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

Expected Output:

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

Code In Python

def strongly_connected_components(edges, num_nodes): # Write your logic here pass # Prefilled input edges = [[0, 1], [1, 2], [2, 0], [1, 3], [3, 4], [4, 5], [5, 3]] num_nodes = 6 print(strongly_connected_components(edges, num_nodes))

Run Code?

Click Run Button to view compiled output

25. Bridge Detection (Tarjan)

Required Input:

[[0,1],[1,2],[2,0],[1,3]] 
4

Expected Output:

[[1, 3]]

Code In Python

def find_bridges(num_nodes, edges): # Write your logic here pass # Prefilled input edges = [[0,1],[1,2],[2,0],[1,3]] num_nodes = 4 print(find_bridges(num_nodes, edges))

Run Code?

Click Run Button to view compiled output

26. Number of Islands (DFS)

Required Input:

[
  ['1','1','0','0'],
  ['1','0','0','1'],
  ['0','0','1','1']
]

Expected Output:

Code In Python

def num_islands(grid): # Write your logic here pass # Prefilled input grid = [ ['1','1','0','0'], ['1','0','0','1'], ['0','0','1','1'] ] print(num_islands(grid))

Run Code?

Click Run Button to view compiled output

27. Redundant Connection (Union-Find)

Required Input:

[[1,2],[1,3],[2,3]]

Expected Output:

[2, 3]

Code In Python

def find_redundant_connection(edges): # Write your logic here pass # Prefilled input edges = [[1,2],[1,3],[2,3]] print(find_redundant_connection(edges))

Run Code?

Click Run Button to view compiled output

28. Minimum Height Trees

Required Input:

4
[[1,0],[1,2],[1,3]]

Expected Output:

[1]

Code In Python

def find_min_height_trees(n, edges): # Write your logic here pass # Prefilled input n = 4 edges = [[1,0],[1,2],[1,3]] print(find_min_height_trees(n, edges))

Run Code?

Click Run Button to view compiled output

29. Reconstruct Itinerary

Required Input:

[["MUC", "LHR"], ["JFK", "MUC"], ["LHR", "SFO"], ["SFO", "JFK"]]

Expected Output:

['JFK', 'MUC', 'LHR', 'SFO', 'JFK']

Code In Python

def find_itinerary(tickets): # Write your logic here pass # Prefilled input tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["LHR", "SFO"], ["SFO", "JFK"]] print(find_itinerary(tickets))

Run Code?

Click Run Button to view compiled output

30. Alien Dictionary

Required Input:

wrt wrf er ett rftt

Expected Output:

wertf

Code In Python

def alien_order(words): # Write your logic here pass # Prefilled input words = input().split() print(alien_order(words))

Run Code?

Click Run Button to view compiled output

3 of 3