Transform one word into another by changing only one letter at a time

 Posted on July 24, 2014  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem Given two words of equal length that are in a dictionary, write a method to transform one word into another word by changing only one letter at a time. The new word you get in each step must be in the dictionary. EXAMPLE Input: DAMP, LIKE Output: DAMP -> LAMP -> LIMP -> LIME -> LIKE Solution Try thinking this problem in terms of graphs: Consider all words in a dictionary as vertices, and insert an edge between each two vertices that differ by only one letter. [Read More]
Graph  kodeknight  shortest-path  hard  BFS  CrackingTheCodingInterview 

Find if there is a path between two vertices in a directed graph

 Posted on February 9, 2014  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Why do you need to have 3 states (“Visited, &… Anonymous - Aug 4, 2016Why do you need to have 3 states (“Visited, “Unvisited”, and “Visiting”)? It seems like we do the same thing - adding the node to the queue - if it’s unvisited, but there is no functional distinction between visited and visiting (in either state we skip it - we won’t enqueue it and we won’t check against it). [Read More]
Graph  kodeknight  connectivity  BFS  Directed Graph  CrackingTheCodingInterview 

Find if there is a path between two vertices in a directed graph

 Posted on February 9, 2014  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem : Given a Directed Graph and two vertices in it, check whether there is a path from the first given vertex to second. Solution We have already seen solution to connectivity in undirected graph via bfs. Now lets see it on directed graph. BFS to check the connectivity public enum State { Unvisited, Visited, Visiting; } public static boolean search(Graph g, Node start, Node end) { LinkedList<Node> q = new LinkedList<Node>(); // operates as Stack for (Node u : g. [Read More]
Graph  kodeknight  connectivity  BFS  Directed Graph  CrackingTheCodingInterview 

Binary Tree Level-Order Traversal Using Depth First Search (DFS) [Not to USE BFS]

 Posted on October 5, 2013  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Given a binary tree, print out the tree in level order (ie, from left to right, level by level). Output a newline after the end of each level. Breadth First Search (BFS) is not allowed. We have already seen how to do level order traversal here. Example So consider the tree: 1 / \ 2 3 / \ / \ 4 5 6 7 The BFS or level order traversal here is : [Read More]
kodeknight  BFS  DFS  traversal  binary-search-tree  BST  level-order-traversal 

BFS (Breadth first search) on Graph

 Posted on August 25, 2013  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Algorithm Starting at some arbitrarily chosen vertex s (s stands for start vertex) , we mark v so that we know we’ve visited it, process v, and  then visit i.e. mark the vertex as visited and process all of v’s neighbors.  Now that we’ve visited and processed all of v’s neighbors,  we need to visit and process all of v’s neighbors neighbors Pseudocode BFS(graph G, vertex s) allnodesinitiallyunexploredall nodes initially unexplored \-mark s as explored let Q = queue data structure, initialized with s while (Q not empty) remove the first node of Q, call it v for each edge (v, w): if w is unexplored mark w as explored add w to Q (at the end) We visit each node only once and each edge at most twice (for edge(v, w), we might encounter it when we’re at node v and at node w). [Read More]
Graph  kodeknight  queue  BFS  graph-search  Undirected Graph 

Dijkstra's algorithm for equal weight edges using BFS

 Posted on August 25, 2013  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

This is the application of BFS (breadth first search) dist(v) = fewest number of edges on path s to v. Here is the pseudocode: Initialize dist(v) = {0 if v=s, infinity if v != s} foreach vertex v in all vertices { if(v==s) dist(v) = 0; else dist(v) = infinity; } Now apply BFS, and hen considering edge (v, w), if w is unexplored, then set dist(w) = dist(v)+1, keeping rest of the BFS same. [Read More]
Graph  kodeknight  BFS  graph-search 

BFS and Undirected Connectivity

 Posted on August 4, 2013  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Let G=(V,E) be an undirected graph (Note - for directed graph, better algorithms are available) Connected Components - the pieces of G, where graphs are connected in equivalence class. Formal definition of max connectivity - Equivalence relation between 2 vertices u and v for every u to v path in G. Equivalence relation between 2 vertices means they have to satisfly 3 conditions of equivalence Reflexive - Everything has to be related to itself Symmetric - If u is related to v, then v is related to u, which is not a problem for undirected graph Transitive - If u and v are related and v and w are related, then u and w are related Application [Read More]
Graph  kodeknight  connectivity  BFS  graph-search 

Dijkstra's Shortest Path Algorithm

 Posted on August 4, 2013  (Last modified on August 7, 2020)  |  6 minutes  |  Kinshuk Chandra

It’s Dijkstra’s algorithm, that lets you find single-source shortest paths. Problem Problem - Single source shortest paths Input - Directed graph G=(V,E) Source vertex s  Output - foreach v∈V, compute L(v)=length of a shortest s-v path in G. Assumptions: There is a path from vertex s to vertex v (otherwise, the path length is infinity) Edge lengths are non-negative (there are other algorithms for this called , but most famous being Bellman ford algorithm which uses dynamic programming) Example of shortest path [Read More]
Graph  kodeknight  shortest-path  time complexity  BFS  incomplete  heap  graph-search 

Graph Search Introduction

 Posted on August 3, 2013  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Graph search algorithms are important but lets have some motivations. Motivation behind graph search Here are few motivations: Minimal Road network - Are there sufficient roads for people to go from one place to another. Imagine, Haridwar is only connected via Delhi and there is a natural calamity, then one way people can reach there for relief etc is via Delhi, resulting in worst disaster management, but suppose it is connected via many places, sending relief will be easier. [Read More]
Graph  kodeknight  BFS  DFS  incomplete  graph-search 

Graph Traversal Methods

 Posted on July 30, 2013  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

There are two possible traversal methods for a graph: i. Breadth-First Traversal ii. Depth-First Traversal i. Breadth-First Traversal: Traverse all the vertices starting from a given ‘start vertex’. Hence, such a traversal follows the ‘neighbour-first’ principle by considering the following: - No vertex is visited more than once - Only those vertices that can be reached are visited Importantly here, we make use of the Queue data structure. In effect, we house the vertices in the queue that are to be visited soon in the order which they are added to this queue i. [Read More]
Breadth-First Traversal  kodeknight  Depth-First Traversal  BFS  DFS  Directed Graph  Data Structure