removing chars from a string - C

Question

Suppose I have a char* word = "abaradasaddragfavvdavgasbga00rarcrawabr0ac0ra0ra0vra0" and I want to remove all the '0' chars from the word, in place, without using extra-memory or memmove. How could I do it? So the output would be: "abaradasaddragfavvdavgasbgararcrawabracraravra" ** What I have tried **:

void removeZeros( char* word) {

   int size = strlen( word );
   int i;
   for( i = 0; i < size; i++ ){
         if( word[i] == '0' ){
             word[ i ]  = word[ i + 1 ];
             i++;
         }
   }
}

* Rules **:

should be done in place
should not call any built-in function like memmove or remove
should not use extra-memory
should not assign it to another variable

@willglynn That's not a homework question, I was in an interview and they asked to do so without `memmove`, which was the only way I knew. — cybertextron, Sep 21 '12 at 23:33
Well, if you know how to do it with `memmove()`, what's to stop you from doing it with your own implementation of `memmove()`? — willglynn, Sep 21 '12 at 23:34
The Microsoft manager which I was interviewing with ... he asked to do it in place, with no helper function call, with no extra memory nor assigning it to another variable. — cybertextron, Sep 21 '12 at 23:37
possible duplicate of [Function to remove spaces from string/char array in C](http://stackoverflow.com/questions/13084236/function-to-remove-spaces-from-string-char-array-in-c) — Jonathan Leffler, Mar 03 '14 at 03:01

Caesar · Answer 1 · 2012-09-21T23:41:33.313

4

#include <algorithm>
#include <iostream>
using namespace std;

int main()
{
    char word[] = "abaradasaddragfavvdavgasbga00rarcrawabr0ac0ra0ra0vra0";

    int size = strlen( word ) + 1;

    std::remove(word, (sizeof(char) * size) + word, '0');
    std::cout << word;

}

edited Sep 21 '12 at 23:41

answered Sep 21 '12 at 23:35

Caesar

9,483
8
40
66

Caesar, thanks for your answer, but it shouldn't be calling another function to remove the `'0'` for me. – cybertextron Sep 21 '12 at 23:37
1

@philippe You should state that in the original post. – Caesar Sep 21 '12 at 23:44
I think the question is now only about C... – Kerrek SB Sep 21 '12 at 23:45
@I've updated my question. I was caught off guard in this question too, because I always used `memmove` if it was `C` and `remove` if it was `C++`. – cybertextron Sep 21 '12 at 23:47

score 3 · Answer 2 · answered Sep 21 '12 at 23:33

3

Iterate over the string from start to end. For each 0 you find, increment an integer called offset, say. For every non-0 character, move it down by the current value of offset. Make sure to put a null byte on the end.

answered Sep 21 '12 at 23:33

1''

26,823
32
143
200

Like I did in my answer? – cybertextron Sep 21 '12 at 23:34

score 3 · Accepted Answer · answered Sep 21 '12 at 23:47

3

// this assumes your variable word is really a cstr and is NULL terminated
// also, it assumes that it's not in read only memory space like your small
// example shows but is actually in-place writeable
char* write_position = word;
char* scan_position = word;
for( ; *scan_position != '\0'; scan_position++ ) {
  if( *scan_position == '0' ) continue;
  *(write_position++) = *scan_position;
}
*write_position = '\0';

answered Sep 21 '12 at 23:47

Jason Coco

77,985
20
184
180

Jason, almost there ... but it can't use an extra variable or pointer ( You use `char * scan_position` ). – cybertextron Sep 21 '12 at 23:49
The code in your post includes two integer variables. Are local variables allowed or not? – willglynn Sep 21 '12 at 23:50
The `integer` variables are of course allowed. The creating a copy of `char* word`, assigning it to a pointer or another variable, using a function to remove the `'0'` `char` is not. – cybertextron Sep 21 '12 at 23:53
1

@philippe I think that your interviewer didn't want you to allocate another string. You need local variables to track your position, whether they're pointers (which, IMHO is the easiest as demonstrated above), or offsets, it needs to be tracked. If my interviewer told me I'd done this incorrect with the above code because of the `scan_position` variable, I'd laugh and turn down the job. Of course, you could always simply advance the `word` variable in exactly the same way, but I don't know the rest of the context and wouldn't want to update a pointer that I don't know where it came from. – Jason Coco Sep 21 '12 at 23:53
@philippe You are not understanding C. I did not create any copies of this string or memory at all. It is the exact same memory cost plus 64 bits on a 32-bit processor or 128 bits on a 64-bit processor. – Jason Coco Sep 21 '12 at 23:54
I saw your solution, it's correct ... you just did it in another way I was expecting. Thank you so much. – cybertextron Sep 21 '12 at 23:56

removing chars from a string - C

3 Answers3