cpp
exercises
exercises.cpp⚙️cpp
/**
* C++ Vectors - Exercises
*
* Practice problems to reinforce understanding of C++ vectors.
* Each exercise includes a description, TODO section, and hints.
* Complete solutions are provided in the ANSWER KEY at the bottom.
*
* Difficulty Levels:
* ⭐ - Beginner
* ⭐⭐ - Intermediate
* ⭐⭐⭐ - Advanced
*
* Compile: g++ -std=c++17 -Wall -Wextra exercises.cpp -o exercises
* Run: ./exercises
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <string>
#include <cmath>
using namespace std;
// Helper to print vector
template<typename T>
void printVector(const vector<T>& v, const string& label = "") {
if (!label.empty()) cout << label << ": ";
cout << "[";
for (size_t i = 0; i < v.size(); i++) {
cout << v[i];
if (i < v.size() - 1) cout << ", ";
}
cout << "]" << endl;
}
// ============================================================
// Exercise 1: Find Second Largest ⭐
// ============================================================
/**
* Find and return the second largest element in a vector.
* If the vector has less than 2 elements, return -1.
*
* Examples:
* secondLargest({3, 7, 2, 9, 1}) returns 7
* secondLargest({5, 5, 5}) returns 5 (duplicates are OK)
* secondLargest({1}) returns -1
*/
int secondLargest(const vector<int>& v) {
// TODO: Find and return the second largest element
// Hint: Track both largest and second largest
// Hint: Handle edge cases (size < 2)
return -1; // Replace with your implementation
}
// ============================================================
// Exercise 2: Remove All Occurrences ⭐
// ============================================================
/**
* Remove all occurrences of a target value from the vector.
* Modify the vector in place.
*
* Examples:
* removeAll({1, 2, 3, 2, 4, 2}, 2) -> {1, 3, 4}
* removeAll({5, 5, 5}, 5) -> {}
*/
void removeAll(vector<int>& v, int target) {
// TODO: Remove all occurrences of target
// Hint: Use erase-remove idiom
// Hint: Or use manual iteration with iterator adjustment
}
// ============================================================
// Exercise 3: Rotate Vector ⭐
// ============================================================
/**
* Rotate the vector to the left by k positions.
*
* Examples:
* rotateLeft({1, 2, 3, 4, 5}, 2) -> {3, 4, 5, 1, 2}
* rotateLeft({1, 2, 3}, 1) -> {2, 3, 1}
*/
void rotateLeft(vector<int>& v, int k) {
// TODO: Rotate vector left by k positions
// Hint: k = k % v.size() to handle k > size
// Hint: You can use std::rotate from <algorithm>
}
// ============================================================
// Exercise 4: Find Missing Number ⭐⭐
// ============================================================
/**
* Given a vector containing n distinct numbers from 0 to n,
* find the one number that is missing.
*
* Examples:
* findMissing({3, 0, 1}) returns 2
* findMissing({0, 1}) returns 2
* findMissing({9,6,4,2,3,5,7,0,1}) returns 8
*/
int findMissing(const vector<int>& v) {
// TODO: Find the missing number
// Hint: Sum of 0 to n is n*(n+1)/2
// Hint: Subtract actual sum to find missing
return -1; // Replace with your implementation
}
// ============================================================
// Exercise 5: Move Zeros ⭐⭐
// ============================================================
/**
* Move all zeros to the end while maintaining the relative
* order of non-zero elements.
*
* Examples:
* moveZeros({0, 1, 0, 3, 12}) -> {1, 3, 12, 0, 0}
* moveZeros({0, 0, 1}) -> {1, 0, 0}
*/
void moveZeros(vector<int>& v) {
// TODO: Move all zeros to the end
// Hint: Use two-pointer technique
// Hint: Or use stable_partition from <algorithm>
}
// ============================================================
// Exercise 6: Find Duplicates ⭐⭐
// ============================================================
/**
* Return a vector containing all elements that appear
* more than once in the input vector.
*
* Examples:
* findDuplicates({1, 2, 3, 2, 4, 3, 5}) returns {2, 3}
* findDuplicates({1, 2, 3}) returns {}
*/
vector<int> findDuplicates(const vector<int>& v) {
// TODO: Find all duplicate elements
// Hint: Sort a copy, then find adjacent equals
// Hint: Or use a map to count occurrences
return {}; // Replace with your implementation
}
// ============================================================
// Exercise 7: Product Except Self ⭐⭐
// ============================================================
/**
* Return a vector where each element is the product of all
* elements except the one at that index.
* Do NOT use division.
*
* Examples:
* productExceptSelf({1, 2, 3, 4}) returns {24, 12, 8, 6}
* productExceptSelf({-1, 1, 0, -3, 3}) returns {0, 0, 9, 0, 0}
*/
vector<int> productExceptSelf(const vector<int>& v) {
// TODO: Calculate product of all elements except self
// Hint: Use prefix and suffix products
// Hint: First pass: calculate prefix products
// Hint: Second pass: multiply by suffix products
return {}; // Replace with your implementation
}
// ============================================================
// Exercise 8: Merge Intervals ⭐⭐⭐
// ============================================================
/**
* Merge overlapping intervals.
* Each interval is represented as {start, end}.
*
* Examples:
* mergeIntervals({{1,3},{2,6},{8,10},{15,18}}) returns {{1,6},{8,10},{15,18}}
* mergeIntervals({{1,4},{4,5}}) returns {{1,5}}
*/
vector<pair<int,int>> mergeIntervals(vector<pair<int,int>> intervals) {
// TODO: Merge overlapping intervals
// Hint: Sort by start time
// Hint: Iterate and merge if current overlaps with previous
return {}; // Replace with your implementation
}
// ============================================================
// Exercise 9: Longest Consecutive Sequence ⭐⭐⭐
// ============================================================
/**
* Find the length of the longest consecutive elements sequence.
*
* Examples:
* longestConsecutive({100, 4, 200, 1, 3, 2}) returns 4 (sequence: 1,2,3,4)
* longestConsecutive({0, 3, 7, 2, 5, 8, 4, 6, 0, 1}) returns 9
*/
int longestConsecutive(const vector<int>& v) {
// TODO: Find longest consecutive sequence
// Hint: Use a set for O(1) lookup
// Hint: For each number, check if it's the start of a sequence
// Hint: Count consecutive numbers starting from there
return 0; // Replace with your implementation
}
// ============================================================
// Exercise 10: Subarray Sum Equals K ⭐⭐⭐
// ============================================================
/**
* Count the number of contiguous subarrays that sum to k.
*
* Examples:
* subarraySum({1, 1, 1}, 2) returns 2
* subarraySum({1, 2, 3}, 3) returns 2 ({1,2} and {3})
*/
int subarraySum(const vector<int>& v, int k) {
// TODO: Count subarrays with sum = k
// Hint: Use prefix sum with hash map
// Hint: If prefixSum[j] - prefixSum[i] = k, subarray from i+1 to j has sum k
// Hint: Map stores count of each prefix sum seen so far
return 0; // Replace with your implementation
}
// ============================================================
// BONUS Exercise: Three Sum ⭐⭐⭐
// ============================================================
/**
* Find all unique triplets in the array which give the sum of zero.
*
* Examples:
* threeSum({-1, 0, 1, 2, -1, -4}) returns {{-1, -1, 2}, {-1, 0, 1}}
*/
vector<vector<int>> threeSum(vector<int> nums) {
// TODO: Find all triplets that sum to zero
// Hint: Sort the array first
// Hint: Fix one element, then use two-pointer technique
// Hint: Skip duplicates to avoid duplicate triplets
return {}; // Replace with your implementation
}
// ============================================================
// Test Functions
// ============================================================
void testExercise1() {
cout << "\n=== Testing Exercise 1: Second Largest ===" << endl;
vector<int> v1 = {3, 7, 2, 9, 1};
vector<int> v2 = {5, 5, 5};
vector<int> v3 = {1};
cout << "secondLargest({3,7,2,9,1}) = " << secondLargest(v1) << " (expected: 7)" << endl;
cout << "secondLargest({5,5,5}) = " << secondLargest(v2) << " (expected: 5)" << endl;
cout << "secondLargest({1}) = " << secondLargest(v3) << " (expected: -1)" << endl;
}
void testExercise2() {
cout << "\n=== Testing Exercise 2: Remove All ===" << endl;
vector<int> v = {1, 2, 3, 2, 4, 2};
printVector(v, "Before");
removeAll(v, 2);
printVector(v, "After removeAll(2)");
cout << "(expected: [1, 3, 4])" << endl;
}
void testExercise3() {
cout << "\n=== Testing Exercise 3: Rotate Left ===" << endl;
vector<int> v = {1, 2, 3, 4, 5};
printVector(v, "Before");
rotateLeft(v, 2);
printVector(v, "After rotateLeft(2)");
cout << "(expected: [3, 4, 5, 1, 2])" << endl;
}
void testExercise4() {
cout << "\n=== Testing Exercise 4: Find Missing ===" << endl;
vector<int> v1 = {3, 0, 1};
vector<int> v2 = {9, 6, 4, 2, 3, 5, 7, 0, 1};
cout << "findMissing({3,0,1}) = " << findMissing(v1) << " (expected: 2)" << endl;
cout << "findMissing({9,6,4,2,3,5,7,0,1}) = " << findMissing(v2) << " (expected: 8)" << endl;
}
void testExercise5() {
cout << "\n=== Testing Exercise 5: Move Zeros ===" << endl;
vector<int> v = {0, 1, 0, 3, 12};
printVector(v, "Before");
moveZeros(v);
printVector(v, "After moveZeros");
cout << "(expected: [1, 3, 12, 0, 0])" << endl;
}
void testExercise6() {
cout << "\n=== Testing Exercise 6: Find Duplicates ===" << endl;
vector<int> v = {1, 2, 3, 2, 4, 3, 5};
auto result = findDuplicates(v);
sort(result.begin(), result.end());
printVector(result, "findDuplicates({1,2,3,2,4,3,5})");
cout << "(expected: [2, 3])" << endl;
}
void testExercise7() {
cout << "\n=== Testing Exercise 7: Product Except Self ===" << endl;
vector<int> v = {1, 2, 3, 4};
auto result = productExceptSelf(v);
printVector(result, "productExceptSelf({1,2,3,4})");
cout << "(expected: [24, 12, 8, 6])" << endl;
}
void testExercise8() {
cout << "\n=== Testing Exercise 8: Merge Intervals ===" << endl;
vector<pair<int,int>> intervals = {{1,3}, {2,6}, {8,10}, {15,18}};
auto result = mergeIntervals(intervals);
cout << "mergeIntervals: ";
for (auto& p : result) cout << "{" << p.first << "," << p.second << "} ";
cout << endl;
cout << "(expected: {1,6} {8,10} {15,18})" << endl;
}
void testExercise9() {
cout << "\n=== Testing Exercise 9: Longest Consecutive ===" << endl;
vector<int> v1 = {100, 4, 200, 1, 3, 2};
vector<int> v2 = {0, 3, 7, 2, 5, 8, 4, 6, 0, 1};
cout << "longestConsecutive({100,4,200,1,3,2}) = " << longestConsecutive(v1) << " (expected: 4)" << endl;
cout << "longestConsecutive({0,3,7,2,5,8,4,6,0,1}) = " << longestConsecutive(v2) << " (expected: 9)" << endl;
}
void testExercise10() {
cout << "\n=== Testing Exercise 10: Subarray Sum ===" << endl;
vector<int> v1 = {1, 1, 1};
vector<int> v2 = {1, 2, 3};
cout << "subarraySum({1,1,1}, 2) = " << subarraySum(v1, 2) << " (expected: 2)" << endl;
cout << "subarraySum({1,2,3}, 3) = " << subarraySum(v2, 3) << " (expected: 2)" << endl;
}
void testBonus() {
cout << "\n=== Testing BONUS: Three Sum ===" << endl;
vector<int> v = {-1, 0, 1, 2, -1, -4};
auto result = threeSum(v);
cout << "threeSum({-1,0,1,2,-1,-4}):" << endl;
for (auto& triplet : result) {
cout << " [" << triplet[0] << ", " << triplet[1] << ", " << triplet[2] << "]" << endl;
}
cout << "(expected: [-1,-1,2] and [-1,0,1])" << endl;
}
// ============================================================
// Main Function
// ============================================================
int main() {
cout << "╔════════════════════════════════════════════════════════════╗" << endl;
cout << "║ C++ VECTORS - EXERCISES ║" << endl;
cout << "╚════════════════════════════════════════════════════════════╝" << endl;
testExercise1();
testExercise2();
testExercise3();
testExercise4();
testExercise5();
testExercise6();
testExercise7();
testExercise8();
testExercise9();
testExercise10();
testBonus();
cout << "\n╔════════════════════════════════════════════════════════════╗" << endl;
cout << "║ Complete the TODO sections and re-run! ║" << endl;
cout << "╚════════════════════════════════════════════════════════════╝" << endl;
return 0;
}
// ============================================================
// ANSWER KEY
// ============================================================
/*
// Exercise 1: Second Largest
int secondLargest(const vector<int>& v) {
if (v.size() < 2) return -1;
int first = INT_MIN, second = INT_MIN;
for (int x : v) {
if (x > first) {
second = first;
first = x;
} else if (x > second) {
second = x;
}
}
return second == INT_MIN ? first : second;
}
// Exercise 2: Remove All
void removeAll(vector<int>& v, int target) {
v.erase(remove(v.begin(), v.end(), target), v.end());
}
// Exercise 3: Rotate Left
void rotateLeft(vector<int>& v, int k) {
if (v.empty()) return;
k = k % v.size();
rotate(v.begin(), v.begin() + k, v.end());
}
// Exercise 4: Find Missing
int findMissing(const vector<int>& v) {
int n = v.size();
int expectedSum = n * (n + 1) / 2;
int actualSum = accumulate(v.begin(), v.end(), 0);
return expectedSum - actualSum;
}
// Exercise 5: Move Zeros
void moveZeros(vector<int>& v) {
int writeIdx = 0;
for (int i = 0; i < v.size(); i++) {
if (v[i] != 0) {
swap(v[i], v[writeIdx]);
writeIdx++;
}
}
}
// Exercise 6: Find Duplicates
vector<int> findDuplicates(const vector<int>& v) {
vector<int> sorted = v;
sort(sorted.begin(), sorted.end());
vector<int> result;
for (size_t i = 1; i < sorted.size(); i++) {
if (sorted[i] == sorted[i-1] &&
(result.empty() || result.back() != sorted[i])) {
result.push_back(sorted[i]);
}
}
return result;
}
// Exercise 7: Product Except Self
vector<int> productExceptSelf(const vector<int>& v) {
int n = v.size();
vector<int> result(n, 1);
// Calculate prefix products
int prefix = 1;
for (int i = 0; i < n; i++) {
result[i] = prefix;
prefix *= v[i];
}
// Calculate suffix products and multiply
int suffix = 1;
for (int i = n - 1; i >= 0; i--) {
result[i] *= suffix;
suffix *= v[i];
}
return result;
}
// Exercise 8: Merge Intervals
vector<pair<int,int>> mergeIntervals(vector<pair<int,int>> intervals) {
if (intervals.empty()) return {};
sort(intervals.begin(), intervals.end());
vector<pair<int,int>> result;
result.push_back(intervals[0]);
for (size_t i = 1; i < intervals.size(); i++) {
if (intervals[i].first <= result.back().second) {
result.back().second = max(result.back().second, intervals[i].second);
} else {
result.push_back(intervals[i]);
}
}
return result;
}
// Exercise 9: Longest Consecutive
#include <unordered_set>
int longestConsecutive(const vector<int>& v) {
unordered_set<int> nums(v.begin(), v.end());
int longest = 0;
for (int num : nums) {
// Only start counting from beginning of sequence
if (nums.find(num - 1) == nums.end()) {
int current = num;
int length = 1;
while (nums.find(current + 1) != nums.end()) {
current++;
length++;
}
longest = max(longest, length);
}
}
return longest;
}
// Exercise 10: Subarray Sum
#include <unordered_map>
int subarraySum(const vector<int>& v, int k) {
unordered_map<int, int> prefixCount;
prefixCount[0] = 1; // Empty subarray
int sum = 0;
int count = 0;
for (int num : v) {
sum += num;
// If (sum - k) exists as a prefix sum, we found subarrays
if (prefixCount.find(sum - k) != prefixCount.end()) {
count += prefixCount[sum - k];
}
prefixCount[sum]++;
}
return count;
}
// BONUS: Three Sum
vector<vector<int>> threeSum(vector<int> nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for (size_t i = 0; i < nums.size(); i++) {
// Skip duplicates for first number
if (i > 0 && nums[i] == nums[i-1]) continue;
int target = -nums[i];
size_t left = i + 1;
size_t right = nums.size() - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum < target) {
left++;
} else if (sum > target) {
right--;
} else {
result.push_back({nums[i], nums[left], nums[right]});
// Skip duplicates
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
}
}
}
return result;
}
*/