Interview Help

Credit to https://www.youtube.com/watch?v=lDTKnzrX6qU

Mandatory Learn


  • Iteration and Recursion
  • Arrays and Matricies
  • Linked lists
  • Queues,Stacks,Heaps
  • Sets, Hash Maps (Dict)
  • Trees
  • Binary Search
  • Graph Traversal
    • Depth First
    • Breadth First
  • Backtracking
  • Sorting
    • Merge Sort
    • Quick Sort

Memorise Implementation and Time and Space Complexity - Big O Notation

Good to Learn


  • Dynamic Programming
  • Brocken down into
  • Memorisation - Storing and reusing values by recursive call
  • Divide and Conquer - Solving sub problem of your problem

Good to practice proof


  • Contrapositive
  • Contradiction
  • Cases
  • Induction

Practice problems with ....

  • Multiple pointers
  • Sliding window
  • Greedy Algorithms
  • Object Oriented Programming

In interviews use


  • Hashmaps when you can "Very Powerful" - For python use "from collections import Counter"
  • Stacks and Queues
  • Sets and Depth First Search

Helpful Links


https://cs61a.org/

https://inst.eecs.berkeley.edu/~cs61b/sp20/

https://cs50.harvard.edu/college/2020/fall/weeks/3/

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/

https://www.youtube.com/watch?v=GKgAVjJxh9w&list=PLX6IKgS15Ue02WDPRCmYKuZicQHit9kFt&index=1

Geeksforgeeks Data structures

Hackerrank Data structures

You as a person


1. Be Experienced


NOT MEASURED BY REPETITION OR YEARS OF EXPERIENCE

Measured by rate you absorb lessons and how useful they were

- Look for patterns in your mistakes

After doing a problem ask yourself "What is the one thing I could have known/done that would have made everything else easier?" (DO NOT FORGET THIS!!!!)


Common Mistake

- Don't write code before you what what you are going to be doing.

(Problem Solving while coding is hard - Problem Solve first then code )

Solution

  1. Think about the question
  2. Draw out visualisations
  3. Talk through it with your interviewer
  4. State assumptions
  5. Ask question
  6. Explain solution
  7. Finally start coding


- use multiple pointers where possible in arrays 


- dictionaries for frequency counting

2. Know What You Are Doing


DO NOT "IN THE MOMMENT"

Rely on habits, rules and systems

1 . When the interviewer hands you the problem "WHAT DO YOU DO?"

You should make use of :

  • Description of the problem
  • Sample input and output
  • Constaraints
  • Whiteboard

2 .USE VISUALISATIONS

3.Explain solutionn in plain english

4.Step by step solution

6.Pseudocode

7.Functions

8.Implemet


If you get stuck ask yourself:

  • Why is this hard to code?
  • What assumptions can I make?
  • What is my Big O
  • What is the next best Big O
  • Why is this possible?
  • Where is the repeated work happening?
  • Does this need to happen?

3. Be Smart at everything you do


Creativity

  • Ask questions
  • Self Awareness
    • Are you going down the wrong path?

Consistency

  • Do it everyday

Intensity

  • Mental engagement
  • Envision the goal
  • Pretend the problem at hand is the interview problem

My time on Hackerrank


Challenge - Jumping on the clouds

Prerequisite:

Involves Arrays 

Problem solve:

  1. Look at first value in list
  2. Check two values ahead  
  3. If it is 
    1. one then I cant jump there:
      1. One value ahead will be zero because of constraint so I can move there 
    2. zero I can jump there 
  4. Add one to a jump counter 
  5. Loop 
  6. Return counter 

Areas to look out for 

  1. Look for two values ahead when value does not exist 
  2. Try to use a pointer 


Answer

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def jumpingOnClouds(c):
    pointer,jumps = 0,0
    while pointer<(len(c)-2):
        pointer = pointer + 1 if c[pointer+2] else pointer +2
        jumps += 1
    
    if pointer < len(c)-1:
        jumps += 1

    return jumps


What is the one thing I could have known/done that would have made everything else easier? 

  1. 1
    expression_if_true if condition else expression_if_false
  2. If you are dealing with zeros and ones remember you can implement boolean rules (anything that is not zero is TRUE)



Challenge - Minimum Swaps

Prerequisite:

Involves Arrays 

Problem solve:

  1. pointer -Look for the smallest element in list 
  2. Swap that element with the first element 
  3. Move pointer right 
  4. Look for second smallest element 
  5. Swap
  6. Loop

Areas to look out for 

  1. Use pointer 


Answer

1
2
3
4
5
6
7
8
    count=0
    for i in range(len(arr)):
        while(arr[i]!=i+1):
            count+=1
            temp=arr[i]
            arr[i]=arr[temp-1]
            arr[temp-1]=temp 
    return count


What is the one thing I could have known/done that would have made everything else easier? 

Did not get this one :( - The mistake I made was that I was looking for the next smallest element in the list - this is inefficient

In the question it mentioned that the numbers in the list were consecutive

What I should have done is checked the next element after my pointer.


Challenge - Strings: Making Anagrams

Prerequisite:

Involves Hash Maps 

Problem solve:

  1. Create a hash map for a and b 
  2. subtract b from a 
  3. Total all the values

Answer

1
2
3
4
def makeAnagram(a, b):
    a,b =Counter(a),Counter(b)
    a.subtract(b)
    return sum(abs(i) for i in a.values())


What is the one thing I could have known/done that would have made everything else easier? 

Use the sum function to total an iterable


Challenge - Alternating Characters

Prerequisite:

Involves Arrays

Problem solve:

  1. Convert string to list
  2. if next character is the same as current character then delete otherwise move to the next character 
  3. loop
  4. count length of list  

Answer

1
2
def alternatingCharacters(s):
    return (len([i for i in range(1,len(s)) if s[i-1] == s[i]]))

What is the one thing I could have known/done that would have made everything else easier? 

You don't need to delete the next element, you just need to count all corresponding elements. 

Use list comprehension when you can 

Next element compares to previous element



Data Structures that I have covered


Linked Lists


  • Create node
    • Node holds data and points to next node 
  • Create linked list with methods
    • Insert node at end
    • Insert node at head
    • Insert node at position
    • Delete end node
    • Delete head node
    • Check if list empty
    • Traverse list
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
class Node:
    def __init__(self,data):
        self.data = data
        self.next = None
        

class linked_list:
    def __init__(self):
        self.head=None
        self.count=0

    def insertEnd(self, newNode):
        if self.head is None:
            self.head=newNode
        else:
            lastNode=self.head
            while True:
                if lastNode.next is None:
                    break
                lastNode=lastNode.next
            lastNode.next=newNode

    def insertHead(self, newNode):
        tempNode = self.head
        self.head = newNode         
        self.head.next = tempNode        
        del tempNode


    def insertAt(self, newNode, position):
        currentNode=self.head
        currentPosition=0
        while True:
            if currentPosition == position:
                previousNode.next=newNode
                newNode.next=currentNode
                break
            previousNode=currentNode
            currentNode=currentNode.next
            currentPosition += 1

    def deleteEnd(self):
        lastNode=self.head
        while lastNode.next is not None:
            prevNode=lastNode
            lastNode=lastNode.next
        prevNode.next=None

    

    def deleteAt(self, position):
        currentNode=self.head
        currentPosition=0
        while True:
            if currentPosition == position:
                prevNode.next=currentNode.next
                currentNode.next=None
                break
            prevNode=currentNode
            currentNode=currentNode.next
            currentPosition +=1

          
            

    def isEmpty(self):
        if self.head is None:
            return True
        else:
            return False

    def traversal(self):
        currentNode=self.head
        while currentNode is not None:
            print(currentNode.data)
            currentNode=currentNode.next
    

    def deleteHead(self):
        if self.isEmpty() is False:
            prevHead=self.head
            self.head=self.head.next
            prevHead.next=None
            print("The first item is deleted successfully")
        else:
            print("Linked List is empty, Delete Failed")

Recursion


Factorial recursion 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def factorialList (n):
    if n == 1:
        ansList = [0] * n
        ansList [0] = 1
    else :
        ansList = factorialList(n-1)
        ansList.append(n*ansList[n-2])
    return ansList

value=int (input("Enter the range : "))
print( factorialList ( value ))


Recursive total of list 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def recursiveSum ( aList ):
    return recSum( aList ,0)
def recSum( aList , pos ):
    if pos == len( aList ):
        return 0
    else :
        return aList [ pos ] + recSum( aList , pos+1)

a=[1,2,3,4,5]
print(recursiveSum(a))

Recusrsive prints the numbers 1 to n.

1
2
3
4
5
6
def printToN(N):
    if N<1:
        return
    else :
        printToN(N-1)
        print(N)

Recursive function to find the smallest item in a list

1
2
3
4
5
6
7
def findMinimum(lst):
    if len(lst) == 1:
        return lst[0]
    else:
        return min(lst[0], findMinimum(lst[1:]))
listA = [9,-2,6,1,80,9,-2, -8, 90, -9]
print(findMinimum(listA))

Merge Sort


Split list into multiple small lists

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import random  # for testing

# merge sort (naive version) -------------------------------------------


def merge(l,r):
    """Take two *sorted* lists, return the merged result."""
    result=[]
    while len(l)>0 and len(r)>0:
        if l[0] < r[0]:
            result.append(l[0])
            del l[0]
        else:
            result.append(r[0])
            del r[0]
    # one of either l or r may still have elements in; we need
    # to make sure these are included in the result
    result.extend(l)
    result.extend(r)
    return result



def mergesort(xs):
    """Mergesort."""
    if len(xs) <= 1:
        # NOTE list is very small... and already sorted
        return xs
    midpoint = len(xs)//2  # NOTE integer division
    l, r = xs[0:midpoint], xs[midpoint:]
    l2, r2 = mergesort(l), mergesort(r)
    return merge(l2,r2)


# example --------------------------------------------------------------

print("Merge example:",str(merge([4,7,9],[1,2,10,11,12])))


arr=[9,8,1,2,3,7,6,5,1,2,3]
print("Mergesort example: ",str(mergesort(arr)))


# testing -------------------------------------------------------------

def sorted(xs):
    return all(xs[i] <= xs[i+1] for i in range(0,len(xs)-1))

    
arr=[9,8,1,2,3,7,6,5,1,2,3]
for x in range(0,100):
    random.shuffle(arr)
    print("Unsorted:", str(arr))
    arr=mergesort(arr)
    assert sorted(arr)
    print("Sorted!:", str(arr))
    print()

Binary trees


Create node

  • has type "node"
  • has a left pointer
  • has a right pointer
  • has a label

Create leaf

  • has type "leaf"
  • has a label


Methods

  • Check to see if it is a node
  • Check to see if it is a leaf
  • Copy node
  • Print tree
  • Count leaves
  • Total values of nodes and leaves
  • Check to see if tree contains your value
  • All nodes at given level
  • Pre-order nodes
  • In-order nodes
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
# simple binary trees --------------------------------------------------

# we represent a binary tree using simple objects
from contextlib import redirect_stdout


class Object(object):
    pass


def node(l, v, r):
    n = Object()
    n.type = "node"
    n.left = l
    n.label = v
    n.right = r
    return n


def copy_node(n1,n2):
    n2.type = n1.type
    n2.left = n1.left
    n2.label = n1.label
    n2.right = n1.right


def leaf(v):
    n = Object()
    n.type = "leaf"
    n.label = v
    return n


def is_leaf(n):
    if n.type == "leaf":
        return True
    else:
        return False

# NOTE really this should be "is_internal_node"
def is_node(n):
    if n.type == "node":
        return True
    else:
        return False


def left(n):
    assert is_node(n)
    return n.left


def label(n):
    if is_node(n):
        return n.label
    else:
        assert is_leaf(n)
        return n.label


def right(n):
    assert is_node(n)
    return n.right


def print_tree(t0):
    def aux(t,n:int):
        print(" "*n,end='')
        if is_leaf(t):
            print(t.label)
        else:
            assert is_node(t)
            print(t.label)
            aux(t.left,n+1)
            aux(t.right,n+1)
    aux(t0, 0)


def tree_to_string(t0):
    s=""
    def aux(t,n:int):
        nonlocal s
        s+=" "*n
        if is_leaf(t):
            s+=str(t.label)+"\n"
        else:
            assert is_node(t)
            s+=str(t.label)+"\n"
            aux(t.left,n+1)
            aux(t.right,n+1)
    aux(t0, 0)
    return s


t2s=tree_to_string


# example tree ---------------------------------------------------------

def example_tree():
    ex = node(
        leaf(2),
        3,
        node(
            leaf(4),
            5,
            leaf(6)))
    return ex


ex = example_tree()


print("Example tree:", tree_to_string(ex),sep='\n')


# subtree_at -----------------------------------------------------------

# take a string like "llrl" which tells you which subtree to go to,
# and return the corresponding subtree in the tree
def subtree_at(s, t):
    # print((s,str(t)))
    if s == "": return t
    if is_leaf(t):
        raise RuntimeError("subtree_at: found a leaf, could not descend further: " + str(t))
    if s[0] == 'l': return subtree_at(s[1:], left(t))
    if s[0] == 'r': return subtree_at(s[1:], right(t))
    raise RuntimeError("subtree_at: unknown character: " + str(s[0]))

with open('ignore.txt', 'w') as f:
    with redirect_stdout(f):
        print("Subtree_at example 1:",tree_to_string(subtree_at("l", ex)))
        print("Subtree_at example 2:",tree_to_string(subtree_at("r", ex)))
        print("Subtree_at example 3:",tree_to_string(subtree_at("rl", ex)))


# leaves -----------------------------------------------------------

def count_leaves(n):
    if is_leaf(n):
        return 1
    else:
        return (count_leaves(left(n)) +
                count_leaves(right(n)))


print("Count_leaves example:", count_leaves(ex))


def leaves(t):
    if is_leaf(t):
        return [label(t)]
    else:
        return leaves(left(t)) + leaves(right(t))


print("Leaves example:", str(leaves(ex)))


# values ---------------------------------------------------------------

# NOTE same as "leaves", except also includes inner node labels
def values(t):
    if is_leaf(t):
        return [label(t)]
    else:
        return values(left(t)) + [label(t)] + values(right(t))


# eval -----------------------------------------------------------------

def eval_(n):
    if is_leaf(n):
        # NOTE we assume a leaf has a value that is an int
        return label(n)
    else:
        v = label(n)
        if v == "+":
            return eval_(left(n)) + eval_(right(n))
        elif v == "*":
            return eval_(left(n)) * eval_(right(n))
        else:
            raise RuntimeError(
                "eval_: unexpected node value: " + str(v))


def eval_test():
    print("Eval leaf(3):", str(eval_(leaf(3))))
    t1 = node(leaf(1),"+",leaf(2))
    print("Eval t1:", str(eval_(t1)))
    t2 = node(leaf(1),"+",
              node(leaf(2),"+",leaf(3)))
    print("Eval t2:", str(eval_(t2)))

eval_test()



# challenge: tree_contains ---------------------------------------------------

def tree_contains(t,i):
    if is_leaf(t):
        return (t.label == i)
    else:
        if t.label == i: return True
        else: return (tree_contains(t.left,i) or
                      tree_contains(t.right,i))


print("Tree contains 1, should be False:", str(tree_contains(ex,1)))
print("Tree contains 3, should be True:", str(tree_contains(ex,3)))





# challenge: nodes_at_level --------------------------------------------------

def nodes_at_level(t,i):
    if i == 0: return [t.label]
    else:
        if is_leaf(t): return []
        else: return (nodes_at_level(t.left,i-1)+
                      nodes_at_level(t.right,i-1))


print("Nodes at level (should be [4,6]):", nodes_at_level(ex,2))




# challenge: nodes_less_than -------------------------------------------

def nodes_less_than(t,i):
    if is_leaf(t):
        if t.label < i: return [t.label]
        else: return []
    else:
        ls = nodes_less_than(t.left,i)
        rs = nodes_less_than(t.right,i)
        if t.label < i:
            at_this_node = [t.label]
        else:
            at_this_node = []
        return at_this_node+ls+rs


print("Nodes less than (should be [3,2,4]):", nodes_less_than(ex,5))


# pre-order ------------------------------------------------------------

def pre_order(t):
    if is_leaf(t):
        return [label(t)]
    else:
        return ([label(t)] +
                pre_order(left(t)) +
                pre_order(right(t)))


print("pre-order example:", str(pre_order(ex)))


# in-order ------------------------------------------------------------

def in_order(t):
    if is_leaf(t):
        return [label(t)]
    else:
        return (in_order(left(t)) +
                [label(t)] +
                in_order(right(t)))


print("in-order example:",str(in_order(ex)))



# binary search tree ---------------------------------------------------

# NOTE some of the leaves may be None!

def bst_insert(t, i0):
    # print(str(t))
    if is_node(t):
        if i0 == label(t): return
        if i0 < label(t):
            bst_insert(left(t), i0)
        else:
            bst_insert(right(t), i0)
    else:
        # we have a leaf with a single value
        assert is_leaf(t)
        v = label(t)
        # NOTE leaf values can now be None
        if v is None:
            t.label = i0  # just replace None with i
        elif i0 == v:
            return  # do nothing
        elif i0 < v:
            new_node = node(leaf(i0), v, leaf(None))
            copy_node(new_node,t)
        else:
            # NOTE i>v
            new_node = node(leaf(None), v, leaf(i0))
            copy_node(new_node, t)
    return


# example --------------------------------------------------------------

import random


def bst_ex1():
    ex = leaf(99)

    for x in range(0, 9):
        i = random.randrange(30)
        print("bst, inserting: " + str(i))
        bst_insert(ex, i)

    print()
    print("bst example")
    print("bst: " + t2s(ex))
    print("bst values: " + str(values(ex)))

Breadth first search


For tree

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
# bst_contains -------------------------------------------------------------

def bst_contains(t, i):
    # uncomment the following to see how bst_contains executes
    # print("bst_contains: looking at: ",t2s(t),sep="\n")  # show how search progresses
    if is_leaf(t):
        return label(t) == i
    else:
        if i == label(t):
            return True
        elif i < label(t):
            return bst_contains(left(t), i)
        else:
            return bst_contains(right(t), i)


# see http://jimblackler.net/treefun/index.html for a way to visualize
# the example tree that follows; also see file tree_example.png
viz="""
99
 17
  11
   5
    2
     1
     None
    None
   13
  23
   None
   26
 None
"""

ex1 = node(
    node(leaf(1),2,leaf(None)),
    5,
    leaf(None))

ex11 = node(
    ex1,
    11,
    leaf(13))

ex2 = node(leaf(None),23,leaf(26))

ex3 = node(ex11,17,ex2)

ex = node(ex3, 99, leaf(None))

print("Example bst:", t2s(ex), sep='\n')


print("Bst_contains 2:",bst_contains(ex, 2))
print("Bst_contains 3:",bst_contains(ex, 3))








# breadth-first -------------------------------------------------------

# breadth-first search/traversal: root, all nodes at depth 1 (from left to right), all at depth 2, etc.

bfs_order=[]

# NOTE "pure" bfs doesn't return anything - bfs is a way of traversing through a tree
def bfs(t0):
    """Traverse a tree in breadth-first order."""
    q=[t0]
    while len(q) > 0:
        t = q[0]
        del q[0]
        # At this point, we do something with the
        # node; for the time being, we just
        # append the label to some global variable
        bfs_order.append(t.label)
        if is_leaf(t): pass
        else: q.append(t.left); q.append(t.right)

bfs(ex)
print("Bfs example 1:", str(bfs_order))


ex = node(
    node(leaf(4),2,leaf(5)),
    1,
    node(leaf(6),3,leaf(7)))

bfs_order=[]  # reset to empty
bfs(ex)

print("Bfs example 2:", str(bfs_order))

For maze

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
# BFS to find a path through a maze
import csv

maze=[]
with open('maze.txt') as csv_file:
    csv_reader = csv.reader(csv_file, delimiter=',')
    for row in csv_reader:
        maze.append(row)

print(str(maze))

print(maze[0][1])  # row 0, column 1

# assume we start at position 0,0; then we have to get to position ...

rows=len(maze)
cols=len(maze[0])  # assume maze is rectangular
end=(rows-1,cols-1)

def is_empty(x,y):
    # first take care of the blocks that are off the map
    if x<0: return False
    if y<0: return False
    if x>3: return False
    if y>3: return False
    if (maze[x][y]).strip() != "": return False
    else: return True


def bfs_maze0():
    q=[(0,0)]
    while len(q) > 0:
        x,y = q[0]
        # check if we are done
        if (x,y) == end:
            print("Found a path to the exit!")
            return
        # where can we move from here?
        for dx in [-1,0,1]:  # dx is "difference in x"
            for dy in [-1,0,1]:
                if dy+dx == 1 or dy+dx == -1:
                    if is_empty(x+dx,y+dy):
                        q.append((x+dx,y+dy))
        del q[0]

fuel=1000
# we stop searching if we run out of fuel;
# this stops the search from hanging if there is no path through the maze


def bfs_maze():
    q=[(0,0)]
    while len(q) > 0:
        global fuel
        fuel-=1
        if fuel <= 0: return
        x,y = q[0]
        # check if we are done
        if (x,y) == end:
            print("Found a path to the exit!")
            return
        # where can we move from here?
        for dx in [-1,0,1]:  # dx is "difference in x"
            for dy in [-1,0,1]:
                if dy+dx == 1 or dy+dx == -1:
                    if is_empty(x+dx,y+dy):
                        q.append((x+dx,y+dy))
        del q[0]

# NOTE if there is no path to the exit, the search will continue for ever unless we have something like
# "fuel"
bfs_maze()

fuel=1000  # reset fuel

# this version prints out the path
def bfs_maze2():
    q=[(0,0,[(0,0)])]
    while len(q) > 0:
        global fuel
        fuel-=1
        if fuel <= 0: return
        x,y,path = q[0]
        # check if we are done
        if (x,y) == end:
            print("Found a path to the exit!", str(path))
            return
        # where can we move from here?
        for dx in [-1,0,1]:  # dx is "difference in x"
            for dy in [-1,0,1]:
                if dy+dx == 1 or dy+dx == -1:
                    if is_empty(x+dx,y+dy):
                        print(x+dx,y+dy)
                        updated_path=list(path)  # copy old path
                        updated_path.append((x+dx,y+dy))
                        q.append((x+dx,y+dy,updated_path))
        del q[0]

bfs_maze2()

Depth first search


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# depth-first search -------------------------------------------------

# NOTE this is a global variable!
dfs_order=[]

# pre-order (since binary tree)
# NOTE dfs does not "return" anything - dfs is a way of searching
# through a tree
def dfs(t0):
    if is_leaf(t0):
        # At this point we do something with the node.
        # For the time being, we just append it to
        # some global variable
        dfs_order.append(t0.label)
    else:
        assert is_node(t0)
        # See previous comment
        dfs_order.append(t0.label)
        dfs(t0.left)
        dfs(t0.right)


dfs(ex)
print("Dfs example:", str(dfs_order))