These are the notes for C Coding Questions, episode 7, placement practice for people who finished the SyntaxPilot C course. The first array questions: the largest and second largest element (with duplicates and negative numbers), the minimum and maximum in one pass (and with fewer comparisons), and the sum and average (the integer division trap and the overflow trap).
Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the complexity.
Every program was compiled with gcc -Wall -O2 -Wno-unused-result main.c -o main -lm (gcc 13.3, Linux x86-64, 32-bit int), the SyntaxPilot compiler's C command with warnings on, and every output below is real.
Arrays in one picture: a class marks register
| In a marks register | In C |
|---|---|
| one row per student, numbered | an array: int a[100]; is 100 ints stored side by side |
| go straight to row 3 | a[3]: the index is the position, from 0 to n - 1 |
| find the topper by reading every row once | one pass: one for loop over the array, time O(n) |
- An array is a fixed number of values of one type, stored next to each other in memory.
- The index of an element is its position. The first is
a[0], the last ofnelements isa[n - 1]. Readinga[n]ora[-1]is outside the array: undefined behaviour (UB), the C standard promises nothing about what happens. - One pass means looking at every element once. If the array doubles in size, the work doubles: O(n) ("big O of n") time.
- O(1) extra space means the program needs only a few variables, however big the array is.
All three programs read the input in the same format: first n, then n integers.
Q1: Largest and second largest
Problem. Read n, then n integers. Print the largest and the second largest: the biggest value that is strictly smaller than the largest. If there is none, say so.
| Input | Output |
|---|---|
5 / 12 35 1 10 34 |
largest 35, second 34 |
3 / -5 -2 -9 |
largest -2, second -5 |
4 / 10 10 5 3 |
largest 10, second 5 (not 10 again) |
3 / 7 7 7 |
largest 7, no second largest |
1 / 42 |
largest 42, no second largest |
Edge cases: all negative numbers, duplicates of the largest, all equal, a single element.
Think out loud
No sorting needed. Keep two boxes, first and second, like a race with two medals:
- a number bigger than
first: the oldfirstmoves down tosecond, the number becomesfirst; - otherwise, a number bigger than
secondbecomessecond.
For 12 35 1 10 34: first 12 → first 35, second 12 → no change → no change → second 34.
The obvious attempt: start both at 0
#include <stdio.h>
int main() {
int n, a[100];
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
int first = 0, second = 0;
for (int i = 0; i < n; i++) {
if (a[i] > first) {
second = first;
first = a[i];
} else if (a[i] > second) {
second = a[i];
}
}
printf("largest %d, second %d\n", first, second);
return 0;
}
Input 5 12 35 1 10 34:
largest 35, second 34
Input 3 -5 -2 -9:
largest 0, second 0
Input 4 10 10 5 3:
largest 10, second 10
Two wrong answers, and no warning from the compiler.
Why it failed
- Starting at 0. No negative number is ever bigger than 0, so 0 "wins", a value that isn't even in the list. Never start a maximum at a made-up value: start at
a[0], an element that really exists. - Duplicates. The second
10is not bigger thanfirst(10), but it is bigger thansecond, so it slips in. A copy of the largest is not the second largest:secondmay only take values strictly smaller thanfirst. - No second at all. For
7 7 7there is no second largest. A flagfoundremembers whether we have seen any second value.
The fix
#include <stdio.h>
int main() {
int n, a[100];
scanf("%d", &n);
if (n < 1 || n > 100) {
printf("n must be 1 to 100\n");
return 0;
}
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
int first = a[0], second = 0, found = 0;
for (int i = 1; i < n; i++) {
if (a[i] > first) {
second = first;
first = a[i];
found = 1;
} else if (a[i] < first && (!found || a[i] > second)) {
second = a[i];
found = 1;
}
}
if (found) printf("largest %d, second %d\n", first, second);
else printf("largest %d, no second largest\n", first);
return 0;
}
Input 3 -5 -2 -9:
largest -2, second -5
Input 4 10 10 5 3:
largest 10, second 5
Input 3 7 7 7:
largest 7, no second largest
Input 1 42:
largest 42, no second largest
Input 5 12 35 1 10 34:
largest 35, second 34
Input 4 3 10 10 8:
largest 10, second 8
Input 0:
n must be 1 to 100
Complexity: one pass, O(n) time; O(1) extra space (besides the input array).
Why not sort?
Sorting first and reading from the end works, but sorting costs O(n log n) (faster than O(n²) but slower than one pass), and you still have to skip the copies of the largest. One pass with two boxes is O(n) and handles duplicates in the same loop. That is the answer interviewers want.
Q2: Min and max in one pass
Problem. Read n ≥ 1, then n integers (a week of temperatures). Print the smallest and the largest, in one pass. Interview follow-up: how many comparisons does your code make? A comparison is one check like a < b.
| Input | Output |
|---|---|
6 / 4 9 -3 7 0 5 |
min -3, max 9 |
1 / -8 |
min -8, max -8 |
The obvious attempt: INT_MAX without <limits.h>
Starting min at the biggest possible int makes any number smaller, and max at the smallest. Both programs below count comparisons in cmp.
#include <stdio.h>
int main() {
int n, a[100];
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
int min = INT_MAX, max = INT_MIN, cmp = 0;
for (int i = 0; i < n; i++) {
cmp++;
if (a[i] < min) min = a[i];
cmp++;
if (a[i] > max) max = a[i];
}
printf("min %d, max %d, comparisons %d\n", min, max, cmp);
return 0;
}
Compiler output (it does not compile):
main.c: In function 'main':
main.c:7:15: error: 'INT_MAX' undeclared (first use in this function)
7 | int min = INT_MAX, max = INT_MIN, cmp = 0;
| ^~~~~~~
main.c:2:1: note: 'INT_MAX' is defined in header '<limits.h>'; did you forget to '#include <limits.h>'?
1 | #include <stdio.h>
+++ |+#include <limits.h>
2 |
main.c:7:15: note: each undeclared identifier is reported only once for each function it appears in
7 | int min = INT_MAX, max = INT_MIN, cmp = 0;
| ^~~~~~~
main.c:7:30: error: 'INT_MIN' undeclared (first use in this function)
7 | int min = INT_MAX, max = INT_MIN, cmp = 0;
| ^~~~~~~
main.c:7:30: note: 'INT_MIN' is defined in header '<limits.h>'; did you forget to '#include <limits.h>'?
Why: INT_MAX lives in <limits.h>
INT_MAX (2,147,483,647) and INT_MIN (-2,147,483,648) are macros: names that the preprocessor replaces with numbers before the program is compiled. They are defined in the header <limits.h>, and <stdio.h> doesn't bring them in. gcc even prints the fix in its note. (Starting min = max = a[0] also works and needs no header.)
#include <stdio.h>
#include <limits.h>
int main() {
int n, a[100];
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
int min = INT_MAX, max = INT_MIN, cmp = 0;
for (int i = 0; i < n; i++) {
cmp++;
if (a[i] < min) min = a[i];
cmp++;
if (a[i] > max) max = a[i];
}
printf("min %d, max %d, comparisons %d\n", min, max, cmp);
return 0;
}
Input 6 4 9 -3 7 0 5:
min -3, max 9, comparisons 12
Input 1 -8:
min -8, max -8, comparisons 2
Input 3 -5 -2 -9:
min -9, max -2, comparisons 6
Correct, but 2 comparisons per element: 12 for 6 numbers.
The pair trick: about 3n/2 comparisons
Take the numbers two at a time:
- Compare the two numbers of the pair with each other (1 comparison): now you know the smaller and the bigger.
- The smaller can never be a new maximum, and the bigger can never be a new minimum. So compare the smaller only with
minand the bigger only withmax(2 comparisons).
That is 3 comparisons per 2 numbers instead of 4. If n is odd, the first element starts as both min and max; if n is even, one comparison sets them from the first pair. In total about 3n/2 − 2 comparisons (7 for n = 6) instead of 2n.
#include <stdio.h>
int main() {
int n, a[100];
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
int min, max, i, cmp = 0;
if (n % 2 == 1) {
min = max = a[0];
i = 1;
} else {
cmp++;
if (a[0] < a[1]) { min = a[0]; max = a[1]; }
else { min = a[1]; max = a[0]; }
i = 2;
}
for (; i + 1 < n; i += 2) {
int small = a[i], big = a[i + 1];
cmp++;
if (small > big) { small = a[i + 1]; big = a[i]; }
cmp++;
if (small < min) min = small;
cmp++;
if (big > max) max = big;
}
printf("min %d, max %d, comparisons %d\n", min, max, cmp);
return 0;
}
Input 6 4 9 -3 7 0 5:
min -3, max 9, comparisons 7
Input 1 -8:
min -8, max -8, comparisons 0
Input 7 4 9 -3 7 0 5 11:
min -3, max 11, comparisons 9
Input 3 -5 -2 -9:
min -9, max -2, comparisons 3
Complexity: both versions are O(n) time and O(1) extra space. The pair trick saves about a quarter of the comparisons, not a whole loop; it matters when comparing is expensive (for example comparing long strings).
Q3: Sum and average
Problem. Read n, then n integers. Print the sum and the average with two decimal places.
| Input | Output |
|---|---|
3 / 10 20 30 |
sum 60, average 20.00 |
2 / 1 2 |
sum 3, average 1.50 |
3 / three times 2000000000 |
sum 6000000000, average 2000000000.00 |
0 |
rejected (an average of nothing is a division by zero) |
The obvious attempt
#include <stdio.h>
int main() {
int n, a[100], sum = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
for (int i = 0; i < n; i++) sum = sum + a[i];
float avg = sum / n;
printf("sum %d, average %.2f\n", sum, avg);
return 0;
}
Input 3 10 20 30:
sum 60, average 20.00
Input 2 1 2:
sum 3, average 1.00
Why: integer division
sum and n are both int, so sum / n is integer division: 3 / 2 is 1, and the .5 is thrown away (C rounds towards zero). Only then is 1 stored in the float. The type on the left doesn't change how the right side is computed.
The fix is a cast: (double)sum converts sum to a double before the division, so the division is done in doubles. (double)(sum / n) would be too late: it casts the already-truncated result.
#include <stdio.h>
int main() {
int n, a[100], sum = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
for (int i = 0; i < n; i++) sum = sum + a[i];
double avg = (double)sum / n;
printf("sum %d, average %.2f\n", sum, avg);
return 0;
}
Input 2 1 2:
sum 3, average 1.50
Input 3 2000000000 2000000000 2000000000:
sum 1705032704, average 568344234.67
Why: the sum overflowed
Each number fits in an int (up to 2,147,483,647), but their sum, 6,000,000,000, doesn't. Going past the limit of a signed integer is signed overflow, and in C that is undefined behaviour: the language promises nothing. This build happened to wrap around and print 1705032704 (6,000,000,000 − 4,294,967,296). The fix: keep the sum in a long long (at least 64 bits, up to about 9.2 × 10¹⁸) and print it with %lld. Also check n ≥ 1.
#include <stdio.h>
int main() {
int n, a[100];
scanf("%d", &n);
if (n < 1 || n > 100) {
printf("n must be 1 to 100\n");
return 0;
}
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
long long sum = 0;
for (int i = 0; i < n; i++) sum = sum + a[i];
double avg = (double)sum / n;
printf("sum %lld, average %.2f\n", sum, avg);
return 0;
}
Input 3 2000000000 2000000000 2000000000:
sum 6000000000, average 2000000000.00
Input 2 1 2:
sum 3, average 1.50
Input 3 -1 -2 2:
sum -1, average -0.33
Input 3 10 20 30:
sum 60, average 20.00
Input 0:
n must be 1 to 100
Complexity: one pass, O(n) time, O(1) extra space.
Complexity summary
| Question | Obvious attempt | Fixed | Time | Extra space |
|---|---|---|---|---|
| Largest and second | wrong for negatives and duplicates | start at a[0], second < first, a found flag |
O(n) | O(1) |
| (by sorting) | O(n log n) | |||
| Min and max | compile error without <limits.h> |
2 comparisons per element | O(n) | O(1) |
| (pair trick) | about 3n/2 comparisons | O(n) | O(1) | |
| Sum and average | 1.00 for 1 2; overflow for big numbers |
long long sum, (double)sum / n |
O(n) | O(1) |
Common mistakes (and the real messages)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
int first = 0, second = 0; |
no error: largest 0, second 0 for -5 -2 -9 |
no negative number beats 0 | first = a[0] |
else if (a[i] > second) |
no error: second 10 for 10 10 5 3 |
a copy of the largest slips in | a[i] < first && ... |
| no "none" case | 7 7 7 prints a made-up second |
there is no second largest | a found flag |
int min = INT_MAX; without the header |
error: 'INT_MAX' undeclared (first use in this function) and note: 'INT_MAX' is defined in header '<limits.h>'; did you forget to '#include <limits.h>'? |
it is a macro from <limits.h> |
#include <limits.h> |
float avg = sum / n; |
no error: 1.00 for 1 2 |
int / int drops the fraction |
(double)sum / n |
(double)(sum / n) |
1.00 |
the cast comes after the division | cast sum, not the result |
int sum of big numbers |
no error: 1705032704 |
signed overflow (UB) | long long sum, %lld |
no check of n |
division by zero for n = 0 |
an average of nothing | reject n < 1 |
Your turn: third largest distinct (solution)
Problem. Read n, then n integers. Print the third largest distinct value (copies count once), or "no third largest". 5 1 9 9 7 3 → 5 (the distinct values from the top are 9, 7, 5). 4 4 2 → no third largest.
Idea. Three boxes first, second, third with flags have2 and have3. Skip a value equal to one you already hold. A bigger value pushes the others down one place.
Show the solution
#include <stdio.h>
int main() {
int n, a[100];
scanf("%d", &n);
if (n < 1 || n > 100) {
printf("n must be 1 to 100\n");
return 0;
}
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
int first = a[0], second = 0, third = 0, have2 = 0, have3 = 0;
for (int i = 1; i < n; i++) {
int x = a[i];
if (x == first || (have2 && x == second) || (have3 && x == third)) continue;
if (x > first) {
third = second; have3 = have2;
second = first; have2 = 1;
first = x;
} else if (!have2 || x > second) {
third = second; have3 = have2;
second = x; have2 = 1;
} else if (!have3 || x > third) {
third = x; have3 = 1;
}
}
if (have3) printf("third largest %d\n", third);
else printf("no third largest\n");
return 0;
}
Input 6 5 1 9 9 7 3:
third largest 5
Input 3 4 4 2:
no third largest
Input 5 -1 -2 -3 -4 -5:
third largest -3
Input 4 10 9 9 8:
third largest 8
Input 6 3 3 2 2 1 1:
third largest 1
Input 1 5:
no third largest
Time O(n), extra space O(1).
Practice questions (with solutions)
1. Second smallest element. The mirror image of Q1.
Solution
#include <stdio.h>
int main() {
int n, a[100];
scanf("%d", &n);
if (n < 1 || n > 100) {
printf("n must be 1 to 100\n");
return 0;
}
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
int first = a[0], second = 0, found = 0;
for (int i = 1; i < n; i++) {
if (a[i] < first) {
second = first;
first = a[i];
found = 1;
} else if (a[i] > first && (!found || a[i] < second)) {
second = a[i];
found = 1;
}
}
if (found) printf("smallest %d, second smallest %d\n", first, second);
else printf("smallest %d, no second smallest\n", first);
return 0;
}
Input 5 12 35 1 10 34:
smallest 1, second smallest 10
Input 4 1 1 2 3:
smallest 1, second smallest 2
Input 3 7 7 7:
smallest 7, no second smallest
2. Count the elements greater than the average. Compare a[i] * n > sum in long long, so no division (and no rounding) is needed.
Solution
#include <stdio.h>
int main() {
int n, a[100];
scanf("%d", &n);
if (n < 1 || n > 100) {
printf("n must be 1 to 100\n");
return 0;
}
long long sum = 0;
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
sum = sum + a[i];
}
int count = 0;
for (int i = 0; i < n; i++)
if ((long long)a[i] * n > sum) count++;
printf("average %.2f, %d above it\n", (double)sum / n, count);
return 0;
}
Input 5 10 20 30 40 50:
average 30.00, 2 above it
Input 3 5 5 5:
average 5.00, 0 above it
Input 4 1 2 2 2:
average 1.75, 3 above it
3. Index of the largest element (the first one if there is a tie). Keep the index, not the value; > (not >=) keeps the first of equal values.
Solution
#include <stdio.h>
int main() {
int n, a[100];
scanf("%d", &n);
if (n < 1 || n > 100) {
printf("n must be 1 to 100\n");
return 0;
}
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
int best = 0;
for (int i = 1; i < n; i++)
if (a[i] > a[best]) best = i;
printf("largest %d at index %d\n", a[best], best);
return 0;
}
Input 5 3 9 2 9 1:
largest 9 at index 1
Input 3 -5 -2 -9:
largest -2 at index 1
Quick quiz
int a = 7, b = 2;
printf("%d %.1f %.1f\n",
a / b, a / 2.0, (double)(a / b));
(A) 3 3.5 3.0 (B) 3 3.5 3.5 (C) 3.5 3.5 3.5 (D) 3 3.0 3.0
Answer
(A). 7 / 2 is integer division: 3. 7 / 2.0 has a double operand, so the division is done in doubles: 3.5. (double)(a / b) divides first (3) and casts too late: 3.0.
Output:
3 3.5 3.0
Interview questions
- Find the second largest element in one pass. Two variables, start from
a[0]; a bigger value pushesfirstdown tosecond; a value smaller thanfirstbut bigger thansecondreplacessecond. O(n), O(1). - Why not sort to find the second largest? Sorting is O(n log n) and still needs to skip duplicates; one pass is O(n).
- What should the second largest of
10 10 5be? 5: the second largest distinct value. Ask the interviewer if unsure, and handle "no second largest". - How many comparisons do you need for min and max? About 3n/2 − 2 with the pair method, instead of 2n − 2.
- Why does
float avg = sum / n;give the wrong answer? Both operands areint, so the division is integer division before the value is stored. - Where are
INT_MAXandINT_MINdefined? In<limits.h>. - How do you avoid overflow when summing many
ints? Accumulate in along long(or check before adding). - What is undefined behaviour? Code whose result the C standard doesn't define, such as signed overflow or reading outside an array. The program may print anything, crash, or seem to work.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Array | A fixed number of values of one type, stored side by side | int a[100]; |
| Element | One value in an array | a[3] |
| Index | The position of an element, from 0 to n − 1 | a[0] is the first |
| One pass | Looking at every element exactly once | one for loop |
| Big O notation | How the work grows with the input size | O(n), O(n log n) |
| O(n) time | Double the input, double the work | one pass |
| O(1) extra space | A fixed number of extra variables | first, second |
| Second largest | The biggest value strictly smaller than the largest | 10 10 5 → 5 |
| Distinct | Counting copies once | 9 9 7 has 2 distinct values |
| Flag | A variable that remembers whether something happened | found = 1 |
| Comparison | One check like a < b |
cmp++ counts them |
| Pair trick | Compare two elements first, then the smaller with min and the bigger with max | 3 comparisons per 2 numbers |
| Macro | A name the preprocessor replaces before compiling | INT_MAX |
| Header | A file of declarations and macros you #include |
<limits.h>, <stdio.h> |
INT_MAX / INT_MIN |
The largest and smallest int |
2147483647 / -2147483648 |
| Integer division | int / int: the fraction is dropped |
7 / 2 = 3 |
| Cast | Converting a value to another type | (double)sum |
double |
A floating-point number with about 15-16 significant digits | 1.5 |
long long |
An integer of at least 64 bits | up to about 9.2 × 10¹⁸ |
| Signed overflow | A signed result too big for its type: undefined behaviour | int sum of 3 × 2,000,000,000 |
| Undefined behaviour (UB) | The C standard doesn't define what happens | overflow, a[n] |
| Edge case | An input at the boundary | n = 1, all equal, all negative |
| Sorting | Putting elements in order | O(n log n) with a good algorithm |
Summary
- Start a maximum or minimum at a real element,
a[0], never at 0. - Second largest: one pass with two boxes;
secondonly takes values smaller thanfirst; a flag for "no second largest". INT_MAXandINT_MINneed#include <limits.h>.- Min and max: O(n) either way; the pair trick needs about 3n/2 comparisons instead of 2n.
- Average: cast before dividing,
(double)sum / n; keep big sums in along longand print with%lld; rejectn < 1.
Next episode: Array questions II: reverse an array in place, left rotate by one, and rotate by k with the reversal trick (k larger than n).