Array Interview Problems with C++ Solutions
Problem: Count Pairs with Given Sum
int arr[] = {1, 5, 7, -1, 5};
int n = sizeof(arr)/sizeof(arr[0]);
int sum = 6, count = 0;
for(int i = 0; i < n; i++)
for(int j = i+1; j < n; j++)
if(arr[i] + arr[j] == sum)
count++;
cout << "Pairs with sum " << sum << ": " << count;
Problem: Find the Element which Appears Once (XOR Trick)
int arr[] = {2, 3, 5, 4, 5, 3, 4};
int n = sizeof(arr)/sizeof(arr[0]);
int result = 0;
for(int i = 0; i < n; i++)
result ^= arr[i];
cout << "Unique element is: " << result;
Problem: Kadane's Algorithm - Maximum Subarray Sum
int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3};
int n = sizeof(arr)/sizeof(arr[0]);
int maxSum = arr[0], current = arr[0];
for(int i = 1; i < n; i++) {
current = max(arr[i], current + arr[i]);
maxSum = max(maxSum, current);
}
cout << "Maximum subarray sum is: " << maxSum;
Problem: Count Occurrences of a Number
int arr[] = {1, 2, 2, 2, 3, 4, 2};
int n = sizeof(arr)/sizeof(arr[0]);
int x = 2, count = 0;
for(int i = 0; i < n; i++)
if(arr[i] == x)
count++;
cout << "Number " << x << " occurred " << count << " times";
Problem: Find Minimum Difference Between Elements (Sorting)
int arr[] = {1, 5, 3, 19, 18, 25};
int n = sizeof(arr)/sizeof(arr[0]);
sort(arr, arr + n);
int minDiff = INT_MAX;
for(int i = 1; i < n; i++)
minDiff = min(minDiff, arr[i] - arr[i-1]);
cout << "Minimum difference: " << minDiff;
Problem: Count Even and Odd Numbers
int arr[] = {1, 2, 3, 4, 5, 6};
int n = sizeof(arr)/sizeof(arr[0]);
int even = 0, odd = 0;
for(int i = 0; i < n; i++) {
if(arr[i] % 2 == 0)
even++;
else
odd++;
}
cout << "Even: " << even << ", Odd: " << odd;
Problem: Replace Each Element with Greatest on Right
int arr[] = {16, 17, 4, 3, 5, 2};
int n = sizeof(arr)/sizeof(arr[0]);
int maxFromRight = arr[n-1];
arr[n-1] = -1;
for(int i = n-2; i >= 0; i--) {
int temp = arr[i];
arr[i] = maxFromRight;
if(temp > maxFromRight)
maxFromRight = temp;
}
for(int i = 0; i < n; i++)
cout << arr[i] << " ";
Problem: Sort 0s, 1s, and 2s (Dutch National Flag)
int arr[] = {0, 1, 2, 0, 1, 2, 1, 0};
int n = sizeof(arr)/sizeof(arr[0]);
int low = 0, mid = 0, high = n-1;
while(mid <= high) {
if(arr[mid] == 0)
swap(arr[low++], arr[mid++]);
else if(arr[mid] == 1)
mid++;
else
swap(arr[mid], arr[high--]);
}
for(int i = 0; i < n; i++)
cout << arr[i] << " ";
Problem: Rotate Array by K Positions
void reverse(int arr[], int start, int end) {
while(start < end)
swap(arr[start++], arr[end--]);
}
int arr[] = {1, 2, 3, 4, 5, 6, 7};
int n = sizeof(arr)/sizeof(arr[0]);
int k = 3;
k %= n;
reverse(arr, 0, n-1);
reverse(arr, 0, k-1);
reverse(arr, k, n-1);
for(int i = 0; i < n; i++)
cout << arr[i] << " ";
Problem: Count Inversions in Array (Brute Force)
int arr[] = {1, 20, 6, 4, 5};
int n = sizeof(arr)/sizeof(arr[0]);
int count = 0;
for(int i = 0; i < n-1; i++)
for(int j = i+1; j < n; j++)
if(arr[i] > arr[j])
count++;
cout << "Inversion count: " << count;
