1st question

solution

class DSU {
public:
    vector<int> parent;
    vector<int> size;

    DSU(int n) {
        parent.resize(n);
        size.resize(n, 1);
        for (int i = 0; i < n; ++i)
            parent[i] = i;
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    void union_sets(int x, int y) {
        int px = find(x), py = find(y);
        if (px != py) {
            if (size[px] < size[py])
                swap(px, py);
            parent[py] = px;
            size[px] += size[py];
        }
    }
};

int numberOfFlowers(int M, int N, vector<vector<int>>& A) {
    auto get_index = [&](int i, int j) {
        return i * N + j;
    };

    DSU dsu(M * N);
    set<int> flower_types;

    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < N; ++j) {
            flower_types.insert(A[i][j]);
            if (i > 0 && A[i][j] == A[i-1][j]) {
                dsu.union_sets(get_index(i, j), get_index(i-1, j));
            }
            if (j > 0 && A[i][j] == A[i][j-1]) {
                dsu.union_sets(get_index(i, j), get_index(i, j-1));
            }
        }
    }

    unordered_map<int, int> root_to_type;
    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < N; ++j) {
            int root = dsu.find(get_index(i, j));
            root_to_type[root] = A[i][j];
        }
    }

    unordered_map<int, vector<int>> type_to_roots;
    for (auto& [root, ftype] : root_to_type) {
        type_to_roots[ftype].push_back(root);
    }

    int max_area = 0;
    for (int t1 : flower_types) {
        for (int t2 : flower_types) {
            if (t1 > t2) continue;
            int area = 0;
            for (int root : type_to_roots[t1]) {
                area += dsu.size[root];
            }
            if (t1 != t2) {
                for (int root : type_to_roots[t2]) {
                    area += dsu.size[root];
                }
            }
            max_area = max(max_area, area);
        }
    }

    return max_area;
}

2nd question

solution

#include <iostream>
#include <unordered_map>

class LRUCache {
public:
    struct Node {
        int key;
        Node* prev;
        Node* next;
        Node(int k) : key(k), prev(nullptr), next(nullptr) {}
    };

    Node* head;
    Node* tail;
    int capacity;
    std::unordered_map<int, Node*> cacheMap;

    LRUCache(int cap) {
        capacity = cap;
        head = new Node(-1);
        tail = new Node(-1);
        head->next = tail;
        tail->prev = head;
    }

    ~LRUCache() {
        Node* curr = head;
        while (curr) {
            Node* next = curr->next;
            delete curr;
            curr = next;
        }
    }

    void addNode(Node* newNode) {
        Node* temp = head->next;
        newNode->next = temp;
        newNode->prev = head;
        head->next = newNode;
        temp->prev = newNode;
    }

    void deleteNode(Node* delNode) {
        Node* prevNode = delNode->prev;
        Node* nextNode = delNode->next;
        prevNode->next = nextNode;
        nextNode->prev = prevNode;
    }

    bool get(int key) {
        if (cacheMap.find(key) != cacheMap.end()) {
            Node* resNode = cacheMap[key];
            cacheMap.erase(key);
            deleteNode(resNode);
            addNode(resNode);
            cacheMap[key] = head->next;
            return true;
        }
        return false;
    }

    void put(int key) {
        if (cacheMap.find(key) != cacheMap.end()) {
            Node* curr = cacheMap[key];
            cacheMap.erase(key);
            deleteNode(curr);
        }
        if (cacheMap.size() == capacity) {
            cacheMap.erase(tail->prev->key);
            deleteNode(tail->prev);
        }
        Node* newNode = new Node(key);
        addNode(newNode);
        cacheMap[key] = head->next;
    }
};

void pagesInCache(int X, int N, int* page) {
    LRUCache cache(X);
    int hits = 0;
    for (int i = 0; i < N; ++i) {
        if (cache.get(page[i])) {
            hits++;
        } else {
            cache.put(page[i]);
        }
    }
    int hitRate = (hits * 100) / N;
    std::cout << hitRate << std::endl;
}

int main() {
    int X = 3;  // Cache capacity
    int N = 8;  // Number of pages
    int page[] = {1, 2, 3, 4, 1, 2, 5, 1};  // Pages to be accessed
    pagesInCache(X, N, page);
    return 0;
}