exercises

/**
 * STL Containers - Exercises
 * Compile: g++ -std=c++17 -Wall exercises.cpp -o exercises
 */

#include <iostream>
#include <vector>
#include <array>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <string>
using namespace std;

// ============================================================
// Exercise 1: Vector Operations ⭐
// ============================================================

// TODO: Create function that:
// - Takes a vector of ints
// - Removes all even numbers
// - Doubles all remaining numbers
// - Returns modified vector

void exercise1() {
    // vector<int> v = {1, 2, 3, 4, 5, 6};
    // auto result = processVector(v);
    // Output: {2, 6, 10}
    cout << "(Implement processVector)" << endl;
}

// ============================================================
// Exercise 2: Map Word Counter ⭐⭐
// ============================================================

// TODO: Create function that counts word frequencies
// Input: vector of strings
// Output: map<string, int> with counts

void exercise2() {
    // vector<string> words = {"apple", "banana", "apple", "cherry", "banana", "apple"};
    // auto counts = countWords(words);
    // apple: 3, banana: 2, cherry: 1
    cout << "(Implement word counter)" << endl;
}

// ============================================================
// Exercise 3: Set Operations ⭐⭐
// ============================================================

// TODO: Create functions for set operations:
// - setUnion(set a, set b)
// - setIntersection(set a, set b)
// - setDifference(set a, set b)

void exercise3() {
    // set<int> a = {1, 2, 3, 4};
    // set<int> b = {3, 4, 5, 6};
    // setUnion: {1,2,3,4,5,6}
    // setIntersection: {3,4}
    // setDifference: {1,2}
    cout << "(Implement set operations)" << endl;
}

// ============================================================
// Exercise 4: Stack Brackets ⭐⭐
// ============================================================

// TODO: Use stack to check if brackets are balanced
// Support: (), [], {}

void exercise4() {
    // isBalanced("({[]})") -> true
    // isBalanced("([)]") -> false
    // isBalanced("((())") -> false
    cout << "(Implement bracket checker)" << endl;
}

// ============================================================
// Exercise 5: Priority Queue Tasks ⭐⭐
// ============================================================

// TODO: Create task scheduler using priority_queue
// struct Task { string name; int priority; }
// Higher priority = processed first

void exercise5() {
    // TaskScheduler ts;
    // ts.addTask("Low", 1);
    // ts.addTask("High", 3);
    // ts.addTask("Medium", 2);
    // ts.processAll(); // High, Medium, Low
    cout << "(Implement task scheduler)" << endl;
}

// ============================================================
// Exercise 6: LRU Cache ⭐⭐⭐
// ============================================================

// TODO: Implement simple LRU Cache using list + unordered_map
// - get(key) - returns value or -1
// - put(key, value) - inserts/updates
// - Capacity limit, evicts least recently used

void exercise6() {
    // LRUCache cache(2);  // capacity 2
    // cache.put(1, 1);
    // cache.put(2, 2);
    // cache.get(1);       // returns 1
    // cache.put(3, 3);    // evicts key 2
    cout << "(Implement LRU Cache)" << endl;
}

// ============================================================
// Exercise 7: Graph Adjacency List ⭐⭐⭐
// ============================================================

// TODO: Implement graph using map<int, set<int>>
// - addEdge(u, v) - add edge
// - removeEdge(u, v)
// - hasPath(u, v) - BFS/DFS

void exercise7() {
    // Graph g;
    // g.addEdge(1, 2);
    // g.addEdge(2, 3);
    // g.hasPath(1, 3);  // true
    cout << "(Implement Graph with containers)" << endl;
}

// ============================================================
// Exercise 8: Multimap Index ⭐⭐⭐
// ============================================================

// TODO: Use multimap to create inverted index
// Input: vector of (docId, content) pairs
// Output: word -> list of docIds

void exercise8() {
    // vector<pair<int, string>> docs = {
    //     {1, "hello world"},
    //     {2, "world news"},
    //     {3, "hello again"}
    // };
    // auto index = buildIndex(docs);
    // index["hello"] -> {1, 3}
    // index["world"] -> {1, 2}
    cout << "(Implement inverted index)" << endl;
}

// ============================================================
// MAIN
// ============================================================

int main() {
    cout << "=== STL Containers Exercises ===" << endl;
    
    cout << "\nEx1: Vector Operations" << endl;
    exercise1();
    
    cout << "\nEx2: Word Counter" << endl;
    exercise2();
    
    cout << "\nEx3: Set Operations" << endl;
    exercise3();
    
    cout << "\nEx4: Bracket Checker" << endl;
    exercise4();
    
    cout << "\nEx5: Task Scheduler" << endl;
    exercise5();
    
    cout << "\nEx6: LRU Cache" << endl;
    exercise6();
    
    cout << "\nEx7: Graph" << endl;
    exercise7();
    
    cout << "\nEx8: Inverted Index" << endl;
    exercise8();
    
    return 0;
}

// ============================================================
// ANSWERS
// ============================================================
/*
Ex1:
vector<int> processVector(vector<int> v) {
    v.erase(remove_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; }), v.end());
    for (int& x : v) x *= 2;
    return v;
}

Ex2:
map<string, int> countWords(const vector<string>& words) {
    map<string, int> counts;
    for (const auto& w : words) counts[w]++;
    return counts;
}

Ex3:
set<int> setUnion(const set<int>& a, const set<int>& b) {
    set<int> result = a;
    result.insert(b.begin(), b.end());
    return result;
}
set<int> setIntersection(const set<int>& a, const set<int>& b) {
    set<int> result;
    for (int x : a) if (b.count(x)) result.insert(x);
    return result;
}

Ex4:
bool isBalanced(const string& s) {
    stack<char> stk;
    map<char, char> match = {{')', '('}, {']', '['}, {'}', '{'}};
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') stk.push(c);
        else if (match.count(c)) {
            if (stk.empty() || stk.top() != match[c]) return false;
            stk.pop();
        }
    }
    return stk.empty();
}

Ex5:
struct Task { string name; int priority; };
struct TaskScheduler {
    priority_queue<pair<int, string>> pq;
    void addTask(string n, int p) { pq.push({p, n}); }
    void processAll() {
        while (!pq.empty()) {
            cout << pq.top().second << " ";
            pq.pop();
        }
    }
};
*/