5 ms·

I'm nowhere near an experience C coder, but doesn't the in place part mean that you don't create any additional variables or strings and just modify z_terminate

I'm nowhere near an experience C coder, but doesn't the in place part mean that you don't create any additional variables or strings and just modify z_terminated? Is that even possible? This is an honest question, because the solution is obvious this way, but a bit harder if you can't create additional variables.

amalcon 16y ago
"In-place" usually means "using only a constant amount of additional storage." You're using a constant amount of additional storage if you even use a function call (unless you're invoking certain compiler directives and/or optimizations), because C function calls usually involve placing a return address on the stack. This is also why quicksort is considered to take up log(n) space: it calls itself recursively, and thus uses up a bit of the stack for each recursive call.
ydant 16y ago
The solution in the link only uses pointers to the string. "In place" as I understood it means not allocating additional memory for the string. His code does that, but it does need two pointers (the one passed in, and the one created to keep track of secondary position) in order to traverse the string. Because the resulting string will only be shorter (never longer), this works. You simply keep track of where you're copying to and where you're copying from, and move character by character until you reach the end. The resulting string may have extra stuff at the end, but since it's null terminated the standard C string functions will not see that cruft as they will stop at the first null.
RiderOfGiraffes 16y ago
"In place" usually means that the result is in the same place as the input, and you don't create an intermediate copy. Creating a fix, known number of additional variables to assist with the calculation is OK. Some people allocated memory, copied out the input, then put back the bits they wanted to keep. That is not "in place".
- Retric 16y ago
  Your routine should modify the given zero-terminated string in place, removing all instances of the given char. The main point of the whole exercise is to see if the candidate can write any code - anything after that is a bonus. Now if the input and output of a function are correct I think you where simply less clear than you may have thought. If you had said "string in place (don't allocate any memory)," I suspect far more people would have given you the output you wanted.
  - deleted 16y ago
    [deleted]
  - RiderOfGiraffes 16y ago
    The main point is as you quote. Secondary points are to see if the candidate can understand common expressions and idioms, and if not, either to look them up, or to ask. As it says elsewhere, the purpose is to get some code, then use it as a start for the discussion. If someone allocates memory then that's where I start. In that case they clearly they don't understand the usual meaning of the expression "in-place." > If you had said "string in place (don't allocate > any memory)," I suspect far more people would have > given you the output you wanted. I suspect you're wrong, and I would be interested to see if anyone else comments on that point. I got nearly 100 submissions, and only one (from memory) allocated memory. All the others did the modification "in-place" as requested.
    - Retric 16y ago
      Some people allocated memory, copied out the input, then put back the bits they wanted to keep. That is not "in place". "Some people" implies more than one. I would have done it in place because that was the simplest approach and not doing so would have been silly. However, just because it seems that way to us does not mean everyone knew you required more than just output in that fashion. Anyway, I was more commenting on the style where you mix the requirements for an interface with the requirements for the algorithm. IMO "I need a function / API that does X efficiently" is much better than saying "does X using hash tables". AKA, if you don’t' want someone to use malloc then you can say so, but giving the reasons why you don't want malloc is more useful. PS: It’s really a minor point and I thank you for doing this bit of research. I was simply trying to help you communicate in a more clear fashion.
aplusbi 16y ago
Usually "inplace" means "in constant memory space." In other words, running the algorithm on an input of size N requires the same amount of memory as running the algorithm on an input of size M.
RiderOfGiraffes 16y ago
I've just realised that you might think that z_terminated actually "contains" the string, and hence "in-place" would mean modifying z_terminated. But z_terminated is a pointer to a lump of memory that contains bytes. In that context "in-place" means that you move things around in the lump of memory you are given (the one pointed to by z_terminated) rather than allocating some more memory and using that. If I'm right, your misconception is by no means unique, but it's a dangerous one that shows that you don't understand what's going on in C with regards pointers, memory and strings. If I'm wrong then I apologise.

amalcon 16y ago

"In-place" usually means "using only a constant amount of additional storage." You're using a constant amount of additional storage if you even use a function call (unless you're invoking certain compiler directives and/or optimizations), because C function calls usually involve placing a return address on the stack. This is also why quicksort is considered to take up log(n) space: it calls itself recursively, and thus uses up a bit of the stack for each recursive call.

ydant 16y ago

The solution in the link only uses pointers to the string. "In place" as I understood it means not allocating additional memory for the string. His code does that, but it does need two pointers (the one passed in, and the one created to keep track of secondary position) in order to traverse the string. Because the resulting string will only be shorter (never longer), this works. You simply keep track of where you're copying to and where you're copying from, and move character by character until you reach the end. The resulting string may have extra stuff at the end, but since it's null terminated the standard C string functions will not see that cruft as they will stop at the first null.

RiderOfGiraffes 16y ago

"In place" usually means that the result is in the same place as the input, and you don't create an intermediate copy. Creating a fix, known number of additional variables to assist with the calculation is OK. Some people allocated memory, copied out the input, then put back the bits they wanted to keep. That is not "in place".

Retric 16y ago
Your routine should modify the given zero-terminated string in place, removing all instances of the given char. The main point of the whole exercise is to see if the candidate can write any code - anything after that is a bonus. Now if the input and output of a function are correct I think you where simply less clear than you may have thought. If you had said "string in place (don't allocate any memory)," I suspect far more people would have given you the output you wanted.
- deleted 16y ago
  [deleted]
- RiderOfGiraffes 16y ago
  The main point is as you quote. Secondary points are to see if the candidate can understand common expressions and idioms, and if not, either to look them up, or to ask. As it says elsewhere, the purpose is to get some code, then use it as a start for the discussion. If someone allocates memory then that's where I start. In that case they clearly they don't understand the usual meaning of the expression "in-place." > If you had said "string in place (don't allocate > any memory)," I suspect far more people would have > given you the output you wanted. I suspect you're wrong, and I would be interested to see if anyone else comments on that point. I got nearly 100 submissions, and only one (from memory) allocated memory. All the others did the modification "in-place" as requested.
  - Retric 16y ago
    Some people allocated memory, copied out the input, then put back the bits they wanted to keep. That is not "in place". "Some people" implies more than one. I would have done it in place because that was the simplest approach and not doing so would have been silly. However, just because it seems that way to us does not mean everyone knew you required more than just output in that fashion. Anyway, I was more commenting on the style where you mix the requirements for an interface with the requirements for the algorithm. IMO "I need a function / API that does X efficiently" is much better than saying "does X using hash tables". AKA, if you don’t' want someone to use malloc then you can say so, but giving the reasons why you don't want malloc is more useful. PS: It’s really a minor point and I thank you for doing this bit of research. I was simply trying to help you communicate in a more clear fashion.

aplusbi 16y ago

Usually "inplace" means "in constant memory space." In other words, running the algorithm on an input of size N requires the same amount of memory as running the algorithm on an input of size M.

RiderOfGiraffes 16y ago

I've just realised that you might think that z_terminated actually "contains" the string, and hence "in-place" would mean modifying z_terminated. But z_terminated is a pointer to a lump of memory that contains bytes. In that context "in-place" means that you move things around in the lump of memory you are given (the one pointed to by z_terminated) rather than allocating some more memory and using that. If I'm right, your misconception is by no means unique, but it's a dangerous one that shows that you don't understand what's going on in C with regards pointers, memory and strings. If I'm wrong then I apologise.