Patterns

Question 1

INSTRUMENT:

How to check if the type of an object is a list?

Answer 1

lista = [1,2,3]
if type(lista) is list:
      return list

Question 2

INSTRUMENT:

How to create a personalizable function for comparing?

Answer 2

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

Question 3

INSTRUMENT:

What do I do if I want to know where an element in a sorted list should be placed?

Answer 3

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)

Question 4

ALGORITHM: briefly describe merge sort and implement it

Answer 4

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

Question 5

CODE SNIPPET:

Can you convert an integer in a list with list(num)?

Answer 5

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]

Question 6

INSTRUMENT, BINARY: how to convert a number to a binary number?

Answer 6

#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!

Question 7

INSTRUMENT, BINARY: how can you do left shift or right shift? what are the results? what do they mean mathematically?

Answer 7

left shift

a = 5
a &laquo_space;1 #from 101 to 1010 –> from 5 to 10
a &laquo_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&raquo_space; 1 #from 101 to 10 –> from 5 to 2
a&raquo_space; 2 #from 101 to 1 –> from 5 to 1
#shifting numers right is like divide per due elevated at number of shifts (// division)

Question 8

INSTRUMENT, BINARY: if I have to evaluate every single bit of a number where could I store the result?

Answer 8

In a list of 32 elements, given that a binary number usually does not exceed 32 bits

Question 9

INSTRUMENT, STRINGS: how can I compare chars values (even numbers) to sort them?

Answer 9

you can use ord(‘a’) or ord(‘9’)

Question 10

CODE SNIPPET: what is Hamming distance? How do we calculate it?

Answer 10

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 += 1

Question 11

CODE SNIPPET: given two numbers how con you find GCD (greatest command divisor)?

Answer 11

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

Question 12

INSTRUMENT, STRINGS:

I have a list, I want to convert it to a string. How do I do that?

Answer 12

I use join:
a = [‘c’, ‘i’,’a’,’o’]
‘‘.join(a) –> ‘ciao’

Question 13

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?

Answer 13

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)

Question 14

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?

Answer 14

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}’)

Question 15

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?

Answer 15

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

Question 16

INSTRUMENT: how can i find max and min of a list?

Answer 16

lista = [1,2,3]
min(lista)
max(lista)

Question 17

PATTERN: 2sum implement it, which pattern do I use?

Answer 17

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

Question 18

Can I modify the index of a for cycle?

Answer 18

Yes, but with bad consequences. Do not do that ! (use a while instead)

Question 19

CODE SNIPPET: given list find all contiguous subarrays

Answer 19

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

Question 20

PATTERN 3SUM: what do I do? Comp time?

Answer 20

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 21

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?

Answer 21

I do not sum +1, I sum (r - l + 1)

Question 22

INSTRUMENT: I have a binary number, how do I convert it in decimal?

Answer 22

a = '000100'
a = int(a, 2)

Question 23

INSTRUMENT: I want to insert an element in a list at a certain index. What do I do?

Answer 23

lista = [1,2,3,4,5]
lista.insert(‘b’, 2)
#ottengo [1,2,’b’,3,4,5]

Question 24

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

Answer 24

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#

Question 25

PATTERN, HASHING: I have an O(n^4) brute force approach, but I see I can use hashing. How does complexity lowers at least?

Answer 25

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.

Question 26

INSTRUMENT: I need a dictio with a precise order, import it

Answer 26

from collections import OrderedDict w = OrderedDict()

Question 27

PATTERN: I need to store, retrieve and delete efficiently. What do I use?

Answer 27

HashMap, hashing technique

Question 28

INSTRUMENT: I want to split a string, how do I do that?

Answer 28

stringa = 'ciao come stai?' | stringa.split(' ') #['ciao', 'come', 'stai?']

Question 29

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?

Answer 29

list subdivided per spaces, where there are multiple spaces: 'a a' #6 spaces ['a', '', '', '', '', '',a] #5 spaces as empty strings 2) 'a a'.split()

Question 30

ALGORITHM, KMP ALGO: | explain (brefly) and implement KMP

Answer 30

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

Question 31

PATTERN: what is the base to obtain all of the contiguous algorithms with a certain property in O(n) ? code and explain it

Answer 31

``` #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) #for conbube intervals (ex:NUMRANGE) use always 'less (or equal than)'!

Question 32

DATA STRUCTURE: explain what is: - a binary tree - a complete tree - maxheap and minheap property

Answer 32

- 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

Question 33

PATTERNS: When do I want to use trees (ex: heaps) instead of hashmaps (dictios)?

Answer 33

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

Question 34

INSTRUMENTS/DATA STRUCTURE: briefly code all the operations you can perform with heaps

Answer 34

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

Question 35

CODE SNIPPET: implement heapsort (having heapq library):

Answer 35

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

Question 36

PATTERNS: find k smallest/largest elements. What do I use?

Answer 36

Use a heap.

Question 37

CODE SNIPPET: I need to define a maxheap but python provides just minheap. What do I do?

Answer 37

Just insert in the heap the values negated.

Question 38

TECHNIQUE: I have a list of duplicates but one. How do I find it ?

Answer 38

Xor btween two duplicates values gives 0, perform xor of all the lists, the remaining value is the non duplciated value

Question 39

PATTERN: given a list obtain all of the contiguous subarray

Answer 39

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

Question 40

HOW DO YOU REVERSE A LINKED LIST?

Answer 40

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

Question 41

HOW DO YOU DETECT A CYCLE IN A LINKED LIST?

Answer 41

#LINKED LISTS-->cycle #detect cycle hare and tortoise ``` 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

Question 42

HOW DO YOU DETECT WHERE A CYCLE HAS BEGAN IN A LINKED LIST?

Answer 42

#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

Question 43

INSTRUMENT: I use an innested method. What is seen? what not?

Answer 43

'complex' objects (list, dictio, tuple, ecc..) are seen normal variables no. Use nonlocal for them

Question 44

DATASTRUCTURE, TUPLE: what are his characteristics?

Answer 44

tupla = ('banana', 'cherry', 'apple) | Unordered, unchangeable

Question 45

I need to count for each element in iterable how many copies it has . What do I do?

Answer 45

from collections import Counter lista = [1,2,2,1,3] aq = Counter(lista) {1:2, 2:2, 3:1}

Question 46

frozenset. Explain.

Answer 46

frozenset('aaa') #obtain {'a'} It takes an iterable object and makes it immutable

Question 47

Posso fare heapify di una lista di liste (matrice)?

Answer 47

Si ma ogni singolo elemento sara una lista, non un numero. Dipende da cosa ti serve!

Question 48

5 // 2 = 2., . -5 // 2?

Answer 48

-5 // 2 = -2.5. Rounding is made to be as near as possible to minus infinite, be careful.

Question 49

When do I want to store indices in a heap?

Answer 49

When we need to be sure we are nt using no duplicates combination (ex: sums, ecc...)

Question 50

I need that built in specific functions compare objects as I want. How?

Answer 50

I redefine '' operation in the class: class Pair(): def __init__(): .... .... def __lt__(self, other): def __gt__(self, other):

Question 51

DATA STRUCTURE, BINARY SEARCH TREE: - In order traversal - Pre order traversal - Post order traversal

Answer 51

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)

Question 52

What is a binary search tree?

Answer 52

right only bigger values, left only smaller values

Question 53

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?

Answer 53

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)

Question 54

BINARY SEARCH TREE, I HAVE TO VISIT IT, OR FIND SOME PROPERTIES. What do I use?

Answer 54

Stacks are perfect for in order traversal in O(n) and find any useful properties

Question 55

Implement DFS and BFS:

Answer 55

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

Question 56

I have to recover a BST (2 node value swapped). What do I do? ( You can use space)

Answer 56

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)

Question 57

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?

Answer 57

Morris traversal (you have to learn it)

Question 58

TREE: I need for a given node (or all the nodes) to know which his parent is. What Do I do?

Answer 58

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.

Question 59

I have a tree, but I need to use parents: what do I do

Answer 59

I consider the tree as an undirected graph, so I use a visited hashmap and a parent hasmap

Question 60

TREE, RECURSION, SUM OF EACH PATH. What is the idea?

Answer 60

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

Question 61

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

Answer 61

Even if passed as parameter, non simple variables have a global scope: it will be a list of ten 1's.

Question 62

Tree, I want all paths with dfs, store them in a list of lists. Paths path[] Do I need backtracking for path? where?

Answer 62

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]

Question 63

Is Trie (prefix tree) binary?

Answer 63

NO it would have no sense!

Question 64

Wht do you have in the root of a Trie?

Answer 64

Nothing, leave it free! (Think about it, it would have nos ense otherwise!)

Question 65

I need to implement Trie. What Do I need of course?

Answer 65

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

Question 66

given array of numbers find2 values s.t. Xor is maximized: what I use?

Answer 66

TRIE, adjusting numbers length (in bit)

Question 67

Use enumerate for B = [1,2,3]

Answer 67

for i, num in enumerate(B): print(i) print(num)

Question 68

What is zip() function and how do you use it?

Answer 68

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

Question 69

When a binary search tree is balanced?

Answer 69

When for each node, the height of left tree and height of right tree does not differ of more than one

Question 70

TREE, I have to delete nodes with a certain property. How do I do it?

Answer 70

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/

Question 71

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?

Answer 71

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

Question 72

GRAPH / UNDIRECTED TREE: I need to define a structure that says me for each node con quali nodi e' collegato. Come faccio?

Answer 72

Uso una lista di liste: la lista i contiene i nodi collegati all i-esimo nodo.

Question 73

BALANCE /ROTATE/ CHANGE STRUCTURE OF A BINARY TREE. WHAT DO I DO?

Answer 73

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)

Question 74

Invert a binary tree

Answer 74

use bfs and swap for each node you pop his left and right (this way you swap all of the subtrees!)

Question 75

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?

Answer 75

IT CAN CHANGE! Consider while you reason that maybe you can change the tree structure! (Doable changes)

Question 76

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

Question 77

INSTRUMENT: Given a list, I need the index where there is value x. What do I do>

Answer 77

Use python built in index function: lista = [1,2,4,23,0] lista.index(4) --> 2

Question 78

2 TREES to merge or confront: DFS OR BFS?

Answer 78

DFS

Question 79

I have to do a particular (ex vertical) tree traversal. What do I do?

Answer 79

Create coordinates for the tree (height, width)! | ex: https://leetcode.com/problems/binary-tree-vertical-order-traversal/submissions/

Question 80

some traversal between in pre or post, but I cant use recursion. What do I do?

Answer 80

Use a BFS approach, just modify how you pop and insert values, also you could need to use two stacks!

Question 81

How you validate BST?

Answer 81

use boundaries that changes through iterations

Question 82

conta di inversioni o cose che sono 'parted i un processo di ordinamento'

Answer 82

Usa un merge sort scrtitto a mano e personalizzato apposta

Question 83

compute mid without overflows

Answer 83

m = l+(r-l)//2

Question 84

argmax function does not exist in python. How can I create it?

Answer 84

f = lambda x: lista[x] | max(range(len(l), key: f)

Question 85

Common substring/palindromic bit is a sequence, NOT CONSECUTIVE CHARACTERS. What do I do?

Answer 85

use 2d DP

Question 86

devo risolvere un problema con 2d DP. Quale domande mi pongo?

Answer 86

- cosa contiene una cella? Di conseguenz come ha senso costruire quel valore?

Question 87

KNAPSACK 0/1

Answer 87

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

Question 88

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!

Question 89

UNBOUNDED KNAPSACK: come lo fai?

Answer 89

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

Question 90

WORD BREAK: what do I do?

Answer 90

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)

Question 91

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

Question 92

cumulative sum: how do you use that?

Answer 92

you can use that in arrays (1d or 2d) in order to find subarrays with a given property (es sum to a target)

Question 93

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