Graph Data Structure & Algorithms

Introduction to graphs

Graph Data Structure & Algorithms Problems

Graph traversal

Problem	Score	Companies	Time	Status
Path in Directed Graph	150	uber	40:20
Water Flow	200		69:12
Stepping Numbers	300	Epic systems Amazon	59:52
Capture Regions on Board	500		65:57
Word Search Board	500	Epic systems Amazon infoworks	59:16

Depth first search

Problem	Score	Companies	Time	Status
Path with good nodes!	150	Tower Research Capital	57:16
Largest Distance between nodes of a Tree	200		77:39
Good Graph	200		61:49
Cycle in Directed Graph	200	Amazon Morgan Stanley	55:20
Delete Edge!	200	Flipkart	63:57
Two teams?	300	Directi	52:28

Bfs

Problem	Score	Companies	Time	Status
Valid Path	200	Morgan Stanley Amazon Codenation Directi	83:46
Snake Ladder Problem!	200	Amazon	63:57
Region in BinaryMatrix	200	Amazon	44:12
Level Order	300	Groupon Goldman Sachs	29:55
Smallest Multiple With 0 and 1	300	Amazon	74:26
Min Cost Path	300	Directi	65:56
Permutation Swaps!	300	Directi	55:45

Graph connectivity

Problem	Score	Companies	Time	Status
Commutable Islands	200	Amazon	77:21
Possibility of finishing all courses given pre-requisites	200	Amazon Flipkart Grab infoworks Zenefits	64:33
Cycle in Undirected Graph	200	Amazon	52:26
Black Shapes	300	Amazon	48:52

Graph adhoc

Problem	Score	Companies	Time	Status
Convert Sorted List to Binary Search Tree	300		44:30

Shortest path

Problem	Score	Companies	Time	Status
Sum Of Fibonacci Numbers	300		52:49
Knight On Chess Board	300	Goldman Sachs Amazon Tower Research Capital	67:27
Useful Extra Edges	400	curefit Directi juspay	62:08
Word Ladder I	600	Ebay	68:57
Word Ladder II	800	Ebay	67:23

Graph hashing

Problem	Score	Companies	Time	Status
Clone Graph	500	Amazon	56:55

Additional Practice

Problem	Score	Companies	Time	Status
Connected Components	200	IBM	19:55
File Search	200	AlphaGrep	20:42
Mother Vertex	200	Paytm	50:15
Path in Matrix	200	Amazon	26:20