   Reversing a string without using new memory
  Hi,I've heard of an interview question that basically asks you to reverse a string without using new memory. I'm not sure how to do this.Up till now I've been doing this:-// Reverse string functionint ReverseString(string &str){str = string(str.rbegin(), str.rend());return 1;} This obviously isn't right and I was wondering if anyone could help me out at all?I've heard a rumor of a NULL element at the end of the string that can be used to shift elements about?   
  Hopefully, this is just curiosity, not about how to pass an interview.Let's say you have an array of chars of known length (5 in this case):|H|e|l|l|o|How would you access i-th element?How would you determine its length?When you know previous two things, how would you reverse such an array?Now all that's left is to figure out how those apply to std::string.   ;  Of course, you could just use std::reverse().   ;  When you say no memory, are you also referring to stack memory? e.g. no local temporary variables. If so, then just do a reflection around the middle of the string doing a couple of bitwise operations.   ;Quote:Original post by AntheusHopefully, this is just curiosity, not about how to pass an interview.Let's say you have an array of chars of known length (5 in this case):|H|e|l|l|o|How would you access i-th element?How would you determine its length?When you know previous two things, how would you reverse such an array?Now all that's left is to figure out how those apply to std::string.Yeah its just a curiosity.I know how to access the i-th element and get the strings length, its just where do i store the i-th element while I'm moving things about without creating a temp to hold it?Quote:Original post by SiCraneOf course, you could just use std::reverse().lol would be nice, but I'm not sure they'd accept that as an answer really.   ;Quote:Original post by SiCraneOf course, you could just use std::reverse().I was going to say that this would be a good idea if you wanted to annoy your interviewer by being deliberately obtuse -- and then realized immediately that's not the case. I would start by pointing out the existence of std::reverse to solve the problem, and then go into the usual solution in order to prove that I do have some concept of what's going on.This demonstrates both that you have basic algorithmic competency AND that you know how to use the standard library when appropriate. And if I were interviewing you, I'd feel a lot more comfortable hiring you if you know that std::reverse existed.   ;template < typename T > void swap( T& lhs, T& rhs ) { // equivalent to std::swap    T temp = lhs;    lhs = rhs;    rhs = temp;}template < typename BiDirectionalIterator > void reverse( BiDirectionalIterator begin, BiDirectionalIterator end ) { // equivalent to std::reverse    while (begin!=end && begin!=--end) swap(*begin++,*end);}INB4UndefinedBehavior:  This abuses the sequence-point-inducing nature of an unoverloaded operator&& :D   ;  As noted, it is generally ideal to use the standard library.  The standard library is well understood and major implementations are basically bug free.This particular algorithm was critical back in the day when computer time was rented by the minute, and both ram and disk space were rented by the byte.For the sake of the programming quiz, there is a very old xor trick to swap elements:xor a, bxor b, axor a, bIf the reason it works is not immediately obvious to you, try it out by hand a few times.  This type of bit-wise manipulation is, or should be, covered in your computer theory classes.Start a at the beginning, b at the end, and walk them toward each other until they meet.  The only memory required are the pointers a and b, but they can be kept in registers.  This allows you to save a tiny bit of money on your computer rental.   ;  My post was actually a response to this line:Quote:Original post by ScottH87Up till now I've been doing this:-;Quote:Original post by ScottH87I know how to access the i-th element and get the strings length, its just where do i store the i-th element while I'm moving things about without creating a temp to hold it?Hmmm...void reverse(std::string & s) {  for (int i = 0; i< s.length()/2; i++) {    char temp = s;    s = s[s.length()-i-1];    s[s.length()-i-1] = temp;  }};What counts as allocation? the 'temp'?1) stack frame + s parameter2) i counter3) result of s.length3.1) divisor and remainder of s.length() / 2 (2 registers probably)4) temp5) result of s.length()At minimum, the i, and temp cannot be avoided. (btw, is anyone willing to take on a challenge of reversing a C-string literal, shorter than 256 bytes, or a wide string shorter than 2^(sizeof(wchar_t), by using null terminator for loop counter as well? It should be doable....)The real question is:- Reverse a string with O(1) memory complexity, instead of O(n), as the original example showsThis is what the question is about. Whether you use xor, std::swap, or #DEFINE SWAP(a,b) is a minor detail, which can lead to further debate.Reverse a linked list with O(1) memory complexity is a related question.   