Interview-style array problems. Write each one yourself first, then open the solution – every solution was compiled and run, and the output shown is the real output. Tick "Mark as solved" to track your progress.
Question 1Medium
Find the second largest distinct value in one pass. Report when there is none (all values equal).
Solution
main.c
#include <stdio.h>
#include <limits.h>
int second_largest(const int *a, int n, int *out) {
int first = INT_MIN, second = INT_MIN;
for (int i = 0; i < n; i++) {
if (a[i] > first) {
second = first;
first = a[i];
} else if (a[i] < first && a[i] > second) {
second = a[i];
}
}
if (second == INT_MIN)
return 0; /* fewer than two distinct values */
*out = second;
return 1;
}
int main(void) {
int a[] = {12, 35, 1, 10, 35, 34};
int b[] = {7, 7, 7};
int s;
if (second_largest(a, 6, &s))
printf("second largest = %d\n", s);
if (!second_largest(b, 3, &s))
printf("no second largest in b\n");
return 0;
}
Output Verified by compiling and running
second largest = 34
no second largest in b
Keep the two best values seen so far. The duplicate 35 is skipped by a[i] < first, so the answer is 34, not 35. One pass, O(n) time, O(1) memory – better than sorting.
Rotate an array left by k positions in place, using O(1) extra memory.
Solution
main.c
#include <stdio.h>
static void reverse(int *a, int i, int j) {
while (i < j) {
int t = a[i];
a[i++] = a[j];
a[j--] = t;
}
}
void rotate_left(int *a, int n, int k) {
k %= n;
reverse(a, 0, k - 1); /* reverse the first k */
reverse(a, k, n - 1); /* reverse the rest */
reverse(a, 0, n - 1); /* reverse everything */
}
int main(void) {
int a[] = {1, 2, 3, 4, 5, 6, 7};
rotate_left(a, 7, 3);
for (int i = 0; i < 7; i++)
printf("%d ", a[i]);
printf("\n");
return 0;
}
Output Verified by compiling and running
4 5 6 7 1 2 3
Three reversals do the rotation: [3 2 1 | 7 6 5 4] → reverse all → 4 5 6 7 1 2 3. Each element moves a constant number of times: O(n) time, no second array. k %= n handles k larger than n.
Given a sorted array, remove the duplicates in place and return the new length.
Solution
main.c
#include <stdio.h>
int unique(int *a, int n) {
if (n == 0)
return 0;
int w = 1; /* next write position */
for (int r = 1; r < n; r++)
if (a[r] != a[w - 1])
a[w++] = a[r];
return w;
}
int main(void) {
int a[] = {1, 1, 2, 3, 3, 3, 4, 5, 5};
int n = unique(a, 9);
printf("%d unique:", n);
for (int i = 0; i < n; i++)
printf(" %d", a[i]);
printf("\n");
return 0;
}
Output Verified by compiling and running
5 unique: 1 2 3 4 5
Two indexes: r reads every element, w marks where the next new value goes. Because the array is sorted, a value is new exactly when it differs from the last one written.
Find the largest sum of a contiguous subarray, and print where it starts and ends.
Solution
main.c
#include <stdio.h>
int max_subarray(const int *a, int n, int *from, int *to) {
int best = a[0], cur = a[0], start = 0;
*from = *to = 0;
for (int i = 1; i < n; i++) {
if (cur < 0) { /* a negative prefix only hurts: start again */
cur = a[i];
start = i;
} else {
cur += a[i];
}
if (cur > best) {
best = cur;
*from = start;
*to = i;
}
}
return best;
}
int main(void) {
int a[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int from, to;
int best = max_subarray(a, 9, &from, &to);
printf("max sum = %d (a[%d]..a[%d])\n", best, from, to);
return 0;
}
Output Verified by compiling and running
max sum = 6 (a[3]..a[6])
Kadane keeps the best sum ending at the current element. If that running sum drops below zero, a new subarray starts. The best is 4 − 1 + 2 + 1 = 6. Starting from a[0] (not 0) makes it correct even when every element is negative.
Search a sorted array. If the key is missing, report where it would be inserted.
Solution
main.c
#include <stdio.h>
/* Index of the first element >= key, or n if there is none */
int lower_bound(const int *a, int n, int key) {
int lo = 0, hi = n;
while (lo < hi) {
int mid = lo + (hi - lo) / 2; /* cannot overflow, unlike (lo + hi) / 2 */
if (a[mid] < key)
lo = mid + 1;
else
hi = mid;
}
return lo;
}
int main(void) {
int a[] = {3, 8, 8, 15, 21, 42};
int keys[] = {8, 16, 50, 1};
for (int k = 0; k < 4; k++) {
int i = lower_bound(a, 6, keys[k]);
if (i < 6 && a[i] == keys[k])
printf("%d found at %d\n", keys[k], i);
else
printf("%d not found (insert at %d)\n", keys[k], i);
}
return 0;
}
Output Verified by compiling and running
8 found at 1
16 not found (insert at 4)
50 not found (insert at 6)
1 not found (insert at 0)
The half-open range [lo, hi) shrinks until one position is left: the first element that is not smaller than the key. With duplicates it finds the first 8 (index 1). lo + (hi - lo) / 2 is the overflow-safe midpoint.
Merge two sorted arrays into a third sorted array.
Solution
main.c
#include <stdio.h>
void merge(const int *a, int n, const int *b, int m, int *out) {
int i = 0, j = 0, k = 0;
while (i < n && j < m)
out[k++] = (a[i] <= b[j]) ? a[i++] : b[j++];
while (i < n)
out[k++] = a[i++];
while (j < m)
out[k++] = b[j++];
}
int main(void) {
int a[] = {1, 4, 7, 10}, b[] = {2, 3, 8};
int out[7];
merge(a, 4, b, 3, out);
for (int i = 0; i < 7; i++)
printf("%d ", out[i]);
printf("\n");
return 0;
}
Output Verified by compiling and running
1 2 3 4 7 8 10
Compare the fronts of both arrays and take the smaller; when one runs out, copy the rest of the other. O(n + m) – the merge step of merge sort. Using <= keeps equal values in their original order (stable).
#include <stdio.h>
int main(void) {
int a[2][3] = {{1, 2, 3}, {4, 5, 6}};
int b[3][2] = {{7, 8}, {9, 10}, {11, 12}};
int r[2][2] = {0};
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
for (int k = 0; k < 3; k++)
r[i][j] += a[i][k] * b[k][j];
for (int i = 0; i < 2; i++)
printf("%5d%5d\n", r[i][0], r[i][1]);
return 0;
}
Output Verified by compiling and running
58 64
139 154
r[i][j] is row i of a times column j of b: for example 1×7 + 2×9 + 3×11 = 58. The inner sizes must match (3 and 3), and the result is 2 × 2. r must start at zero because the loop adds into it.
An array holds the numbers 1 to n with exactly one missing, in any order. Find the missing number without sorting and without risking overflow.
Solution
main.c
#include <stdio.h>
int missing(const int *a, int len) {
int n = len + 1, x = 0;
for (int i = 1; i <= n; i++)
x ^= i; /* XOR of 1..n */
for (int i = 0; i < len; i++)
x ^= a[i]; /* cancels every number that is present */
return x;
}
int main(void) {
int a[] = {1, 2, 4, 6, 3, 7, 8};
printf("missing number = %d\n", missing(a, 7));
return 0;
}
Output Verified by compiling and running
missing number = 5
x ^ x = 0 and x ^ 0 = x, so XOR-ing 1..n with every element cancels all the numbers that appear twice and leaves the missing one. Unlike the sum formula n(n+1)/2, XOR can never overflow.
We use Google Analytics cookies to see how LearnFrenzy is used and make it better, and Google AdSense to keep it free.
No analytics or ad cookies are set until you accept. Privacy Policy
·