C++ Interview Questions with Answers

// Hello World in C++
#include <iostream>
using namespace std;

int main() {
    cout << "Hello, World!" << endl;
    return 0;
}

// Data Types in C++
#include <iostream>
#include <string>
using namespace std;

int main() {
    int age = 25;
    float salary = 50000.50f;
    double pi = 3.14159265358979;
    char grade = 'A';
    bool isActive = true;
    string name = "Alice";

    cout << "Age: "      << age       << endl;
    cout << "Salary: "   << salary    << endl;
    cout << "Pi: "       << pi        << endl;
    cout << "Grade: "    << grade     << endl;
    cout << "Active: "   << isActive  << endl;
    cout << "Name: "     << name      << endl;
    return 0;
}

// Variables, Constants, References
#include <iostream>
using namespace std;

int main() {
    int x = 10;
    const int MAX = 100;     // constant
    constexpr double PI = 3.14159; // compile-time constant

    int &ref = x;            // reference to x
    ref = 42;                // modifies x through ref

    cout << "x = "   << x   << endl;  // 42
    cout << "MAX = " << MAX  << endl;
    cout << "PI = "  << PI   << endl;
    cout << "ref = " << ref  << endl;  // 42

    // auto type deduction
    auto val = 3.14;
    auto str = "Hello";
    cout << "auto val: " << val << endl;
    cout << "auto str: " << str << endl;
    return 0;
}

// OOP - Classes and Objects
#include <iostream>
#include <string>
using namespace std;

class Car {
private:
    string brand;
    int year;
    double price;

public:
    // Constructor
    Car(string b, int y, double p)
        : brand(b), year(y), price(p) {}

    // Getter methods
    string getBrand() const { return brand; }
    int    getYear()  const { return year;  }
    double getPrice() const { return price; }

    // Member function
    void display() const {
        cout << "Brand: " << brand
             << ", Year: "  << year
             << ", Price: $" << price << endl;
    }

    // Destructor
    ~Car() {
        cout << brand << " destroyed." << endl;
    }
};

int main() {
    Car c1("Toyota", 2022, 25000.0);
    Car c2("BMW",    2023, 55000.0);

    c1.display();
    c2.display();

    cout << "Brand: " << c1.getBrand() << endl;
    return 0;
}

// Constructors and Destructors
#include <iostream>
#include <string>
using namespace std;

class Student {
    string name;
    int age;
public:
    // Default constructor
    Student() : name("Unknown"), age(0) {
        cout << "Default constructor called" << endl;
    }

    // Parameterized constructor
    Student(string n, int a) : name(n), age(a) {
        cout << "Parameterized constructor: " << name << endl;
    }

    // Copy constructor
    Student(const Student &s) : name(s.name), age(s.age) {
        cout << "Copy constructor: " << name << endl;
    }

    void display() const {
        cout << "Name: " << name << ", Age: " << age << endl;
    }

    ~Student() {
        cout << "Destructor: " << name << endl;
    }
};

int main() {
    Student s1;
    Student s2("Alice", 20);
    Student s3 = s2;   // copy constructor

    s1.display();
    s2.display();
    s3.display();
    return 0;
}

// Inheritance in C++
#include <iostream>
#include <string>
using namespace std;

class Animal {
protected:
    string name;
    int age;
public:
    Animal(string n, int a) : name(n), age(a) {}

    virtual void speak() const {
        cout << name << " makes a sound." << endl;
    }

    void info() const {
        cout << "Name: " << name << ", Age: " << age << endl;
    }
};

class Dog : public Animal {
    string breed;
public:
    Dog(string n, int a, string b)
        : Animal(n, a), breed(b) {}

    void speak() const override {
        cout << name << " says: Woof!" << endl;
    }

    void display() const {
        info();
        cout << "Breed: " << breed << endl;
    }
};

class Cat : public Animal {
public:
    Cat(string n, int a) : Animal(n, a) {}

    void speak() const override {
        cout << name << " says: Meow!" << endl;
    }
};

int main() {
    Dog dog("Rex", 3, "German Shepherd");
    Cat cat("Whiskers", 2);

    dog.display();
    dog.speak();
    cat.speak();

    // Polymorphism via base pointer
    Animal *a = &dog;
    a->speak();
    return 0;
}

// Polymorphism and Virtual Functions
#include <iostream>
using namespace std;

class Shape {
public:
    virtual double area() const = 0;      // pure virtual
    virtual double perimeter() const = 0; // pure virtual
    virtual void display() const {
        cout << "Area: "      << area()
             << ", Perimeter: " << perimeter() << endl;
    }
    virtual ~Shape() {}
};

class Circle : public Shape {
    double radius;
public:
    Circle(double r) : radius(r) {}
    double area()      const override { return 3.14159 * radius * radius; }
    double perimeter() const override { return 2 * 3.14159 * radius; }
};

class Rectangle : public Shape {
    double width, height;
public:
    Rectangle(double w, double h) : width(w), height(h) {}
    double area()      const override { return width * height; }
    double perimeter() const override { return 2 * (width + height); }
};

int main() {
    Shape *shapes[] = {
        new Circle(5.0),
        new Rectangle(4.0, 6.0)
    };

    for (auto s : shapes) {
        s->display();
        delete s;
    }
    return 0;
}

// Operator Overloading
#include <iostream>
using namespace std;

class Vector2D {
public:
    double x, y;
    Vector2D(double x = 0, double y = 0) : x(x), y(y) {}

    // + operator
    Vector2D operator+(const Vector2D &v) const {
        return Vector2D(x + v.x, y + v.y);
    }

    // - operator
    Vector2D operator-(const Vector2D &v) const {
        return Vector2D(x - v.x, y - v.y);
    }

    // * scalar
    Vector2D operator*(double s) const {
        return Vector2D(x * s, y * s);
    }

    // == operator
    bool operator==(const Vector2D &v) const {
        return x == v.x && y == v.y;
    }

    // << output
    friend ostream& operator<<(ostream &os, const Vector2D &v) {
        os << "(" << v.x << ", " << v.y << ")";
        return os;
    }
};

int main() {
    Vector2D v1(3, 4), v2(1, 2);
    cout << "v1 = " << v1 << endl;
    cout << "v2 = " << v2 << endl;
    cout << "v1 + v2 = " << (v1 + v2) << endl;
    cout << "v1 - v2 = " << (v1 - v2) << endl;
    cout << "v1 * 2  = " << (v1 * 2)  << endl;
    cout << "v1==v2: "   << (v1 == v2) << endl;
    return 0;
}

// Templates in C++
#include <iostream>
#include <string>
using namespace std;

// Function template
template <typename T>
T myMax(T a, T b) { return a > b ? a : b; }

template <typename T>
void swap(T &a, T &b) { T temp = a; a = b; b = temp; }

// Class template
template <typename T>
class Stack {
    T data[100];
    int top = -1;
public:
    void push(T val) { data[++top] = val; }
    T    pop()       { return data[top--]; }
    T    peek()      { return data[top]; }
    bool isEmpty()   { return top == -1; }
};

// Multiple type parameters
template <typename K, typename V>
struct Pair {
    K key; V value;
    Pair(K k, V v) : key(k), value(v) {}
    void print() { cout << key << " -> " << value << endl; }
};

int main() {
    cout << myMax(10, 20)        << endl;
    cout << myMax(3.5, 2.1)      << endl;
    cout << myMax(string("B"), string("A")) << endl;

    Stack<int>    si; si.push(1); si.push(2); si.push(3);
    cout << si.pop() << " " << si.pop() << endl;

    Pair<string, int> p("age", 25);
    p.print();
    return 0;
}

// STL - Vectors
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {5, 2, 8, 1, 9, 3};

    // Add elements
    v.push_back(7);
    v.insert(v.begin(), 0);

    // Size and capacity
    cout << "Size: "     << v.size()     << endl;
    cout << "Capacity: " << v.capacity() << endl;

    // Iterate
    for (int x : v) cout << x << " ";
    cout << endl;

    // Sort
    sort(v.begin(), v.end());
    for (int x : v) cout << x << " ";
    cout << endl;

    // Find and erase
    auto it = find(v.begin(), v.end(), 8);
    if (it != v.end()) v.erase(it);

    // 2D vector
    vector<vector<int>> mat(3, vector<int>(3, 0));
    mat[1][1] = 5;
    cout << "mat[1][1] = " << mat[1][1] << endl;

    return 0;
}

// STL - Map and Unordered_Map
#include <iostream>
#include <map>
#include <unordered_map>
using namespace std;

int main() {
    // map (sorted by key)
    map<string, int> scores;
    scores["Alice"] = 95;
    scores["Bob"]   = 87;
    scores["Carol"] = 92;

    for (auto &[name, score] : scores)
        cout << name << ": " << score << endl;

    cout << "Alice: " << scores["Alice"] << endl;
    cout << "Contains Bob: " << scores.count("Bob") << endl;

    // unordered_map (O(1) average)
    unordered_map<string, int> freq;
    string words[] = {"apple","banana","apple","cherry","banana","apple"};
    for (auto &w : words) freq[w]++;

    for (auto &[word, cnt] : freq)
        cout << word << ": " << cnt << endl;

    return 0;
}

// STL - Set and Priority Queue
#include <iostream>
#include <set>
#include <queue>
#include <vector>
using namespace std;

int main() {
    // set - unique sorted elements
    set<int> s = {5, 2, 8, 2, 1, 9, 5};
    for (int x : s) cout << x << " ";
    cout << endl;  // 1 2 5 8 9

    s.insert(6);
    s.erase(2);
    cout << "Contains 5: " << s.count(5) << endl;

    // priority_queue (max-heap by default)
    priority_queue<int> maxPQ;
    maxPQ.push(3); maxPQ.push(1); maxPQ.push(9); maxPQ.push(5);
    while (!maxPQ.empty()) {
        cout << maxPQ.top() << " ";
        maxPQ.pop();
    }
    cout << endl;  // 9 5 3 1

    // min-heap
    priority_queue<int, vector<int>, greater<int>> minPQ;
    minPQ.push(3); minPQ.push(1); minPQ.push(9); minPQ.push(5);
    while (!minPQ.empty()) {
        cout << minPQ.top() << " ";
        minPQ.pop();
    }
    cout << endl;  // 1 3 5 9
    return 0;
}

// Exception Handling
#include <iostream>
#include <stdexcept>
#include <string>
using namespace std;

// Custom exception
class ValidationError : public runtime_error {
    int code;
public:
    ValidationError(const string &msg, int c)
        : runtime_error(msg), code(c) {}
    int getCode() const { return code; }
};

double divide(double a, double b) {
    if (b == 0) throw invalid_argument("Division by zero!");
    return a / b;
}

int getAge(int age) {
    if (age < 0 || age > 150)
        throw ValidationError("Invalid age: " + to_string(age), 400);
    return age;
}

int main() {
    // Basic try-catch
    try {
        cout << divide(10, 2)  << endl;
        cout << divide(10, 0)  << endl;  // throws
    } catch (const invalid_argument &e) {
        cout << "Error: " << e.what() << endl;
    }

    // Custom exception
    try {
        getAge(200);
    } catch (const ValidationError &e) {
        cout << "Validation [" << e.getCode() << "]: " << e.what() << endl;
    } catch (const exception &e) {
        cout << "General: " << e.what() << endl;
    }
    return 0;
}

// Smart Pointers
#include <iostream>
#include <memory>
#include <string>
using namespace std;

class Resource {
    string name;
public:
    Resource(string n) : name(n) {
        cout << "Resource acquired: " << name << endl;
    }
    void use() const { cout << "Using: " << name << endl; }
    ~Resource() { cout << "Resource released: " << name << endl; }
};

int main() {
    // unique_ptr - sole ownership
    {
        unique_ptr<Resource> up = make_unique<Resource>("UniqueRes");
        up->use();
        // auto-deleted when out of scope
    }

    // shared_ptr - shared ownership
    shared_ptr<Resource> sp1 = make_shared<Resource>("SharedRes");
    {
        shared_ptr<Resource> sp2 = sp1;  // shared
        cout << "Count: " << sp1.use_count() << endl;  // 2
        sp2->use();
    }
    cout << "Count: " << sp1.use_count() << endl;  // 1

    // weak_ptr - non-owning
    weak_ptr<Resource> wp = sp1;
    if (auto sp3 = wp.lock()) {
        sp3->use();
    }

    return 0;
}

// Lambda Expressions
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

int main() {
    // Basic lambda
    auto greet = [](string name) {
        cout << "Hello, " << name << "!" << endl;
    };
    greet("Alice");

    // Capture by value and reference
    int x = 10, y = 20;
    auto addXY  = [x, y]()  { return x + y; };
    auto modifyX = [&x]()   { x *= 2; };

    cout << "addXY: " << addXY() << endl;
    modifyX();
    cout << "x after modifyX: " << x << endl;

    // Lambda with STL
    vector<int> nums = {5, 1, 8, 3, 9, 2, 7};
    sort(nums.begin(), nums.end(), [](int a, int b){ return a < b; });
    for (int n : nums) cout << n << " ";
    cout << endl;

    // filter with lambda
    vector<int> evens;
    copy_if(nums.begin(), nums.end(), back_inserter(evens),
            [](int n){ return n % 2 == 0; });
    for (int n : evens) cout << n << " ";
    cout << endl;

    // std::function
    function<int(int,int)> multiply = [](int a, int b){ return a * b; };
    cout << "3 * 4 = " << multiply(3, 4) << endl;

    return 0;
}

// Move Semantics and Rvalue References
#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Buffer {
    int *data;
    size_t size;
public:
    Buffer(size_t n) : size(n), data(new int[n]) {
        cout << "Constructed, size=" << n << endl;
    }

    // Copy constructor
    Buffer(const Buffer &other) : size(other.size), data(new int[other.size]) {
        copy(other.data, other.data + size, data);
        cout << "Copied" << endl;
    }

    // Move constructor
    Buffer(Buffer &&other) noexcept : size(other.size), data(other.data) {
        other.data = nullptr;
        other.size = 0;
        cout << "Moved" << endl;
    }

    ~Buffer() { delete[] data; cout << "Destroyed" << endl; }
};

int main() {
    Buffer b1(10);
    Buffer b2 = b1;            // copy
    Buffer b3 = move(b1);      // move (no copy!)

    // Move with strings
    string s1 = "Hello, World!";
    string s2 = move(s1);  // s1 is now empty
    cout << "s2: " << s2 << endl;
    cout << "s1 empty: " << s1.empty() << endl;

    return 0;
}

// File I/O with fstream
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

struct Student {
    string name;
    int age;
    double gpa;
};

int main() {
    // Write to file
    ofstream outFile("students.txt");
    outFile << "Alice 20 3.85" << endl;
    outFile << "Bob 22 3.62"   << endl;
    outFile << "Carol 21 3.91" << endl;
    outFile.close();

    // Read from file
    ifstream inFile("students.txt");
    vector<Student> students;
    Student s;
    while (inFile >> s.name >> s.age >> s.gpa) {
        students.push_back(s);
    }
    inFile.close();

    for (auto &st : students)
        cout << st.name << " | Age:" << st.age
             << " | GPA:" << st.gpa << endl;

    // stringstream
    string data = "John 25 3.50";
    istringstream iss(data);
    Student s2;
    iss >> s2.name >> s2.age >> s2.gpa;
    cout << "Parsed: " << s2.name << " " << s2.gpa << endl;

    return 0;
}

// STL Algorithms
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

int main() {
    vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};

    // sort and unique
    sort(v.begin(), v.end());
    auto last = unique(v.begin(), v.end());
    v.erase(last, v.end());
    for (int x : v) cout << x << " ";
    cout << endl;

    // accumulate, min, max
    cout << "Sum: "  << accumulate(v.begin(), v.end(), 0) << endl;
    cout << "Min: "  << *min_element(v.begin(), v.end()) << endl;
    cout << "Max: "  << *max_element(v.begin(), v.end()) << endl;

    // count_if and find_if
    int evens = count_if(v.begin(), v.end(), [](int x){ return x%2==0; });
    cout << "Evens: " << evens << endl;

    auto it = find_if(v.begin(), v.end(), [](int x){ return x > 4; });
    if (it != v.end()) cout << "First > 4: " << *it << endl;

    // transform
    vector<int> doubled(v.size());
    transform(v.begin(), v.end(), doubled.begin(), [](int x){ return x*2; });
    for (int x : doubled) cout << x << " ";
    cout << endl;

    return 0;
}

// Linked List in C++
#include <iostream>
using namespace std;

template <typename T>
struct Node {
    T data;
    Node *next;
    Node(T d) : data(d), next(nullptr) {}
};

template <typename T>
class LinkedList {
    Node<T> *head;
public:
    LinkedList() : head(nullptr) {}

    void pushFront(T val) {
        Node<T> *node = new Node<T>(val);
        node->next = head;
        head = node;
    }

    void pushBack(T val) {
        Node<T> *node = new Node<T>(val);
        if (!head) { head = node; return; }
        Node<T> *curr = head;
        while (curr->next) curr = curr->next;
        curr->next = node;
    }

    void display() const {
        Node<T> *curr = head;
        while (curr) {
            cout << curr->data << " -> ";
            curr = curr->next;
        }
        cout << "nullptr" << endl;
    }

    ~LinkedList() {
        while (head) {
            Node<T> *tmp = head;
            head = head->next;
            delete tmp;
        }
    }
};

int main() {
    LinkedList<int> list;
    list.pushBack(10);
    list.pushBack(20);
    list.pushBack(30);
    list.pushFront(5);
    list.display();
    return 0;
}

// Stack and Queue using STL
#include <iostream>
#include <stack>
#include <queue>
#include <deque>
using namespace std;

int main() {
    // Stack
    stack<int> st;
    st.push(10); st.push(20); st.push(30);
    cout << "Stack top: " << st.top() << endl;
    while (!st.empty()) {
        cout << st.top() << " ";
        st.pop();
    }
    cout << endl;

    // Queue
    queue<int> q;
    q.push(10); q.push(20); q.push(30);
    cout << "Queue front: " << q.front() << endl;
    while (!q.empty()) {
        cout << q.front() << " ";
        q.pop();
    }
    cout << endl;

    // Deque (double-ended)
    deque<int> dq;
    dq.push_front(1); dq.push_back(2);
    dq.push_front(0); dq.push_back(3);
    for (int x : dq) cout << x << " ";
    cout << endl;  // 0 1 2 3

    return 0;
}

// Binary Search in C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Manual binary search
int binarySearch(vector<int> &arr, int target) {
    int left = 0, right = arr.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

int main() {
    vector<int> arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};

    // Manual
    cout << "Index of 23: " << binarySearch(arr, 23) << endl;

    // STL binary_search
    cout << "Contains 56: " << binary_search(arr.begin(), arr.end(), 56) << endl;

    // lower_bound and upper_bound
    auto lb = lower_bound(arr.begin(), arr.end(), 16);
    auto ub = upper_bound(arr.begin(), arr.end(), 16);
    cout << "lower_bound(16): index " << (lb - arr.begin()) << endl;
    cout << "upper_bound(16): index " << (ub - arr.begin()) << endl;

    return 0;
}

// Sorting Algorithms in C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void bubbleSort(vector<int> &arr) {
    int n = arr.size();
    for (int i = 0; i < n-1; i++) {
        bool swapped = false;
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                swap(arr[j], arr[j+1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

void mergeSort(vector<int> &arr, int l, int r) {
    if (l >= r) return;
    int m = l + (r-l)/2;
    mergeSort(arr, l, m);
    mergeSort(arr, m+1, r);
    vector<int> tmp;
    int i=l, j=m+1;
    while (i<=m && j<=r)
        tmp.push_back(arr[i]<=arr[j] ? arr[i++] : arr[j++]);
    while (i<=m) tmp.push_back(arr[i++]);
    while (j<=r) tmp.push_back(arr[j++]);
    for (int k=l; k<=r; k++) arr[k] = tmp[k-l];
}

int main() {
    vector<int> v1 = {64, 34, 25, 12, 22, 11, 90};
    bubbleSort(v1);
    for (int x : v1) cout << x << " ";
    cout << endl;

    vector<int> v2 = {38, 27, 43, 3, 9, 82, 10};
    mergeSort(v2, 0, v2.size()-1);
    for (int x : v2) cout << x << " ";
    cout << endl;

    // STL sort
    vector<int> v3 = {5,3,1,8,2,7};
    sort(v3.begin(), v3.end());
    for (int x : v3) cout << x << " ";
    cout << endl;
    return 0;
}

// Recursion in C++
#include <iostream>
using namespace std;

int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n-1);
}

int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n-1) + fibonacci(n-2);
}

void hanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        cout << "Move disk 1: " << from << " -> " << to << endl;
        return;
    }
    hanoi(n-1, from, aux, to);
    cout << "Move disk " << n << ": " << from << " -> " << to << endl;
    hanoi(n-1, aux, to, from);
}

int power(int base, int exp) {
    if (exp == 0) return 1;
    if (exp % 2 == 0) {
        int half = power(base, exp/2);
        return half * half;
    }
    return base * power(base, exp-1);
}

int main() {
    cout << "5! = "    << factorial(5) << endl;
    cout << "fib(8) = " << fibonacci(8) << endl;
    cout << "2^10 = "  << power(2, 10) << endl;
    cout << "Tower of Hanoi (3 disks):" << endl;
    hanoi(3, 'A', 'C', 'B');
    return 0;
}

// Dynamic Memory - new and delete
#include <iostream>
#include <memory>
using namespace std;

class Matrix {
    int **data;
    int rows, cols;
public:
    Matrix(int r, int c) : rows(r), cols(c) {
        data = new int*[rows];
        for (int i = 0; i < rows; i++)
            data[i] = new int[cols]();
    }

    void set(int r, int c, int val) { data[r][c] = val; }
    int  get(int r, int c) const    { return data[r][c]; }

    void print() const {
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++)
                cout << data[i][j] << " ";
            cout << endl;
        }
    }

    ~Matrix() {
        for (int i = 0; i < rows; i++) delete[] data[i];
        delete[] data;
    }
};

int main() {
    // Single value
    int *p = new int(42);
    cout << "Value: " << *p << endl;
    delete p;

    // Array
    int *arr = new int[5]{10, 20, 30, 40, 50};
    for (int i = 0; i < 5; i++) cout << arr[i] << " ";
    cout << endl;
    delete[] arr;

    // Class
    Matrix m(3, 3);
    m.set(0, 0, 1); m.set(1, 1, 5); m.set(2, 2, 9);
    m.print();
    return 0;
}

// String Operations in C++
#include <iostream>
#include <string>
#include <algorithm>
#include <sstream>
using namespace std;

int main() {
    string s = "Hello, World!";

    // Basic operations
    cout << "Length: "   << s.length()       << endl;
    cout << "Substr: "   << s.substr(7, 5)   << endl;
    cout << "Find: "     << s.find("World")  << endl;

    // Modify
    string t = s;
    replace(t.begin(), t.end(), 'l', 'L');
    cout << "Replaced: " << t << endl;

    // Case conversion
    string upper = s;
    transform(upper.begin(), upper.end(), upper.begin(), ::toupper);
    cout << "Upper: " << upper << endl;

    // Split using stringstream
    string csv = "Alice,Bob,Carol,Dave";
    stringstream ss(csv);
    string token;
    while (getline(ss, token, ','))
        cout << token << " ";
    cout << endl;

    // Reverse and palindrome check
    string rev = s;
    reverse(rev.begin(), rev.end());
    cout << "Reversed: " << rev << endl;

    string pal = "racecar";
    string revpal = pal;
    reverse(revpal.begin(), revpal.end());
    cout << pal << " is" << (pal == revpal ? "" : " not") << " palindrome" << endl;

    return 0;
}

// Multiple Inheritance and Virtual Base
#include <iostream>
using namespace std;

class Vehicle {
public:
    int speed;
    Vehicle(int s) : speed(s) {}
    virtual void move() { cout << "Moving at " << speed << endl; }
};

class Electric {
public:
    int battery;
    Electric(int b) : battery(b) {}
    virtual void charge() { cout << "Charging battery: " << battery << "%" << endl; }
};

// Multiple inheritance
class ElectricCar : public Vehicle, public Electric {
    string model;
public:
    ElectricCar(string m, int s, int b)
        : Vehicle(s), Electric(b), model(m) {}

    void display() {
        cout << "Model: "   << model   << endl;
        cout << "Speed: "   << speed   << " km/h" << endl;
        cout << "Battery: " << battery << "%" << endl;
    }

    void move() override {
        cout << model << " glides silently at " << speed << " km/h" << endl;
    }
};

int main() {
    ElectricCar tesla("Tesla Model 3", 250, 85);
    tesla.display();
    tesla.move();
    tesla.charge();
    return 0;
}

// Abstract Classes and Interfaces
#include <iostream>
#include <vector>
#include <memory>
using namespace std;

// Interface (pure abstract class)
class IDrawable {
public:
    virtual void draw()    const = 0;
    virtual void resize(double factor) = 0;
    virtual double getArea() const = 0;
    virtual ~IDrawable() {}
};

class Circle : public IDrawable {
    double radius;
public:
    Circle(double r) : radius(r) {}
    void draw()    const override { cout << "Drawing Circle r=" << radius << endl; }
    void resize(double f) override { radius *= f; }
    double getArea() const override { return 3.14159 * radius * radius; }
};

class Square : public IDrawable {
    double side;
public:
    Square(double s) : side(s) {}
    void draw()    const override { cout << "Drawing Square s=" << side << endl; }
    void resize(double f) override { side *= f; }
    double getArea() const override { return side * side; }
};

int main() {
    vector<unique_ptr<IDrawable>> shapes;
    shapes.push_back(make_unique<Circle>(5.0));
    shapes.push_back(make_unique<Square>(4.0));

    for (auto &s : shapes) {
        s->draw();
        cout << "Area: " << s->getArea() << endl;
        s->resize(2.0);
        s->draw();
        cout << "New Area: " << s->getArea() << endl;
    }
    return 0;
}

// Iterators and Range-Based Loops
#include <iostream>
#include <vector>
#include <list>
#include <map>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3, 4, 5};

    // Iterator
    for (auto it = v.begin(); it != v.end(); ++it)
        cout << *it << " ";
    cout << endl;

    // Reverse iterator
    for (auto it = v.rbegin(); it != v.rend(); ++it)
        cout << *it << " ";
    cout << endl;

    // Range-based for
    for (const auto &x : v) cout << x << " ";
    cout << endl;

    // List iterator
    list<string> lst = {"alpha","beta","gamma"};
    for (auto &s : lst) cout << s << " ";
    cout << endl;

    // Map iterator
    map<string,int> m = {{"a",1},{"b",2},{"c",3}};
    for (auto it = m.begin(); it != m.end(); ++it)
        cout << it->first << "=" << it->second << " ";
    cout << endl;

    // Structured bindings C++17
    for (auto &[key, val] : m)
        cout << key << "->" << val << " ";
    cout << endl;

    return 0;
}

// Design Patterns - Singleton and Factory
#include <iostream>
#include <memory>
#include <string>
using namespace std;

// Singleton
class Config {
    static Config *instance;
    string dbUrl = "localhost:5432";
    Config() {}
public:
    static Config* getInstance() {
        if (!instance) instance = new Config();
        return instance;
    }
    string getDbUrl() const { return dbUrl; }
    void setDbUrl(string url) { dbUrl = url; }
};
Config* Config::instance = nullptr;

// Factory Pattern
class Logger {
public:
    virtual void log(const string &msg) = 0;
    virtual ~Logger() {}
};

class ConsoleLogger : public Logger {
public:
    void log(const string &msg) override {
        cout << "[CONSOLE] " << msg << endl;
    }
};

class FileLogger : public Logger {
public:
    void log(const string &msg) override {
        cout << "[FILE] " << msg << endl;
    }
};

unique_ptr<Logger> createLogger(const string &type) {
    if (type == "console") return make_unique<ConsoleLogger>();
    if (type == "file")    return make_unique<FileLogger>();
    return nullptr;
}

int main() {
    Config *cfg = Config::getInstance();
    cout << cfg->getDbUrl() << endl;

    auto logger = createLogger("console");
    logger->log("App started");

    auto flog = createLogger("file");
    flog->log("Error occurred");
    return 0;
}

// Namespaces in C++
#include <iostream>
#include <string>
using namespace std;

namespace Math {
    const double PI = 3.14159265;

    double circleArea(double r) { return PI * r * r; }
    double rectArea(double w, double h) { return w * h; }

    namespace Advanced {
        double power(double base, int exp) {
            double result = 1;
            for (int i = 0; i < exp; i++) result *= base;
            return result;
        }
    }
}

namespace Physics {
    const double G = 9.81;
    double kineticEnergy(double m, double v) { return 0.5 * m * v * v; }
    double weight(double mass) { return mass * G; }
}

int main() {
    cout << "PI = "          << Math::PI << endl;
    cout << "Circle area = " << Math::circleArea(5.0) << endl;
    cout << "2^8 = "         << Math::Advanced::power(2, 8) << endl;
    cout << "Weight(70kg) = "<< Physics::weight(70) << " N" << endl;

    // using declaration
    using Math::rectArea;
    cout << "Rect area = " << rectArea(4, 5) << endl;

    return 0;
}

// Two Sum Problem in C++
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

// Hash map approach O(n)
vector<int> twoSum(vector<int> &nums, int target) {
    unordered_map<int, int> mp;
    for (int i = 0; i < (int)nums.size(); i++) {
        int complement = target - nums[i];
        if (mp.count(complement))
            return {mp[complement], i};
        mp[nums[i]] = i;
    }
    return {};
}

// Two pointer (sorted input)
vector<pair<int,int>> twoSumPairs(vector<int> arr, int target) {
    vector<pair<int,int>> result;
    int l = 0, r = arr.size() - 1;
    while (l < r) {
        int sum = arr[l] + arr[r];
        if (sum == target) { result.push_back({arr[l], arr[r]}); l++; r--; }
        else if (sum < target) l++;
        else r--;
    }
    return result;
}

int main() {
    vector<int> nums = {2, 7, 11, 15};
    auto res = twoSum(nums, 9);
    cout << "Indices: [" << res[0] << ", " << res[1] << "]" << endl;

    vector<int> sorted = {1, 2, 3, 4, 6};
    for (auto [a,b] : twoSumPairs(sorted, 6))
        cout << "Pair: " << a << " + " << b << endl;
    return 0;
}

// Kadane's Algorithm in C++
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

pair<int, pair<int,int>> maxSubarray(vector<int> &arr) {
    int maxSum = INT_MIN, currSum = 0;
    int start = 0, end = 0, tempStart = 0;

    for (int i = 0; i < (int)arr.size(); i++) {
        currSum += arr[i];
        if (currSum > maxSum) {
            maxSum = currSum;
            start  = tempStart;
            end    = i;
        }
        if (currSum < 0) {
            currSum   = 0;
            tempStart = i + 1;
        }
    }
    return {maxSum, {start, end}};
}

int main() {
    vector<int> arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    auto [sum, range] = maxSubarray(arr);
    auto [s, e] = range;

    cout << "Max Sum: " << sum << endl;
    cout << "Subarray: ";
    for (int i = s; i <= e; i++) cout << arr[i] << " ";
    cout << endl;
    return 0;
}

// Binary Tree in C++
#include <iostream>
#include <queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

class BinaryTree {
    TreeNode *root;

    void inorder(TreeNode *node) {
        if (!node) return;
        inorder(node->left);
        cout << node->val << " ";
        inorder(node->right);
    }

    int height(TreeNode *node) {
        if (!node) return 0;
        return 1 + max(height(node->left), height(node->right));
    }

public:
    BinaryTree() : root(nullptr) {}

    void insert(int val) {
        TreeNode *node = new TreeNode(val);
        if (!root) { root = node; return; }
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            auto curr = q.front(); q.pop();
            if (!curr->left)  { curr->left  = node; return; }
            else q.push(curr->left);
            if (!curr->right) { curr->right = node; return; }
            else q.push(curr->right);
        }
    }

    void inorder()       { inorder(root); cout << endl; }
    int  height()        { return height(root); }
};

int main() {
    BinaryTree bt;
    for (int v : {1,2,3,4,5,6,7}) bt.insert(v);
    bt.inorder();
    cout << "Height: " << bt.height() << endl;
    return 0;
}

// Binary Search Tree in C++
#include <iostream>
#include <vector>
using namespace std;

struct BST {
    int val;
    BST *left, *right;
    BST(int v) : val(v), left(nullptr), right(nullptr) {}
};

BST* insert(BST *root, int val) {
    if (!root) return new BST(val);
    if (val < root->val) root->left  = insert(root->left, val);
    else if (val > root->val) root->right = insert(root->right, val);
    return root;
}

bool search(BST *root, int val) {
    if (!root) return false;
    if (root->val == val) return true;
    return val < root->val ? search(root->left, val)
                           : search(root->right, val);
}

void inorder(BST *root) {
    if (!root) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

int main() {
    BST *root = nullptr;
    for (int v : {50, 30, 70, 20, 40, 60, 80})
        root = insert(root, v);

    inorder(root); cout << endl;
    cout << "Search 40: " << (search(root, 40) ? "Found" : "Not found") << endl;
    cout << "Search 99: " << (search(root, 99) ? "Found" : "Not found") << endl;
    return 0;
}

// Graph BFS and DFS in C++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Graph {
    int V;
    vector<vector<int>> adj;
public:
    Graph(int v) : V(v), adj(v) {}

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    void bfs(int start) {
        vector<bool> visited(V, false);
        queue<int> q;
        visited[start] = true;
        q.push(start);
        cout << "BFS: ";
        while (!q.empty()) {
            int v = q.front(); q.pop();
            cout << v << " ";
            for (int u : adj[v])
                if (!visited[u]) { visited[u] = true; q.push(u); }
        }
        cout << endl;
    }

    void dfsHelper(int v, vector<bool> &visited) {
        visited[v] = true;
        cout << v << " ";
        for (int u : adj[v])
            if (!visited[u]) dfsHelper(u, visited);
    }

    void dfs(int start) {
        vector<bool> visited(V, false);
        cout << "DFS: ";
        dfsHelper(start, visited);
        cout << endl;
    }
};

int main() {
    Graph g(6);
    g.addEdge(0,1); g.addEdge(0,2);
    g.addEdge(1,3); g.addEdge(2,4); g.addEdge(3,5);
    g.bfs(0);
    g.dfs(0);
    return 0;
}

// Dijkstra's Algorithm in C++
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

typedef pair<int,int> pii;

void dijkstra(vector<vector<pii>> &graph, int src, int V) {
    vector<int> dist(V, INT_MAX);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    dist[src] = 0;
    pq.push({0, src});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto [w, v] : graph[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    cout << "Shortest distances from " << src << ":" << endl;
    for (int i = 0; i < V; i++)
        cout << "  To " << i << ": " << (dist[i]==INT_MAX ? -1 : dist[i]) << endl;
}

int main() {
    int V = 5;
    vector<vector<pii>> graph(V);
    auto addEdge = [&](int u, int v, int w) {
        graph[u].push_back({w, v});
        graph[v].push_back({w, u});
    };
    addEdge(0,1,10); addEdge(0,3,5);
    addEdge(1,2,1);  addEdge(1,3,2);
    addEdge(2,4,4);  addEdge(3,4,9);
    dijkstra(graph, 0, V);
    return 0;
}

// Dynamic Programming - Classic Problems
#include <iostream>
#include <vector>
#include <string>
using namespace std;

// 0/1 Knapsack
int knapsack(vector<int> &w, vector<int> &v, int W) {
    int n = w.size();
    vector<vector<int>> dp(n+1, vector<int>(W+1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= W; j++) {
            dp[i][j] = dp[i-1][j];
            if (w[i-1] <= j)
                dp[i][j] = max(dp[i][j], dp[i-1][j-w[i-1]] + v[i-1]);
        }
    return dp[n][W];
}

// Longest Common Subsequence
int lcs(string &s1, string &s2) {
    int m = s1.size(), n = s2.size();
    vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            dp[i][j] = s1[i-1]==s2[j-1] ? dp[i-1][j-1]+1
                                         : max(dp[i-1][j], dp[i][j-1]);
    return dp[m][n];
}

int main() {
    vector<int> weights = {1, 3, 4, 5};
    vector<int> values  = {1, 4, 5, 7};
    cout << "Knapsack(W=7): " << knapsack(weights, values, 7) << endl;

    string s1 = "ABCBDAB", s2 = "BDCAB";
    cout << "LCS: " << lcs(s1, s2) << endl;
    return 0;
}

// Hash Map - Custom Implementation
#include <iostream>
#include <list>
#include <vector>
#include <string>
using namespace std;

template <typename K, typename V>
class HashMap {
    int capacity;
    vector<list<pair<K,V>>> table;

    int hashFn(K key) {
        return hash<K>{}(key) % capacity;
    }

public:
    HashMap(int cap = 16) : capacity(cap), table(cap) {}

    void put(K key, V val) {
        int idx = hashFn(key);
        for (auto &[k,v] : table[idx])
            if (k == key) { v = val; return; }
        table[idx].push_back({key, val});
    }

    V get(K key) {
        int idx = hashFn(key);
        for (auto &[k,v] : table[idx])
            if (k == key) return v;
        throw runtime_error("Key not found");
    }

    bool contains(K key) {
        int idx = hashFn(key);
        for (auto &[k,v] : table[idx])
            if (k == key) return true;
        return false;
    }

    void remove(K key) {
        int idx = hashFn(key);
        table[idx].remove_if([&](auto &p){ return p.first == key; });
    }
};

int main() {
    HashMap<string,int> mp;
    mp.put("alice", 90); mp.put("bob", 85); mp.put("carol", 92);
    cout << "alice: " << mp.get("alice") << endl;
    cout << "Contains bob: " << mp.contains("bob") << endl;
    mp.remove("bob");
    cout << "Contains bob after remove: " << mp.contains("bob") << endl;
    return 0;
}

// Heap and Priority Queue in C++
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

// K largest elements
vector<int> kLargest(vector<int> arr, int k) {
    priority_queue<int, vector<int>, greater<int>> minHeap;
    for (int x : arr) {
        minHeap.push(x);
        if ((int)minHeap.size() > k) minHeap.pop();
    }
    vector<int> res;
    while (!minHeap.empty()) { res.push_back(minHeap.top()); minHeap.pop(); }
    return res;
}

// Merge K sorted arrays
vector<int> mergeKSorted(vector<vector<int>> &arrays) {
    priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<>> pq;
    for (int i = 0; i < (int)arrays.size(); i++)
        if (!arrays[i].empty()) pq.push({arrays[i][0], i, 0});

    vector<int> result;
    while (!pq.empty()) {
        auto [val, i, j] = pq.top(); pq.pop();
        result.push_back(val);
        if (j+1 < (int)arrays[i].size())
            pq.push({arrays[i][j+1], i, j+1});
    }
    return result;
}

int main() {
    vector<int> arr = {3,1,5,12,2,11,9};
    auto top3 = kLargest(arr, 3);
    cout << "Top 3: ";
    for (int x : top3) cout << x << " ";
    cout << endl;

    vector<vector<int>> kArr = {{1,4,7},{2,5,8},{3,6,9}};
    auto merged = mergeKSorted(kArr);
    for (int x : merged) cout << x << " ";
    cout << endl;
    return 0;
}

// Trie Data Structure in C++
#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

class TrieNode {
public:
    unordered_map<char, TrieNode*> children;
    bool isEnd = false;
};

class Trie {
    TrieNode *root;
public:
    Trie() : root(new TrieNode()) {}

    void insert(const string &word) {
        TrieNode *curr = root;
        for (char c : word) {
            if (!curr->children.count(c))
                curr->children[c] = new TrieNode();
            curr = curr->children[c];
        }
        curr->isEnd = true;
    }

    bool search(const string &word) {
        TrieNode *curr = root;
        for (char c : word) {
            if (!curr->children.count(c)) return false;
            curr = curr->children[c];
        }
        return curr->isEnd;
    }

    bool startsWith(const string &prefix) {
        TrieNode *curr = root;
        for (char c : prefix) {
            if (!curr->children.count(c)) return false;
            curr = curr->children[c];
        }
        return true;
    }
};

int main() {
    Trie t;
    t.insert("apple"); t.insert("app"); t.insert("apply");
    cout << t.search("apple")      << endl;  // 1
    cout << t.search("app")        << endl;  // 1
    cout << t.search("ap")         << endl;  // 0
    cout << t.startsWith("appl")   << endl;  // 1
    cout << t.startsWith("xyz")    << endl;  // 0
    return 0;
}

// Segment Tree in C++
#include <iostream>
#include <vector>
using namespace std;

class SegmentTree {
    vector<int> tree;
    int n;

    void build(vector<int> &arr, int node, int l, int r) {
        if (l == r) { tree[node] = arr[l]; return; }
        int mid = (l+r)/2;
        build(arr, 2*node, l, mid);
        build(arr, 2*node+1, mid+1, r);
        tree[node] = tree[2*node] + tree[2*node+1];
    }

    void update(int node, int l, int r, int idx, int val) {
        if (l == r) { tree[node] = val; return; }
        int mid = (l+r)/2;
        if (idx <= mid) update(2*node, l, mid, idx, val);
        else            update(2*node+1, mid+1, r, idx, val);
        tree[node] = tree[2*node] + tree[2*node+1];
    }

    int query(int node, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return 0;
        if (ql <= l && r <= qr) return tree[node];
        int mid = (l+r)/2;
        return query(2*node, l, mid, ql, qr) +
               query(2*node+1, mid+1, r, ql, qr);
    }

public:
    SegmentTree(vector<int> &arr) : n(arr.size()), tree(4*arr.size()) {
        build(arr, 1, 0, n-1);
    }
    void update(int idx, int val) { update(1, 0, n-1, idx, val); }
    int  query(int l, int r)      { return query(1, 0, n-1, l, r); }
};

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11};
    SegmentTree st(arr);
    cout << "Sum [1,3]: "  << st.query(1, 3) << endl;  // 15
    st.update(1, 10);
    cout << "Sum [1,3] after update: " << st.query(1, 3) << endl; // 22
    return 0;
}

// Union-Find in C++
#include <iostream>
#include <vector>
using namespace std;

class UnionFind {
    vector<int> parent, rank;
public:
    UnionFind(int n) : parent(n), rank(n, 0) {
        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];
    }

    bool unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        if (rank[px] < rank[py]) swap(px, py);
        parent[py] = px;
        if (rank[px] == rank[py]) rank[px]++;
        return true;
    }

    bool connected(int x, int y) { return find(x) == find(y); }
};

int main() {
    UnionFind uf(6);
    uf.unite(0, 1); uf.unite(1, 2); uf.unite(3, 4);
    cout << "0-2: " << uf.connected(0, 2) << endl;  // 1
    cout << "0-3: " << uf.connected(0, 3) << endl;  // 0
    uf.unite(2, 3);
    cout << "0-4 after merge: " << uf.connected(0, 4) << endl;  // 1
    return 0;
}

// Sliding Window Maximum in C++
#include <iostream>
#include <vector>
#include <deque>
using namespace std;

vector<int> maxSlidingWindow(vector<int> &nums, int k) {
    deque<int> dq;  // stores indices
    vector<int> result;

    for (int i = 0; i < (int)nums.size(); i++) {
        // Remove out-of-window indices
        while (!dq.empty() && dq.front() < i - k + 1)
            dq.pop_front();

        // Remove smaller elements from rear
        while (!dq.empty() && nums[dq.back()] < nums[i])
            dq.pop_back();

        dq.push_back(i);

        if (i >= k - 1) result.push_back(nums[dq.front()]);
    }
    return result;
}

int main() {
    vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;
    auto res = maxSlidingWindow(nums, k);
    cout << "Sliding window max: ";
    for (int x : res) cout << x << " ";
    cout << endl;  // 3 3 5 5 6 7
    return 0;
}

// KMP String Matching in C++
#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<int> buildLPS(const string &pattern) {
    int m = pattern.size();
    vector<int> lps(m, 0);
    int len = 0, i = 1;
    while (i < m) {
        if (pattern[i] == pattern[len]) lps[i++] = ++len;
        else if (len) len = lps[len-1];
        else lps[i++] = 0;
    }
    return lps;
}

vector<int> kmpSearch(const string &text, const string &pattern) {
    vector<int> positions;
    vector<int> lps = buildLPS(pattern);
    int n = text.size(), m = pattern.size();
    int i = 0, j = 0;

    while (i < n) {
        if (text[i] == pattern[j]) { i++; j++; }
        if (j == m) {
            positions.push_back(i - j);
            j = lps[j-1];
        } else if (i < n && text[i] != pattern[j]) {
            if (j) j = lps[j-1];
            else i++;
        }
    }
    return positions;
}

int main() {
    string text = "AABAACAADAABAABA";
    string pat  = "AABA";
    auto pos = kmpSearch(text, pat);
    cout << "Pattern found at: ";
    for (int p : pos) cout << p << " ";
    cout << endl;
    return 0;
}

// N-Queens in C++
#include <iostream>
#include <vector>
using namespace std;

class NQueens {
    int n;
    vector<vector<int>> board;
    int solutions = 0;

    bool isSafe(int row, int col) {
        for (int j = 0; j < col; j++)
            if (board[row][j]) return false;
        for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
            if (board[i][j]) return false;
        for (int i = row, j = col; i < n && j >= 0; i++, j--)
            if (board[i][j]) return false;
        return true;
    }

    void solve(int col) {
        if (col == n) {
            solutions++;
            if (solutions == 1) {
                for (auto &row : board) {
                    for (int x : row) cout << (x ? "Q " : ". ");
                    cout << endl;
                }
            }
            return;
        }
        for (int row = 0; row < n; row++) {
            if (isSafe(row, col)) {
                board[row][col] = 1;
                solve(col + 1);
                board[row][col] = 0;
            }
        }
    }

public:
    NQueens(int n) : n(n), board(n, vector<int>(n, 0)) {}
    void run() {
        solve(0);
        cout << "Total solutions: " << solutions << endl;
    }
};

int main() {
    NQueens q(8);
    q.run();
    return 0;
}

// LRU Cache in C++
#include <iostream>
#include <list>
#include <unordered_map>
using namespace std;

class LRUCache {
    int capacity;
    list<pair<int,int>> cache;  // {key, value}
    unordered_map<int, list<pair<int,int>>::iterator> mp;

public:
    LRUCache(int cap) : capacity(cap) {}

    int get(int key) {
        if (!mp.count(key)) return -1;
        cache.splice(cache.begin(), cache, mp[key]);
        return mp[key]->second;
    }

    void put(int key, int value) {
        if (mp.count(key)) {
            cache.splice(cache.begin(), cache, mp[key]);
            mp[key]->second = value;
            return;
        }
        if ((int)cache.size() == capacity) {
            auto last = cache.back();
            mp.erase(last.first);
            cache.pop_back();
        }
        cache.push_front({key, value});
        mp[key] = cache.begin();
    }
};

int main() {
    LRUCache lru(2);
    lru.put(1, 10); lru.put(2, 20);
    cout << lru.get(1) << endl;  // 10
    lru.put(3, 30);              // evicts key 2
    cout << lru.get(2) << endl;  // -1
    cout << lru.get(3) << endl;  // 30
    return 0;
}

// Graph - Topological Sort in C++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> topoSort(int V, vector<vector<int>> &adj) {
    vector<int> inDegree(V, 0);
    for (int u = 0; u < V; u++)
        for (int v : adj[u]) inDegree[v]++;

    queue<int> q;
    for (int i = 0; i < V; i++)
        if (inDegree[i] == 0) q.push(i);

    vector<int> order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u])
            if (--inDegree[v] == 0) q.push(v);
    }

    return order.size() == V ? order : vector<int>{};
}

int main() {
    int V = 6;
    vector<vector<int>> adj(V);
    adj[5].push_back(2); adj[5].push_back(0);
    adj[4].push_back(0); adj[4].push_back(1);
    adj[2].push_back(3); adj[3].push_back(1);

    auto order = topoSort(V, adj);
    cout << "Topological Order: ";
    for (int v : order) cout << v << " ";
    cout << endl;
    return 0;
}

// Bit Manipulation in C++
#include <iostream>
using namespace std;

bool isBitSet(int n, int p)  { return (n >> p) & 1; }
int  setBit(int n, int p)    { return n | (1 << p);  }
int  clearBit(int n, int p)  { return n & ~(1 << p); }
int  toggleBit(int n, int p) { return n ^ (1 << p);  }
int  countBits(int n) {
    int c = 0;
    while (n) { n &= n-1; c++; }
    return c;
}
bool isPowerOf2(int n)  { return n > 0 && !(n & (n-1)); }

// Find single non-duplicate (all others appear twice)
int findUnique(vector<int> &arr) {
    int res = 0;
    for (int x : arr) res ^= x;
    return res;
}

int main() {
    int n = 0b10110100;
    cout << "Number: "     << n            << endl;
    cout << "Bit 2 set? "  << isBitSet(n,2) << endl;
    cout << "Set bit 0: "  << setBit(n,0)   << endl;
    cout << "Clear bit 4: "<< clearBit(n,4) << endl;
    cout << "Toggle bit 7:"<< toggleBit(n,7)<< endl;
    cout << "Count bits: " << countBits(n)  << endl;
    cout << "isPow2(16): " << isPowerOf2(16)<< endl;

    vector<int> arr = {2,3,5,4,5,3,4};
    cout << "Unique: " << findUnique(arr) << endl;  // 2
    return 0;
}

// Number Theory in C++
#include <iostream>
#include <vector>
using namespace std;

int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }
int lcm(int a, int b) { return a / gcd(a,b) * b; }

bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i*i <= n; i++)
        if (n%i == 0) return false;
    return true;
}

vector<int> sieve(int limit) {
    vector<bool> notPrime(limit+1, false);
    notPrime[0] = notPrime[1] = true;
    for (int i = 2; i*i <= limit; i++)
        if (!notPrime[i])
            for (int j = i*i; j <= limit; j += i)
                notPrime[j] = true;
    vector<int> primes;
    for (int i = 2; i <= limit; i++)
        if (!notPrime[i]) primes.push_back(i);
    return primes;
}

long long modPow(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

int main() {
    cout << "GCD(48,18)=" << gcd(48,18) << endl;
    cout << "LCM(4,6)="   << lcm(4,6)   << endl;
    cout << "isPrime(17)=" << isPrime(17) << endl;

    auto primes = sieve(50);
    for (int p : primes) cout << p << " ";
    cout << endl;

    cout << "2^10 mod 1000 = " << modPow(2,10,1000) << endl;
    return 0;
}

// STL - Pair, Tuple, Array
#include <iostream>
#include <vector>
#include <array>
#include <tuple>
#include <algorithm>
using namespace std;

int main() {
    // pair
    pair<string,int> p = {"Alice", 90};
    cout << p.first << ": " << p.second << endl;

    vector<pair<string,int>> students = {
        {"Bob",85}, {"Alice",90}, {"Carol",92}
    };
    sort(students.begin(), students.end(),
         [](auto &a, auto &b){ return a.second > b.second; });
    for (auto &[name,score] : students)
        cout << name << ": " << score << endl;

    // tuple
    tuple<string,int,double> t = {"Dave", 25, 3.85};
    cout << get<0>(t) << " " << get<1>(t) << " " << get<2>(t) << endl;

    auto [name, age, gpa] = t;
    cout << name << " age=" << age << " gpa=" << gpa << endl;

    // array (fixed size, stack allocated)
    array<int,5> arr = {5,3,1,4,2};
    sort(arr.begin(), arr.end());
    for (int x : arr) cout << x << " ";
    cout << endl;

    return 0;
}

// Two Pointers Technique
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Container with most water
int maxWater(vector<int> &h) {
    int l = 0, r = h.size()-1, maxArea = 0;
    while (l < r) {
        maxArea = max(maxArea, min(h[l],h[r]) * (r-l));
        h[l] < h[r] ? l++ : r--;
    }
    return maxArea;
}

// 3-sum
vector<vector<int>> threeSum(vector<int> nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    for (int i = 0; i < (int)nums.size()-2; i++) {
        if (i > 0 && nums[i] == nums[i-1]) continue;
        int l = i+1, r = nums.size()-1;
        while (l < r) {
            int sum = nums[i]+nums[l]+nums[r];
            if (sum == 0) {
                res.push_back({nums[i],nums[l],nums[r]});
                while (l<r && nums[l]==nums[l+1]) l++;
                while (l<r && nums[r]==nums[r-1]) r--;
                l++; r--;
            } else if (sum < 0) l++;
            else r--;
        }
    }
    return res;
}

int main() {
    vector<int> h = {1,8,6,2,5,4,8,3,7};
    cout << "Max water: " << maxWater(h) << endl;  // 49

    vector<int> nums = {-1,0,1,2,-1,-4};
    for (auto &v : threeSum(nums)) {
        for (int x : v) cout << x << " ";
        cout << endl;
    }
    return 0;
}

// Backtracking in C++
#include <iostream>
#include <vector>
#include <string>
using namespace std;

// Generate all subsets
void subsets(vector<int> &nums, int idx,
             vector<int> &curr, vector<vector<int>> &res) {
    res.push_back(curr);
    for (int i = idx; i < (int)nums.size(); i++) {
        curr.push_back(nums[i]);
        subsets(nums, i+1, curr, res);
        curr.pop_back();
    }
}

// Generate permutations
void permute(vector<int> &nums, int start, vector<vector<int>> &res) {
    if (start == (int)nums.size()) { res.push_back(nums); return; }
    for (int i = start; i < (int)nums.size(); i++) {
        swap(nums[start], nums[i]);
        permute(nums, start+1, res);
        swap(nums[start], nums[i]);
    }
}

int main() {
    vector<int> nums = {1, 2, 3};
    vector<int> curr;
    vector<vector<int>> subRes;
    subsets(nums, 0, curr, subRes);
    cout << "Subsets (" << subRes.size() << "):" << endl;
    for (auto &s : subRes) {
        cout << "[ ";
        for (int x : s) cout << x << " ";
        cout << "]" << endl;
    }

    vector<vector<int>> permRes;
    permute(nums, 0, permRes);
    cout << "Permutations (" << permRes.size() << "):" << endl;
    for (auto &p : permRes) {
        for (int x : p) cout << x << " ";
        cout << endl;
    }
    return 0;
}

// Greedy Algorithms in C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Activity Selection
int activitySelection(vector<pair<int,int>> activities) {
    sort(activities.begin(), activities.end(),
         [](auto &a, auto &b){ return a.second < b.second; });
    int count = 1, lastEnd = activities[0].second;
    for (int i = 1; i < (int)activities.size(); i++) {
        if (activities[i].first >= lastEnd) {
            count++;
            lastEnd = activities[i].second;
        }
    }
    return count;
}

// Fractional Knapsack
double fractionalKnapsack(vector<pair<int,int>> items, int W) {
    sort(items.begin(), items.end(), [](auto &a, auto &b){
        return (double)a.first/a.second > (double)b.first/b.second;
    });
    double total = 0;
    for (auto &[val, wt] : items) {
        if (W >= wt) { total += val; W -= wt; }
        else { total += (double)val/wt * W; break; }
    }
    return total;
}

int main() {
    vector<pair<int,int>> acts = {{1,3},{2,5},{4,6},{6,8},{5,7}};
    cout << "Max activities: " << activitySelection(acts) << endl;

    // {value, weight}
    vector<pair<int,int>> items = {{60,10},{100,20},{120,30}};
    cout << "Max value (W=50): " << fractionalKnapsack(items, 50) << endl;
    return 0;
}

// Type Traits and SFINAE in C++
#include <iostream>
#include <type_traits>
#include <vector>
using namespace std;

// enable_if to restrict template
template <typename T>
typename enable_if<is_integral<T>::value, bool>::type
isEven(T n) { return n % 2 == 0; }

// if_constexpr C++17
template <typename T>
void printType(T val) {
    if constexpr (is_integral_v<T>)
        cout << "Integer: " << val << endl;
    else if constexpr (is_floating_point_v<T>)
        cout << "Float: "   << val << endl;
    else
        cout << "Other: "   << val << endl;
}

// Variadic template
template <typename T>
T sum(T val) { return val; }

template <typename T, typename ...Args>
T sum(T first, Args... rest) {
    return first + sum(rest...);
}

int main() {
    cout << isEven(42) << endl;   // 1
    cout << isEven(7)  << endl;   // 0

    printType(42);
    printType(3.14);
    printType("hello");

    cout << "Sum: " << sum(1, 2, 3, 4, 5) << endl;  // 15
    return 0;
}

// Observer Design Pattern in C++
#include <iostream>
#include <vector>
#include <string>
#include <memory>
using namespace std;

// Observer interface
class Observer {
public:
    virtual void update(const string &event, int data) = 0;
    virtual ~Observer() {}
};

// Subject
class StockMarket {
    vector<Observer*> observers;
    int price;
    string symbol;
public:
    StockMarket(string s, int p) : symbol(s), price(p) {}

    void subscribe(Observer *o)   { observers.push_back(o); }
    void unsubscribe(Observer *o) {
        observers.erase(remove(observers.begin(), observers.end(), o),
                        observers.end());
    }

    void setPrice(int newPrice) {
        price = newPrice;
        for (auto *o : observers)
            o->update(symbol, price);
    }
};

class Investor : public Observer {
    string name;
public:
    Investor(string n) : name(n) {}
    void update(const string &sym, int price) override {
        cout << name << " notified: " << sym << " = $" << price << endl;
    }
};

int main() {
    StockMarket apple("AAPL", 150);
    Investor alice("Alice"), bob("Bob");

    apple.subscribe(&alice);
    apple.subscribe(&bob);
    apple.setPrice(155);

    apple.unsubscribe(&bob);
    apple.setPrice(160);
    return 0;
}

// RAII and Resource Management
#include <iostream>
#include <fstream>
#include <mutex>
#include <stdexcept>
using namespace std;

// RAII File Handler
class FileHandler {
    fstream file;
    string filename;
public:
    FileHandler(const string &name, ios::openmode mode)
        : filename(name) {
        file.open(name, mode);
        if (!file.is_open())
            throw runtime_error("Cannot open: " + name);
        cout << "File opened: " << name << endl;
    }

    void write(const string &data) { file << data << endl; }
    string read() {
        string content((istreambuf_iterator<char>(file)),
                        istreambuf_iterator<char>());
        return content;
    }

    ~FileHandler() {
        if (file.is_open()) {
            file.close();
            cout << "File closed: " << filename << endl;
        }
    }
};

// RAII Mutex Lock Guard
class LockGuard {
    mutex &mtx;
public:
    LockGuard(mutex &m) : mtx(m) { mtx.lock(); cout << "Locked" << endl; }
    ~LockGuard() { mtx.unlock(); cout << "Unlocked" << endl; }
};

int main() {
    {
        FileHandler fh("test.txt", ios::out);
        fh.write("Hello RAII!");
        fh.write("Line 2");
    }  // auto-closed here

    mutex m;
    {
        LockGuard lg(m);
        cout << "Critical section" << endl;
    }  // auto-unlocked here

    return 0;
}

// Concurrency with std::thread
#include <iostream>
#include <thread>
#include <mutex>
#include <vector>
#include <atomic>
using namespace std;

mutex mtx;
atomic<int> atomicCounter(0);

void threadTask(int id, vector<int> &results) {
    int localSum = 0;
    for (int i = id * 1000; i < (id+1) * 1000; i++)
        localSum += i;

    lock_guard<mutex> lock(mtx);
    results[id] = localSum;
    atomicCounter++;
    cout << "Thread " << id << " done. Sum=" << localSum << endl;
}

int main() {
    const int numThreads = 4;
    vector<thread> threads;
    vector<int> results(numThreads, 0);

    for (int i = 0; i < numThreads; i++)
        threads.emplace_back(threadTask, i, ref(results));

    for (auto &t : threads) t.join();

    long long total = 0;
    for (int r : results) total += r;
    cout << "Total sum: " << total << endl;
    cout << "Threads completed: " << atomicCounter << endl;
    return 0;
}

// Regular Expressions in C++
#include <iostream>
#include <regex>
#include <string>
#include <vector>
using namespace std;

int main() {
    // Email validation
    regex emailRx(R"([a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+.[a-zA-Z]{2,})");
    vector<string> emails = {"user@example.com","invalid-email","hello@world.org"};
    for (auto &e : emails)
        cout << e << ": " << (regex_match(e, emailRx) ? "Valid" : "Invalid") << endl;

    // Search and replace
    string text = "The quick brown fox jumps over the lazy dog";
    regex wordRx(R"(w{4})");
    string replaced = regex_replace(text, wordRx, "****");
    cout << "Replaced: " << replaced << endl;

    // Find all matches
    string data = "Price: $100, Discount: $20, Total: $80";
    regex numRx(R"($(d+))");
    auto begin = sregex_iterator(data.begin(), data.end(), numRx);
    auto end   = sregex_iterator();
    cout << "Numbers found: ";
    for (auto it = begin; it != end; ++it)
        cout << (*it)[1] << " ";
    cout << endl;

    return 0;
}

// Advanced Templates - Variadic and Fold
#include <iostream>
#include <string>
#include <sstream>
using namespace std;

// Fold expression (C++17)
template <typename ...Args>
auto sum(Args... args) { return (args + ...); }

template <typename ...Args>
auto product(Args... args) { return (args * ...); }

// Perfect forwarding
template <typename T>
void process(T &&val) {
    if constexpr (is_lvalue_reference_v<T>)
        cout << "lvalue: " << val << endl;
    else
        cout << "rvalue: " << val << endl;
}

// Compile-time factorial
template <int N>
struct Factorial { static const int value = N * Factorial<N-1>::value; };
template <>
struct Factorial<0> { static const int value = 1; };

// Type list
template <typename ...Types>
struct TypeList {
    static const size_t size = sizeof...(Types);
};

int main() {
    cout << "Sum: "     << sum(1,2,3,4,5)     << endl;  // 15
    cout << "Product: " << product(2,3,4)      << endl;  // 24
    cout << "Factorial<6>: " << Factorial<6>::value << endl;  // 720

    int x = 42;
    process(x);      // lvalue
    process(100);    // rvalue

    using TL = TypeList<int, double, string>;
    cout << "TypeList size: " << TL::size << endl;  // 3
    return 0;
}

// Ranges and Views (C++20)
#include <iostream>
#include <vector>
#include <ranges>
#include <algorithm>
#include <numeric>
using namespace std;

int main() {
    vector<int> nums = {1,2,3,4,5,6,7,8,9,10};

    // Filter even numbers and square them
    auto result = nums
        | views::filter([](int n){ return n % 2 == 0; })
        | views::transform([](int n){ return n * n; });

    cout << "Even squares: ";
    for (int x : result) cout << x << " ";
    cout << endl;

    // Take first 5
    auto first5 = nums | views::take(5);
    cout << "First 5: ";
    for (int x : first5) cout << x << " ";
    cout << endl;

    // Reverse view
    auto rev = nums | views::reverse;
    cout << "Reversed: ";
    for (int x : rev) cout << x << " ";
    cout << endl;

    // Drop while less than 5
    auto dropped = nums | views::drop_while([](int n){ return n < 5; });
    cout << "Drop while <5: ";
    for (int x : dropped) cout << x << " ";
    cout << endl;

    return 0;
}

// Matrix Operations in C++
#include <iostream>
#include <vector>
using namespace std;

using Matrix = vector<vector<int>>;

Matrix multiply(const Matrix &A, const Matrix &B) {
    int r = A.size(), c = B[0].size(), k = B.size();
    Matrix C(r, vector<int>(c, 0));
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
            for (int p = 0; p < k; p++)
                C[i][j] += A[i][p] * B[p][j];
    return C;
}

Matrix transpose(const Matrix &A) {
    int r = A.size(), c = A[0].size();
    Matrix T(c, vector<int>(r));
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
            T[j][i] = A[i][j];
    return T;
}

void rotate90(Matrix &M) {
    int n = M.size();
    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++) swap(M[i][j], M[j][i]);
    for (auto &row : M) reverse(row.begin(), row.end());
}

void print(const Matrix &M) {
    for (auto &row : M) {
        for (int x : row) cout << x << " ";
        cout << endl;
    }
}

int main() {
    Matrix A = {{1,2,3},{4,5,6},{7,8,9}};
    Matrix B = {{9,8,7},{6,5,4},{3,2,1}};

    cout << "A*B:" << endl; print(multiply(A,B));
    cout << "T(A):" << endl; print(transpose(A));
    rotate90(A);
    cout << "A rotated 90CW:" << endl; print(A);
    return 0;
}

// Trapping Rain Water in C++
#include <iostream>
#include <vector>
using namespace std;

int trap(vector<int> &height) {
    int l = 0, r = height.size()-1;
    int leftMax = 0, rightMax = 0, water = 0;
    while (l < r) {
        if (height[l] < height[r]) {
            height[l] >= leftMax ? leftMax = height[l]
                                 : (water += leftMax - height[l]);
            l++;
        } else {
            height[r] >= rightMax ? rightMax = height[r]
                                  : (water += rightMax - height[r]);
            r--;
        }
    }
    return water;
}

int main() {
    vector<int> h1 = {0,1,0,2,1,0,1,3,2,1,2,1};
    cout << "Water trapped: " << trap(h1) << endl;  // 6

    vector<int> h2 = {4,2,0,3,2,5};
    cout << "Water trapped: " << trap(h2) << endl;  // 9
    return 0;
}

// Longest Increasing Subsequence in C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// DP O(n^2)
int lis_dp(vector<int> &arr) {
    int n = arr.size();
    vector<int> dp(n, 1);
    for (int i = 1; i < n; i++)
        for (int j = 0; j < i; j++)
            if (arr[j] < arr[i]) dp[i] = max(dp[i], dp[j]+1);
    return *max_element(dp.begin(), dp.end());
}

// Binary Search O(n log n)
int lis_bs(vector<int> &arr) {
    vector<int> tails;
    for (int x : arr) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);
        else *it = x;
    }
    return tails.size();
}

int main() {
    vector<int> arr = {10, 9, 2, 5, 3, 7, 101, 18};
    cout << "LIS (DP): "  << lis_dp(arr) << endl;  // 4
    cout << "LIS (BS): "  << lis_bs(arr) << endl;  // 4
    return 0;
}

// Shortest Path - Bellman-Ford in C++
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

struct Edge { int u, v, w; };

void bellmanFord(vector<Edge> &edges, int V, int src) {
    vector<int> dist(V, INT_MAX);
    dist[src] = 0;

    for (int i = 1; i < V; i++)
        for (auto &[u,v,w] : edges)
            if (dist[u] != INT_MAX && dist[u]+w < dist[v])
                dist[v] = dist[u]+w;

    // Check negative cycle
    for (auto &[u,v,w] : edges)
        if (dist[u] != INT_MAX && dist[u]+w < dist[v]) {
            cout << "Negative cycle detected!" << endl; return;
        }

    cout << "Distances from " << src << ":" << endl;
    for (int i = 0; i < V; i++)
        cout << "  " << i << ": " << dist[i] << endl;
}

int main() {
    int V = 5;
    vector<Edge> edges = {
        {0,1,-1},{0,2,4},{1,2,3},{1,3,2},
        {1,4,2},{3,2,5},{3,1,1},{4,3,-3}
    };
    bellmanFord(edges, V, 0);
    return 0;
}

// Floyd-Warshall in C++
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

void floydWarshall(vector<vector<int>> dist) {
    int V = dist.size();
    for (int k = 0; k < V; k++)
        for (int i = 0; i < V; i++)
            for (int j = 0; j < V; j++)
                if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

    cout << "All-Pairs Shortest Paths:" << endl;
    for (auto &row : dist) {
        for (int x : row)
            x == INT_MAX ? cout << "INF " : cout << x << "   ";
        cout << endl;
    }
}

int main() {
    const int INF = INT_MAX;
    vector<vector<int>> graph = {
        {0,  3,  INF, 7  },
        {8,  0,  2,   INF},
        {5,  INF,0,   1  },
        {2,  INF,INF, 0  }
    };
    floydWarshall(graph);
    return 0;
}

// Kruskal's MST in C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Edge { int u, v, w; };

class DSU {
    vector<int> parent, rank;
public:
    DSU(int n) : parent(n), rank(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
    bool unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        if (rank[px] < rank[py]) swap(px, py);
        parent[py] = px;
        if (rank[px] == rank[py]) rank[px]++;
        return true;
    }
};

int main() {
    int V = 4;
    vector<Edge> edges = {{0,1,10},{0,2,6},{0,3,5},{1,3,15},{2,3,4}};
    sort(edges.begin(), edges.end(), [](auto &a, auto &b){ return a.w < b.w; });

    DSU dsu(V);
    int cost = 0;
    cout << "MST Edges:" << endl;
    for (auto &[u,v,w] : edges)
        if (dsu.unite(u, v)) {
            cout << u << " -- " << v << " (weight " << w << ")" << endl;
            cost += w;
        }
    cout << "MST Cost: " << cost << endl;
    return 0;
}

// String Algorithms in C++
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

// Longest palindromic substring (expand around center)
string longestPalindrome(string s) {
    int n = s.size(), start = 0, maxLen = 1;
    auto expand = [&](int l, int r) {
        while (l >= 0 && r < n && s[l] == s[r]) { l--; r++; }
        if (r-l-1 > maxLen) { maxLen = r-l-1; start = l+1; }
    };
    for (int i = 0; i < n; i++) { expand(i,i); expand(i,i+1); }
    return s.substr(start, maxLen);
}

// Check anagram
bool isAnagram(string s1, string s2) {
    if (s1.size() != s2.size()) return false;
    unordered_map<char,int> freq;
    for (char c : s1) freq[c]++;
    for (char c : s2) if (--freq[c] < 0) return false;
    return true;
}

// Group anagrams
vector<vector<string>> groupAnagrams(vector<string> &words) {
    unordered_map<string, vector<string>> mp;
    for (auto &w : words) {
        string key = w; sort(key.begin(), key.end());
        mp[key].push_back(w);
    }
    vector<vector<string>> res;
    for (auto &[k,v] : mp) res.push_back(v);
    return res;
}

int main() {
    cout << longestPalindrome("babad") << endl;
    cout << isAnagram("listen","silent") << endl;

    vector<string> words = {"eat","tea","tan","ate","nat","bat"};
    for (auto &grp : groupAnagrams(words)) {
        for (auto &w : grp) cout << w << " ";
        cout << endl;
    }
    return 0;
}

// Coin Change and Subset Sum in C++
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

// Minimum coins
int coinChange(vector<int> &coins, int amount) {
    vector<int> dp(amount+1, INT_MAX);
    dp[0] = 0;
    for (int i = 1; i <= amount; i++)
        for (int c : coins)
            if (c <= i && dp[i-c] != INT_MAX)
                dp[i] = min(dp[i], dp[i-c]+1);
    return dp[amount] == INT_MAX ? -1 : dp[amount];
}

// Count ways
int countWays(vector<int> &coins, int amount) {
    vector<int> dp(amount+1, 0);
    dp[0] = 1;
    for (int c : coins)
        for (int i = c; i <= amount; i++)
            dp[i] += dp[i-c];
    return dp[amount];
}

// Subset sum
bool subsetSum(vector<int> &arr, int target) {
    int n = arr.size();
    vector<vector<bool>> dp(n+1, vector<bool>(target+1, false));
    for (int i = 0; i <= n; i++) dp[i][0] = true;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= target; j++) {
            dp[i][j] = dp[i-1][j];
            if (arr[i-1] <= j) dp[i][j] = dp[i][j] || dp[i-1][j-arr[i-1]];
        }
    return dp[n][target];
}

int main() {
    vector<int> coins = {1,5,6,9};
    cout << "Min coins for 11: " << coinChange(coins, 11) << endl;
    cout << "Ways for 10: "      << countWays(coins, 10)  << endl;

    vector<int> arr = {3,34,4,12,5,2};
    cout << "Subset sum 9: "  << subsetSum(arr, 9)   << endl;
    cout << "Subset sum 30: " << subsetSum(arr, 30)  << endl;
    return 0;
}

// Monotonic Stack Problems
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

// Next Greater Element
vector<int> nextGreater(vector<int> &arr) {
    int n = arr.size();
    vector<int> res(n, -1);
    stack<int> st;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && arr[st.top()] < arr[i]) {
            res[st.top()] = arr[i];
            st.pop();
        }
        st.push(i);
    }
    return res;
}

// Largest Rectangle in Histogram
int largestRect(vector<int> &heights) {
    stack<int> st;
    int maxArea = 0;
    heights.push_back(0);
    for (int i = 0; i < (int)heights.size(); i++) {
        while (!st.empty() && heights[st.top()] > heights[i]) {
            int h = heights[st.top()]; st.pop();
            int w = st.empty() ? i : i - st.top() - 1;
            maxArea = max(maxArea, h * w);
        }
        st.push(i);
    }
    return maxArea;
}

int main() {
    vector<int> arr = {4,5,2,10,8};
    auto ng = nextGreater(arr);
    cout << "Next Greater: ";
    for (int x : ng) cout << x << " ";
    cout << endl;  // 5 10 10 -1 -1

    vector<int> h = {2,1,5,6,2,3};
    cout << "Largest Rect: " << largestRect(h) << endl;  // 10
    return 0;
}

// Binary Search Variants in C++
#include <iostream>
#include <vector>
using namespace std;

// Search in rotated sorted array
int searchRotated(vector<int> &arr, int target) {
    int l = 0, r = arr.size()-1;
    while (l <= r) {
        int mid = (l+r)/2;
        if (arr[mid] == target) return mid;
        if (arr[l] <= arr[mid]) {
            if (target >= arr[l] && target < arr[mid]) r = mid-1;
            else l = mid+1;
        } else {
            if (target > arr[mid] && target <= arr[r]) l = mid+1;
            else r = mid-1;
        }
    }
    return -1;
}

// Find peak element
int findPeak(vector<int> &arr) {
    int l = 0, r = arr.size()-1;
    while (l < r) {
        int mid = (l+r)/2;
        if (arr[mid] > arr[mid+1]) r = mid;
        else l = mid+1;
    }
    return l;
}

// First and last position
pair<int,int> firstLast(vector<int> &arr, int target) {
    auto first = lower_bound(arr.begin(), arr.end(), target);
    auto last  = upper_bound(arr.begin(), arr.end(), target);
    if (first == arr.end() || *first != target) return {-1,-1};
    return {(int)(first-arr.begin()), (int)(last-arr.begin())-1};
}

int main() {
    vector<int> rotated = {4,5,6,7,0,1,2};
    cout << "Search 0: " << searchRotated(rotated, 0) << endl;  // 4

    vector<int> arr = {1,2,3,1};
    cout << "Peak index: " << findPeak(arr) << endl;  // 2

    vector<int> v = {5,7,7,8,8,10};
    auto [f,l] = firstLast(v, 8);
    cout << "First,Last of 8: " << f << "," << l << endl;  // 3,4
    return 0;
}

// Product of Array Except Self in C++
#include <iostream>
#include <vector>
using namespace std;

vector<int> productExceptSelf(vector<int> &nums) {
    int n = nums.size();
    vector<int> result(n, 1);

    // Left pass
    for (int i = 1; i < n; i++)
        result[i] = result[i-1] * nums[i-1];

    // Right pass
    int right = 1;
    for (int i = n-1; i >= 0; i--) {
        result[i] *= right;
        right *= nums[i];
    }
    return result;
}

int main() {
    vector<int> nums = {1, 2, 3, 4};
    auto res = productExceptSelf(nums);
    cout << "Output: ";
    for (int x : res) cout << x << " ";
    cout << endl;  // 24 12 8 6
    return 0;
}

// Flood Fill and Number of Islands
#include <iostream>
#include <vector>
using namespace std;

// Flood Fill
void floodFill(vector<vector<int>> &img, int r, int c,
               int oldColor, int newColor) {
    if (r<0||r>=(int)img.size()||c<0||c>=(int)img[0].size()) return;
    if (img[r][c] != oldColor || img[r][c] == newColor) return;
    img[r][c] = newColor;
    floodFill(img, r+1,c, oldColor, newColor);
    floodFill(img, r-1,c, oldColor, newColor);
    floodFill(img, r,c+1, oldColor, newColor);
    floodFill(img, r,c-1, oldColor, newColor);
}

// Number of Islands
void dfs(vector<vector<char>> &grid, int r, int c) {
    if (r<0||r>=(int)grid.size()||c<0||c>=(int)grid[0].size()
        ||grid[r][c]=='0') return;
    grid[r][c] = '0';
    dfs(grid,r+1,c); dfs(grid,r-1,c);
    dfs(grid,r,c+1); dfs(grid,r,c-1);
}

int numIslands(vector<vector<char>> grid) {
    int count = 0;
    for (int r=0;r<(int)grid.size();r++)
        for (int c=0;c<(int)grid[0].size();c++)
            if (grid[r][c]=='1') { dfs(grid,r,c); count++; }
    return count;
}

int main() {
    vector<vector<char>> grid = {
        {'1','1','0','0'},
        {'1','1','0','0'},
        {'0','0','1','0'},
        {'0','0','0','1'}
    };
    cout << "Islands: " << numIslands(grid) << endl;  // 3
    return 0;
}

// Word Search in Grid (C++)
#include <iostream>
#include <vector>
#include <string>
using namespace std;

bool dfs(vector<vector<char>> &board, string &word,
         int r, int c, int idx) {
    if (idx == (int)word.size()) return true;
    if (r<0||r>=(int)board.size()||c<0||c>=(int)board[0].size()
        ||board[r][c] != word[idx]) return false;
    char tmp = board[r][c];
    board[r][c] = '#';
    bool found = dfs(board,word,r+1,c,idx+1) ||
                 dfs(board,word,r-1,c,idx+1) ||
                 dfs(board,word,r,c+1,idx+1) ||
                 dfs(board,word,r,c-1,idx+1);
    board[r][c] = tmp;
    return found;
}

bool wordSearch(vector<vector<char>> &board, string word) {
    for (int r=0;r<(int)board.size();r++)
        for (int c=0;c<(int)board[0].size();c++)
            if (dfs(board, word, r, c, 0)) return true;
    return false;
}

int main() {
    vector<vector<char>> board = {
        {'A','B','C','E'},
        {'S','F','C','S'},
        {'A','D','E','E'}
    };
    cout << wordSearch(board, "ABCCED") << endl;  // 1
    cout << wordSearch(board, "SEE")    << endl;  // 1
    cout << wordSearch(board, "ABCB")   << endl;  // 0
    return 0;
}

// Spiral Matrix in C++
#include <iostream>
#include <vector>
using namespace std;

vector<int> spiralOrder(vector<vector<int>> &matrix) {
    vector<int> res;
    int top=0, bottom=matrix.size()-1;
    int left=0, right=matrix[0].size()-1;

    while (top<=bottom && left<=right) {
        for (int i=left; i<=right; i++)   res.push_back(matrix[top][i]);
        top++;
        for (int i=top; i<=bottom; i++)   res.push_back(matrix[i][right]);
        right--;
        if (top<=bottom) {
            for (int i=right; i>=left; i--) res.push_back(matrix[bottom][i]);
            bottom--;
        }
        if (left<=right) {
            for (int i=bottom; i>=top; i--) res.push_back(matrix[i][left]);
            left++;
        }
    }
    return res;
}

int main() {
    vector<vector<int>> mat = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9,10,11,12},
        {13,14,15,16}
    };
    cout << "Spiral: ";
    for (int x : spiralOrder(mat)) cout << x << " ";
    cout << endl;
    return 0;
}

// Sudoku Solver in C++
#include <iostream>
#include <vector>
using namespace std;

bool isValid(vector<vector<char>> &board, int r, int c, char num) {
    for (int i=0; i<9; i++) {
        if (board[r][i] == num) return false;
        if (board[i][c] == num) return false;
        if (board[3*(r/3)+i/3][3*(c/3)+i%3] == num) return false;
    }
    return true;
}

bool solve(vector<vector<char>> &board) {
    for (int r=0; r<9; r++)
        for (int c=0; c<9; c++)
            if (board[r][c] == '.') {
                for (char num='1'; num<='9'; num++) {
                    if (isValid(board, r, c, num)) {
                        board[r][c] = num;
                        if (solve(board)) return true;
                        board[r][c] = '.';
                    }
                }
                return false;
            }
    return true;
}

int main() {
    vector<vector<char>> board = {
        {'5','3','.','.','7','.','.','.','.'},
        {'6','.','.','1','9','5','.','.','.'},
        {'.','9','8','.','.','.','.','6','.'},
        {'8','.','.','.','6','.','.','.','3'},
        {'4','.','.','8','.','3','.','.','1'},
        {'7','.','.','.','2','.','.','.','6'},
        {'.','6','.','.','.','.','2','8','.'},
        {'.','.','.','4','1','9','.','.','5'},
        {'.','.','.','.','8','.','.','7','9'}
    };
    solve(board);
    for (auto &row : board) {
        for (char c : row) cout << c << " ";
        cout << endl;
    }
    return 0;
}

// Priority Queue Custom Comparator
#include <iostream>
#include <vector>
#include <queue>
#include <string>
using namespace std;

struct Task {
    string name;
    int priority;
    int deadline;
};

struct Cmp {
    bool operator()(const Task &a, const Task &b) {
        if (a.priority != b.priority) return a.priority < b.priority;
        return a.deadline > b.deadline;
    }
};

int main() {
    priority_queue<Task, vector<Task>, Cmp> taskQueue;
    taskQueue.push({"Write Report",    3, 5});
    taskQueue.push({"Fix Bug",         5, 2});
    taskQueue.push({"Code Review",     4, 3});
    taskQueue.push({"Deploy Feature",  5, 1});
    taskQueue.push({"Write Tests",     3, 4});

    cout << "Task execution order:" << endl;
    while (!taskQueue.empty()) {
        auto t = taskQueue.top(); taskQueue.pop();
        cout << "  [P=" << t.priority << ",D=" << t.deadline
             << "] " << t.name << endl;
    }
    return 0;
}

// Graph - Minimum Spanning Tree Prim's
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

typedef pair<int,int> pii;

int primMST(vector<vector<pii>> &graph, int V) {
    vector<int> key(V, INT_MAX);
    vector<bool> inMST(V, false);
    priority_queue<pii, vector<pii>, greater<pii>> pq;

    key[0] = 0;
    pq.push({0, 0});
    int totalCost = 0;

    while (!pq.empty()) {
        auto [wt, u] = pq.top(); pq.pop();
        if (inMST[u]) continue;
        inMST[u] = true;
        totalCost += wt;

        for (auto [w, v] : graph[u]) {
            if (!inMST[v] && w < key[v]) {
                key[v] = w;
                pq.push({key[v], v});
            }
        }
    }
    return totalCost;
}

int main() {
    int V = 5;
    vector<vector<pii>> graph(V);
    auto addEdge = [&](int u, int v, int w) {
        graph[u].push_back({w,v});
        graph[v].push_back({w,u});
    };
    addEdge(0,1,2); addEdge(0,3,6);
    addEdge(1,2,3); addEdge(1,3,8);
    addEdge(1,4,5); addEdge(2,4,7);
    addEdge(3,4,9);

    cout << "MST Cost (Prim's): " << primMST(graph, V) << endl;  // 16
    return 0;
}

// Iterator Pattern in C++
#include <iostream>
#include <vector>
#include <list>
using namespace std;

// Custom Iterator for a range
template <typename T>
class Range {
    T start_, end_, step_;
public:
    Range(T s, T e, T step = 1) : start_(s), end_(e), step_(step) {}

    struct Iterator {
        T current, step;
        Iterator(T c, T s) : current(c), step(s) {}
        T operator*() { return current; }
        Iterator& operator++() { current += step; return *this; }
        bool operator!=(const Iterator &o) { return current < o.current; }
    };

    Iterator begin() { return Iterator(start_, step_); }
    Iterator end()   { return Iterator(end_,   step_); }
};

int main() {
    // Custom range
    for (int x : Range<int>(1, 11))     cout << x << " ";
    cout << endl;

    for (int x : Range<int>(0, 20, 2)) cout << x << " ";
    cout << endl;

    // STL iterator patterns
    vector<int> v = {1,2,3,4,5};
    auto it = v.begin() + 2;
    cout << "Element at index 2: " << *it << endl;

    // advance, distance
    advance(it, 2);
    cout << "After advance(2): " << *it << endl;
    cout << "Distance from begin: "
         << distance(v.begin(), it) << endl;

    return 0;
}

// Compile-Time Programming (constexpr)
#include <iostream>
#include <array>
using namespace std;

constexpr int factorial(int n) {
    return n <= 1 ? 1 : n * factorial(n-1);
}

constexpr int fibonacci(int n) {
    return n <= 1 ? n : fibonacci(n-1) + fibonacci(n-2);
}

constexpr bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i*i <= n; i++)
        if (n % i == 0) return false;
    return true;
}

// Compile-time array of primes
template <int N>
constexpr auto makePrimes() {
    array<int, N> primes{};
    int count = 0;
    for (int n = 2; count < N; n++)
        if (isPrime(n)) primes[count++] = n;
    return primes;
}

int main() {
    constexpr int f = factorial(10);
    constexpr int fib = fibonacci(15);
    cout << "10! = "       << f   << endl;
    cout << "fib(15) = "   << fib << endl;

    constexpr auto primes = makePrimes<10>();
    cout << "First 10 primes: ";
    for (int p : primes) cout << p << " ";
    cout << endl;

    static_assert(factorial(5) == 120, "Compile-time check");
    cout << "All compile-time checks passed!" << endl;
    return 0;
}

// Memory Management and Allocators
#include <iostream>
#include <memory>
#include <vector>
using namespace std;

// Custom deleter
struct FileDeleter {
    void operator()(FILE *f) const {
        if (f) { fclose(f); cout << "File auto-closed" << endl; }
    }
};

// Object Pool
template <typename T>
class ObjectPool {
    vector<unique_ptr<T>> pool;
    vector<T*> available;
public:
    ObjectPool(int size) {
        for (int i = 0; i < size; i++) {
            pool.push_back(make_unique<T>());
            available.push_back(pool.back().get());
        }
    }

    T* acquire() {
        if (available.empty()) return nullptr;
        T* obj = available.back();
        available.pop_back();
        return obj;
    }

    void release(T* obj) {
        available.push_back(obj);
    }

    int freeCount() const { return available.size(); }
};

struct Connection {
    int id = 0;
    bool active = false;
};

int main() {
    // unique_ptr with custom deleter
    unique_ptr<FILE, FileDeleter> fp(fopen("test.txt", "w"));
    if (fp) fprintf(fp.get(), "Hello RAII file!\n");
    // auto-closed when fp goes out of scope

    // Object pool
    ObjectPool<Connection> pool(3);
    cout << "Free: " << pool.freeCount() << endl;  // 3

    Connection *c1 = pool.acquire();
    Connection *c2 = pool.acquire();
    c1->id = 1; c1->active = true;
    c2->id = 2; c2->active = true;
    cout << "Free: " << pool.freeCount() << endl;  // 1

    pool.release(c1);
    cout << "Free: " << pool.freeCount() << endl;  // 2

    // shared_ptr with custom deleter
    shared_ptr<int> sp(new int[5]{1,2,3,4,5},
                       [](int *p){ delete[] p; cout << "Array deleted\n"; });
    cout << "sp[0]=" << sp.get()[0] << endl;

    return 0;
}

// Sorting with Custom Comparators
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

struct Student {
    string name;
    int age;
    double gpa;
};

int main() {
    vector<Student> students = {
        {"Alice", 20, 3.85},
        {"Bob",   22, 3.62},
        {"Carol", 21, 3.91},
        {"Dave",  20, 3.75},
        {"Eve",   22, 3.91}
    };

    // Sort by GPA descending
    sort(students.begin(), students.end(),
         [](const Student &a, const Student &b){
             return a.gpa > b.gpa;
         });
    cout << "By GPA desc:" << endl;
    for (auto &s : students)
        cout << "  " << s.name << " " << s.gpa << endl;

    // Sort by age asc, then name asc
    sort(students.begin(), students.end(),
         [](const Student &a, const Student &b){
             if (a.age != b.age) return a.age < b.age;
             return a.name < b.name;
         });
    cout << "By age, then name:" << endl;
    for (auto &s : students)
        cout << "  " << s.name << " age=" << s.age << endl;

    // Stable sort preserves relative order for equal elements
    stable_sort(students.begin(), students.end(),
                [](const Student &a, const Student &b){
                    return a.gpa > b.gpa;
                });
    cout << "Stable sort by GPA:" << endl;
    for (auto &s : students)
        cout << "  " << s.name << " " << s.gpa << endl;

    return 0;
}

// Graph Cycle Detection in C++
#include <iostream>
#include <vector>
using namespace std;

// Directed graph - DFS with recursion stack
bool dfsCycle(int v, vector<vector<int>> &adj,
              vector<bool> &visited, vector<bool> &recStack) {
    visited[v] = recStack[v] = true;
    for (int u : adj[v]) {
        if (!visited[u] && dfsCycle(u, adj, visited, recStack))
            return true;
        else if (recStack[u]) return true;
    }
    recStack[v] = false;
    return false;
}

bool hasCycleDirected(int V, vector<vector<int>> &adj) {
    vector<bool> visited(V, false), recStack(V, false);
    for (int i = 0; i < V; i++)
        if (!visited[i] && dfsCycle(i, adj, visited, recStack))
            return true;
    return false;
}

// Undirected graph - Union Find
bool hasCycleUndirected(int V, vector<pair<int,int>> &edges) {
    vector<int> parent(V);
    iota(parent.begin(), parent.end(), 0);
    function<int(int)> find = [&](int x) -> int {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    };
    for (auto [u, v] : edges) {
        int pu = find(u), pv = find(v);
        if (pu == pv) return true;
        parent[pu] = pv;
    }
    return false;
}

int main() {
    int V = 4;
    vector<vector<int>> adj(V);
    adj[0].push_back(1); adj[1].push_back(2);
    adj[2].push_back(3); adj[3].push_back(1); // cycle

    cout << "Directed cycle: "
         << hasCycleDirected(V, adj) << endl;  // 1

    vector<pair<int,int>> edges = {{0,1},{1,2},{2,0}};
    cout << "Undirected cycle: "
         << hasCycleUndirected(3, edges) << endl;  // 1
    return 0;
}

// Counting Sort and Radix Sort in C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void countingSort(vector<int> &arr) {
    if (arr.empty()) return;
    int maxVal = *max_element(arr.begin(), arr.end());
    vector<int> count(maxVal + 1, 0);
    for (int x : arr) count[x]++;
    int idx = 0;
    for (int i = 0; i <= maxVal; i++)
        while (count[i]-- > 0) arr[idx++] = i;
}

void countSortByDigit(vector<int> &arr, int exp) {
    int n = arr.size();
    vector<int> output(n), count(10, 0);
    for (int x : arr) count[(x / exp) % 10]++;
    for (int i = 1; i < 10; i++) count[i] += count[i-1];
    for (int i = n-1; i >= 0; i--) {
        output[count[(arr[i]/exp)%10]-1] = arr[i];
        count[(arr[i]/exp)%10]--;
    }
    arr = output;
}

void radixSort(vector<int> &arr) {
    int maxVal = *max_element(arr.begin(), arr.end());
    for (int exp = 1; maxVal / exp > 0; exp *= 10)
        countSortByDigit(arr, exp);
}

int main() {
    vector<int> v1 = {4,2,2,8,3,3,1,7,5};
    countingSort(v1);
    cout << "Counting: ";
    for (int x : v1) cout << x << " ";
    cout << endl;

    vector<int> v2 = {170,45,75,90,802,24,2,66};
    radixSort(v2);
    cout << "Radix:    ";
    for (int x : v2) cout << x << " ";
    cout << endl;
    return 0;
}

// Advanced STL - unordered_set, multimap, bitset
#include <iostream>
#include <unordered_set>
#include <multimap>
#include <bitset>
#include <set>
using namespace std;

int main() {
    // unordered_set - O(1) average lookup
    unordered_set<int> us = {3,1,4,1,5,9,2,6};
    us.insert(7);
    cout << "Contains 5: " << us.count(5) << endl;
    cout << "Size: " << us.size() << endl;

    // multiset - sorted, allows duplicates
    multiset<int> ms = {3,1,4,1,5,9,2,6,5};
    cout << "Multiset: ";
    for (int x : ms) cout << x << " ";
    cout << endl;
    cout << "Count of 5: " << ms.count(5) << endl;

    // multimap - multiple values per key
    multimap<string,int> mm;
    mm.insert({"Alice", 90}); mm.insert({"Alice", 95});
    mm.insert({"Bob",   85}); mm.insert({"Bob",   88});
    auto range = mm.equal_range("Alice");
    cout << "Alice scores: ";
    for (auto it = range.first; it != range.second; ++it)
        cout << it->second << " ";
    cout << endl;

    // bitset - fixed-size bit array
    bitset<8> b("10110100");
    cout << "Bitset: "    << b          << endl;
    cout << "Count: "     << b.count()  << endl;
    cout << "Flip bit 0: "<< b.flip(0)  << endl;
    cout << "b & 11110000: " << (b & bitset<8>("11110000")) << endl;

    return 0;
}

// String Matching - Rabin-Karp in C++
#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<int> rabinKarp(const string &text, const string &pattern) {
    vector<int> positions;
    int n = text.size(), m = pattern.size();
    const int BASE = 31, MOD = 1e9 + 9;

    // Compute hash of pattern and first window
    long long patHash = 0, winHash = 0, power = 1;

    for (int i = 0; i < m; i++) {
        patHash = (patHash + (pattern[i]-'a'+1) * power) % MOD;
        winHash = (winHash + (text[i]  -'a'+1) * power) % MOD;
        if (i < m-1) power = power * BASE % MOD;
    }

    for (int i = 0; i <= n-m; i++) {
        if (patHash == winHash) {
            if (text.substr(i, m) == pattern)
                positions.push_back(i);
        }
        if (i < n-m) {
            winHash = (winHash - (text[i]-'a'+1) + MOD) % MOD;
            winHash = winHash * (MOD+1-BASE) % MOD;
            winHash = (winHash + (text[i+m]-'a'+1) * power) % MOD;
        }
    }
    return positions;
}

int main() {
    string text    = "aabaacaadaabaaba";
    string pattern = "aaba";
    auto pos = rabinKarp(text, pattern);
    cout << "Rabin-Karp found at: ";
    for (int p : pos) cout << p << " ";
    cout << endl;
    return 0;
}

// Expression Evaluation using Stack
#include <iostream>
#include <stack>
#include <string>
#include <sstream>
using namespace std;

// Evaluate Reverse Polish Notation
int evalRPN(vector<string> &tokens) {
    stack<int> st;
    for (auto &t : tokens) {
        if (t == "+" || t == "-" || t == "*" || t == "/") {
            int b = st.top(); st.pop();
            int a = st.top(); st.pop();
            if (t == "+") st.push(a + b);
            if (t == "-") st.push(a - b);
            if (t == "*") st.push(a * b);
            if (t == "/") st.push(a / b);
        } else {
            st.push(stoi(t));
        }
    }
    return st.top();
}

// Infix to Postfix
string infixToPostfix(const string &expr) {
    stack<char> ops;
    string result;
    auto prec = [](char c) {
        if (c=='+'||c=='-') return 1;
        if (c=='*'||c=='/') return 2;
        return 0;
    };
    for (char c : expr) {
        if (isdigit(c)) { result += c; result += ' '; }
        else if (c == '(') ops.push(c);
        else if (c == ')') {
            while (ops.top() != '(') { result += ops.top(); result += ' '; ops.pop(); }
            ops.pop();
        } else {
            while (!ops.empty() && prec(ops.top()) >= prec(c))
                { result += ops.top(); result += ' '; ops.pop(); }
            ops.push(c);
        }
    }
    while (!ops.empty()) { result += ops.top(); result += ' '; ops.pop(); }
    return result;
}

int main() {
    vector<string> rpn = {"2","1","+","3","*"};
    cout << "RPN eval: " << evalRPN(rpn) << endl;  // 9

    cout << "Infix to Postfix: "
         << infixToPostfix("(2+3)*4") << endl;
    return 0;
}

// Advanced OOP - Mixins and CRTP
#include <iostream>
#include <string>
using namespace std;

// CRTP (Curiously Recurring Template Pattern)
template <typename Derived>
class Printable {
public:
    void print() const {
        static_cast<const Derived*>(this)->printImpl();
    }
};

template <typename Derived>
class Comparable {
public:
    bool operator==(const Derived &o) const {
        return static_cast<const Derived*>(this)->compareTo(o) == 0;
    }
    bool operator<(const Derived &o) const {
        return static_cast<const Derived*>(this)->compareTo(o) < 0;
    }
    bool operator>(const Derived &o) const {
        return static_cast<const Derived*>(this)->compareTo(o) > 0;
    }
};

class Point : public Printable<Point>, public Comparable<Point> {
    double x, y;
public:
    Point(double x, double y) : x(x), y(y) {}
    void printImpl() const {
        cout << "Point(" << x << ", " << y << ")" << endl;
    }
    double dist() const { return x*x + y*y; }
    int compareTo(const Point &o) const {
        if (dist() < o.dist()) return -1;
        if (dist() > o.dist()) return  1;
        return 0;
    }
};

int main() {
    Point p1(3, 4), p2(1, 1), p3(3, 4);
    p1.print();
    p2.print();
    cout << "p1 == p3: " << (p1 == p3) << endl;  // 1
    cout << "p1 >  p2: " << (p1 >  p2) << endl;  // 1
    cout << "p2 <  p1: " << (p2 <  p1) << endl;  // 1
    return 0;
}

// Concurrency - Condition Variables and Producer-Consumer
#include <iostream>
#include <thread>
#include <mutex>
#include <queue>
#include <condition_variable>
using namespace std;

class BoundedBuffer {
    queue<int> buffer;
    int capacity;
    mutex mtx;
    condition_variable notFull, notEmpty;

public:
    BoundedBuffer(int cap) : capacity(cap) {}

    void produce(int item) {
        unique_lock<mutex> lock(mtx);
        notFull.wait(lock, [this]{ return (int)buffer.size() < capacity; });
        buffer.push(item);
        cout << "Produced: " << item
             << " | Buffer size: " << buffer.size() << endl;
        notEmpty.notify_one();
    }

    int consume() {
        unique_lock<mutex> lock(mtx);
        notEmpty.wait(lock, [this]{ return !buffer.empty(); });
        int item = buffer.front(); buffer.pop();
        cout << "Consumed: " << item
             << " | Buffer size: " << buffer.size() << endl;
        notFull.notify_one();
        return item;
    }
};

int main() {
    BoundedBuffer bb(3);

    thread producer([&]() {
        for (int i = 1; i <= 6; i++) bb.produce(i);
    });

    thread consumer([&]() {
        for (int i = 0; i < 6; i++) bb.consume();
    });

    producer.join();
    consumer.join();
    return 0;
}

// Type Erasure and std::any / std::variant
#include <iostream>
#include <variant>
#include <any>
#include <vector>
#include <string>
using namespace std;

// std::variant - type-safe union
using Value = variant<int, double, string, bool>;

void printValue(const Value &v) {
    visit([](auto &&val){ cout << val << endl; }, v);
}

string typeName(const Value &v) {
    if (holds_alternative<int>(v))    return "int";
    if (holds_alternative<double>(v)) return "double";
    if (holds_alternative<string>(v)) return "string";
    if (holds_alternative<bool>(v))   return "bool";
    return "unknown";
}

// std::any - completely type-erased
void printAny(const any &a) {
    if (a.type() == typeid(int))
        cout << "int: " << any_cast<int>(a) << endl;
    else if (a.type() == typeid(string))
        cout << "string: " << any_cast<string>(a) << endl;
    else if (a.type() == typeid(double))
        cout << "double: " << any_cast<double>(a) << endl;
}

int main() {
    vector<Value> values = {42, 3.14, string("hello"), true};
    for (auto &v : values) {
        cout << typeName(v) << ": ";
        printValue(v);
    }

    // Transform: double all ints
    for (auto &v : values)
        if (holds_alternative<int>(v))
            v = get<int>(v) * 2;

    cout << "After doubling ints:" << endl;
    for (auto &v : values) printValue(v);

    // std::any
    vector<any> items = {42, string("world"), 3.14};
    for (auto &a : items) printAny(a);

    return 0;
}

// Coroutines Concept (C++20 Generator)
#include <iostream>
#include <vector>
#include <functional>
using namespace std;

// Simulated generator using callbacks (pre-C++20 friendly)
class FibGenerator {
    long long a = 0, b = 1;
    int count;
public:
    FibGenerator(int n) : count(n) {}

    void forEach(function<void(long long)> callback) {
        for (int i = 0; i < count; i++) {
            callback(a);
            long long c = a + b;
            a = b; b = c;
        }
    }

    vector<long long> toVector() {
        vector<long long> result;
        forEach([&](long long v){ result.push_back(v); });
        return result;
    }
};

// Range generator
class RangeGenerator {
    int start_, end_, step_;
public:
    RangeGenerator(int s, int e, int step = 1)
        : start_(s), end_(e), step_(step) {}

    void forEach(function<void(int)> cb) {
        for (int i = start_; i < end_; i += step_) cb(i);
    }

    vector<int> filter(function<bool(int)> pred) {
        vector<int> result;
        forEach([&](int v){ if (pred(v)) result.push_back(v); });
        return result;
    }

    vector<int> map(function<int(int)> fn) {
        vector<int> result;
        forEach([&](int v){ result.push_back(fn(v)); });
        return result;
    }
};

int main() {
    FibGenerator fg(10);
    auto fibs = fg.toVector();
    cout << "Fibonacci: ";
    for (auto x : fibs) cout << x << " ";
    cout << endl;

    RangeGenerator rg(1, 21);
    auto evens = rg.filter([](int x){ return x % 2 == 0; });
    cout << "Even numbers: ";
    for (int x : evens) cout << x << " ";
    cout << endl;

    auto squares = RangeGenerator(1, 6).map([](int x){ return x*x; });
    cout << "Squares: ";
    for (int x : squares) cout << x << " ";
    cout << endl;

    return 0;
}

// Design Pattern - Strategy and Command
#include <iostream>
#include <memory>
#include <vector>
#include <functional>
using namespace std;

// Strategy Pattern
class SortStrategy {
public:
    virtual void sort(vector<int> &arr) = 0;
    virtual string name() const = 0;
    virtual ~SortStrategy() {}
};

class BubbleStrategy : public SortStrategy {
public:
    void sort(vector<int> &arr) override {
        int n = arr.size();
        for (int i = 0; i < n-1; i++)
            for (int j = 0; j < n-i-1; j++)
                if (arr[j] > arr[j+1]) swap(arr[j], arr[j+1]);
    }
    string name() const override { return "Bubble Sort"; }
};

class STLStrategy : public SortStrategy {
public:
    void sort(vector<int> &arr) override {
        std::sort(arr.begin(), arr.end());
    }
    string name() const override { return "STL Sort"; }
};

class Sorter {
    unique_ptr<SortStrategy> strategy;
public:
    Sorter(unique_ptr<SortStrategy> s) : strategy(move(s)) {}
    void setStrategy(unique_ptr<SortStrategy> s) { strategy = move(s); }
    void sort(vector<int> &arr) {
        cout << "Using: " << strategy->name() << endl;
        strategy->sort(arr);
    }
};

// Command Pattern
class Command {
public:
    virtual void execute() = 0;
    virtual void undo()    = 0;
    virtual ~Command() {}
};

class Counter {
    int value = 0;
public:
    void increment(int n) { value += n; }
    void decrement(int n) { value -= n; }
    int  get() const      { return value; }
};

class IncrementCommand : public Command {
    Counter &counter; int amount;
public:
    IncrementCommand(Counter &c, int a) : counter(c), amount(a) {}
    void execute() override { counter.increment(amount); }
    void undo()    override { counter.decrement(amount); }
};

int main() {
    vector<int> arr = {5,3,8,1,9,2};
    Sorter sorter(make_unique<BubbleStrategy>());
    sorter.sort(arr);
    for (int x : arr) cout << x << " ";
    cout << endl;

    sorter.setStrategy(make_unique<STLStrategy>());
    arr = {5,3,8,1,9,2};
    sorter.sort(arr);
    for (int x : arr) cout << x << " ";
    cout << endl;

    Counter c;
    vector<unique_ptr<Command>> history;
    history.push_back(make_unique<IncrementCommand>(c, 10));
    history.push_back(make_unique<IncrementCommand>(c, 5));
    for (auto &cmd : history) cmd->execute();
    cout << "Counter: " << c.get() << endl;  // 15
    history.back()->undo();
    cout << "After undo: " << c.get() << endl;  // 10
    return 0;
}

// Advanced Lambda and Functional Programming
#include <iostream>
#include <vector>
#include <functional>
#include <numeric>
#include <algorithm>
using namespace std;

// Higher-order functions
template <typename T>
vector<T> myMap(vector<T> v, function<T(T)> fn) {
    transform(v.begin(), v.end(), v.begin(), fn);
    return v;
}

template <typename T>
vector<T> myFilter(vector<T> v, function<bool(T)> pred) {
    v.erase(remove_if(v.begin(), v.end(), [&](T x){ return !pred(x); }), v.end());
    return v;
}

template <typename T, typename R>
R myReduce(vector<T> v, R init, function<R(R,T)> fn) {
    return accumulate(v.begin(), v.end(), init, fn);
}

// Function composition
template <typename F, typename G>
auto compose(F f, G g) {
    return [f, g](auto x){ return f(g(x)); };
}

// Memoization
template <typename T, typename R>
function<R(T)> memoize(function<R(T)> fn) {
    unordered_map<T, R> cache;
    return [fn, cache](T x) mutable -> R {
        if (!cache.count(x)) cache[x] = fn(x);
        return cache[x];
    };
}

int main() {
    vector<int> nums = {1,2,3,4,5,6,7,8,9,10};

    auto doubled = myMap<int>(nums, [](int x){ return x * 2; });
    cout << "Doubled: ";
    for (int x : doubled) cout << x << " ";
    cout << endl;

    auto evens = myFilter<int>(nums, [](int x){ return x % 2 == 0; });
    cout << "Evens: ";
    for (int x : evens) cout << x << " ";
    cout << endl;

    int sum = myReduce<int,int>(nums, 0, [](int a, int b){ return a+b; });
    cout << "Sum: " << sum << endl;

    auto addOne   = [](int x){ return x + 1; };
    auto doubleIt = [](int x){ return x * 2; };
    auto addOneThenDouble = compose(doubleIt, addOne);
    cout << "compose(double, +1)(5) = " << addOneThenDouble(5) << endl;  // 12

    // Memoized fibonacci
    function<int(int)> fib = [&](int n) -> int {
        return n <= 1 ? n : fib(n-1) + fib(n-2);
    };
    auto memoFib = memoize<int,int>(fib);
    cout << "fib(10) = " << memoFib(10) << endl;

    return 0;
}

// Complete Bank Account System in C++
#include <iostream>
#include <string>
#include <vector>
#include <stdexcept>
#include <iomanip>
using namespace std;

class Transaction {
public:
    enum Type { DEPOSIT, WITHDRAWAL, TRANSFER };
    Type   type;
    double amount;
    string description;
    double balanceAfter;

    Transaction(Type t, double amt, string desc, double bal)
        : type(t), amount(amt), description(desc), balanceAfter(bal) {}

    void print() const {
        string typeStr;
        switch(type) {
            case DEPOSIT:    typeStr = "DEPOSIT";    break;
            case WITHDRAWAL: typeStr = "WITHDRAWAL"; break;
            case TRANSFER:   typeStr = "TRANSFER";   break;
        }
        cout << fixed << setprecision(2)
             << setw(12) << typeStr
             << " | Amount: $" << setw(9) << amount
             << " | Balance: $" << setw(9) << balanceAfter
             << " | " << description << endl;
    }
};

class BankAccount {
    string   owner;
    string   accountNo;
    double   balance;
    vector<Transaction> history;

    static int nextAccNo;

public:
    BankAccount(string name, double initialDeposit = 0.0)
        : owner(name), balance(0.0) {
        accountNo = "ACC" + to_string(++nextAccNo);
        if (initialDeposit > 0) deposit(initialDeposit, "Initial deposit");
    }

    void deposit(double amount, string desc = "Deposit") {
        if (amount <= 0)
            throw invalid_argument("Deposit amount must be positive");
        balance += amount;
        history.emplace_back(Transaction::DEPOSIT, amount, desc, balance);
    }

    void withdraw(double amount, string desc = "Withdrawal") {
        if (amount <= 0)
            throw invalid_argument("Withdrawal amount must be positive");
        if (amount > balance)
            throw runtime_error("Insufficient funds");
        balance -= amount;
        history.emplace_back(Transaction::WITHDRAWAL, amount, desc, balance);
    }

    void transfer(BankAccount &target, double amount) {
        withdraw(amount, "Transfer to " + target.accountNo);
        target.deposit(amount, "Transfer from " + accountNo);
    }

    void printStatement() const {
        cout << string(60, '=') << endl;
        cout << "Account: " << accountNo
             << " | Owner: " << owner
             << " | Balance: $" << fixed << setprecision(2) << balance << endl;
        cout << string(60, '-') << endl;
        for (auto &t : history) t.print();
        cout << string(60, '=') << endl;
    }

    double  getBalance()   const { return balance;   }
    string  getOwner()     const { return owner;     }
    string  getAccountNo() const { return accountNo; }
};

int BankAccount::nextAccNo = 1000;

class Bank {
    string name;
    vector<BankAccount*> accounts;
public:
    Bank(string n) : name(n) {}

    BankAccount* createAccount(string owner, double initial = 0.0) {
        auto *acc = new BankAccount(owner, initial);
        accounts.push_back(acc);
        cout << "Account created: " << acc->getAccountNo()
             << " for " << owner << endl;
        return acc;
    }

    void listAccounts() const {
        cout << "
=== " << name << " - All Accounts ===" << endl;
        for (auto *acc : accounts)
            cout << acc->getAccountNo() << " | "
                 << setw(15) << acc->getOwner()
                 << " | Balance: $"
                 << fixed << setprecision(2) << acc->getBalance() << endl;
    }

    double totalAssets() const {
        double total = 0;
        for (auto *acc : accounts) total += acc->getBalance();
        return total;
    }

    ~Bank() { for (auto *acc : accounts) delete acc; }
};

int main() {
    Bank bank("C++ National Bank");

    auto *alice = bank.createAccount("Alice Johnson", 5000.0);
    auto *bob   = bank.createAccount("Bob Smith",     3000.0);
    auto *carol = bank.createAccount("Carol White",   1000.0);

    alice->deposit(2000.0, "Salary");
    alice->withdraw(500.0, "Rent");
    alice->transfer(*bob, 1000.0);

    try {
        carol->withdraw(5000.0);  // Should throw
    } catch (const runtime_error &e) {
        cout << "Error: " << e.what() << endl;
    }

    bob->deposit(200.0, "Freelance payment");
    carol->deposit(3000.0, "Bonus");
    carol->transfer(*alice, 500.0);

    alice->printStatement();
    bob->printStatement();
    carol->printStatement();

    bank.listAccounts();
    cout << fixed << setprecision(2)
         << "Total Assets: $" << bank.totalAssets() << endl;

    return 0;
}

// Iterative Deepening DFS (IDDFS) in C++
#include <iostream>
#include <vector>
using namespace std;

bool dls(vector<vector<int>> &adj, int curr,
         int target, int depth, vector<bool> &visited) {
    if (curr == target) return true;
    if (depth == 0)     return false;
    visited[curr] = true;
    for (int next : adj[curr])
        if (!visited[next])
            if (dls(adj, next, target, depth-1, visited))
                return true;
    visited[curr] = false;  // backtrack
    return false;
}

bool iddfs(vector<vector<int>> &adj, int src, int target, int maxDepth) {
    for (int depth = 0; depth <= maxDepth; depth++) {
        vector<bool> visited(adj.size(), false);
        cout << "Searching at depth " << depth << "..." << endl;
        if (dls(adj, src, target, depth, visited))
            return true;
    }
    return false;
}

int main() {
    int V = 7;
    vector<vector<int>> adj(V);
    adj[0] = {1, 2};
    adj[1] = {3, 4};
    adj[2] = {5, 6};

    cout << "IDDFS: Search for node 6 from 0" << endl;
    bool found = iddfs(adj, 0, 6, 5);
    cout << "Found: " << (found ? "Yes" : "No") << endl;

    cout << "
IDDFS: Search for node 9 from 0 (not exists)" << endl;
    found = iddfs(adj, 0, 9, 3);
    cout << "Found: " << (found ? "Yes" : "No") << endl;
    return 0;
}

// Sparse Table for Range Minimum Query
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

class SparseTable {
    vector<vector<int>> table;
    vector<int> log2floor;
    int n;

public:
    SparseTable(vector<int> &arr) {
        n = arr.size();
        int LOG = log2(n) + 1;
        table.assign(LOG, vector<int>(n));
        log2floor.resize(n + 1);

        // Precompute log2 floor values
        log2floor[1] = 0;
        for (int i = 2; i <= n; i++)
            log2floor[i] = log2floor[i/2] + 1;

        // Build sparse table
        table[0] = arr;
        for (int j = 1; j < LOG; j++)
            for (int i = 0; i + (1<<j) <= n; i++)
                table[j][i] = min(table[j-1][i],
                                  table[j-1][i + (1<<(j-1))]);
    }

    // Range Minimum Query O(1)
    int query(int l, int r) {
        int k = log2floor[r - l + 1];
        return min(table[k][l], table[k][r - (1<<k) + 1]);
    }
};

int main() {
    vector<int> arr = {2, 4, 3, 1, 6, 7, 8, 9, 1, 7};
    SparseTable st(arr);

    cout << "RMQ(0,4): " << st.query(0, 4) << endl;  // 1
    cout << "RMQ(2,7): " << st.query(2, 7) << endl;  // 1
    cout << "RMQ(5,9): " << st.query(5, 9) << endl;  // 1
    cout << "RMQ(0,2): " << st.query(0, 2) << endl;  // 2
    return 0;
}

// Fenwick Tree (Binary Indexed Tree)
#include <iostream>
#include <vector>
using namespace std;

class FenwickTree {
    vector<int> tree;
    int n;
public:
    FenwickTree(int n) : n(n), tree(n + 1, 0) {}

    // Point update: add val to index i (1-indexed)
    void update(int i, int val) {
        for (; i <= n; i += i & (-i))
            tree[i] += val;
    }

    // Prefix sum query [1, i]
    int query(int i) {
        int sum = 0;
        for (; i > 0; i -= i & (-i))
            sum += tree[i];
        return sum;
    }

    // Range sum query [l, r]
    int query(int l, int r) {
        return query(r) - query(l - 1);
    }

    // Build from array
    void build(vector<int> &arr) {
        for (int i = 0; i < (int)arr.size(); i++)
            update(i + 1, arr[i]);
    }
};

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11};
    FenwickTree ft(arr.size());
    ft.build(arr);

    cout << "Prefix sum [1,3]: " << ft.query(1, 3) << endl;  // 9
    cout << "Prefix sum [2,5]: " << ft.query(2, 5) << endl;  // 24
    cout << "Total sum: "        << ft.query(1, 6) << endl;  // 36

    ft.update(3, 6);  // arr[2] += 6 => 5+6=11
    cout << "After update(3,6):" << endl;
    cout << "Prefix sum [1,3]: " << ft.query(1, 3) << endl;  // 15
    cout << "Total sum: "        << ft.query(1, 6) << endl;  // 42
    return 0;
}

// Shell Sort and Interpolation Search in C++
#include <iostream>
#include <vector>
using namespace std;

void shellSort(vector<int> &arr) {
    int n = arr.size();
    for (int gap = n/2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int temp = arr[i], j = i;
            while (j >= gap && arr[j-gap] > temp) {
                arr[j] = arr[j-gap];
                j -= gap;
            }
            arr[j] = temp;
        }
    }
}

int interpolationSearch(vector<int> &arr, int target) {
    int low = 0, high = arr.size() - 1;
    while (low <= high &&
           target >= arr[low] &&
           target <= arr[high]) {
        if (low == high) {
            if (arr[low] == target) return low;
            return -1;
        }
        int pos = low + ((double)(high-low) /
                  (arr[high]-arr[low])) * (target-arr[low]);
        if (arr[pos] == target) return pos;
        if (arr[pos] < target)  low  = pos + 1;
        else                    high = pos - 1;
    }
    return -1;
}

int main() {
    vector<int> arr = {64,34,25,12,22,11,90,1,55,47};
    cout << "Before: ";
    for (int x : arr) cout << x << " ";
    cout << endl;

    shellSort(arr);
    cout << "After Shell Sort: ";
    for (int x : arr) cout << x << " ";
    cout << endl;

    // Interpolation search on sorted array
    vector<int> sorted = {10,20,30,40,50,60,70,80,90,100};
    cout << "Search 70:  index = "
         << interpolationSearch(sorted, 70)  << endl;  // 6
    cout << "Search 45:  index = "
         << interpolationSearch(sorted, 45)  << endl;  // -1
    cout << "Search 100: index = "
         << interpolationSearch(sorted, 100) << endl;  // 9
    return 0;
}

// Advanced C++ - Concepts (C++20)
#include <iostream>
#include <concepts>
#include <vector>
#include <string>
using namespace std;

// Define concepts
template <typename T>
concept Numeric = is_arithmetic_v<T>;

template <typename T>
concept Printable = requires(T t) {
    { cout << t } -> same_as<ostream&>;
};

template <typename T>
concept Container = requires(T t) {
    t.begin();
    t.end();
    t.size();
    typename T::value_type;
};

// Constrained function templates
template <Numeric T>
T square(T x) { return x * x; }

template <Numeric T>
T clamp(T val, T lo, T hi) {
    return val < lo ? lo : val > hi ? hi : val;
}

template <Container C>
void printContainer(const C &c) {
    cout << "[ ";
    for (const auto &x : c) cout << x << " ";
    cout << "]" << endl;
}

template <Container C>
auto sum(const C &c) {
    typename C::value_type total{};
    for (const auto &x : c) total += x;
    return total;
}

int main() {
    cout << "square(5):    " << square(5)    << endl;
    cout << "square(3.14): " << square(3.14) << endl;
    cout << "clamp(15,0,10): " << clamp(15, 0, 10) << endl;
    cout << "clamp(-5,0,10): " << clamp(-5, 0, 10) << endl;

    vector<int>    vi = {1,2,3,4,5};
    vector<double> vd = {1.1,2.2,3.3};
    vector<string> vs = {"hello","world","cpp"};

    printContainer(vi);
    printContainer(vd);
    printContainer(vs);

    cout << "Sum int:    " << sum(vi) << endl;
    cout << "Sum double: " << sum(vd) << endl;
    return 0;
}

// Multithreading with std::async and Futures
#include <iostream>
#include <future>
#include <vector>
#include <numeric>
#include <chrono>
using namespace std;

// Parallel sum using futures
long long parallelSum(vector<int> &arr, int l, int r) {
    if (r - l <= 100000) {
        return accumulate(arr.begin()+l, arr.begin()+r, 0LL);
    }
    int mid = (l + r) / 2;
    auto futLeft  = async(launch::async, parallelSum, ref(arr), l, mid);
    auto futRight = async(launch::async, parallelSum, ref(arr), mid, r);
    return futLeft.get() + futRight.get();
}

// Async task with return value
future<string> fetchData(int id) {
    return async(launch::async, [id]() {
        this_thread::sleep_for(chrono::milliseconds(100));
        return "Data from source " + to_string(id);
    });
}

// Promise and Future
void compute(promise<int> &&prom, int a, int b) {
    try {
        if (b == 0) throw invalid_argument("Division by zero");
        prom.set_value(a / b);
    } catch (...) {
        prom.set_exception(current_exception());
    }
}

int main() {
    // Parallel sum
    vector<int> arr(1000000, 1);
    auto start = chrono::high_resolution_clock::now();
    long long total = parallelSum(arr, 0, arr.size());
    auto end = chrono::high_resolution_clock::now();
    cout << "Parallel sum: " << total << endl;
    cout << "Time: "
         << chrono::duration_cast<chrono::milliseconds>(end-start).count()
         << " ms" << endl;

    // Multiple async tasks
    auto f1 = fetchData(1);
    auto f2 = fetchData(2);
    auto f3 = fetchData(3);
    cout << f1.get() << endl;
    cout << f2.get() << endl;
    cout << f3.get() << endl;

    // Promise / Future
    promise<int> prom;
    future<int>  fut = prom.get_future();
    thread t(compute, move(prom), 42, 7);
    try {
        cout << "Result: " << fut.get() << endl;
    } catch (const exception &e) {
        cout << "Exception: " << e.what() << endl;
    }
    t.join();
    return 0;
}

// Complete Library Management System in C++
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <stdexcept>
#include <memory>
#include <string>
#include <iomanip>
using namespace std;

// -------- Book --------
class Book {
    string isbn, title, author, genre;
    int    year, totalCopies, availableCopies;
public:
    Book(string isbn, string title, string author,
         string genre, int year, int copies = 1)
        : isbn(isbn), title(title), author(author),
          genre(genre), year(year),
          totalCopies(copies), availableCopies(copies) {}

    bool isAvailable()   const { return availableCopies > 0; }
    void checkout()            { if (isAvailable()) availableCopies--; }
    void returnBook()          { if (availableCopies < totalCopies) availableCopies++; }

    string getISBN()     const { return isbn;   }
    string getTitle()    const { return title;  }
    string getAuthor()   const { return author; }
    string getGenre()    const { return genre;  }
    int    getYear()     const { return year;   }
    int    getAvailable()const { return availableCopies; }

    void display() const {
        cout << left
             << setw(15) << isbn
             << setw(30) << title
             << setw(20) << author
             << setw(12) << genre
             << setw(6)  << year
             << "[" << availableCopies << "/" << totalCopies << "]" << endl;
    }
};

// -------- Member --------
class Member {
    string id, name, email;
    vector<string> borrowedISBNs;
    static const int MAX_BORROW = 5;
public:
    Member(string id, string name, string email)
        : id(id), name(name), email(email) {}

    bool canBorrow()     const { return (int)borrowedISBNs.size() < MAX_BORROW; }
    void borrow(const string &isbn)  { borrowedISBNs.push_back(isbn); }
    void returnBook(const string &isbn) {
        borrowedISBNs.erase(
            remove(borrowedISBNs.begin(), borrowedISBNs.end(), isbn),
            borrowedISBNs.end());
    }

    bool hasBorrowed(const string &isbn) const {
        return find(borrowedISBNs.begin(), borrowedISBNs.end(), isbn)
               != borrowedISBNs.end();
    }

    string getId()    const { return id;    }
    string getName()  const { return name;  }
    string getEmail() const { return email; }

    void display() const {
        cout << "Member [" << id << "] " << name
             << " | Email: " << email
             << " | Borrowed: " << borrowedISBNs.size()
             << "/" << MAX_BORROW << endl;
        if (!borrowedISBNs.empty()) {
            cout << "  Books: ";
            for (auto &b : borrowedISBNs) cout << b << " ";
            cout << endl;
        }
    }
};

// -------- Library --------
class Library {
    string name;
    unordered_map<string, shared_ptr<Book>>   books;
    unordered_map<string, shared_ptr<Member>> members;

public:
    Library(string n) : name(n) {}

    // ---- Book Management ----
    void addBook(shared_ptr<Book> book) {
        books[book->getISBN()] = book;
        cout << "Book added: " << book->getTitle() << endl;
    }

    void removeBook(const string &isbn) {
        if (books.erase(isbn))
            cout << "Book " << isbn << " removed." << endl;
        else
            throw runtime_error("Book not found: " + isbn);
    }

    // ---- Member Management ----
    void registerMember(shared_ptr<Member> member) {
        members[member->getId()] = member;
        cout << "Member registered: " << member->getName() << endl;
    }

    // ---- Borrow / Return ----
    void borrowBook(const string &memberId, const string &isbn) {
        auto &m = getMember(memberId);
        auto &b = getBook(isbn);

        if (!m->canBorrow())
            throw runtime_error(m->getName() + " has reached borrow limit");
        if (!b->isAvailable())
            throw runtime_error("Book not available: " + b->getTitle());

        b->checkout();
        m->borrow(isbn);
        cout << m->getName() << " borrowed: " << b->getTitle() << endl;
    }

    void returnBook(const string &memberId, const string &isbn) {
        auto &m = getMember(memberId);
        auto &b = getBook(isbn);

        if (!m->hasBorrowed(isbn))
            throw runtime_error(m->getName() + " did not borrow this book");

        b->returnBook();
        m->returnBook(isbn);
        cout << m->getName() << " returned: " << b->getTitle() << endl;
    }

    // ---- Search ----
    vector<shared_ptr<Book>> searchByAuthor(const string &author) const {
        vector<shared_ptr<Book>> res;
        for (auto &[isbn, b] : books)
            if (b->getAuthor().find(author) != string::npos) res.push_back(b);
        return res;
    }

    vector<shared_ptr<Book>> searchByGenre(const string &genre) const {
        vector<shared_ptr<Book>> res;
        for (auto &[isbn, b] : books)
            if (b->getGenre() == genre) res.push_back(b);
        return res;
    }

    // ---- Display ----
    void displayAllBooks() const {
        cout << "
=== " << name << " - Catalog ===" << endl;
        cout << left
             << setw(15) << "ISBN"
             << setw(30) << "Title"
             << setw(20) << "Author"
             << setw(12) << "Genre"
             << setw(6)  << "Year"
             << "Copies" << endl;
        cout << string(90, '-') << endl;
        vector<shared_ptr<Book>> sorted;
        for (auto &[k,v] : books) sorted.push_back(v);
        sort(sorted.begin(), sorted.end(),
             [](auto &a, auto &b){ return a->getTitle() < b->getTitle(); });
        for (auto &b : sorted) b->display();
    }

    void displayAllMembers() const {
        cout << "
=== " << name << " - Members ===" << endl;
        for (auto &[id, m] : members) m->display();
    }

    void displayStats() const {
        int total = books.size(), available = 0;
        for (auto &[k,v] : books)
            if (v->isAvailable()) available++;
        cout << "
=== Stats ===" << endl;
        cout << "Total books:     " << total     << endl;
        cout << "Available:       " << available << endl;
        cout << "Checked out:     " << (total - available) << endl;
        cout << "Total members:   " << members.size() << endl;
    }

private:
    shared_ptr<Book>   &getBook(const string &isbn) {
        auto it = books.find(isbn);
        if (it == books.end()) throw runtime_error("Book not found: " + isbn);
        return it->second;
    }
    shared_ptr<Member> &getMember(const string &id) {
        auto it = members.find(id);
        if (it == members.end()) throw runtime_error("Member not found: " + id);
        return it->second;
    }
};

// -------- Main --------
int main() {
    Library lib("C++ City Library");

    // Add books
    lib.addBook(make_shared<Book>("978-0","The C++ Book",    "Bjarne Stroustrup","Programming",2020,3));
    lib.addBook(make_shared<Book>("978-1","Design Patterns", "Gang of Four",     "Programming",2015,2));
    lib.addBook(make_shared<Book>("978-2","Clean Code",      "Robert Martin",    "Programming",2008,4));
    lib.addBook(make_shared<Book>("978-3","Dune",            "Frank Herbert",    "Sci-Fi",     1965,2));
    lib.addBook(make_shared<Book>("978-4","1984",            "George Orwell",    "Fiction",    1949,3));

    // Register members
    lib.registerMember(make_shared<Member>("M001","Alice Johnson","alice@email.com"));
    lib.registerMember(make_shared<Member>("M002","Bob Smith",    "bob@email.com"));
    lib.registerMember(make_shared<Member>("M003","Carol White",  "carol@email.com"));

    lib.displayAllBooks();

    // Borrow books
    lib.borrowBook("M001", "978-0");
    lib.borrowBook("M001", "978-2");
    lib.borrowBook("M002", "978-1");
    lib.borrowBook("M003", "978-3");

    // Error handling
    try {
        lib.borrowBook("M001", "978-9");  // nonexistent
    } catch (const runtime_error &e) {
        cout << "Error: " << e.what() << endl;
    }

    // Return
    lib.returnBook("M001", "978-0");
    lib.borrowBook("M002", "978-0");

    // Search
    cout << "
Search by genre 'Programming':" << endl;
    for (auto &b : lib.searchByGenre("Programming")) b->display();

    lib.displayAllMembers();
    lib.displayStats();

    return 0;
}