Practice Problems

advanced

Part of Advanced C++

Theory

This lesson focuses on practical problem-solving in C++. You'll implement classic algorithms and mathematical functions. Each problem demonstrates important C++ concepts and techniques.

Problem-Solving Approach

When approaching any programming problem:

Understand the problem — What are the inputs and outputs?
Plan the algorithm — Write pseudocode or draw a flowchart
Choose data structures — Array, vector, map, etc.
Implement — Write clean, well-structured code
Test — Verify with sample inputs
Optimize — Improve performance if needed

Common String Operations

Strings are fundamental to many problems:

// String reversal
string reverseString(const string& str) {
    return string(str.rbegin(), str.rend());
}
 
// Palindrome check
bool isPalindrome(const string& str) {
    string cleaned;
    for (char c : str) {
        if (isalnum(c)) cleaned += tolower(c);
    }
    string reversed(cleaned.rbegin(), cleaned.rend());
    return cleaned == reversed;
}

Mathematical Functions

Many problems involve mathematical computations:

// Factorial
long long factorial(int n) {
    long long result = 1;
    for (int i = 2; i <= n; i++) result *= i;
    return result;
}
 
// Fibonacci
int fibonacci(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        int temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

Array and Search Algorithms

Linear search — O(n):

int linearSearch(const vector<int>& arr, int target) {
    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}

Binary search — O(log n), requires sorted array:

int binarySearch(const 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;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

Sorting

Bubble sort — O(n²):

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;  // Optimization: already sorted
    }
}

Number Theory Problems

Prime number check:

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

Armstrong number (a number equal to sum of cubes of its digits):

bool isArmstrong(int n) {
    int original = n, sum = 0;
    while (n > 0) {
        int digit = n % 10;
        sum += digit * digit * digit;
        n /= 10;
    }
    return sum == original;
}

Sum of digits:

int sumOfDigits(int n) {
    int sum = 0;
    n = abs(n);
    while (n > 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

Always consider edge cases: empty arrays, negative numbers, zero, very large inputs. Test your code with these boundary conditions.

Practical Examples

Example 1: Complete Problem Solutions

cpp

Example 2: Search and Sort Algorithms

cpp

For competitive programming or interviews, practice writing these algorithms from memory. Know the time and space complexity of each one.

Exercises

Prime Number and Armstrong Number Checker

medium

Write a program that asks the user for a range (start and end). For each number in the range, determine if it is prime, an Armstrong number, both, or neither. Print the results in a formatted table.

Expected Output:

A formatted table showing each number with Yes/No for prime and Armstrong. For range 1-10, 2,3,5,7 are prime; 1-9 are Armstrong.

Student Grade Analysis with Statistics

medium

Write a program that reads student scores, stores them in a vector, and computes: average, median, mode, standard deviation, min, max, and a letter grade distribution.

Expected Output:

Mean: 84.50\nMedian: 85.50\nMode: 88\nStd Dev: 7.21\nMin: 69\nMax: 95\nGrade Dist: A:5 B:7 C:5 D:2 F:1

Binary Search Tree from Array

hard

Write a program that takes a sorted array and constructs a balanced Binary Search Tree. Then implement in-order, pre-order, and post-order traversal. Finally, implement a function to find the K-th smallest element.

Expected Output:

In-order: 1 2 3 4 5 6 7 8 9 10\nPre-order: 5 2 1 3 4 8 6 7 9 10\nPost-order: 1 4 3 2 7 6 10 9 8 5\n3rd smallest: 3\n7th smallest: 7

Mini Quiz

Mini Project

Mini Project: Complete Problem Solutions Library

Create a comprehensive C++ library of algorithmic functions. Organize them into categories (searching, sorting, math, strings, arrays) with a menu-driven interface that lets users test each algorithm with custom input.

Requirements:

Bonus Challenge

Implement advanced algorithms: merge sort, quick sort, Dijkstra's shortest path. Add timing measurement using <chrono> to compare algorithm performance.