My Interview question

5 June, 2019

Find all pass codes for the old android unlock screen. Can’t pass over the same node.

# a - b - c
# | \ | / |
# d - e - f
# | / | \ |
# g - h - i
# 
graph = {}
graph['a'] = ['b', 'd', 'e']
graph['b'] = ['a', 'c', 'e']
graph['c'] = ['b', 'e', 'f']
graph['d'] = ['a', 'e', 'g']
graph['e'] = ['a', 'b', 'c', 'd', 'f', 'g', 'h', 'i']
graph['f'] = ['c', 'e', 'i']
graph['g'] = ['d', 'e', 'h']
graph['h'] = ['g', 'e', 'i']
graph['i'] = ['h', 'e', 'f']

Interviewee has to write this part. Whatever langage is fine. If they’re done we talk about using compute (parallism) or memory (memoizing) to speed it up.

def find_all(a_graph, test):
  for g in a_graph:
      dfs(g, '', test)
      
def dfs(node, visited, test):
  newvisted = visited + node
  test(newvisted)
  for neighbor in graph[node]:
      if neighbor not in visited:
          dfs(neighbor, newvisted, test)
          
find_all(graph, print)  

Here’s a coworker’s java solution

Here’s an iterative solution

def dfs_iter(node,  test):
  stack = [node]
  while stack:
    path = stack.pop()
    test(path)
    for neighbor in graph[path[-1]]:
      if not neighbor in path:
        stack.append(path + neighbor)

or golang

package main

import (
	"fmt"
	"strings"
)

var graph = map[string][]string{
	"a": {"b", "d", "e"},
	"b": {"a", "c", "e"},
	"c": {"b", "e", "f"},
	"d": {"a", "e", "g"},
	"e": {"a", "b", "c", "d", "f", "g", "h", "i"},
	"f": {"c", "e", "i"},
	"g": {"d", "e", "h"},
	"h": {"g", "e", "i"},
	"i": {"h", "e", "f"},
}

func dfs(node, visited string, test func(string)) {
	newvisted := visited + node
	test(newvisted)
	for _, neighbor := range graph[node] {
		if !strings.Contains(newvisted, neighbor) {
			dfs(neighbor, newvisted, test)
		}
	}
}

func main() {
	for node := range graph {
		dfs(node, "", func (t string) {
			fmt.Printf(t + "\n")
		})
	}
}