The Dreaded C Test

The C Test is a mechanism to test whether a candidate for a C-Based job opening can handle the technical complexity of the language. C can be a very tricky language to master, not even counting the skill set needed for embedded coding, and it is entirely possible to design a C test that the vast majority of engineers would fail. Hence many consider the C test to be an obstacle to passing the interview. Below is a very basic alternative format of a C test which can get the average applicant started as to what to expect from a simple interview type question.

---

Problem: Implement a Basic In-Memory String Manipulation Library

Description: You’re tasked with implementing a simplified in-memory library to handle string manipulation functions in C. This test will assess your ability to work with pointers and manage memory effectively.

You need to implement the following three functions:

1. reverse_words: Reverse the order of words in a given string in place. Words are defined as sequences of non-space characters, and words are separated by spaces. The function should not allocate any additional memory.
2. remove_duplicates: Remove duplicate characters in a string in place. Keep only the first occurrence of each character, and shift all unique characters to the left, filling the rest with null characters (\0).
3. substring: Check if one string is a substring of another. Return a pointer to the first occurrence of the substring, or NULL if the substring is not found.

Function Signatures

void reverse_words(char *str);
void remove_duplicates(char *str);
char *substring(const char *str, const char *sub);

Constraints

• You cannot use any standard C library functions like strlen, strcpy, or strstr.
• The string is guaranteed to fit within the available memory.
• Assume strings are null-terminated.

---

Example Inputs and Outputs

1. reverse_words
   • Input: "hello world from C"
   • Output: "C from world hello"
2. remove_duplicates
   • Input: "programming"
   • Output: "progamin"
3. substring
   • Input:
     • str = "hello world"
     • sub = "world"
   • Output: Pointer to "world" within str

---

Implementation Hints

1. For reverse_words, reverse the entire string first, and then reverse each word individually to achieve the word order reversal.
2. For remove_duplicates, use a boolean array to track characters that have already been added to the result. Shift unique characters to the beginning, replacing duplicates with null characters.
3. For substring, iterate through each position in str and check if sub matches, character by character, from that position. Return the pointer when you find a match.

---

Sample Solution Outline

Here’s a high-level outline of how each function might look:

#include <stdio.h>
#include <stdbool.h>

// Function to reverse a portion of a string between two pointers
void reverse(char *start, char *end) {
    while (start < end) {
        char temp = *start;
        *start++ = *end;
        *end-- = temp;
    }
}

// Function to reverse the order of words in a string
void reverse_words(char *str) {
    if (!str) return;

    // Reverse the entire string
    char *start = str, *end = str;
    while (*end) end++;
    reverse(start, end - 1);

    // Reverse each word in the reversed string
    char *word_start = str;
    while (*str) {
        if (*str == ' ' || *(str + 1) == '\0') {
            reverse(word_start, *str == ' ' ? str - 1 : str);
            word_start = str + 1;
        }
        str++;
    }
}

// Function to remove duplicate characters from a string
void remove_duplicates(char *str) {
    if (!str) return;

    bool seen[256] = {0};  // Array to track seen characters
    char *write_ptr = str;

    while (*str) {
        if (!seen[(unsigned char)*str]) {
            seen[(unsigned char)*str] = true;
            *write_ptr++ = *str;
        }
        str++;
    }
    *write_ptr = '\0';
}

// Function to check if sub is a substring of str
char *substring(const char *str, const char *sub) {
    if (!str || !sub) return NULL;

    const char *p1 = str;
    const char *p2 = sub;

    while (*str) {
        p1 = str;
        p2 = sub;

        // Compare str with sub character by character
        while (*p1 && *p2 && *p1 == *p2) {
            p1++;
            p2++;
        }

        // If we reached the end of sub, we found a match
        if (!*p2) return (char *)str;

        str++;
    }
    return NULL;
}

int main() {
    char str1[] = "hello world from C";
    reverse_words(str1);
    printf("Reversed words: %s\n", str1);

    char str2[] = "programming";
    remove_duplicates(str2);
    printf("Without duplicates: %s\n", str2);

    char *result = substring("hello world", "world");
    if (result) printf("Substring found: %s\n", result);
    else printf("Substring not found\n");

    return 0;
}

---

Explanation

• reverse_words: This function reverses the entire string first, then each word to achieve the final reversed order.
• remove_duplicates: A boolean array is used to track which characters have been seen, ensuring each character is written only once.
• substring: The function performs a character-by-character comparison from each position in str, returning a pointer when a match is found.

---

Testing Notes

Make sure to test edge cases:

• Empty strings.
• Strings with only spaces or no spaces.
• Cases where str does not contain sub.
• Strings with all unique characters or all identical characters.

This test will reveal a candidate’s ability to write efficient, memory-safe C code, especially in pointer handling and algorithmic logic.