Strings in C

Intel's C round often takes away and asks you to write the short library functions yourself. Writing strlen means walking a pointer to the NUL byte, and the bugs show up around that walk. A scan reads one byte past its buffer, or an int wraps while digits are still arriving. Both mistakes compile cleanly and pass the happy-path test. The interviewer will look for them.

Why ask this? Below the operating system, the library often isn't there. Boot firmware runs before any C runtime exists, and a driver is often built freestanding with only the headers it brings along. So the same few hand-written routines come up again and again in the C round and on the firmware track. Each one takes about fifteen minutes, and most of that time goes to the edge cases.

The Intel angle

Before you write a line, say which library function you're replacing. strstr and strtol each have a documented contract, and Intel's follow-ups tend to check your version against it. An empty needle matches at index 0, because that's what strstr returns. An out-of-range number in strtol clamps and sets errno instead of wrapping. Firmware and driver engineers at Intel write these routines for real when no runtime is linked, so they notice quickly when yours disagrees with the contract.

The NUL byte and the length you do not have

A C string carries no length. It is a run of char that ends at the first zero byte, and every routine in finds that byte by walking to it. When you write the walk yourself, two things follow. Measuring costs a full pass every time, so a loop that calls strlen in its condition turns a linear scan quadratic. The terminator also belongs to the buffer without belonging to the string, so anything that rearranges characters has to stop one short of it.

// strlen by hand: walk to the terminator, return the distance walked
size_t my_strlen(const char *s) {
    const char *p = s;
    while (*p != '\0') p++;   // stop ON the NUL, never past it
    return (size_t)(p - s);   // pointer difference is the length
}

Asked at Intel

Three problems, each a library routine written without the library: reversal as a warm-up, then substring search, then the integer parse that firmware interviews pair with malloc and byte swapping. Read each answer in C or C++, the language you'll write in the round, then run the Python model on the empty and overflowing inputs before you explain it out loud.

1

Reverse a String In Place: Two Pointers, No Library

EasyCommonly asked

Problem

Given a string s of ASCII characters, reverse it in place and return the result. Swap characters from the two ends inward with a pair of indexes. Do not call a library reverse, do not slice backward, and do not copy into a second buffer.

For this exercise the string arrives as a string and you return the reversed string, but the work that matters is the swap on a char buffer underneath. In C that buffer ends in a NUL byte, you find its length by walking to that byte, and the NUL never moves. Aim for O(n) time and O(1) extra space.

Inputs = "hello"Output"olleh"

h swaps with o, e swaps with the second l, and the middle l stays where it is.

Inputs = "ab"Output"ba"

Two characters trade places in a single swap, then the indexes cross and the loop stops.

Inputs = ""Output""

An empty string has nothing to swap, so it comes back unchanged.

How this uses the pattern

Put one index on the first character and one on the last. Swap the two characters, step both indexes toward the middle, and stop as soon as they meet or cross.

Reverse a String In Place: Two Pointers, No Library

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Show test cases (7)

Need a hint? (3 available)

The Intel angle

Reversing a string without built-ins keeps turning up as a warm-up in Intel's C and pointers round, and the algorithm is the easy part. In C the string is a char buffer with a NUL byte at the end. You find the length by walking a pointer to that byte, because a no-library round takes strlen away, and the terminator itself must never be swapped. Reverse it into slot zero and you hand back an empty string. The swap stays in place because boot code and drivers often run with no heap to copy into. Get the pointers right and the interviewer often moves straight on to reversing the words of a sentence.

Take it further

Reverse the order of the words in a sentence, still in place and still without a second buffer. Reverse the whole string first, then walk it and reverse each word back between its spaces. Both passes reuse the same two-pointer helper, so the cost stays O(n) time and O(1) extra space.

Show solution & walkthrough

2

Substring Search: Find the Needle by Walking Pointers

EasyCommonly asked

Problem

Given two strings haystack and needle, return the index where needle first occurs inside haystack, or -1 if it never does. Write the comparison yourself, one character at a time. Library calls such as strstr, find, indexOf or Python's in are off the table, because the exercise is the scan they hide.

An empty needle matches at index 0, the same answer C's strstr gives when it hands back the haystack itself. Some versions of the question ask only whether needle is present, and returning the index answers that too. Aim for O((n - m + 1) * m) time with O(1) extra space, and be ready to explain why the outer loop stops where it does.

Inputhaystack = "hello"needle = "ll"Output2

The window that starts at index 2 reads "ll".

Inputhaystack = "aaa"needle = "aaaa"Output-1

The needle is longer than the haystack, so there is no legal start at all.

Inputhaystack = "abc"needle = ""Output0

An empty needle matches before the first character, as strstr does.

How this uses the pattern

Slide a start index i from 0 up to n - m inclusive. At each start, walk a second index j across the needle while the characters agree. If j reaches m, every character matched and i is the answer.

Substring Search: Find the Needle by Walking Pointers

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Show test cases (8)

Need a hint? (3 available)

The Intel angle

Writing strStr by hand is part of the manual string work Intel's technical rounds keep asking for, next to reversing a string without built-ins. Say up front that you're writing the library function, since below the OS there may be no std::string, only a char pointer and a length. Two bounds decide the result: the outer loop stops at n minus m, the last start where the needle fits, and an empty needle matches at index 0, as C's strstr returns the haystack. Compute n minus m on size_t with a long needle and it wraps, the scan reads past the buffer, and that bug ships to a board. Describe KMP, and write it only if asked.

Take it further

Make the worst case linear with Knuth-Morris-Pratt. Precompute, for each prefix of the needle, the length of its longest proper prefix that is also a suffix, then scan the haystack once without ever stepping backward in it. You spend O(m) extra memory on the table and get O(n + m) time.

Show solution & walkthrough

3

String to Integer (atoi): Clamp Before the Multiply

MediumCommonly asked

Problem

Write my_atoi(s), which turns a string into a 32-bit signed integer the way C's atoi family does, with no library parsing call. Skip leading space characters. A tab or newline counts as an ordinary character and ends the parse. Read at most one + or -. Then read digits until the first non-digit or the end of the string, and ignore whatever follows. If no digit was read, return 0.

If the value falls outside the range -2147483648 to 2147483647, clamp it to the nearer end, which is how strtol saturates. Your accumulator may never pass through an overflowed value on the way there, so the range test has to happen before the multiply. Aim for one left-to-right pass, O(n) time and O(1) extra space.

Inputs = " -042"Output-42

Three spaces are skipped, the minus sets the sign, and the leading zero adds nothing.

Inputs = "1337c0d3"Output1337

Parsing stops at the first non-digit, the c, and the rest of the string is ignored.

Inputs = "-91283472332"Output-2147483648

The magnitude passes 2147483648 at the tenth digit, so the result clamps to INT_MIN.

How this uses the pattern

Move one index through four phases in order: spaces, an optional sign, digits, stop. Before each result * 10 + d, compare result against INT_MAX / 10 and clamp right there if the next step would leave the range.

String to Integer (atoi): Clamp Before the Multiply

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Show test cases (13)

Need a hint? (3 available)

The Intel angle

Candidate reports from Intel's firmware and BIOS track list writing atoi by hand, next to malloc and reversing the byte order of a 32-bit word. Boot code parses strings with no C library and no exceptions to catch a bad input. Spaces, a sign and a run of digits are easy to handle, and overflow is what interviewers judge the answer on. Signed overflow in C is undefined behavior, so multiplying first and testing for a wrapped result afterward proves nothing, and the optimizer is entitled to delete that test. Compare against INT_MAX / 10 before you multiply. Then expect a question about the caller, since a bare return value cannot tell a parsed "0" from garbage.

Take it further

Give the caller a way to tell a real 0 from a failed parse. Return a status code and hand back the value separately, the way firmware wraps this in int parse_i32(const char *s, int32_t *out). Report "no digits" and "out of range" as distinct errors. The parse stays one pass, and the only new state is where the digits started.

Show solution & walkthrough

The Intel angle

On the firmware track these routines come back as parsers for input nobody trusts. A command typed into a debug console over a serial line arrives as raw bytes, and boot code has to find the keyword and turn the argument into a number before any C library exists. The same habits apply. Bound every scan by the buffer's length as well as its terminator, check for overflow before the multiply, and hand the caller a status it can test instead of a value that might secretly mean failure.