20 mai 2015

Probleme pentru interviu: Scalabilitate, Sortari si cautari, Testari

 cap. 10 - Scalability & Memory limits                                           

* fie un serviciu care poate fi apelat de pana la 1000 clienti pentru a obtine cateva informatii despre preturi de vanzare. Cum se pot salva informatiile?

Trei variante:
1) date salvate in fisiere text care se pot descarca prin FTP
2) o baza de date SQL : usor de obtinut informatii, functionalitati de backup, rollback, securitate, usor de integrat cu alte unelte . Dezavantaj: poate fi prea complex pentru simple functionalitati, trebuie cunoscut limbajul de interogare SQL, drepturile de securitate si setarea lor.
3) XML : usor de citit atat pentru om cat si pt calculator, cele mai multe limbaje au un API pentru parsarea XML, adaugarea de noi noduri nu incurca parserul existent. Dezavantaj: se trimit clientului toate informatiile indiferent daca sunt necesare sau nu, trebuie parsat intreg continutul pentru a obtine raspuns la o interogare.


* un fisier contine 4 miliarde de numere intregi pozitive. Gasiti un algoritm care poate gasi un numar necontinut in fisier, avand la dispozitie 1 GB de memorie.

4 miliarde = 2^32 numere
spatiul pt 4 miliarde de nr. = 8 * 2^32 = 2^35 biti
1 GB memorie = 2^30 biti  < spatiul necesar

Sol.: creare unui vector de 4 miliarde de biti, initializat cu 0
- pt fiecare numar se seteaza un bit in vector
- la final, se scaneaza vectorul si se returneaza indexul primei valori 0

long nofInt = (long) Integer.MAX_VALUE - 1; // MAX_VALUE e cel mai mare nr. posibil in fisier
byte [] bitfield = new byte [(int) (nofInt / 8)]; // 8 numere continute intr-un octet, similar cu radix sort
void find () {
  // setari
  Scanner in = new Scanner (new FileReader("srcFile.txt"));
  while (in.hasNextInt()) {
    int n = in.nextInt();
    bitfield [n/8] = bitfield [n/8] | (1 << (n%8));  // setarea bitului coresp., n%8 e pozitia in octet
    // pot exista duplicate, caz in care se seteaza din nou bitul
  }
  // cauta primul nr necontinut
  for (int i = 0; i < bitfield.length; i++ ) {
    for (int j = 0; j < 8; j++) {
      if ( (bitfield[i] & (1<<j)) == 0) {
        System.out.println ( i * 8 + j);
        return ;
     }
  }
  // si daca toate numerele au fost consecutive... nu exista!!
 System.out.println ("Nu exista un astfel de numar");
}


* avem un sir cu numere de la 1 la N  (N <= 32.000, necunoscut) . Pot exista duplicate. Folosind maxim 4 KB de memorie, cum se pot afisa toate elementele duplicate din sir?

Sol.:  4 KB de memorie pot codifica 4 * 8 * 2^10 = 2^15 biti = 32 Kbiti > 32*10^3 biti = 32.000 biti
=> crearea unui vector cu 32.000 biti
- se parcurge vectorul de biti si pe fiecare pozitie se seteaza 1 (pozitia repr. codificarea numarului curent din sir)
- daca pozitia era deja setata, se tipareste numarul caruia ii corespunde ca fiind duplicat
- fiecare bit reprezinta un numar, exista suficienti biti pentru marcarea fiecarui numar (32.000), deci daca vectorul va fi de tip int, el va avea 1000 elemente intregi, fiecare element avand 32 biti 
- accesul la "cuvant" se face printr-un index = pos / 32, iar in cadrul unui cuvant index2 = pos % 32, unde pos este pozitia "logica"
- exemplu de setare:   bitvec [pos >> 5] |= 1 << (pos & 0x20)  ,  adica la pozitia 2^5 din bitvec, se seteaza bitul de la subpozitia  pos & 32 , adica bitul restului impartirii lui pos la 32 , ceea ce aminteam mai inainte.


cap. 11 - Sortari, cautari                                                                   

* A, B sunt doua siruri deja sortate. Presupunem ca A are suficiente spatii libere la sfarsit astfel incat B poate incapea acolo. Cum se poate incorpora B in A a.i. A sa fie sortat?

Sol.: ne mutam la capatul lui A si inseram elemente de la sfarsit catre fatza, incepand cu cele mai mari elemente din A sau din B. Cand A sau B se termina, doar copiem sirul ramas pe pozitiile din A.


* sa se sorteze un sir de siruri de caractere astfel incat toate anagramele stau una langa cealalta.

Sol.: singura conditie de aranjare este ca anagramele sa stea impreuna, nu conteaza ordinea... O anagrama reprezinta orice permutatie folosind caracterele dintr-un sir de caractere.
- creeaza un HashMap <String, list of String>
- pt. fiecare string, sorteaza-i caracterele si adauga anagrama la lista corespunzatoare sirului sortat
- la sfarsit, se transforma HashMap-ul intr-un sir care va aparea sortat


* se da un sir sortat de numere intregi care a fost rotit de un numar necunoscut de ori. Sa se afle un anumit element din sir.

Sol.: in cazul obisnuit, la partitionarea in 2 a sirului, o parte va fi sortata crescator, iar in cealalta va aparea trecerea brusca de la un minim la maxim sau invers.

array = [9,10,4,5,6,7,8]

def find (A, elem, frm, to):
mid = (frm+to) // 2
if elem == A[to]:
print ("Position is ", to)
return None
elif elem == A[frm]:
print ("Position is ", frm)
return None
# case: left side is ordered and elem within the limits
if A[frm] < A[mid] and elem > A[frm] and elem < A[to]:
find (A, elem, frm, mid)
# case: right side is ordered and elem within the limits
elif A[mid] < A[to] and elem > A[mid] and elem < A[to]:
find (A, elem, mid, to)
# case: left side ordered and right is not => search in right
elif A[frm] < A[mid]:
find(A, elem, mid, to)
# case: right side ordered and left is not => search in left
elif A[mid] < A[to]:
find(A, elem, frm, mid)
else:
print ("Element not found:", elem)
return None
find(array, 10, 0, len(array)-1)


* avem o matrice M x N in care fiecare linie si coloana este sortata crescator. Sa se afle un element cautand intr-o astfel de matrice.

Sol.: ca si in cazul cautarii binare, se cauta sa se elimine portiuni din matrice in care sigur nu poate aparea elementul. Exista mai multe abordari: mai jos, ne pozitionam pe elementul din centrul matricei si in functie de comparatie, fie eliminam coltul stanga-sus de acest element, fie restul matricei. In carte, abordarea e ca se exclud linii care incep cu un element > ce cautam sau se incheie cu un element < al nostru, idem pt coloane.

matrix = [[1,2,3,4], [4,7,9,10], [5,9,11,15], [20,21,25,27]]
M = len(matrix)-1
N = len(matrix[0])-1

def find (A, fromI, toI, fromJ, toJ, elem):
midI = (fromI + toI) // 2
midJ = (fromJ + toJ) // 2

if fromI > toI or fromJ > toJ:
print("Element not found:", elem)
return False

# base cases
if elem == A[midI][midJ]:
print("Found at (", midI, ",", midJ, ")")
return True

if fromI == toI:
# search on the line
for j in range (fromJ, toJ+1):
if elem == A[fromI][j]:
print("Found at (", fromI, ",", j, ")")
return True
elif fromJ == toJ:
# search on the column
for i in range (fromI, toI+1):
if elem == A[i][fromJ]:
print("Found at (", i, ",", fromJ, ")")
return True

elif elem > A[midI-1][midJ] and elem > A[midI][midJ-1]:
# ignore left corner
result = find (A, fromI, toI, midJ+1, N, elem)
if result == False:
return find (A, midI+1, M, fromJ, midJ, elem)
else:
# search in left corner
return find (A, 0, midI, 0, midJ, elem)
return False

find(matrix, 0, 3, 0, 3, 10)


* intr-un numar de circ, oamenii se aseaza unul deasupra celuilalt pentru a forma un turn. Asezarea se face astfel incat deasupra sa vina un om mai scund si mai putin greu decat cel sub. Sa se afle cel mai mare numar de oameni din circ care poate forma un astfel de turn, stiind wi, hi greutatile respectiv inaltimile tuturor oamenilor angajati.

Sol.: Problema este echivalenta gasirii unei secvente de oameni ordonate astfel incat urmatorul om in sir sa aiba atat inaltimea cat si greutatea mai mica decat cel de dinaintea lui.
Intai, se sorteaza dupa inaltime. Apoi, se calculeaza cel mai mare subsir crescator in functie de greutate (vezi detalii aici). Acest subsir reprezinta cel mai mare numar de oameni care poate participa la alcatuirea turnului.


* se citeste un flux de numere intregi. Sa se afle rangul unui element (numarul de numere mai mici decat el). Implementati track (int x) care se apeleaza de fiecare data cand un numar este generat, si getRank (int x) care obtine rangul.

Sol.: Se construieste un arbore binar de cautare.
track (x) :  adauga un nod in arbore, detalii aici
getRank (node, x) { 
  if x == node.data 
    return node.leftSize()
  if x < node.data
    return getRank (node.left, x)
  else
    return node.leftSize() + 1 + getRank (node.right, x)
}


cap. 12 - Testari                                                                                 

Testarea programelor:
- manuala vs. automata
- black box vs. white box
White box: set pot testa functii in mod individual, modular. Accent pe validarea I/O
Black box: se testeaza intreg produsul fara sa stii cum este implementat

* un program crapa cand este pornit. Dupa 10 incercari de depanare, se observa ca niciodata nu crapa in acelasi loc. Aplicatia are un singur fir de executie, limbaj de programare C (stdlib). Ce ar putea cauza problema? Cum se poate investiga mai departe?

Sol.: Cauze:
- variabile la intamplare: datele de intrare ale utilizatorului variaza; numere generate aleator; se ia in calcul data/ora/momentul zilei
- variabile neinitializate care pot lua valori la intamplare
- memory leaks: programul a consumat memoria alocata (heap overflow, coruperea datelor pe stiva) => valorile variabilelor depind de alte procese care ruleaza la un moment dat
- dependente externe - alte librarii pot livra valori gresite
Se poate investiga cu runtime tools gen valgrind si altele.


* Cum se poate testa un pix? :)

Sol.: 
1) trebuie puse o multime de intrebari despre: cine va folosi pixul, pentru ce, functionalitati dorite.
2) in functie de raspunsuri, se creeaza un set de constrangeri. In general, atentie la: 
- nevoile/problemele consumatorului si ce se poate astepta in functie de ele -> de exemplu daca utilizatorul este un copil, pasta de pix nu trebuie sa fie toxica
- ce ar trebui sa furnizeze produsul -> scris pe hartie? pe suprafata dura? se verifica daca functioneaza
- ce nu ar trebui sa furnizeze produsul sub nicio forma -> nu ar trebui sa scrie pe pereti? se verifica
- cazuri de utilizare obisnuite 
- cazuri de utilizare pe muchie / exceptii
- conditii de esuare -> cum se poate sparge pixul, este suficient de dur materialul?
- securitate / incredere   -> in cazul de fata N/A

Niciun comentariu: