Interview-style string 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 1Easy
Reverse a string in place without a second buffer. It must also work for an empty string.
Solution
main.c
#include <stdio.h>
#include <string.h>
void reverse(char *s) {
size_t n = strlen(s);
if (n == 0)
return; /* s + n - 1 would be before the string */
for (char *l = s, *r = s + n - 1; l < r; l++, r--) {
char t = *l;
*l = *r;
*r = t;
}
}
int main(void) {
char a[] = "LearnFrenzy", b[] = "";
reverse(a);
reverse(b);
printf("%s [%s]\n", a, b);
return 0;
}
Output Verified by compiling and running
yznerFnraeL []
Swap the outer pair and move both pointers inwards. The empty-string check matters: with n = 0, s + n - 1 would point before the array, which is undefined behaviour.
Check whether a sentence is a palindrome, ignoring case, spaces and punctuation.
Solution
main.c
#include <stdio.h>
#include <ctype.h>
#include <string.h>
int is_palindrome(const char *s) {
const char *l = s, *r = s + strlen(s); /* r is one past the end */
while (l < r) {
if (!isalnum((unsigned char) *l)) {
l++;
} else if (!isalnum((unsigned char) r[-1])) {
r--;
} else {
if (tolower((unsigned char) *l) != tolower((unsigned char) r[-1]))
return 0;
l++;
r--;
}
}
return 1;
}
int main(void) {
printf("%d %d %d\n",
is_palindrome("A man, a plan, a canal: Panama"),
is_palindrome("race a car"),
is_palindrome(""));
return 0;
}
Output Verified by compiling and running
1 0 1
Two pointers skip anything that is not a letter or digit and compare the rest case-insensitively. Keeping r one past the end and reading r[-1] avoids ever forming an address before the string.
Check whether two strings contain exactly the same characters, in O(n) time.
Solution
main.c
#include <stdio.h>
int is_anagram(const char *a, const char *b) {
int count[256] = {0};
for (; *a; a++)
count[(unsigned char) *a]++;
for (; *b; b++)
count[(unsigned char) *b]--;
for (int i = 0; i < 256; i++)
if (count[i] != 0)
return 0;
return 1;
}
int main(void) {
printf("listen/silent: %s\n", is_anagram("listen", "silent") ? "yes" : "no");
printf("rat/car: %s\n", is_anagram("rat", "car") ? "yes" : "no");
return 0;
}
Output Verified by compiling and running
listen/silent: yes
rat/car: no
Count up for the first string and down for the second; anagrams leave every counter at zero. This is O(n), faster than sorting both strings (O(n log n)).
Count the words in a string where words may be separated by several spaces or tabs, with spaces at both ends.
Solution
main.c
#include <stdio.h>
#include <ctype.h>
int count_words(const char *s) {
int words = 0, in_word = 0;
for (; *s; s++) {
if (isspace((unsigned char) *s)) {
in_word = 0;
} else if (!in_word) {
in_word = 1; /* first letter of a new word */
words++;
}
}
return words;
}
int main(void) {
printf("%d\n", count_words(" Learn C\tthe modern way "));
return 0;
}
Output Verified by compiling and running
5
Count transitions from "outside a word" to "inside a word". Counting spaces instead would give the wrong answer whenever spaces repeat or appear at the ends.
Turn "pointers are fun" into "fun are pointers" in place, without a second buffer.
Solution
main.c
#include <stdio.h>
#include <string.h>
static void rev(char *l, char *r) {
while (l < r) {
char t = *l;
*l++ = *r;
*r-- = t;
}
}
void reverse_words(char *s) {
size_t n = strlen(s);
if (n == 0)
return;
rev(s, s + n - 1); /* 1. reverse the whole sentence */
for (char *w = s; *w; ) { /* 2. reverse each word back */
while (*w == ' ')
w++;
char *e = w;
while (*e && *e != ' ')
e++;
if (e > w)
rev(w, e - 1);
w = e;
}
}
int main(void) {
char s[] = "pointers are fun";
reverse_words(s);
printf("%s\n", s);
return 0;
}
Output Verified by compiling and running
fun are pointers
Reversing the whole string puts the words in the right order but spelled backwards ("nuf era sretniop"); reversing each word fixes the spelling. O(n) time, O(1) extra space.
Find the first character that appears exactly once, or report that there is none.
Solution
main.c
#include <stdio.h>
int first_unique(const char *s) {
int count[256] = {0};
for (const char *p = s; *p; p++)
count[(unsigned char) *p]++;
for (const char *p = s; *p; p++)
if (count[(unsigned char) *p] == 1)
return (int) (p - s);
return -1;
}
int main(void) {
const char *tests[] = {"swiss", "aabb"};
for (int i = 0; i < 2; i++) {
int k = first_unique(tests[i]);
if (k >= 0)
printf("%s: '%c' at %d\n", tests[i], tests[i][k], k);
else
printf("%s: none\n", tests[i]);
}
return 0;
}
Output Verified by compiling and running
swiss: 'w' at 1
aabb: none
Two passes: count every character, then walk the string again and return the first one with a count of 1. Walking the string (not the table) keeps the original order. O(n) time.
Write parse_int() that accepts only a complete, in-range integer and rejects empty text, trailing junk and overflow.
Solution
main.c
#include <errno.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
/* Returns 1 and stores the value if text is a whole int, 0 otherwise */
int parse_int(const char *text, int *out) {
char *end;
errno = 0;
long v = strtol(text, &end, 10);
if (end == text || *end != '\0')
return 0; /* no digits, or junk after them */
if (errno == ERANGE || v < INT_MIN || v > INT_MAX)
return 0; /* does not fit in an int */
*out = (int) v;
return 1;
}
int main(void) {
const char *inputs[] = {"42", "-17", "12abc", "", "99999999999"};
for (int i = 0; i < 5; i++) {
int v;
if (parse_int(inputs[i], &v))
printf("\"%s\" -> %d\n", inputs[i], v);
else
printf("\"%s\" -> invalid\n", inputs[i]);
}
return 0;
}
end shows where parsing stopped: at the start means no digits, anywhere before '\0' means trailing junk. errno catches values too big for long, and the range check catches values that fit long but not int. atoi() can do none of this.
Compress a string by run-length encoding: "aaabbcddddd" becomes "a3b2c1d5". Never overflow the output buffer.
Solution
main.c
#include <stdio.h>
void rle(const char *s, char *out, size_t size) {
size_t used = 0;
out[0] = '\0';
while (*s && used < size) {
char c = *s;
int run = 0;
while (*s == c) {
s++;
run++;
}
int w = snprintf(out + used, size - used, "%c%d", c, run);
if (w < 0)
break;
used += (size_t) w;
}
}
int main(void) {
char out[32];
rle("aaabbcddddd", out, sizeof out);
printf("%s\n", out);
return 0;
}
Output Verified by compiling and running
a3b2c1d5
Count each run of equal characters, then append "character + count" with snprintf(), which is told how much room is left. If the output fills up, used reaches size and the loop stops instead of overflowing.
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
·