Case study: word ladder find all paths

Sept. 24, 2019

The interview lasted one hour 7 minutes, the first 50 minutes or so the interviewee worked on the algorithm. We had some discussion about how to improve the algorithm.

The interviewee went to Google, Amazon, Uber and Microsoft onsite. He also showed how to run the code using pseduo code. It is such a good learning expereince for me.

Transcript starts from here.

	import java.io.*;
	import java.util.*;
	/*
	* To execute Java, please define "static void main" on a class
	* named Solution.
	*
	* If you need more classes, simply define them inline.
	algorithm:
	- create a directed graph represented by adjecency list
	- Define visited set, and list of list of strings paths
	- function (source, destination, visited, emptyList, graph, paths) // good, {}, []
	// curpath = [good, bood,]
	// visited = {good, bood, beod}
	good -> g$od
	function (source, destination, visited, curPath, graph, paths) { // good .. bood .. beod
	- add source to the curPath
	- add source to visited
	- if (source is destination)
	- add copy of curPath to the paths
	return;
	- for (each neighbor of source) // neighbor = bood .. beod .. besd
	- if (neighbor is not visited)
	- function(neighbor, destination, visited, curPath, graph, paths) // bood ..beod .. besd
	- remove source from curPath
	- remove neighbor from visited
	}
	*/
	class Solution {
	private static List<List<String>> getAllPaths(String source, String destination, Set<String> dict) {
	Map<String, Set<String>> graph = createGraph(source, destination, dict);
	// System.out.println(graph);
	List<List<String>> paths = new ArrayList<>();
	Set<String> visited = new HashSet<>();
	List<String> curPath = new ArrayList<>();
	curPath.add(source);
	helper(source, destination, visited, curPath, graph, paths); //
	return paths;
	}
	private static void helper(String source,
	String destination,
	Set<String> visited,
	List<String> curPath,
	Map<String, Set<String>> graph,
	List<List<String>> paths) {
	// System.out.println(source + " " + curPath + " " + visited);
	if (source.equals(destination)) {
	paths.add(new ArrayList<>(curPath));
	return;
	}
	for (String neighbor : graph.get(source)) {
	if (!visited.contains(neighbor)) {
	curPath.add(neighbor);
	visited.add(neighbor);
	helper(neighbor, destination, visited, curPath, graph, paths);
	curPath.remove(curPath.size() - 1);
	visited.remove(neighbor);
	}
	}
	}
	private static Map<String, Set<String>> createGraph(String source, String destination, Set<String> dict) {
	Map<String, Set<String>> graph = new LinkedHashMap<>();
	graph.putIfAbsent(source, new HashSet<>());
	for (String word : dict) {
	if (isOneCharDifferent(source, word)) {
	graph.get(source).add(word);
	}
	}
	for (String word1 : dict) {
	for (String word2 : dict) {
	if (isOneCharDifferent(word1, word2)) {
	graph.putIfAbsent(word1, new HashSet<>());
	graph.putIfAbsent(word2, new HashSet<>());
	graph.get(word1).add(word2);
	graph.get(word2).add(word1);
	}
	}
	}
	return graph;
	}
	private static boolean isOneCharDifferent(String s1, String s2) {
	if (s1.length() != s2.length() || s1.equals(s2)) {
	return false;
	}
	boolean diffFound = false;
	for (int i = 0; i < s1.length(); i++) {
	if (s1.charAt(i) != s2.charAt(i)) {
	if (diffFound) {
	return false; // more than one character is different
	}
	diffFound = true;
	}
	}
	return diffFound;
	}
	public static void main(String[] args) {
	String source = "good",
	destination = "best";
	Set<String> dict = new HashSet<>();
	dict.add("bood");
	dict.add("beod");
	dict.add("besd");
	dict.add("goot");
	dict.add("gost");
	dict.add("gest");
	dict.add("best");
	System.out.println(getAllPaths(source, destination, dict));
	}
	}
	/*
	source = "good";
	dest = "best";
	var words = new string[] {"bood", "beod", "besd","goot","gost","gest","best"};
	two paths
	good->bood->beod->besd->best
	good->goot->gost->gest->best
	Given a start and destination word, a list of words as a dictionary, find all paths from source to dest word, each intermediate word should be in dictionary. Each time one char is updated.
	good -> bood, goot
	bood -> beod
	beod -> bood, besd
	besd -> beod, best
	goot -> gost
	gost -> goot, gest
	gest -> gost, best
	best -> gest
	*/

view raw wordLadderFindAllPaths.java hosted with ❤ by GitHub

End here