Definiți o structură (sau mai multe) care să permită lucrul ușor și eficient cu matrice rare. Prin definiție, matricele rare sunt matricele care conțin un număr foarte mic de elemente nenule (cu alte cuvinte, marea majoritate a elementelor sunt egale cu 0). Astfel, este de preferat o reprezentare în care, pentru fiecare element nenul, să se țină minte poziția acestuia și valoarea lui. O reprezentare pentru o întreagă matrice ar reține astfel dimensiunile matricei, precum și o listă cu intrări pentru fiecare element.

Exemplu: Pentru matricea

A =
1 0 0 0
0 0 0 0
0 0 1 2
3 0 0 0

Am avea reprezentarea

A = {n = 4, m = 4, entries = { {0, 0, 1}, {2, 2, 1}, {2, 3, 2}, {4, 0, 3} } }

Realizați un API minimal pentru lucrul cu matrice rare:

• o funcție care citește de la intrare o matrice rară, dată în forma sa densă, și returnează reprezentarea de mai sus.
• o funcție care printează o matrice rară, în forma sa densă
  Follow-up: printați matricea astfel fără a o construi în memorie.
  De ce anume ați avea nevoie ?
• o funcție care adună două matrice rare și returnează rezultatul
• o funcție care înmulțește două matrice rare și returnează rezultatul
• o funcție care ridică la putere o matrice rară și printează rezultatul (Hint: modularizare)

Definiți o structură care să permită lucrul cu un resizable array, care își dublează capacitatea în momentul în care este plin. Apoi, realizați un API minimal pentru lucrul cu resizable arrays:

• o funcție care alocă memorie și inițializează un resizable array gol (cu 0 elemente)
• o funcție care alocă memorie și inițializează un resizable array, dându-se numărul inițial de elemente și valoarea comună a elementelor
• o funcție care adaugă un element dat ca parametru la finalul acestui resizable array
• o funcție care interclasează 2 resizable arrays primite ca parametru, și întoarce rezultatul
• o funcție care eliberează 2 resizable arrays

De multe ori, nu avem la dispoziție o zonă contiguă de memorie pentru a reține un vector suficient de mare (memoria este fragmentată). De aceea, în locul unui vector se poate folosi o listă înlănțuită, în care elementele nu mai sunt situate adiacent în memorie, și fiecare element are acces la următorul element din memorie:

typedef struct Node node_t;
struct Node {
    int value;
    struct Node *next;
};

În mod evident, ultimul element va avea next = NULL.
Realizați un API minimal pentru lucrul cu liste înlănțuite:

• o funcție care să rezerve memorie pentru un nod: node_t *alloc_node(int value);
• o funcție care să adauge un element la începutul unei liste deja existente: node_t *add_first(int value, node_t *head)
• o funcție care adaugă un nou element la finalul unei liste deja existente: node_t *add_last(int value, node_t *head)
• o funcție care printează o astfel de listă înlănțuită: void print_list(node_t *head);
• o funcție care sortează o astfel de listă înlănțuită: node_t *sort_list(node_t *head)
• o funcție care inversează o listă înlănțuită: node_t *reverse_list(node_t *head)

Rezolvați următoarea problemă de pe Hackerrank.