Case study: Word ladder find all paths

Sept. 23, 2019

Introduction

It is my mock interview as an interviewer. I just could not believe that the interviewee had super good performance, he wrote the code and tested the code, no bug, executable code.

Case study

Let me show the code I reviewed.

	'''
	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
	good -> queue - LEVEL 1
	'bood' -> good -> bood -> may have 3 neighbors
	'goot' - > good -> goot -> may have 6 neighbors
	I cannot hear you for some reason.
	continue to BFS - LEVEL 2
	9 paths -> to check
	I think there are audio problems, cannot hear your speaking
	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.
	'''
	import unittest
	from collections import defaultdict, deque
	# Assumption: All words will be the same length
	def validNeighbor(first_word, second_word):
	count_of_differing_characters = 0
	for first_word_chr, second_word_chr in zip(first_word, second_word): #
	if first_word_chr != second_word_chr:
	count_of_differing_characters += 1
	if count_of_differing_characters > 1:
	return False
	return True
	def generatePaths(words, source, dest):
	# Step 1: Preprocess words into nodes, neighbors of words off by 1-letter
	words_graph = defaultdict(list)
	for word_one in words:
	for word_two in words:
	if word_one != word_two and validNeighbor(word_one, word_two):
	words_graph[word_one].append(word_two)
	# O(N * N) - N is size of dictionary, length of list of words
	# N is million numbers -> 10^6
	# Each word
	# Step 2: Traverse over graph using either DFS or BFS, tracking visited nodes
	all_paths = []
	visited_nodes = set()
	bfs_queue = deque([(source, [source])]) #
	# While queue has nodes to process
	while bfs_queue:
	# Pop the current node (latest node), and path so far
	current_node, path_so_far = bfs_queue.popleft()
	# Skip iteration if we've already processed this node
	if current_node in visited_nodes:
	continue
	# For each neighbor, build out queue and paths
	for neighbor in words_graph[current_node]:
	if neighbor == dest:
	# If the neighbor is reached, update all_paths with the current path
	all_paths.append('->'.join(path_so_far + [neighbor]))
	continue
	# Continue processing other neighbors
	bfs_queue.append((neighbor, path_so_far + [neighbor])) # add a node to path
	# Keep track of all nodes that we have processed all neighbors for
	visited_nodes.add(current_node)
	return all_paths
	class Test(unittest.TestCase):
	def test_example(self):
	source = 'good'
	dest = 'best'
	words = ['good', 'bood', 'beod', 'besd','goot','gost','gest','best']
	actual = generatePaths(words, source, dest)
	expected = ['good->bood->beod->besd->best', 'good->goot->gost->gest->best'] #
	self.assertEqual(actual, expected)
	unittest.main(verbosity=2)

view raw wordLadderFindAllPaths.py hosted with ❤ by GitHub

End of python code

Here is my feedback as an interviewer.

Here is the feedback from the interviewee.