# Interview Help

## Mandatory Learn

• Iteration and Recursion
• Arrays and Matricies
• Queues,Stacks,Heaps
• Sets, Hash Maps (Dict)
• Trees
• Binary Search
• Graph Traversal
• Depth 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
• 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

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/

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

2. Draw out visualisations
3. Talk through it with your interviewer
4. State assumptions
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

• 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
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

 ``` 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

 ```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

 ```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

 ```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

• Create node
• Node holds data and points to next node
• Create linked list with methods
• Insert node at end
• Insert node at position
• Delete end 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)))```

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)) ```