David Avraamides Code and other geekery

How Do I Copy Thee? Let Me Count the Ways

Over the years I've interviewed a lot of programmers and one of the questions I've always asked is for the candidate to implement the strcpy function. This article discusses why I asked this question, walks through the range of "solutions" I received, and takes a look back at what I learned about programmers from this one simple question.

Why strcpy?

First I should start off with a bit of a disclaimer: this isn't the only question I ask as part of an interview process. On the contrary, I put candidates through a phone screen, have them take a written quiz (of which this is one of about 40 questions), and follow all that up with a take-home programming problem. No, the strcpy question is just one data point I use when evaluating programmers ... but it is probably one of the best.

To review, strcpy is the function for copying one string to another that is part of the standard library of the C programming language. Sounds simple, but asking someone to code it up is a bit of a loaded question, and that's what makes it so great for interviews. To implement the function, you have to know what it does and how strings are represented in C, which gets to one of the important design choices of C's creators: there is no native string type in C. Instead, a string is represented as a sequence of bytes (char values) in memory terminated with a byte containing zero. A pointer to the first byte in the sequence represents the string, but it's really more of a convention then a first-class data type (although the compiler helps you a little by automatically appending a zero to string constants in memory).

Then there is the design of strcpy itself. It was designed to have the feel of an assignment statement for strings so where you might say

int a, b;
...
a = b;

to copy the value from b into a, you would likewise use

char *a, *b;
...
strcpy(a, b);

to copy the string value from b to a, that is, the destination is the first parameter (left-hand side) and the source is the second parameter (right-hand side), just like an assignment.

Another feature of C is that assignment statements themselves have a well-defined value and this is often used in shortcuts like

int val;
if ((val = getval()) != -1) {
    // do something with val
}

where we can call a function that returns a value, assign it to a variable and test its value in one expression. A (little-known) feature of strcpy is that it returns the value of the destination pointer as a convenience to the caller so you can copy a string, and use the value in one expression as in

char *a, *b;
...
printf("%s\n", strcpy(a, b));

Admittedly, not a feature I've used much, but experienced C programmers are usually aware it's there.

Another interesting thing about implementing strcpy is that the solution is introduced, discussed and refined in the C "bible": The C Programming Language by Brian Kernighan and Dennis Ritchie, more commonly referred to as the "K&R book." Anyone who really wanted to learn C would have at least heard of this book and hopefully been curious enough to read it. If they had (and they paid attention), then they would already know the answer. Experience has shown me, though, that it doesn't appear to be as popular as I would have thought - at least not with the candidates that have crossed my path.

Phrasing the Question

The strcpy question was one of a number of problems I put on a written quiz for interviewing programmers. I liked having candidates write it on paper because it avoided the problem of working on a computer where different programmers use different tools - everyone should be equally familiar with paper and pencil. It also avoided the distractions of a development environment where the person might be messing around with build settings and key bindings rather than focusing on the problem at hand.

As for how to phrase the question, initially I was wary of giving away too much with the signature of the function, and part of the reason for asking this specific question was to see if users were familiar with such a ubiquitous function, so my first version was simply

Implement the C standard library function: strcpy

I figured most people would know what it was and what it did so there wasn't really a need to be more explicit. And if they didn't know the function, then that told me a lot - maybe more than whether or not they could code it. You have to understand, the interviewee had already done well enough on a phone screen to be invited in for a round of interviews. I figured wrong. Asking the question in this way led to very few correct answers. Some people had not heard of the function, many people who knew what it did got the source and destination arguments mixed up and practically no one got the return value right. So for the second version I gave up on people knowing the correct signature from memory and rephrased the question to be more explicit (and more in line with ANSI C):

Implement the following C library function:

char* strcpy(char* s1, const char* s2) {
    ...
}

Note that I didn't give away the source and destination arguments by name but I thought most people would see the const modifier hint. I also expected the return type of the function to jog a few people's memories. It turns out that the const hint was not strong enough, however, as many people continued to confuse the source and destination arguments. A few people understood that they should be returning something, but even with the prototype, very few people actually got that part right.

I tweaked the question again to arrive at the third version. I simply gave up on the return type in order to simplify the problem so they could focus on the basic algorithm. I also named the arguments hoping to clear up the confusion:

Implement the following C library function:

void strcpy(char* dst, const char* src) {
    ...
}

So now I was leading them to the water, and was expecting many correct, or nearly correct solutions. Did I ever say I was a bit of an optimist? How foolish I was to think my new version of the question was clear enough. Granted, most people started off on the right track copying chars from the const src pointer to the dst pointer. (No one ever asked why its return type was not char * so I felt validated on that omission.) But wait, you can do it without calling strlen - think about it! And why are you calling malloc? Or memcpy? Okay, one more refinement and I think I've got it:

Implement the following C library function, without calling any other routines:

void strcpy(char* dst, const char* src) {
    ...
}

Whew!

Evaluating the Answer

There were five key things I looked for when evaluating an answer.

  1. Did they know what the function was supposed to do? That is, was their algorithm an attempt at an actual copy of a string?
  2. Was the algorithm correct? Did they copy all the characters? Did they copy the terminating null? (Later, when we went through the quiz, I'd ask the candidate to walk through their code for the string "Hi" to test/break it.)
  3. Did they follow my instructions - no system calls or other routines?
  4. Did they get the src and dst arguments right?
  5. Did they use arrays or pointers? This was more to see how comfortable they were with pointers.

I also considered a few other points for "extra credit": Did they know about the return value? Did they write defensively (check for null arguments)? As you can see, there is a lot to be learned from such a basic question. I also believe that people are creatures of habit: they tend to do things the same way in this setting as they might on the job. If they were sloppy and careless on the interview ... well caveat emptor.

The other thing I was always thinking about was the context they were in. Sure, interviewing can be stressful, and there were many other problems on the quiz so they couldn't spend all their time on this one, but this was an interview for a job! I expected people to be going a little over the top in order to give a good impression, so details were important. And while I wouldn't say that any one thing on an interview should be a sole determination if someone is hired or not, it was hard for me to get excited about hiring someone that couldn't get this right.

The Solution

Although there are many ways to solve this problem, we can look to the K&R book for the classic solution.

void strcpy(char* dst, const char* src)
{
    while (*dst++ = *src++)
       ;
}
Solution 1: The "classic" K&R answer

It's simple, concise and correct. We can quibble about where to put the semicolon or if we should use braces, but that is all just style - the statement that does all the work is in the test of the while. This solution uses a number of features of the C language to get a lot done in essentially one line of code:

  • A char is copied from one pointer to another using the dereferencing ("*") operator
  • Post-incrementing is used to march the pointers forward in memory after the char is copied
  • It takes advantage of the fact that the result of an assignment is the value of the statement of itself
  • The terminating zero of a C-string is used as a boolean test for the while loop

That's a lot packed into one simple expression! These are all features of C that its creators designed into the language for a purpose. This expression, and slight variations of it, are so common that they are idioms in C programming and any C programmer will likely come across code with statements like these time after time. They better fully understand what's going on here if they are going to master the language (or at least to read and understand other people's code).

I mentioned earlier that the "real" version of strcpy returns a copy of the destination pointer as a convenience. Thus, a more correct version of the function would be

char* strcpy(char* dst, const char* src)
{
    char* ret = dst;

    while (*dst++ = *src++)
        ;

    return ret;
}
Solution 2: Handle the return value correctly

That is, we save a copy of the destination pointer and return it after we've copied the string. While that is more correct, it doesn't demonstrate any real coding skills - it's really more of a trivia question about strcpy. That's why I eventually rephrased my interview question to use a void return type (and of course because no one was getting that detail correct, anyway).

There are a couple of common variations on this solution: using a different looping construct, and using arrays rather than pointers. The following solution shows one variant using a for loop.

char* strcpy(char* dst, const char* src)
{
    int i;
    for(i = 0; src[i] != 0; i++) {
        dst[i] = src[i];
    }
    dst[i] = 0;

    return dst;
}
Solution 3: Using array notation

Since we never modify dst - we use i as an index to offset from the starting address - there is no reason to make a temporary copy for the return value. But since we aren't copying and testing for null in the same statement here, the terminating zero is not copied in the loop. Thus we need to terminate the destination string outside of the loop.

These are all correct solutions in that they copy the string including the terminating null. And although I personally prefer a version using pointers as it demonstrates a degree of understanding and confidence in using them, the array version is perfectly fine.

There are, of course, dozens of other variations that could be written. We could use a for with pointers, use a while loop with arrays, use a do loop - we could even use recursion if we wanted to be silly (and inefficient). But most often I've found good solutions will look a lot like one of the snippets above.

Answers

I've taken a not-so-random sample of some past solutions to show some of the classic mistakes people make. For dramatic effect, I'll start with the good ones and work my way down through the common mistakes people make, all the way to the really awful answers that I'm not even sure what they were trying to do. Remember, these are actual answers from actual programmers. Additionally, these were people who were often gainfully employed at the time of the interview, had been recommended by recruiters or other people, and had already been screened through a phone interview. All of these snippets are exactly as answered including syntax errors, comments, creative operators, etc.

void strcpy(char* dst, const char* src)
{
    for (; dst != Null && src != Null;)
        *dst++ = *src++;
}
Answer 1

So close! If they would have just replaced the test clause of the for loop with its body, they would have nailed it. But they got confused.

  • They assumed "Null" is some pre-defined constant for zero
  • They compared addresses and not the value pointed to by the address so this would not terminate
  • Even if they got the loop test correct, they wouldn't have copied the terminating null character

But all in all not a bad answer and the use of pointers for copy-and-increment is promising. You can tell that they've either read up on C or used it in the past, but probably aren't using it day to day.

void strcpy(char* dst, const char* src)
{
    if (src == NULL) return;
    if (dst == NULL) return;

    while (src[i++] != '\0') {
        dst[i] = src[i];
    }
    dst[i] = '\0';
}
Answer 2

Hey, defensive programming! I like that, and I see him copying the null at the end, could we have a winner? Oh, I'm sorry, you got the last char but forgot the first one (and you forgot to define i).

void strcpy(char* dst, const char* src)
{
    while(*src)
        *dst++ = *src++;
}
Answer 3

Another close one! They seem comfortable with pointers and their use in the copy-and-increment idiom. But the while test is going to kick you out of the loop before you copy the terminating 0 (which you would have noticed if you tested it). Sorry.

void strcpy(char* dst, const char* src)
{
    *dst = *src;
}
Answer 4

Well, it does work for the special case of strcpy(buf, ""), and I have to admit, it is fast, but I was looking for something a little more ... correct.

void strcpy(char* dst, const char* src)
{
    int counter = 0;
    while (*(src + counter) <> '/0') {
        *(dst + counter) = *(src + counter);
        counter++;
    }
}
Answer 5

Well the syntax for "not equals" smells a little like VB and there seems to be confusion on the syntax for an escape character. Overlooking those points, there is still the problem with the terminating null, and while the pointer expressions are valid, I find them less clear than the examples that increment the pointers.

At least in answers 1-5 you can see some familiarity with C and the use of pointers, plus it's clear that people knew what strcpy did, if not exactly how it did it. Now let's move on to some more "creative" answers.

void strcpy(char* dst, const char* src)
{
    char i = null;
    do while i <> '\n'
    {
        i = &src;
        &dst = i;

        dst++;
        src++;
    }
}
Answer 6

There are a number of issues with this answer:

  • Confusion between the dereferencing and address operators (*/&)
  • Wrong syntax for a do/while loop
  • Wrong syntax for "not equals"
  • They are looking for a terminating end of line character, not a null
  • It doesn't copy the terminating null (or \n for that matter)
void strcpy(char* dst, const char* src)
{
    int idst, isrc;
    idst = 0; isrc = 0;
    while (src[isrc] != "\0")
        dst[idst++] = src[isrc++];
}
Answer 7

This time they confused the syntax of a char constant with a string constant. This is actually a very nasty bug (if the compiler didn't warn on type mismatches) as "0" evaluates to an address that stores a string constant so the while would never terminate. Oh, and they also forgot the null (are you beginning to see a theme?).

void strcpy(char* dst, const char* src)
{
    int ilen = 0;
    char *trav, *trav2;

    for(trav = src; *trav++; ilen++);
    free dst;
    dst = malloc(ilen + 1);
    trav2 = dst;
    for (trav = src; *trav2 = *trav++; trav2++);
}
Answer 8

Where do I start?

  • The first for is counting the length of src (we'll see why in a couple of lines)
  • Then they try to free dst (with a syntax error on the free call). That's going to surprise the caller!
  • Now they get (leak) a new chunk of memory that the caller will never know about
  • The second for then actually copies the string correctly! Yeah!

What's funny is if they would have deleted the first three lines (the for, free and malloc), this would be correct (although a bit overly confusing with inconsistent initialization and incrementing statements). Because those three lines are there, however, it copies the string to our newly allocated chunk of memory that no one will know about as soon as the function exits. But I'm being pedantic - it may never get that far since the free call would likely cause a crash. There's also the issue of not following instructions with the use of malloc (at least they didn't call strlen, though).

The use of malloc and free is particularly troubling. This demonstrates that the candidate misunderstands a couple of the basic design decisions that went into the C language: that it has no built-in memory operators (i.e. no new or delete), and that the developer is completely responsible for memory management. Allocating memory inside a function that advertises only to copy a string would violate this rule. More importantly, strcpy requires the user pass in the destination address, thus it should be clear that the user is responsible for making sure that address points to a valid destination with enough space to hold the string.

Note: The strdup function, on the other hand, does violate this rule but clearly states this in its documentation. You can also infer this from its design. It takes only one argument - the source string - and returns the address of a new duplicate of the string. Since the user cannot pass the destination address, the function must allocate it for them - and return it. It is essentially a memory allocator that fills the new chunk of memory for the user, and I think would have been more appropriately called salloc and put in the malloc.h include file rather than string.h. Although strdup may be convenient in certain cases, I still prefer not to use it. I prefer controlling how the memory for the copy is obtained - I might have a static char array that I reuse, or an array on the stack. I think it is much more clear to take responsibility for obtaining the block of memory and calling strcpy with a pointer to it, rather than calling strdup and having to remember to match up a free with each call to it - it's difficult enough matching malloc and free calls.

void strcpy(char* dst, const char* src)
{
    int size = strlen(src);
    malloc(dst, size)  // syntax?

    for (int i = 0; i < size; i++) {
        dst[i] = src[i];
    }
    return dst;
}
Answer 9

I'm disappointed from the first line. They didn't follow instructions and made a call to strlen. And things only get worse with the call to malloc. But they returned dst! Nice! (Except of course it's pointing to a non-terminated string and a different address then was passed in - assuming they would have eventually fixed the malloc call to: dst = malloc(size);.

void strcpy(char* dst, const char* src)
{
    free(dst);
    dst = malloc(sizeof(src));
    if (dst) {

    } else { // error; }
}
Answer 10

Let's see - system calls, freeing dst, and hopefully the string is 3 bytes (4 with the terminating zero) since they are allocating a chunk of memory for the size of an address, and not the length of the string it points to. But then the solution fizzles out. Come on, you weren't shy about using system calls. Why not round it out with a call to memcpy to at least finish it!

Looking Back

There are a number of things I learned about programmers from this one simple question. You can argue whether the question is a good one, whether my criteria for evaluating answers was fair, and whether this question is even relevent anymore. But one thing that you can't argue with is the value of asking people to demonstrate their knowledge by writing code, plus the comparitive value in asking the same question over and over. You learn a lot about people by asking them to solve something real that they should be familiar with and should understand.

First of all you learn how wildly one programmer's knowledge about a language can vary from another's. When someone says they "know" a language, what does that really mean? Does that mean they know the syntax? That they are comfortable with the standard library? That they understand the internal representation of data structures? That they are comfortable with pointers?

You also find out if people are curious or not. When they were learning C, did they find out about the K&R book and read it on their own? Sometimes if a candidate does well I'll have them come back for a second round of interviews and I might ask them, how would you do it now? I love it when they ran home, read up on C and learned how to do it better. Or they proactively just emailed me an improved version because they couldn't let go of it.

What about their style? Is the code legible? Organized? Were they careful? Did they bother to test with the most trivial example to see if it works? Granted, strcpy is too small to answer some of these questions but it wasn't the only programming problem they were given. The point is that looking at someone's code tells a lot about them - it is what you are hiring them to produce and you want to know how they go about creating it. Would you hire a photographer without looking at their portfolio?

Some people may find it disagreeable that I give someone a written quiz as it creates a stressful situation. I agree. I've always worked in a high pressure environment and want to make sure the candidates can handle that pressure (most of my career I worked on trading desks of Wall Street firms).

I've done enough of this to know that this isn't a statistical anomoly. The truth is that there are a lot of bad programmers out there. That's not to say that this simple question is the one true determinator of a good or bad programmer - it's just one of many data points I've used in interviewing programmers. But I'd certainly make the argument that it's positively correlated with a person's skills and knowledge and all other factors being equal, I'd much prefer hiring someone who nailed it then someone who took twenty lines to get it wrong.


30 Comments

Posted by
IcyLiquid
Wednesday February 28, 2007
3:27 a.m.

Wow. I was laughing out loud at the end :)


Posted by
Alex
Wednesday February 28, 2007
9:18 a.m.

It's a very interesting analysis, it is great that you took the time to think about it and express all the ideas in such a story.

The examples were interesting, some were funny; either way, each student who plans to become a programmer should take a look at this.


Posted by
Lee
Wednesday February 28, 2007
11:17 a.m.

Interesting\Funny examples.

It would have been much easier to read if your HTML characters were rendering right though. It looks like you escaped them yourself and the blog software is escaping your escaped version.


Posted by
David Avraamides
Wednesday February 28, 2007
1:23 p.m.

Lee: Oops - I had manually escaped HTML characters when I initially wrote this (because I needed to) and never fixed them when I updated my blog software. I just cleaned them up. Thanks for the note.


Posted by
Anonymous Cowherd
Wednesday February 28, 2007
2:07 p.m.

(Linked from http://www.codinghorror.com/blog/archives/000781.html )

Well, it's your own fault for repeatedly dumbing down the question. A blank stare is less of a hassle than an abysmally stupid answer, and tells you just as much. Obviously, you wouldn't hire any of these "candidates", so why bother wading through their mush?


Posted by
David Avraamides
Wednesday February 28, 2007
2:17 p.m.

AC: I'm not sure what's "my fault." I'm simply pointing out that people who claim they have strong experience in a programming language will often struggle with basic problems, and that it's important to ask them to write some code.

As I stated in the article, you can argue whether this is an appropriate question to ask and whether my evaluations of the answers was fair, but I think its hard to argue with the value of asking people to sit down and write code. That's why you are hiring them.

As for "wading through their mush", I had lots of old copies of solutions lying around and thought it would be interesting to show a few of them to emphasize some of the points in my article. Its my time to spend, so what's the problem?


Posted by
Rene
Wednesday February 28, 2007
5:39 p.m.

With all due respect, the K&R solution is every bit as fallacious as some of the student examples you gave. Most notably because it's not the slightest bit defensive and will crash hard if passed a null pointer for either the source or destination. It wins points for cuteness and being very compact, certainly, but it's hardly a "good" solution.


Posted by
Georgi
Thursday March 1, 2007
1:21 p.m.

Agree with Rene. I'm a C# programmer (I can't say that I'm good or smart [or both]) and I learned that code must be safe. Your K&R primer is good for speed, but likely will crash just like you said for "free call": "But I'm being pedantic - it may never get that far since the free call would likely cause a crash". It is better to combine several ideas and add null checks before doing: while (dst++ = src++)

... Just like the guy from answer 2. At the end: Are you write all of your code from beginning to the end without any mistakes and fixes ? Do you use debugging ? If someone (answer 2) runs his code and find that the first char is not copied, then for about 20 seconds he will fix the problem - and the solution will be better than yours (K&R). It's not urgent for programmers to write code that will run properly at the very first time - it is urgent for programmers to have ability to find their mistakes and fix them. Agree ?


Posted by
David Avraamides
Thursday March 1, 2007
1:50 p.m.

Rene/Georgi: Certainly the "K&R" solution is a good example of a textbook solution: simple, elegant ... and something you shouldn't use in production. When I quizzed candidates, I was thrilled when people would put some defensive coding in, but sadly it didn't happen very often.

But what I was really looking for by asking this question was in general, the candidate's familiarity with C, and specifically, their level of comfort using pointers. Its such an important concept in C that I feel you really need to know it.

If someone wrote a working solution and they handled error/edge cases correctly, then they get a gold star! But remember, the first thing strcpy() must do is copy a string. And as you can see, that in itself was often a stumbling block.

Also note that Linux even today, still includes a similar implementation, dangerous though it is: http://www.google.com/codesearch?hl=en&q=+lang:c+license:gpl+package:linux+strcpy+show:Lc66PI9Xyrk:AnEDQX7Nmcw:0Cp2z-9pfvQ&sa=N&cd=3&ct=rc&cs_p=http://www.kernel.org/pub/linux/kernel/v2.4/linux-2.4.33.3.tar.bz2&cs_f=linux-2.4.33.3/lib/string.c#a0


Posted by
Oran Looney
Thursday March 1, 2007
2:10 p.m.

Yep; reading someone's code is the only way to know if they can code or not. Other hands-on tests, like finding a bug, laying out a UI, or laying out a class hierarchy, also seem like good ideas, although I haven't tried them. I read a book about puzzle interviews at Microsoft ("How would you move Mt. Fuju") and didn't get it at all; why not test people on what they actually do?

The strcpy test will work only work for C programmers. I had an interview with a 2-hour test where they defined a small language language from scratch, and then asked you to program in it. This seems good to me, because it tests more general abilities than experience with a language. The downside is that it does not test curiosity, the geek drive to learn the details and arcania of a language.

Anything that moves us away from current interview practice ("What do you feel your worst trait is?") is good.


Posted by
Bas de Bakker
Friday March 9, 2007
8:23 a.m.

I do not agree that the "defensive programming" part of answer 2 is something to like.

1) The standard lib version doesn't do it this way, so for the earlier versions of the question it would simply be incorrect.

2) Doing nothing is no way to signal an error. It might be argued that for src == NULL, doing nothing is useful behaviour. But for dst == NULL, the caller is simply buggy. And crashing will let you find the bug much faster than ignoring the call.

I remember a coworker who had a program that crashed on a null pointer. He just put an "if != NULL" test around the crashing line without knowing why it crashed. Sure, the program stopped crashing. But the real bug was still there.


Posted by
Evan
Friday March 16, 2007
8:18 p.m.

Would you hire me? Here is my answer!

char strcpy(char dst, const char* src) { ASSERT(!"Depreciated. Use operator= on std::string");
}


Posted by
Evan
Friday March 16, 2007
8:22 p.m.

Ouch. It doesn't compile...

char strcpy(char dst, const char* src) { ASSERT(!"Depreciated. Use operator= on std::string"); return NULL; }


Posted by
David Avraamides
Saturday March 17, 2007
3:29 p.m.

Would you hire me?

Well, not based on that answer. The whole article was about the C programming language. Your suggestion to use std::string's operator= requires the use of C++.

Also, the correct term is "deprecated", meaning that it's obsolete and is being phased out, not "depreciated" which means a reduction in value.


Posted by
boysha
Wednesday March 21, 2007
9:15 a.m.

Hello. Perhaps you could find some time to comment on this little implementation, and perhaps show us an implementation of your own that would have made you happy that day? :)

char strcpy(char dst, const char* src) { // If a null pointer is passed as source // do nothing. if (src == 0) return dst;

// If a null pointer is passed as destination // do nothing, as we're not allowed to call malloc // and I don't know any other way to allocate memory. if (dst == 0) return dst;

// Perhaps we should check the size of allocated memory? // I'm not sure how that works in C // if (sizeof(dst) < sizeof(src)) return dst;

// Copy the characters until you reach the zero. int i; for(i = 0; src[i] != 0; i++) { dst[i] = src[i]; }

// Add a zero to terminate our new string. dst[i] = 0;

// Return the pointer. return dst; }


Posted by
David Avraamides
Friday March 23, 2007
12:31 p.m.

boysha: That's a pretty decent solution - safe, correct and handles the return value.

For the special cases (src or dest are null), its not really clear what you should return. If someone used this in an expression like: printf("%s ", strcpy(buf, 0)) then the printf would probably crash dereferencing the null return value.

You could also shorten it up if you wanted to: if (! src || ! dst) return 0;

In terms of the loop, I prefer the pointer approach simply because you don't need the additional line to copy the terminating null outside of the loop.

Regarding the commented out line about the size of the allocated memory, there is no real way to do that in C. Given a pointer to a chunk of memory, you don't know how "long" that chunk is. If you really think of the pointer (or array address) as just that - a pointer - then its somewhat of a rhetorical question since a pointer is only an address.

That said, the internal implementations of malloc keeps track of the size of the chunk requested so it can mark it as available when free is called. There may be a way to query that information but it's probably not portable (I think *nix uses sbrk() or something like that).


Posted by
boysha
Saturday March 24, 2007
5:56 p.m.

In terms of the loop, I prefer the pointer approach simply because you don't need the additional line to copy the terminating null outside of the loop.

Yeah. I'm comfortable enough with pointers, but I chose this solution because it's easier to see what the code does (it's clear on the first glance). Also, I overcommented the implementation for pretty much the same reason. With proper naming of variables/classes/methods/etc, especially in OO programing, it's easy to read the code and understand it, but having plenty of comments can't hurt, only help. Placing an algorithm in a single line of code is attractive and fun, I like doing that on school tests ;) but shouldn't readability have some priority over it in real commercial programing?

For the special cases (src or dest are null), its not really clear what you should return.

throw ArgumentNullException? ;)

printf("%s ", strcpy(buf, 0)); then the printf would probably crash dereferencing the null return value.

Umm, my implementation returns the "buf" pointer in this case, so it would probably crash, yeah, but only if buf is null, or pointing to some forbidden memory, or a chunk of memory without zero bytes or something like that. :)

Regarding the allocated memory part, I was too lazy to check what sizeof really does. :( Yeah, I wanted to query the "mallocation". Also thought it'd be nice if the function allocated memory when a null pointer is passed for destination.

I actually expected a comment on my rem-lines more than anything else. Thought you guys give extra points for commenting out the code. :) But, the malloc/query part of your comment was educational, I'll make sure to look into that if I ever get back to writing code in a language without garbage collection (Hehe). Thanks for the reply!


Posted by
Kevin Hoang Le
Thursday April 19, 2007
2:38 p.m.

David,

I was looking for some django/python resources, but stumble on this article, spend some time reading it and so here's my contribution:

Like you said, "..we could decide to be silly and inefficient and implement using recursion..." or something like that. Well, you'd be surprised how many developers do not even know what recursion is. Since you covered everything else so well already, so, here I am, being "silly" with my recursive implementations:

1st implementation: char strcpy(char dst, const char src) { char ret = dst; if (src) { dst = src;tt strcpy(++dst, ++src); } else dst = 0;t return ret; }

Then I realize, we can make it more "harder-to-read" :-( but shorter and "sweeter" :-) in my opinion, so

2nd implementation: char strcpy(char dst, const char src) { char ret = dst; if (dst = src) { strcpy(++dst, ++src); } return ret;t }

Like I said, I'm just being "silly" here. I still have a django question to ask you, so please send me your email address, since I can't find anyway to contact you. My email is kevin dot le at pragmaticobjects dot org


Posted by
Kevin Hoang Le
Thursday April 19, 2007
2:45 p.m.

BTW, my recursive strcpy functions are about as safe as the K&R solution, meaning no checking for null pointers at all. But that wasn't what you were asking in the first place.


Posted by
Bill Lynch
Tuesday June 26, 2007
3:53 a.m.

Just a comment on const.

Passing into a function const char * src means ONLY that the address that src points to can't change. In other words, I can legally do src[3] = 'a';. I can't do src = 0x1234;.

What you're looking for in a prototype would be... char * strcpy (const char * dst, const char * const src);

That way, the function can not change the address that either dst or src point to, and the data in src can not be changed as well.


Posted by
Bill Lynch
Tuesday June 26, 2007
4:05 a.m.

Whoops. Had it a bit backwards. I checked and saw that the strcpy specs are as you have, but it's slightly surprising that they didn't do this...

char* strcpy (char * const dst, const char * const src)

(had the first const in the wrong spot).

Although, this might be a c++ only thing?


Posted by
David Avraamides
Tuesday June 26, 2007
8:17 a.m.

Bill: I think 'const' was is an ANSI C addition, not just something for C++. And to your question about why it's not:

char* strcpy(char * const dst, const char * const src);

I think its simply unnecessary. In C, everything is passed by value so when you pass a pointer to a function, the value of the address is passed and if the called function modifies that value, the change is local to that function.


Posted by
Bishu
Thursday July 5, 2007
8:21 a.m.

(char )strcpy(char dest,char src) { char p=dest; if(src) { dest=src; strcpy(dest++,src++); } else dest='\0'; return p; }


Posted by
David Avraamides
Thursday July 5, 2007
8:58 p.m.

Bishu: Nice try but there is a bug in your solution (hint: what is the value of "x++"?). Plus, your recursive solution is about half the speed as the simpler "while (dest++ = src++) ;"

Recursion can be very useful, but rarely is it a good choice for replacing simple iteration (i.e. when you don't really need the stack).


Posted by
Thomas
Saturday September 22, 2007
4:36 p.m.

I would never ask a question like this in an interview. How about a question that's relevant to the task at hand? You obviously had time to study the inner workings on how to implement strcpy and looked for every obscure detail to make yourself look smarter and come around boasting your great knowledge of programming.

For you to claim that someone is a poor programmer because they haven't sat down and studied the strcpy function is about as egotistical as it gets. I don't doubt that you can sit in your tiny cave hacking away at problems that have already been solved by someone who actually had to think about the solution but don't go ranting and raving about how you were able to analyze something that has already been implemented in the gazillion languages already out there.

Come up with something unique, solve a real problem, look at the world outside of your box. You have to imagine that there are problems greater than strcpy to see where I am coming from.

I know exactly what you're thinking too. "Oh this guy is exactly the guy I love to interview and he doesn't get it, that it's all about the details". I have to say, I've spent more time solving real world problems and creating solutions at a much greater scale than this and yes, you have created a tricky question for those people out there that don't understand the underpinnings of a string but you seriously need to get over yourself.

Here's a nice read for you: http://en.wikipedia.org/wiki/Creativity


Posted by
Thomas
Saturday September 22, 2007
4:38 p.m.

Love the comment posting error, btw. Doesn't look like your strcpy did much to solve that issue.


Posted by
Rhialto
Monday October 29, 2007
8:10 p.m.

Re Kevin Hoang Le's recursive solution, I would change it like this which does not need a temporary, and places the stars in more canonical K&R fashion:

char strcpy(char dst, const char src) { if (dst = *src) { return strcpy(dst + 1, src + 1) - 1; } else { return dst; } }

Also, to pick nits: the character that terminates a string is called NUL, not null. And null pointers are denotated with NULL.


Posted by
Moe
Friday December 28, 2007
5:55 p.m.

Uhm... you criticize Answer 6 for not copying the terminating ' ', but in fact it does copy the terminating character, because i (which is used for the test) is only ever changed during the copy, so any value in i has already been copied.

Doesn't make that answer that much better, but at least eliminates the only true logic error.


Posted by
David Avraamides
Friday December 28, 2007
8:07 p.m.

Moe: good catch. Yes it does copy the , assuming the string has a in it. I think the candidate meant to use \0 (a NUL character) and not a linefeed.


Posted by
Lucas McCain
Thursday January 31, 2008
4:56 p.m.

Hey, nice article. As a programming student, and I'm currently working my way through K&R (on my own time) to try and learn C. It's nice to have a "sneak peak" into what might be on the horizon come interview time. Oh and to Thomas: Your comments would make sense if every single applicant could implement strcpy with no trouble. But obviously they can't, I mean seriously, if you're going to say that you know how to program in C and don't understand how to duplicate an array of chars then you don't know C. Seems like a great "wheat from the chaff" kind of question to me.


Closed for comments