cap. 13 - C/C++
Lucruri de baza:
* clase, mosteniri: by default, clasele sunt private
daca avem class Student : public Person { ... } ; Person p = new Student() ; => p va fi Person (static binding, in timpul compilarii) . Pentru dynamic binding se foloseste cuvantul-cheie virtual.
* virtual permite suprascrierea cu ultima definitie a tipului declarat
* virtual destructor va apela destructorul ambelor clase (cea mostenita si cea mostenitoare)
* functiile se pot declara cu valori implicite, la fel ca in Python
* overloading: BookShelf BookShelf::operator+ (BookShelf x) { ... } - supraincarcarea operatorului + pentru a fi aplicat si obiectelor de tip BookShelf
* pointeri: int * p = new int; *p = 7; lungimea pointerului este de 32 sau 64 biti (in functie de tipul masinii)
* tipul
referinta: int a = 5; int & b = a; b = 7; cout<<a; // scrie 7 , aici b este un alias pentru a, nu ocupa memorie pt el insusi
* nu este posibila declaratia: int & b;
dar e ok: int & b = 12; // b este referinta la locul unde este stocat nr. intreg 12
* templates: reutilizare a codului astfel incat aceeasi clasa sa fie aplicabila la mai multe tipuri de date
template <class T>
class ShiftedClass {
T * arr;
int offset, size;
...
}
* o metoda pentru a scrie ultimele K linii dintr-un fisier, folosind C++
Sol.: se foloseste un sir circular de lungime K . Se pastreaza un index al celui mai vechi element si intotdeauna se inlocuieste elementul respectiv cu cel mai nou element(linie) citit.
void printLast (char * filename) {
const int K = 10; // ultimele 10 linii
ifstream file (filename);
string L[K];
int size = 0;
while (file.good()) {
getline ( file, L[size % K] ); // umple vectorul incepand cu cea mai "veche" pozitie
size++;
}
// afla inceputul
int start;
if (size > K) start = size % K; // ce ar fi devenit cea mai "veche" pozitie e acum prima din ultimele K
else start = 0; // au fost mai putin de K linii
int count = min (K, size);
// print the lines
for (int = 0; i < count; i++) {
cout<< L [(start+1)%K] << endl;
}
}
* comparatie intre hash table si un STL map. Cum sunt implementate? Daca nr. de input-uri este mic, care structura de date se foloseste mai bine?
Sol.:
HashTable: - valorile sunt create apeland o functie de hash asupra valorii
- valorile nu se salveaza in ordine ASC sau DESC
- inserarea/cautarea se petrec in O(1)
- trebuie sa rezolve potentialele coliziuni (adesea se face prin inlantuire, linked list)
- implementare: un sir de liste inlantuite, cheia corespunde unui index in sir (care se afla folosind functia de hash), valorile intr-o lista inlantuita corespund unei aceleiasi chei, insa trebuie salvata si cheia pentru a furniza valoarea corecta
STL map: - perechea cheie,valoare se insereaza intr-un arbore binar de cautare, in fct de cheie
- nu este cazul coliziunilor
- inserare/cautare se petrec in O(log n)
Nr. mic de inputs: STL map sau un arbore binar. Nr. mare: hash table.
* cum functioneaza functiile virtuale in C++?
Sol.: Functiile nevirtuale se rezolva in timpul compilarii, cu static binding.
Functiile virtuale se rezolva in timpul rularii, cu dynamic binding. Se salveaza intr-o structura numita vtable, asociata unei clase. Daca functia virtuala nu este suprascrisa, se acceseaza vtable al clasei derivate si adresa functiei se salveaza in clasa-parinte.
* diferenta intre deep-copy si shallow-copy?
Sol.: Deep-copy: copiaza obiectul intocmai (duplicat), daca se modifica copia, originalul ramane intact. Shallow-copy: opusul.
* ce inseamna volatile in C?
Sol.: Cuvantul-cheie volatile informeaza compilatorul ca valoarea unei variabile se poate schimba din exterior, fara nicio corespondenta in codul sursa (se poate realiza datorita SO, al unui altui thread, sau din hardware). Astfel, compilatorul va trebui sa reincarce valoarea din memorie de fiecare data cand se foloseste variabila, iar astfel este prevenit sa nu faca optimizari care ar schimba logica codului.
int volatile x; // volatile int x;
int volatile * volatile x; // pointer volatil la o variabila volatila
* de ce un destructor ar trebui declarat virtual intr-o clasa care poate fi mostenita?
Sol.:
Foo * p = new Bar();
La distrugere, fara un destructor virtual, se apeleaza destructorul din Foo, chiar daca p este de tip Bar. Ca "Bar", p ar putea avea campuri noi care nu vor ajunge sa fie distruse pentru ca nu apar in Foo.
* o metoda care face o copie completa a unui pointer la obiectul de mai jos:
struct Node {
Node * ptr1;
Node * ptr2;
}
Sol.:
typedef map <Node *, Node *> NodeMap;
Node * copy (Node * current, NodeMap & nodeMap) {
// fct recursiva
if (current == NULL) return NULL;
// pt evitarea buclelor infinite de la un ptr care a condus la un ptr deja vizitat
NodeMap :: iterator i = nodeMap.find(current); // std::pair, are first & second
if ( i != nodeMap.end() ) {
return i->second; // valoarea
}
Node * node = new Node; // creeaza copia (sau bucata de copie)
nodeMap[current] = node; // first = current, second = node (~copia lui current este node)
node->ptr1 = copy(current->ptr1, nodeMap);
node->ptr2 = copy(current->ptr2, nodeMap);
return node;
}
// creare
Node * mainCopy (Node * root) {
NodeMap nodeMap;
return copy (root, nodeMap);
}
cap. 14 - Java
Termeni-cheie:
> overloading - doua metode au acelasi nume dar numar diferit de argumente
> overriding - o subclasa redefineste o metoda a parintelui, folosind aceeasi semnatura pentru ea
* ce se intampla cand constructorul unei clase este privat?
R: se asigura faptul ca nimic din afara clasei nu poate instantia direct clasa, astfel singurul mod de a o instantia este folosind o metoda statica si publica (~ Factory Method Pattern)
* try {
...
return 0;
}
catch (Exception e) { ... }
finally { ... } // ajunge sa se execute aceasta portiune??
R: Da, finally se executa intotdeauna dupa ce try se termina. Singurele cazuri cand finally nu se executa sunt: masina virtuala se opreste in timpul try/catch sau thread-ul care executa try/catch este omorat.
* final vs. finally vs. finalize
final: cuvant-cheie pentru o variabila constanta SAU o metoda care nu poate fi suprascrisa SAU o clasa care nu poate fi derivata
finally: in try/catch, o portiune de cod care se executa intotdeauna indiferent daca apare exceptie sau nu
finalize: metoda apelata de garbage collector cand isi da seama ca nu mai exista referinte la resurse care trebuie "curatate"
* ce este object reflection? La ce ajuta?
Class rectDef = Class.forName("MyProj.Rectangle");
rectDef.getConstructor();
Informatii "reflexiva" despre clase si obiecte Java, metode si campuri prezente in timpul rularii; Se pot crea instante noi ale clasei, get/set pe campurile obiectului indiferent de tipul de acces (public/private) . Ajuta la: observarea si manipularea comportamentului la runtime a aplicatiei; pentru depanare si testare.
cap. 15 - Baze de date
Baza de date normalizata vs. nenormalizata: minimizarea redundantei vs. optimizarea timpului de citire (si evitarea join-urilor)
Aici exercitiile sunt de tip sql queries (subqueries, join-uri, having/group by, etc) si de tip teoretic.
* care sunt tipurile de join?
R: JOIN se foloseste la combinarea rezultatelor din 2 tabele care au cel putin un camp folosit pentru a face legatura intre ele.
INNER JOIN: doar randurile unde conditia de join se respecta
OUTER JOIN: INNER JOIN + alte randuri care nu respecta conditia in cel de-al doilea tabel
- LEFT JOIN: rezultatul contine toate inregistrarile din tabelul din stanga sau NULL daca nu exista valori coresp. in tabelul din dreapta
- RIGHT JOIN: idem LEFT, dar invers
- FULL OUTER JOIN: LEFT+ RIGHT
* denormalizare, ce este? pro, contra?
R: O tehnica de optimizare in care adaugam informatii redundante la 1 sau mai multe tabeluri. Ajuta la evitarea join-urilor costisitoare dintr-o baza de date relationala.
Pro: - datele se achizitioneaza mai repede, mai putine join-uri
- interogarile sunt mai simple, riscul greselilor este mai mic
Contra: - update,insert sunt mai costisitoare si mai dificil de scris
- datele pot deveni inconsistente
- din cauza redundantei este nevoie de mai mult spatiu de stocare
* o interogare pt a obtine o lista a studentilor de onoare (top 10%) ordonati dupa medie
Student: sId, name, bday
Coursework: courseId, sId, grade
Course: courseId, courseName
DECLARE @gpaCutOff float;
SET @gpaCutOff = ( SELECT min(GPA) as 'GpaMin'
FROM ( SELECT TOP 10 PERCENT AVG (Coursework.grade) as GPA
FROM Coursework
GROUP BY Coursework.sId
ORDER BY GPA desc) Grades );
SELECT StudentName, GPA
FROM (
SELECT AVG (Coursework.Grade) as GPA, Coursework.sId
FROM Coursework
GROUP BY Coursework.sId
HAVING AVG(Coursework.grade) >= @GpaCutoff
) Honors INNER JOIN Students ON Honors.sId = Student.sId
cap. 16 - Threads & Locks
Fire de executie in Java:
1) implementeaza Runnable SAU
2) extind Thread
Se prefera Runnable deoarece Java nu accepta mostenire multipla.
Metode synchonized: se executa de catre un singur thread la un moment dat ( al doilea thread care nu are voie sa execute metoda trebuie sa apartina aceleiasi instante a obiectului, altfel are voie )
Lock: ReentrantLock
Un Lock in Java este proprietatea thread-ului care l-a creat, niciun alt thread nu poate sa-l modifice. Pentru semafoare, nu .
* diferenta intre un proces si un thread
R: Procesul este o instanta a unui program in executie, foloseste CPU si memorie, se executa intr-un spatiu de adrese separat. Procesele nu-si pot accesa spatiile unul altuia, cu exceptia IPC (interprocess communication prin pipes, files, sockets, etc)
Un thread exista in cadrul unui proces, foloseste resursele procesului, inclusiv heap-ul. Mai multe thread-uri ale aceluiasi proces impart acelasi spatiu de heap, insa fiecare thread are propriile registre si spatiu pe stiva.
* cum se poate masura timpul petrecut intr-un context switch?
R: Trebuie masurat timpul dintre ultima instructiune executata de P1 si prima instr. exe. de P2.
Il fortam pe P2 sa execute fix dupa P1, printr-un pipe: P1 trimite, P2 primeste.
Pasii sunt:
- P1 marcheaza timpul de start, T1
- P1 trimite un token la P2, care ia Td pentru a fi livrat
- P1 incearca sa primeasca un raspuns de la P2, se blocheaza si are loc context switch -> Tc
- P2 incepe sa ruleze, primeste token-ul -> Tr
- P2 trimite un raspuns catre P1, care ajunge in Td
- P2 asteapta un raspuns de la P1, se blocheaza si are loc context switch -> Tc
- P1 incepe sa ruleze, primeste token-ul -> Tr
- P1 marcheaza timpul de final, T2
=> T = 2 ( Td + Tr + Tc ) , unde T = T2 - T1
=> Tc = ...
