Patterns Flashcards
INSTRUMENT:
How to check if the type of an object is a list?
lista = [1,2,3]
if type(lista) is list:
return listINSTRUMENT:
How to create a personalizable function for comparing?
We need to use functools!
import functools
#then we define a compare function
def compare(item1, item2):
if item1 < item2:
return 1 # lo metto dopo
elif item1 > item2:
return -1 # lo metto prima
else:
return 0 #se sono consideration uguali
#calling lista = [1, 4, 3, 2] sorted(lista, key=functools.cmp_to_key(compare))
INSTRUMENT:
What do I do if I want to know where an element in a sorted list should be placed?
Use bisect/bisect_left!
from bisect import bisect_left #from bisect import bisect_right
l1 = [2,3,5] bisect_left(l1, 3) #returns 1! #bisect(l1, 3)
ALGORITHM: briefly describe merge sort and implement it
merge sort algorithm
Merge sort is basically based on split thw tho halfs recursively and then merge them. Comp time of O(nlogn)
Algo:
def merge(left, right, A):
lc, rc = 0, 0
while lc < len(left) and rc < len(right):
if left[lc] <= right[rc]:
A[lc + rc] = left[lc]
lc += 1
else:
A[lc + rc] = right[rc]
rc += 1
if lc == len(left):
A[lc + rc: -1] = right
if rc == len(right):
A[lc + rc: -1] = left
return A
def mergeSort(A):
if len(A) <= 1 : return A
left = mergeSort(A[0:len(A)//2]) right = mergeSort(A[len(A)//2: -1]) return merge(left, right, A)
mergeSort([4,2,5])
CODE SNIPPET:
Can you convert an integer in a list with list(num)?
NO! integer is not an iterable, you need to cast to string before: num = 978 num = str(num) num = list(num) num = [int(i) for i in num]
INSTRUMENT, BINARY: how to convert a number to a binary number?
#we can use format built in function num = 27 num = format(num, 'b') #at this point is a binary string! num = list(num) #now that this is a list we can work on it!
INSTRUMENT, BINARY: how can you do left shift or right shift? what are the results? what do they mean mathematically?
left shift
a = 5
a «_space;1 #from 101 to 1010 –> from 5 to 10
a «_space;2 #from 101 to 10100 –> from 5 to 20
#shifting a number is like multiply it for 2 elevated at number of shifts
a = 5
a»_space; 1 #from 101 to 10 –> from 5 to 2
a»_space; 2 #from 101 to 1 –> from 5 to 1
#shifting numers right is like divide per due elevated at number of shifts (// division)
INSTRUMENT, BINARY: if I have to evaluate every single bit of a number where could I store the result?
In a list of 32 elements, given that a binary number usually does not exceed 32 bits
INSTRUMENT, STRINGS: how can I compare chars values (even numbers) to sort them?
you can use ord(‘a’) or ord(‘9’)
CODE SNIPPET: what is Hamming distance? How do we calculate it?
Hamming distance is the number of different bits for two given numbers. You can just do xor between the two numbers and count the numbers of 1's of the result.
a = 5
b = 6
res = format(a ^ b, 'b')
for i in range(len(res)):
if res[i] == '1':
count += 1CODE SNIPPET: given two numbers how con you find GCD (greatest command divisor)?
You can use Euclidean Algorithm:
’’’
let A,B with A >= B
compute: A mod B = R let A = B, B = R repeat steps till B = 0
return B (before it becomes 0) '''
INSTRUMENT, STRINGS:
I have a list, I want to convert it to a string. How do I do that?
I use join:
a = [‘c’, ‘i’,’a’,’o’]
‘‘.join(a) –> ‘ciao’
PATTERN: I need to find a value, I can find a min value and a max value, so define a search space. What do I use?
BINARY SEARCH:
def bin_src(array, num, left, right):
if left > right:
return -1
mid = left + ((right - left) // 2) #avoid integer overflows (in python is not necessary anyway…)
if array[mid] == num:
return mid
elif array[mid] > num:
return bin_src(array, num, left, mid-1)
else:
return bin_src(array, num, mid+1, right)
bin_src([1,2,5], 5, 0, 2)
CODE SNIPPET: Given 3 values, B, C and N with N > B, C: how can we encode the two values in a single one, then extract them?
We use moltiplication and module:
B = 4 C = 5 N = 7
A = B + (C*N)
print(f’B is {A%N}’)
print(f’C is {A // N}’)
INSTRUMENT, STRINGS: I need a dictio with all alphabet letters with the value set to i = 0. How do I do that with a single line of code?
import string
i = 0 d = dict.fromkeys(string.ascii_lowercase, i) #crea le chiavi (quella funzione genera una stringa che e tutto l alfabeto) e da come value i a tutti
INSTRUMENT: how can i find max and min of a list?
lista = [1,2,3]
min(lista)
max(lista)
PATTERN: 2sum implement it, which pattern do I use?
Use two pointers not sort (from 3sum you sort).
#2sum
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
w = {}
for i in range(len(nums)):
w[nums[i]] = i
for i in range(len(nums)):
B = target - nums[i]
if B in w and w[B] != i:
return [i, w[B]]
Can I modify the index of a for cycle?
Yes, but with bad consequences. Do not do that ! (use a while instead)
CODE SNIPPET: given list find all contiguous subarrays
def solve(A):
res = 0
subs = []
for i in range(len(A)):
subs.append([A[i]])
new_sub = [A[i]]
for j in range(i+1, len(A)):
new_sub.append(A[j])
subs.append(list(new_sub))
return subs
solve([3,4,5])
PATTERN 3SUM: what do I do? Comp time?
I use 2 pointers + sorting list. Comp time of O(n^2)
#3sum (that gives zero)
‘’’
-devi ordinare la lista (tanto il tempo viene mangiato da O(n^2))
-numero per numero e intanto usi il two pointers technique (2 sum with ordered list)
-scorri nel for principale e skippa i numeri uguali per evitare i duplicati
-se trovi una tripla che fa il target, aumenta left e continua ad aumentarlo finche non e un valore diverso
‘’’
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
res = []
for i in range(len(nums)-2):
if i != 0 and nums[i] == nums[i-1]:
continue
l, r = i+1 , len(nums) - 1
tgt = -nums[i]
while l < r:
if nums[l] + nums[r] == tgt:
res.append([nums[i], nums[l], nums[r]])
l += 1
while nums[l] == nums[l-1] and l < r:
l += 1
elif nums[l] + nums[r] > tgt:
r -= 1
else:
l += 1
return res
QUESTION: I need to find all the possible sub arrays with a given property. I find a new value that gives me all other possible combinations with that value: what do I do?
I do not sum +1, I sum (r - l + 1)
INSTRUMENT: I have a binary number, how do I convert it in decimal?
a = '000100' a = int(a, 2)
INSTRUMENT: I want to insert an element in a list at a certain index. What do I do?
lista = [1,2,3,4,5]
lista.insert(‘b’, 2)
#ottengo [1,2,’b’,3,4,5]
INSTRUMENTS, STRINGS:
- check if a string is of all digits
- check if a string is of all characters
- check if a string is only lower characters
- check if a string is only upper characters
- convert strings to upper
- convert strings to lower
string lowercase and uppercase check
#check if a string is composed only by digits (so check if it is a number) '0130'.isdigit() #True '000'.isdigit() #True '-'.isdigit() #False 'A09'.isdigit() #False
#check if a string is composed only by alphabet characters 'A'.isalpha() #True 'a'.isalpha() #True 'As'.isalpha() #True 'A1'.isalpha() #False 'Aaksdjcoasdi'.isalpha() #True 'As#'.isalpha() #False
‘AAA’.islower() #False
‘aaA’.islower() #False
‘aa1’.islower() #True! Numbers are considered ‘neutral’
‘aa#’.islower() #True! any other simbol that is not alpha is neutral
‘AAA’.isupper() #True
‘aaA’.isupper() #False
‘AA1’.isupper() #True
‘AA$’.isupper() #True
‘aSd2’.upper() #ASD2
‘aSd2W#’.lower() #asd2w#
PATTERN, HASHING: I have an O(n^4) brute force approach, but I see I can use hashing. How does complexity lowers at least?
It becomes at least O(n^3). Hashing removes one layer of exponential complexity at least. Then basing on the problem it could reduce it even more: the more layers you can include on the key, the lower time complexity is.
INSTRUMENT: I need a dictio with a precise order, import it
from collections import OrderedDict
w = OrderedDict()
PATTERN: I need to store, retrieve and delete efficiently. What do I use?
HashMap, hashing technique
INSTRUMENT: I want to split a string, how do I do that?
stringa = ‘ciao come stai?’
stringa.split(‘ ‘) #[‘ciao’, ‘come’, ‘stai?’]
INSTRUMENT, STRINGS: ex = “ fwbpudnbrozzifml osdt ulc jsx kxorifrhubk ouhsuhf sswz qfho dqmy sn myq igjgip iwfcqq “
lista = ex.split(‘ ‘)
lista
1) What is the outcome?
2) What If I want a clean spaces result?
list subdivided per spaces, where there are multiple spaces:
‘a a’ #6 spaces
[‘a’, ‘’, ‘’, ‘’, ‘’, ‘‘,a] #5 spaces as empty strings
2) ‘a a’.split()
ALGORITHM, KMP ALGO:
explain (brefly) and implement KMP
def c_LPS(pattern):
lps = [0] * len(pattern)
tp = 0
bt = 1
while bt < len(pattern):
while tp and pattern[bt] != pattern[tp]:
tp = lps[tp-1]
if pattern[bt] == pattern[tp]: tp += 1 lps[bt] = tp bt += 1 else: lps[bt] = 0 bt += 1
return lps
def kmp(txt, pattern): lps = [0] * len(pattern)
j = 0 #pattern ind
i = 0 #txt ind
while i < len(txt):
if txt[i] == pattern[j]:
i, j = i + 1, j + 1
else:
if j == 0:
i += 1
else:
j = lps[j-1]
if j == len(pattern):
print('found')
j = 0
i += 1
kmp('AAAXAAAA', 'AAA')
#domani prova a fare i problemi!
PATTERN: what is the base to obtain all of the contiguous algorithms with a certain property in O(n) ? code and explain it
for conbube intervals (ex:NUMRANGE) use always ‘less (or equal than)’!
#contiguous subarray with a given property in O(n) time: ''' what you have to do is using sliding window, but NOT uograde ans +=1 instead uograde every time of r-l+1 in order to include all the subwindows ''' def count_min_K(A, K): l = 0 ans = 0 temp_sum = 0
for r in range(len(A)):
temp_sum += A[r]
if temp_sum < K:
ans += r - l + 1
else:
while l < r and temp_sum >= K:
temp_sum -= A[l]
l += 1
if temp_sum < K:
ans += r - l + 1
return ans
count_min_K([1, 11, 2, 3, 15], 10)
DATA STRUCTURE: explain what is:
- a binary tree
- a complete tree
- maxheap and minheap property
- A tree where each node has at most two childrens
- All the levels are totally filled, except for the lowest ones
- max heap: root must be greater than all of the elements of the tree. This applies recursively
PATTERNS: When do I want to use trees (ex: heaps) instead of hashmaps (dictios)?
dictios are not efficient for the following tasks:
- Find min/max in logarithmic time
- Iterate through all the elements with a sorted order in linear time
- FInd an element close to x in logarthmic time
INSTRUMENTS/DATA STRUCTURE: briefly code all the operations you can perform with heaps
import heapq
H = [1,3,2,5,7,9]
heapq.heapify(H) #transofrm H in an heap structure takes O(N) time!
heapq. heappush(H, 8) #put the element in the heap maintaining the heap properties
heapq. heappop() #pop the smallest element
heap. nlargest(2, H) #pop the largest ones
heapq. nsmallest(2, H) #pop the smallest ones
heapq.heapreplace(H, 6) #replace the smallest element with the given one maintaining heap structure
CODE SNIPPET: implement heapsort (having heapq library):
import heapq
H = [2,5,1,4,7,3]
heapq.heapify(H) #NOT re declare it!
res = []
for i in range(len(H):
res.append(heapq.heappop())
PATTERNS: find k smallest/largest elements. What do I use?
Use a heap.
CODE SNIPPET: I need to define a maxheap but python provides just minheap. What do I do?
Just insert in the heap the values negated.
TECHNIQUE: I have a list of duplicates but one. How do I find it ?
Xor btween two duplicates values gives 0, perform xor of all the lists, the remaining value is the non duplciated value
PATTERN: given a list obtain all of the contiguous subarray
def solve(A):
res = 0
subs = []
for i in range(len(A)):
subs.append([A[i]])
new_sub = [A[i]]
for j in range(i+1, len(A)):
new_sub.append(A[j])
subs.append(list(new_sub))
return subs
solve([3,4,5])
‘’’
Any number appears in the subarrays with a frequency of (i + 1) * (N - i)
Ricordati che su questi problemi di solito ce sempre una qualche proprieta che ti permette di non dover
creare tutti i subarray/sottostringhe!
‘’’
HOW DO YOU REVERSE A LINKED LIST?
#remember to add the edge case of list of only one element, it is necessary! #YPU HAVE TO KNOW how to reverse a linked list #write clean code:is fundamental with pointers: create different methods, use different while (non devi percorrere tutta la lista in un while unico, un while per operazione!)
def reverse(A): prev = None act = A
while act:
temp = act.next
act.next = prev
prev = act
act = temp
return prev
HOW DO YOU DETECT A CYCLE IN A LINKED LIST?
LINKED LISTS–>cycle
def detect(head): if not head: return False
hare = head
tortoise = head
while hare and hare.next:
hare = hare.next.next
tortoise = tortoise.next
if hare == tortoise:
return True
return False
HOW DO YOU DETECT WHERE A CYCLE HAS BEGAN IN A LINKED LIST?
detect cycle then starting from the beginning move of q to 1 for both pointers
def detectII(head): if not head: return False
hare = head
tortoise = head
meeting = None
while hare and hare.next:
hare = hare.next.next
tortoise = tortoise.next
if hare == tortoise:
meeting = hare
break
if not meeting: return None
start = head
while start != meeting:
start = start.next
meeting = meeting.next
return meeting
INSTRUMENT: I use an innested method. What is seen? what not?
‘complex’ objects (list, dictio, tuple, ecc..) are seen normal variables no. Use nonlocal for them
DATASTRUCTURE, TUPLE: what are his characteristics?
tupla = (‘banana’, ‘cherry’, ‘apple)
Unordered, unchangeable
I need to count for each element in iterable how many copies it has . What do I do?
from collections import Counter
lista = [1,2,2,1,3]
aq = Counter(lista)
{1:2, 2:2, 3:1}
frozenset. Explain.
frozenset(‘aaa’)
#obtain {‘a’}
It takes an iterable object and makes it immutable
Posso fare heapify di una lista di liste (matrice)?
Si ma ogni singolo elemento sara una lista, non un numero. Dipende da cosa ti serve!
5 // 2 = 2., . -5 // 2?
-5 // 2 = -2.5. Rounding is made to be as near as possible to minus infinite, be careful.
When do I want to store indices in a heap?
When we need to be sure we are nt using no duplicates combination (ex: sums, ecc…)
I need that built in specific functions compare objects as I want. How?
I redefine ‘’ operation in the class:
class Pair():
def __init__():
….
….
def \_\_lt\_\_(self, other): def \_\_gt\_\_(self, other):
DATA STRUCTURE, BINARY SEARCH TREE:
- In order traversal
- Pre order traversal
- Post order traversal
https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/
in order: (left, root, right)
pre order: (root, left, right)
post order: (left, right, root)
(Quello che varia e quando visiti la root)
(left e sempre prima di right)
What is a binary search tree?
right only bigger values, left only smaller values
I have a pre-order traversal (array) I need to check if it is valid for a binary search tree. What is the idea? What data structure do I use then?
for A[i] search on the next elements the greater value. After that value no values less than A[I] are allowed. This requires O(n^2) but we can use a stack for O(n) time. (I define a root and empty the stack when I switch tree side)
BINARY SEARCH TREE, I HAVE TO VISIT IT, OR FIND SOME PROPERTIES. What do I use?
Stacks are perfect for in order traversal in O(n) and find any useful properties
Implement DFS and BFS:
#dfs:
def dfs(node):
if node:
dfs(node.left)
print(node.val)
dfs(node.right)
#bfs
def bfs(root):
stack = []
stack.append(root)
while stack:
node = stack.pop(0)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
print(node.val)
I have to recover a BST (2 node value swapped). What do I do? ( You can use space)
Just put all the nodes in a list, take the values and sort them reassign values to the nodes that already in the list. Nodes in the list must be put in a in-order fashion (dfs)
I want to perform in order traversal and but use O(1) space to perform some operation instead of save nodes on a list. What do I do?
Morris traversal (you have to learn it)
TREE: I need for a given node (or all the nodes) to know which his parent is. What Do I do?
I use BFS, and when I check at node.left and node.right for these nodes I save them as key and the value is their father in an hashmap.
I have a tree, but I need to use parents: what do I do
I consider the tree as an undirected graph, so I use a visited hashmap and a parent hasmap
TREE, RECURSION, SUM OF EACH PATH. What is the idea?
This is a recursion where you carry a value between recursion and you let it grow between each recursion (*10). Also, you return it if the node is a leaf or you return the sum of the subtrees.
CAREFUL: This recursion is particular, you need to handle different cases properly
See the example here:
https://leetcode.com/problems/sum-root-to-leaf-numbers/
N.B: Metti un return per la costruzione del risultato dentro un if, poi costruisci left solution e right solution e infine metti il return del risultato che vuoi, cosi facendo ti porti dietro nelle ricorsioni un valore ma una volta finito metti il risultato ottenuto da queste
def prova(A):
lists = []
def innest(path):
if len(path) == 10:
return
path.append(1)
print(path)
innest(path)
innest(path) #CONSIDER THIS: will it be [1] or a list of ten 1's?
innest([])
prova(1)
Even if passed as parameter, non simple variables have a global scope: it will be a list of ten 1’s.
Tree, I want all paths with dfs, store them in a list of lists.
Paths
path[]
Do I need backtracking for path? where?
Yes I need it (del path[-1]). I use it like (this is basic then depends by the problem)
dfs(left)
dfs(right)
del path[-1]
Is Trie (prefix tree) binary?
NO it would have no sense!
Wht do you have in the root of a Trie?
Nothing, leave it free! (Think about it, it would have nos ense otherwise!)
I need to implement Trie. What Do I need of course?
- implement class TreeNode before (NO binary!!) –> he does not need .val attribute, we can directly look at chulds given that root does not contains anything!
- Tree node needs a last character boolean otherwise how can we say that we have word app inside word apple?
given array of numbers find2 values s.t. Xor is maximized: what I use?
TRIE, adjusting numbers length (in bit)
Use enumerate for B = [1,2,3]
for i, num in enumerate(B):
print(i)
print(num)
What is zip() function and how do you use it?
A = [….]
B = [….]
#zip(A,B) create an object: now using sorted we can sort B (the second) basing on the first A
res = [i for _, i in sorted(zip(A,B))]
When a binary search tree is balanced?
When for each node, the height of left tree and height of right tree does not differ of more than one
TREE, I have to delete nodes with a certain property. How do I do it?
You set a dfs recursion, the idea is to call recursion with the idea: call recursion on left and right s.t left subtree and right subtree are set.
Then you delete nodes that does not respect the property
ex: https://www.geeksforgeeks.org/given-a-binary-tree-how-do-you-remove-all-the-half-nodes/
TREE RECURSION, balanced binary tree (o comunque un problema che ti faccia ritrovare in questa situazione): Ho bisogno di piu elementi attraverso la ricorsione, cosa faccio?
FAI TORNARE DENTRO LE RICORSIONI UNA LISTA DI VALORI! cosi hai tutto cio che serve
ex: https://www.youtube.com/watch?v=QfJsau0ItOY
svolgi questo problem
GRAPH / UNDIRECTED TREE: I need to define a structure that says me for each node con quali nodi e’ collegato. Come faccio?
Uso una lista di liste: la lista i contiene i nodi collegati all i-esimo nodo.
BALANCE /ROTATE/ CHANGE STRUCTURE OF A BINARY TREE. WHAT DO I DO?
YOOOO BRO ANSWER IS IN-ORDER TRAVERSAL BRUH:
- do in order traversal and save value sin array
- rebuild the tree as you want: es: balanced: use middle index for root, tjen npde left look in (left, mid-1) and right node in (mid + 1, right)
Invert a binary tree
use bfs and swap for each node you pop his left and right (this way you swap all of the subtrees!)
TREE: you have to build a tree from some order.Once you define a part of the tree that is stable or it can change?
IT CAN CHANGE! Consider while you reason that maybe you can change the tree structure! (Doable changes)
RICERCA INVERSA (albero): Devi osservare i valori dei parent, non sempre ti serve costruire il dizionario: ex: devi trovare se un nodo ha un parent con un valore piu alto (il primo che trovi va bene). Puoi partire dalla root e da li scendere finche il valore e piu alto del valore del nodo poi ti fermi! ex: https://www.interviewbit.com/problems/inorder-traversal-of-cartesian-tree/hints/
INSTRUMENT: Given a list, I need the index where there is value x. What do I do>
Use python built in index function:
lista = [1,2,4,23,0]
lista.index(4) –> 2
2 TREES to merge or confront: DFS OR BFS?
DFS
I have to do a particular (ex vertical) tree traversal. What do I do?
Create coordinates for the tree (height, width)!
ex: https://leetcode.com/problems/binary-tree-vertical-order-traversal/submissions/
some traversal between in pre or post, but I cant use recursion. What do I do?
Use a BFS approach, just modify how you pop and insert values, also you could need to use two stacks!
How you validate BST?
use boundaries that changes through iterations
conta di inversioni o cose che sono ‘parted i un processo di ordinamento’
Usa un merge sort scrtitto a mano e personalizzato apposta
compute mid without overflows
m = l+(r-l)//2
argmax function does not exist in python. How can I create it?
f = lambda x: lista[x]
max(range(len(l), key: f)
Common substring/palindromic bit is a sequence, NOT CONSECUTIVE CHARACTERS. What do I do?
use 2d DP
devo risolvere un problema con 2d DP. Quale domande mi pongo?
- cosa contiene una cella? Di conseguenz come ha senso costruire quel valore?
KNAPSACK 0/1
2D DP –> scegli se mettere l elemento quindi somi il suo valore all ottimale sullo spazio rimasto o non lo metti, quindi ottimale stessa capacita ma senza considerare quell elemento
KNAPSACK DP: ricordati che per una specifica capacita C il knapsack trovera sempre il modo ottimale (peso minore possibile ) per ottenerlo! ragionaci
Inoltre piuttosto che il val max puoi invece trovare il weight che usi (che sara il minimo ottimale) basta che ‘ribalti’ il problema!
UNBOUNDED KNAPSACK: come lo fai?
Basta 1 array 1d: dp[i] lo trovi iterando su ogni valore disponibili: se e gestibile sommmi il uso valore a quello ottimale trovato con il peso rimanente altrimentilo lasci cosi
WORD BREAK: what do I do?
1d dp, start from the end from every character see if there is a match if there is dp[i] e il valore di dp[i + len(word)
DYNAMIC PROGRAMMING:
- 1d or 2d array
- each cell: optimal solution or best solution that finishes in that cell
- you could define two 1d array and work on them
- usually you take min or max and sum something (depends by the problem) or true or false!
- knapsack idea: you don’t take e i-1 or j-1 but in the past row you look ‘somewhere else’
- a volte su una linea del 2d metti l array e nell altro metti una somma crescente o altro non per forza l array ancora!
- knapsack unbounded bottom up: you iterate the dp 1d array multiple times building all the solutions together step by step
cumulative sum: how do you use that?
you can use that in arrays (1d or 2d) in order to find subarrays with a given property (es sum to a target)
GRAPHS, things to do:
use (default) dictio for adj list / set for totally visited nodes
grafo/matrici usa visited set e dfs, chiama tutto le condizioni degli indici le guardi prima
In order to find the diameter of a tree I can take any node from the tree, perform BFS to find a node which is farthest away from it and then perform BFS on that node. The greatest distance from the second BFS will yield the diameter.
saper fare dfs e bfs su matrici e liste (from lista costruisciti una adj list!)
