Esercizi orale

Question 1

Sliding Windows Maxima: Given an array containing n elements and a value that represents the window capacity, find 𝐴 𝑘
the maximum element for each contiguous window.

Answer 1

Trivial solution:
Better solution 1: using Heap
Better solution 2: using BBST
Optimal solution
Proving Correctness

Question 2

Problem: through the desert: The goal of this problem is to determine the minimum amount of fuel needed at the start of the journey in order to reach the end of a street of length units.

Answer 2

O(k log n), k numero stazioni

Question 3

Inversion count: Count the number of elements to sort, A[I] > A[j] and I < J

Answer 3

Per riportarle, insertion sort (#inversioni + n)
Per contarle merge sort (n log n)

Question 4

Limite teorico del sorting basato su confronti

Answer 4

O(n log n)

Question 5

Linear time sorting

Answer 5

Counting sort O(n + m)

Question 6

Linear time sorting per integers

Answer 6

Radix sort O(n + k) dove k è ordine di grandezza per valore max in quell’ordine

Question 7

Max Segment Intersection: Dati k segmenti ed un array di dimensione n, lo scopo è trovare il punto con massimo numero di intersezioni tra i segmenti.

Answer 7

O(n log n) creando struttura dati dove inseriamo segmenti.

Question 8

Fibonacci Numbers
Calculating the n-th term of the Fibonacci series is the “hello world!” of dynamic programming.
Recall that, the series can be calculated in this way:

Answer 8

Soluzione base
Bottom up
Top down

Question 9

Problem: Rod cutting
Given a rod of length n cm and an array of prices P that includes prices of all pieces of size smaller than n. Determine the maximum value obtainable by cutting up the rod and selling the pieces.

Answer 9

Equazione di ricorrenza k varia, R(n) = max( R(k) + P n - k)
DAG

Question 10

Facebook Robber
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police 👮.

Answer 10

Using Dag
Equazione di ricorrenza f(i) = max(f(i - 1) + val, f(i -2))

Question 11

Snake e ladders

Question 12

Minimum cost path Given a matrix M (n m) with integers, the goal is to compute the path with the minimum cost which goes from the top-left corner to the bottom-right corner by moving only down or right. The target time complexity must be (n*m).

Answer 12

Creo Matrice M1 che contiene in ogni casella dimensione min path.
eq ricorrenza W[i][j] = M[i][j] + min ( W[i - 1] [j], W[i][j - 1])

Question 13

Problem: IWGBS - 0110SS 🟢
Giggi has to count in how many ways he can make N digit numbers that are formed by ones and zeroes. But zeroes can not be next to each other. Help him in how many different numbers he can make.

Question 14

Problem: Longest Common Subsequence (LCS) 🟢
Given two strings S1, S2 where len(S1) = n and len(S2) = m find the longest common subsequence. The target time complexity is (n*m).

Answer 14

Matrice che contiene chars increasing.

Question 15

Problem: 0/1 knapsack problem 🟢
We have n items and a knapsack with a capacity C. Each item i has a value vi and a weight wi.
The goal is to select a subset of items, with a total weight that is at most C maximizing the overall value. Note that each item can be taken only once, this is the reason why this problem is denoted as “0/1”. The target time complexity (nC).

Answer 15

Equazione di ricorrenza: M[i][j] = max( M[i-1][j]. M[i-1][j - wi])

Question 16

Problem: subset sum problem 🟢
We have a set S of n integers and a target (integer) v. We want to know if there is a subset of S whose sum is equal to v; each element can be picked once.

Answer 16

Equazione di ricorrenza M[i][j] = M[i-1][j] or M[i-1][j - S[i]]

Question 17

Problem: coin change
There are n types of coins 🪙, of which we have an unlimited number. The values of these n coins are stored in an array C=[c1, … ,cn].
Given an amount of money k, we want to count how many ways we have to reach that amount of money k using the different coins.

Answer 17

Equazione di ricorrenza:
M[i][j] = M[i - 1] [j] + M[i][j - Ci]

Question 18

Problem: Largest independent set on trees 🟢
Given a tree T with n nodes, find one of its largest independent sets.
A set of nodes is defined as “independent”, if for each node in the set there is no edge connecting it to the other nodes in the set.

Answer 18

equazione di ricorrenza LIS(u) = max( 1 + Lis(u.grandchildren), List(u.children))

Question 19

Problem: Longest Increasing Subsequence (LIS)
Given an array of n integers, S, we want to find the length of its longest increasing subarray. We could have more than one subarray with the same length.

Answer 19

DAG
Nˆ2 LIS[i] = 1+ max k<i ( LIS[k] tale che S[k] < S[i])
n log n creiamo BBST dove inseriamo elemento, da quello aggiungiamo 1 cercando predecessore, poi se successore ha LIS minore possiamo eliminare successore.

Question 20

Problem: puzzle
In this problem we have n pairs of coins:

Select k coins to maximize the total value, but you can select the second coin of the pair Ci,2 only if the first one Ci,1 is already select.

Question 21

Problem: Maximum path sum 🟢
Given a binary tree T with n nodes where every node contains a weight w (just a value stored into the node), find the maximum sum of a path from one leaf to another leaf. In other words, for every possible pair of leaf nodes we want to report the maximum sum of the path between those nodes into the pair, so given two leaves we want to consider every possible path among them and report the maximum sum.

Answer 21

Per capire best path partiamo dal concetto del lowest common ancestor, per calcolarlo ritorno due valori, best so far e best to a leaf. Effettuo chiamata ricorsiva a sinistra e destra e verifico qual’é il best to a left, e se é maggiore quello oppure il path destra sinistra

Question 22

Problem: Frogs and mosquitoes (Dynamic 1D Point Location) 🟢
In this problem we have n frogs 🐸lying on the axis x. Each frog has a value t which is the length of its tongue 👅. Then, there are m mosquitos 🦟; each mosquitos j lands at the position bj and has a value aj.
A frog i is able to eat a mosquitos j if bj is in the range [xi , xi+ti].

Answer 22

Ordino rane, applico sweep line e le addo a bbst, quando addo verifico se ci sono overlaps. O(n log n)
Verifico mosche che possono essere mangiate, quando mangio mosca effettuo increasing e verifico se posso mangiare uneaten O((n + m) log n)
Creo array delle mosche non mangiate
O(m log m)

Question 23

Problem: Longest K-good segments (w/ Two Pointers) 🟢
Given A[1,n] of integers and a value k, a subarray is defined as “k-good” if it contains no more than k different integers. In this problem we want to find the longest k-good subarray.

Answer 23

Two pointers

Question 24

Problem #1: Ilya and Queries
You’ve got string s=s1, s2 , … , sn (n is the length of the string), consisting only of characters “a” and “b” and q queries. Each query is described by a pair of integers (i,j, 1 ≤ i ≤ j ≤ n ).
The answer to the query(i,j) is the number of such integers k[i,j] such that Sk=Sk+1.

Answer 24

Prefix sum, 1 se Sk=Sk+1
R(i,j) = Prefix(j) - Prefix(i - 1)

Question 25

Problem #2 : Little girl and maximum
Given an array A[1,n] and a set Q of queries where each query is a RangeSum(i,j).
The goal is to permute values on the array in order to maximize the sum of the results of queries in Q.

Answer 25

Trivial solution leggo queries e creo nuovo array per riordinare array in base a quest’ultimo q * n
Faster sol
Sweep line ordino queries in base ad endpoints, una volta faccio ció tengo conto del numero di occorrenze q log q + n per scorrere
Prefix sum
q + n

Question 26

Problem #3 : Number of ways 🟢
Given an array A[1,n] count the number of ways we can split A in three parts such that the sum of the parts is the same. The solution must run in a linear time.

Answer 26

Mediante prefix sum da destra verifico se raggiungo S/3, in quel caso inserisco 1 nell’array
Poi da sinistra con prefix sum array,

Question 27

(Dynamic) Prefix sums problem
It is an example of a problem that needs segment trees to be solved.

Given an array A[0, n-1] we want to support two operations:
sum(i) := j=0iA[j]
add(i,v) := A[i]+=v

Answer 27

log n

Question 28

Problem: (Dynamic) Range Minimum Query (RMQ) / Anche con occorrenze

Given an array A[0, n-1] we want to support two operations:
add(i,v) := A[i]+=v
RMQ(i,j) := argmin(range(i,j)),
returns the position of the minimum element in A[i .. j]

Question 29

Problem: “shortest prefix ≥ s” 🟢
Given an array A[0, n-1] of non-negative values we want to support these operations:
Add(i,v), as usual
RangeSum(i,j), as usual
Search(s) searches for the shortest prefix of A, say A[0…i] such that
(k=0iA[k] ) ≥ s
it returns the index.

Question 30

Problema numero di occorrenze di x in range

Answer 30

Salviamo hash contenente range, funziona poiché ogni elemento sará salvato in log n posizioni, ossia il path per arrivare

Question 31

Problem: Successor queries in any subarray 🟢
Given an array of integers A[0,n-1] we want to support these operations on a Segment Tree:
Add(i,v) : A[i] += v
Succ(i,j,x) : returns the successor of x in A[i … j]

Answer 31

Salviamo bbst in ogni nodo log n quadro
Spazio n log n
Ottimizzazione con Fractional cascading dove colleghiamo ciascun elemento con successore del nodo figlio

Question 32

Problem: Update the Range
Given an array A[0, n-1] we want to add these operations:
RangeUpdate(i,j,v) := A[k]+=v , k[i,j],
in other words, for each item within the range [i,j] we want to add v.

Access(i) just return the current value for A[i].

Answer 32

Salviamo struttura dati dove nodi contengono valore che si somma.
Con access in log n otteniamo elementi
Possiamo anche utilizzare array F con prefix sums
Lazy propagation dove invece abbiamo operazione di sum, in questo caso doppio segment tree, uno per update e altro per sums.

Question 33

Persistent segment tree
In general, a persistent data structure is one that deals with different versions of the same structure in memory. For example, this means that it considers different versions of the same data structure at different times, keeping track of the updates during time. Operations that modify the data structure increment the timestamp by 1, while operations that query the data structure can specify the timestamp being referred to.

This idea can be applied to every data structure, we will talk with respect to segment trees.

For our discussion, let’s take a segment tree which need to support two operations:
Sum(i,j,t) which returns k=ijA[k] at timestamp t.
Add(i, v) which adds v to A[i] (the timestamp must be incremented)

Answer 33

Possiamo salvare in array k segment trees ad ogni tempo. k n
Better implementation per ogni nodo abbiamo valori in tempo k
complessita n + k log n
ma sum pesante k log n
Ultima implementazione con metodo di accesso alle root n + k log n

Question 33

Persistent segment tree
In general, a persistent data structure is one that deals with different versions of the same structure in memory. For example, this means that it considers different versions of the same data structure at different times, keeping track of the updates during time. Operations that modify the data structure increment the timestamp by 1, while operations that query the data structure can specify the timestamp being referred to.

This idea can be applied to every data structure, we will talk with respect to segment trees.

For our discussion, let’s take a segment tree which need to support two operations:
Sum(i,j,t) which returns k=ijA[k] at timestamp t.
Add(i, v) which adds v to A[i] (the timestamp must be incremented)

Answer 33

Possiamo salvare in array k segment trees ad ogni tempo. k n
Better implementation per ogni nodo abbiamo valori in tempo k
complessita n + k log n
ma sum pesante log k log n
Ultima implementazione con metodo di accesso alle root n + k log n

Question 34

Problem: Triplets 🟡
Given an array A[0,n-1] with positive integers, count the number of triplets (i,j,k), where 0 i<j<kn-1, such that A[i]<A[j]<A[k].

Answer 34

Calcoliamo tutto brute force,
Fixed i + costruzione di array contenente valori maggiori in log n
Usare due array ed incontrarsi a metá strada log n

Question 35

Problem: K-th Smallest Value in Any Subarray [Smallest(i,j,k)]
Given the static array A[0, n-1] we would like to support the operation smallest(i, j, k) which returns the k-th smallest element in A[i … j], with a target time complexity is (log n).

Answer 35

Naive 1 Quick select trova in nˆ2 lo smallest in unordered
Naive 2 per ciascun value di k salvo lo smallest O(nˆ3) space
Con bbst usato simil persistent segment tree, possiamo rimuovere range maggiore da quello minore

Question 36

Static RMQ and Mo’s algorithm
(Static) Range Minimum Query 🟢
Range Minimum Query (RMQ), is a problem where you are given an array of integers and a range, and you want to find the minimum value in that range.

So, given an array of positive integers A[0, n-1] we want to provide this query:
RMQ(i,j) = ( A[i … j] )
If we assume that we can’t change the array, since it’s static, we can obtain a constant time complexity for query, so our targets are:
O(1) time per query note that Segment Tree achieves (log n) here!
(n) space

Answer 36

Costruisco array tutte possibili queries
O(nˆ2) space, O(1) time
Costruisco sparse array parto da posizione i su n ed aggiungo 2 alla 0 .. log n
trovo intersezione tra i due array e rispondo.
Soluzione O(log n) + O(n) space
dividiamo in blocchi dim log n, ottenendo n/log n blocchi, per ogni blocco salvo sparse array + log n posizioni
Soluzione O(1) + O(n) creiamo cartesian tree

Question 37

Problem: Colored Range Query
Given A[1,n] of colors (integers), we want to answer this question:
Distinct(i,j) return all distinct colors in A[i ,j].

The target time complexity is proportional to the number of distinct colors in A[i ,j], called k.

Answer 37

storiamo different colors per ogni segment tree. time complexity O(k log n), space complexity O( n log n) perché path per ciascun elemento é log n.

O(k) + O(n) space
Creiamo P dove colleghiamo ciascun elemento con occorrenza precedente
Costruisco su P segment tree ed effettuo k search del minimum

Question 38

Mo’s algorithm : 3 Or More
Given an array of integers A[1,n] of colors we want to answer (offline) a set Q of q queries 3orMore(i,j), which report the number of colors that occur at least three times in A[i,j].

Answer 38

Trivial effettuiamo q queries con n values
Better possiamo prendere queries e aggiungere o rimuovere values in base a queries precedenti, useless se query a cazzo
Mo’s algo migliora questo utilizzando blocchi di dimensione radical n, ed abbiamo radical n+q * n

Question 39

Mo’s algorithm : Powerful Array
Another example of application of Mo’s algorithm is the following problem:

Given an array of positive integers A[1,n], we want to answer to a several q queries, each query is defined as:
query(i,j) = e De * fe2
where D is the set of distinct elements in A[i ..j] and fe is the frequency for each element e A[i,j]. The time complexity required is ((n+q)n).

Answer 39

Per ciascun valore aggiungiamo suo valore al quadrato