#include <bits/stdc++.h>
using namespace std;

// Function to perform DFS and topological sorting
void topologicalSortUtil(int v, vector<vector<int>> &adj, vector<bool> &visited, stack<int> &st) {
    // Mark the current node as visited
    visited[v] = true;

    // Recur for all adjacent vertices
    for (int i : adj[v]) {
        if (!visited[i])
            topologicalSortUtil(i, adj, visited, st);
    }

    // Push current vertex to stack which stores the result
    st.push(v);
}

vector<vector<int>> constructAdj(int V, vector<vector<int>> &edges) {
    vector<vector<int>> adj(V);

    for (auto it : edges) {
        adj[it[0]].push_back(it[1]);
    }

    return adj;
}

// Function to perform Topological Sort
vector<int> topologicalSort(int V, vector<vector<int>> &edges) {
    // Stack to store the result
    stack<int> st;

    vector<bool> visited(V, false);
    vector<vector<int>> adj = constructAdj(V, edges);

    // Call the recursive helper function for all vertices
    for (int i = 0; i < V; i++) {
        if (!visited[i])
            topologicalSortUtil(i, adj, visited, st);
    }

    vector<int> ans;

    // Append contents of stack
    while (!st.empty()) {
        ans.push_back(st.top());
        st.pop();
    }

    return ans;
}

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

    vector<int> ans = topologicalSort(V, edges);

    for (int node : ans) {
        cout << node << " ";
    }
    cout << endl;

    return 0;
}

Source:geeksforgeeks

#include <bits/stdc++.h>
using namespace std;

// function to check if brackets are balanced
bool areBracketsBalanced(string expr)
{
    stack s;
    char x;

    // Traversing the Expression
    for (int i = 0; i < expr.length(); i++) 
    {
        if (expr[i] == '(' || expr[i] == '[' || expr[i] == '{') 
        {
            // Push the element in the stack
            s.push(expr[i]);
            continue;
        }

        // IF current current character is not opening
        // bracket, then it must be closing. So stack
        // cannot be empty at this point.
        if (s.empty())
            return false;

        switch (expr[i]) {
        case ')':
            // Store the top element in a
            x = s.top();
            s.pop();
            if (x == '{' || x == '[')
                return false;
            break;

        case '}':
            // Store the top element in b
            x = s.top();
            s.pop();
            if (x == '(' || x == '[')
                return false;
            break;

        case ']':
            // Store the top element in c
            x = s.top();
            s.pop();
            if (x == '(' || x == '{')
                return false;
            break;
        }
    }

    // Check Empty Stack
    return (s.empty());
}

// Driver code
int main()
{
    string expr;

    // Taking input from the user
    cout << "Enter an expression: "; cin >> expr;

    // Function call
    if (areBracketsBalanced(expr))
        cout << "Balanced\n";
    else
        cout << "Not Balanced\n";
    return 0;
}

Source : GeeksforGeeks

#include <bits/stdc++.h>
using namespace std;

#define ll long long

bool isMountain(vector<ll> a) {
    ll n = a.size();

    if (n < 3)
        return false;

    ll i = 1;

    // Increasing part
    while (i < n && a[i] > a[i - 1]) {
        i++;
    }

    // Peak cannot be first or last
    if (i == 1 || i == n)
        return false;

    // Decreasing part
    while (i < n && a[i] < a[i - 1]) {
        i++;
    }

    return i == n;
}

int main() {
    ll n;
    cin >> n;

    vector<ll> a(n);
    for (ll i = 0; i < n; i++) {
        cin >> a[i];
    }

    if (isMountain(a)) {
        cout << "Mountain" << endl;
    } else {
        cout << "Not Mountain" << endl;
    }

    return 0;
}

Source: Geeksforgeeks

#include <bits/stdc++.h>
using namespace std;

#define N 6

// Define structure for Activity
struct Activity {
    int start, finish;
};

// Function to compare two activities
bool Sort_activity(Activity s1, Activity s2) {
    return (s1.finish < s2.finish); // Sort by finish time
}

// Function to print the maximum number of activities
void print_Max_Activities(Activity arr[], int n) {
    // Sort activities based on finish time
    sort(arr, arr + n, Sort_activity);

    cout << "Following activities are selected: \n";

    int i = 0;
    cout << "(" << arr[i].start << ", " << arr[i].finish << ")\n";

    // Select the next activity that starts after the last selected activity finishes
    for (int j = 1; j < n; j++) {
        if (arr[j].start >= arr[i].finish) {
            cout << "(" << arr[j].start << ", " << arr[j].finish << ")\n";
            i = j;
        }
    }
}

int main() {
    Activity arr[N];

    // Taking input from the user
    for (int i = 0; i < N; i++) {
        cout << "Enter the start and finish time for job " << i + 1 << " : ";
        cin >> arr[i].start >> arr[i].finish;
    }

    // Function call to print the selected activities
    print_Max_Activities(arr, N);

    return 0;
}

#include <iostream>
#include <string>
using namespace std;

// Bank Management System using Class & Inheritance in C++
/*
1. Saving Account
2. Current Account
3. Account Creation
4. Deposit
5. Withdraw
6. Balance
*/

class account {
private:
    string name;
    int accno;
    string atype;

public:
    void getAccountDetails() {
        cout << "\nEnter Customer Name : ";
        cin >> name;
        cout << "Enter Account Number : ";
        cin >> accno;
        cout << "Enter Account Type : ";
        cin >> atype;
    }

    void displayDetails() {
        cout << "\n\nCustomer Name : " << name;
        cout << "\nAccount Number : " << accno;
        cout << "\nAccount Type : " << atype;
    }
};

class current_account : public account {
private:
    float balance = 0;

public:
    void c_display() {
        cout << "\nBalance : " << balance;
    }

    void c_deposit() {
        float deposit;
        cout << "\nEnter amount to Deposit : ";
        cin >> deposit;
        balance = balance + deposit;
    }

    void c_withdraw() {
        float withdraw;
        cout << "\n\nBalance : " << balance;
        cout << "\nEnter amount to be withdraw : ";
        cin >> withdraw;

        if (balance >= withdraw && balance > 1000) {
            balance = balance - withdraw;
            cout << "\nBalance Amount After Withdraw: " << balance;
        } else {
            cout << "\nInsufficient Balance";
        }
    }
};

class saving_account : public account {
private:
    float sav_balance = 0;

public:
    void s_display() {
        cout << "\nBalance : " << sav_balance;
    }

    void s_deposit() {
        float deposit, interest;
        cout << "\nEnter amount to Deposit : ";
        cin >> deposit;
        sav_balance = sav_balance + deposit;
        interest = (sav_balance * 2) / 100;
        sav_balance = sav_balance + interest;
    }

    void s_withdraw() {
        float withdraw;
        cout << "\nBalance : " << sav_balance;
        cout << "\nEnter amount to be withdraw : ";
        cin >> withdraw;

        if (sav_balance >= withdraw && sav_balance > 500) {
            sav_balance = sav_balance - withdraw;
            cout << "\nBalance Amount After Withdraw: " << sav_balance;
        } else {
            cout << "\nInsufficient Balance";
        }
    }
};

int main() {
    current_account c1;
    saving_account s1;
    char type;
    int choice;

    cout << "\nEnter S for saving customer and C for current a/c customer : ";
    cin >> type;

    if (type == 's' || type == 'S') {
        s1.getAccountDetails();

        while (1) {
            cout << "\nChoose Your Choice" << endl;
            cout << "1) Deposit" << endl;
            cout << "2) Withdraw" << endl;
            cout << "3) Display Balance" << endl;
            cout << "4) Display with full Details" << endl;
            cout << "5) Exit" << endl;
            cout << "Enter Your choice: ";
            cin >> choice;

            switch (choice) {
                case 1:
                    s1.s_deposit();
                    break;
                case 2:
                    s1.s_withdraw();
                    break;
                case 3:
                    s1.s_display();
                    break;
                case 4:
                    s1.displayDetails();
                    s1.s_display();
                    break;
                case 5:
                    goto end;
                default:
                    cout << "\n\nEntered choice is invalid, TRY AGAIN";
            }
        }
    } 
    else if (type == 'c' || type == 'C') {
        c1.getAccountDetails();

        while (1) {
            cout << "\nChoose Your Choice" << endl;
            cout << "1) Deposit" << endl;
            cout << "2) Withdraw" << endl;
            cout << "3) Display Balance" << endl;
            cout << "4) Display with full Details" << endl;
            cout << "5) Exit" << endl;
            cout << "Enter Your choice: ";
            cin >> choice;

            switch (choice) {
                case 1:
                    c1.c_deposit();
                    break;
                case 2:
                    c1.c_withdraw();
                    break;
                case 3:
                    c1.c_display();
                    break;
                case 4:
                    c1.displayDetails();
                    c1.c_display();
                    break;
                case 5:
                    goto end;
                default:
                    cout << "\n\nEntered choice is invalid, TRY AGAIN";
            }
        }
    } 
    else {
        cout << "\nInvalid Account Selection";
    }

end:
    cout << "\nThank You for Banking with us..";
    return 0;
}

SELECT cname
FROM Works
GROUP BY cname
HAVING SUM(salary) < 100000;

SELECT e.ename
FROM Employee e, Works w, Company c
WHERE e.city = c.city
  AND w.cname = c.cname
  AND e.ename = w.ename
  AND e.city = w.city;

UPDATE Works
SET salary = salary + salary * 0.1
WHERE cname = 'First Century Bank';

SELECT cname
FROM Works
GROUP BY cname
HAVING SUM(salary) < 100000;

Inheritance:
Inheritance is an important concept of Object-Oriented Programming (OOP) where one class (child class) can acquire the properties and methods of another class (parent class). It helps in code reuse and creates a relationship between classes.

Example (C++):

#include <iostream>
using namespace std;

class Animal {
public:
    void eat() {
        cout << "Animal is eating" << endl;
    }
};

class Dog : public Animal {
public:
    void bark() {
        cout << "Dog is barking" << endl;
    }
};

int main() {
    Dog d;
    d.eat();   // inherited function
    d.bark();  // own function
}

In this example, the Dog class inherits the eat() function from the Animal class.

Polymorphism:
Polymorphism means “many forms”. It allows the same function name to perform different tasks depending on the situation. It improves flexibility and reusability in programs.

Example (Function Overloading in C++):

#include <iostream>
using namespace std;

class Math {
public:
    int add(int a, int b) {
        return a + b;
    }

    double add(double a, double b) {
        return a + b;
    }
};

int main() {
    Math m;
    cout << m.add(5, 3) << endl;
    cout << m.add(4.5, 2.3) << endl;
}

Here the function add() works in different ways depending on the data type of the arguments. This is an example of polymorphism.

Regular Expression

For binary strings over the alphabet Σ = {0,1} that contain a number of 0's which is a multiple of 3, the regular expression is:

1*(01*01*01*)*1*

Explanation

• 1* allows any number of 1's (including none) before, between, and after the zeros.
• 01*01*01* represents exactly three 0's, where each pair of 0's may be separated by any number of 1's.
• (01*01*01*)* repeats this group any number of times, ensuring the total number of 0's is always a multiple of 3.

Examples

Accepted Strings:
ε
111
000
010010
101001010111
000111000

Rejected Strings:
0
00
0000
10001