Credit to https://www.youtube.com/watch?v=lDTKnzrX6qU
Memorise Implementation and Time and Space Complexity - Big O Notation
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
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!!!!)
- 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
- use multiple pointers where possible in arrays
- dictionaries for frequency counting
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 :
2 .USE VISUALISATIONS
3.Explain solutionn in plain english
4.Step by step solution
6.Pseudocode
7.Functions
8.Implemet
Creativity
Consistency
Intensity
Prerequisite:
Involves Arrays
Problem solve:
Areas to look out for
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
expression_if_true if condition else expression_if_false
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
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.
Involves Hash Maps
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())
Use the sum function to total an iterable
1 2
def alternatingCharacters(s): return (len([i for i in range(1,len(s)) if s[i-1] == s[i]]))
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
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")
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
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))
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()
Create node
Create leaf
Methods
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()
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))