reversing a string
I'm not saying you're wrong Fruny, but str.assign( str.rbegin(), str.rend() ); looks very worrying to me. If you're assigning a value to your string, wouldn't that invalidate your iterators? It will probably work anyway since the string will probably reuse its old allocated buffer, but still, is that a good idea?
Author
Quote:Original post by Thetan
maybe its just my bias, but i like my solution the best
*** Source Snippet Removed ***
This is strictly illegal C++ since the same variable is modified twice in one statement. It may work in most of the compilers but illegal.
Author
I now tried to reverse bits of unsigned integer and wrote this but it crashes
#include <iostream>#include <algorithm>#include <sstream>#include <string>int main(){ unsigned int number=2; std::stringstream str; str<<number; std::reverse(str.str().begin(),str.str().end()); std::cout << str.str();return 0;}
Quote:Original post by smart_idiot
If you're assigning a value to your string, wouldn't that invalidate your iterators? It will probably work anyway since the string will probably reuse its old allocated buffer, but still, is that a good idea?
No, it's guaranteed to work. A temporary string is first built out of the given range, and is then assigned. See 21.3.5.3-10 page 393.
This is a typical interview question, used to see how well you understand arrays and pointers. Thetan's answer is what one generally looks for in this regard.
Probably because str.str() is a temporary and writing to it's begin() and end()... well I doubt it's a good idea.
but this still won't do what you want, it will make a string containing "2", and reverse that... You'll get "2" as a result.
Bit reversal is a cool thing to do, and in fact my favorite language does this rather well (it's 16 bits only, 32 bit would be done via splitting it into 16-bit components and reversing those):
This obviously reverses the bits of .3 and stores the result in .2.
Here is some code I have just written in my boredom, complete with outputting goodness and silly variable names (may not work for all numbers... works for the ones I tested [wink])
#include <iostream>#include <algorithm>#include <sstream>#include <string>int main(){ unsigned int number=2; std::stringstream str; str<<number; std::string s = str.str(); std::reverse(s.begin(),s.end()); std::cout << s;return 0;}but this still won't do what you want, it will make a string containing "2", and reverse that... You'll get "2" as a result.
Bit reversal is a cool thing to do, and in fact my favorite language does this rather well (it's 16 bits only, 32 bit would be done via splitting it into 16-bit components and reversing those):
DO .3 <- !3~#15'$!3~#240' DO .3 <- !3~#15'$!3~#240' DO .2 <- !3~#15'$!3~#240' This obviously reverses the bits of .3 and stores the result in .2.
Here is some code I have just written in my boredom, complete with outputting goodness and silly variable names (may not work for all numbers... works for the ones I tested [wink])
#include <iostream>#include <iomanip>using namespace std;//Kernighan's method (sanity check)int bits(unsigned int v){ unsigned int c; // c accumulates the total bits set in v for (c = 0; v; c++){ v &= v - 1; // clear the least significant bit set } return c;}int main(){ unsigned int x; cin >> x; cout << "was: " << x << endl; cout << "was: 0x" << hex << x << endl; int c = 8 * sizeof(unsigned int) - 1; //don't know how to get amount of bits without platform specific stuff... maybe log base 2 of int_max int b = 0; while(c > b){ cout << "c b: " << dec << c << " " << b << ", x: 0x" << hex << setfill('0') << setw(sizeof(unsigned int)*2) << x << dec << " -- bits = " << bits(x) << endl; x = x & ~(1 << c) //unset cth bit & ~(1 << b) //unset bth bit | ((x & (1 << b))?(1<<c):0) //set cth bit if bth bit was on | ((x & (1 << c))?(1<<b):0); //set bth bit if cth bit was on ++b; --c; } cout << "c b: " << dec << c << " " << b << ", x: 0x" << hex << setfill('0') << setw(sizeof(unsigned int)*2) << x << dec << " -- bits = " << bits(x) << endl; cout << x << "\n0x" << hex << x << endl;}Quote:
C++ all the way!
Quote:
How will you reverse a C-string without using any temporary variables?
Seeing as it looks like an interview question, they're obviously looking to see if he understands how pointer arithmetic and null terminated strings work. I've been asked this before, but the question was phrased as to rule out any use of library functions.
Something like this would be appropriate:
void reverse(char* ioString){ char* begin = ioString; unsigned int length = 0; //calculate the length of the string for(; ioString[length] != '\0'; ++length); char* end = begin + length; while( begin < end ) { --end; char temp = *begin; *begin = *end; *end = temp; ++begin; }}Then if they ask you to make your answer more generic, something like one of these:
template <class T>void array_reverse(T* begin, T* end){ while( begin < end ) { --end; T temp = *begin; *begin = *end; *end = temp; ++begin; }}template <class bidirectional_iter>void range_reverse(bidirectional_iter begin, bidirectional_iter end){ while ( begin != end ) { if( begin == --end ) break; std::iterator_traits<bidirectional_iter>::value_type temp = *begin; *begin = *end; *end = temp; ++begin; }}I assumed that by 'without using any temporary variables' they meant without using a secondary array.
Let's not forget tag dispatching! [razz]
Edit: Uh, I guess this was a little off-topic... [embarrass]
template <class RandomIterator>void reverse(RandomIterator* begin, RandomIterator* end, random_access_iterator_tag){ typedef typename std::iterator_traits<RandomIterator>::value_type T; while( begin < end ) { --end; T temp = *begin; *begin = *end; *end = temp; ++begin; }}template <class bidirectional_iter>void reverse(bidirectional_iter begin, bidirectional_iter end, bidirectional_iterator_tag){ while ( begin != end ) { if( begin == --end ) break; typename std::iterator_traits<bidirectional_iter>::value_type temp = *begin; *begin = *end; *end = temp; ++begin; }}//not really necessary, but it will complain in a less confusing manner, probablytemplate <class Iter, class IncompatibleIteratorCategory>void reverse(Iter, Iter, IncompatibleIteratorCategory){ struct dummy{}; typedef dummy::error IAmAfraidYourIteratorDoesNotMeetTheRequirementsForTheInPlaceReverseAlgorithmSir;}template<class Iterator>void reverse(Iterator begin, Iterator end){ reverse(begin, end, typename std::iterator_traits<Iterator>::iterator_category());}Edit: Uh, I guess this was a little off-topic... [embarrass]
TEUTON, we are rather happy when we can help someone.
However, your last questions smells more and more like homework questions: they are uncorrelated to each other (thus I don't think that they come from a book), and are very specific. You have to understand that coming here to have your answers prevents you from searching the answer by yourself, ans as a consequence you won't learn anything.
Moreover, if we answer homework questions on gamedev, it gives to the poster an unfair advantages in regard to his co-learners. This is comonly known as cheating, and that's why they are forbidden on gdnet.
I really suggest you to try to find the anwers by yourself. If you are stucked at a particular problem, and if this problem has really nothing to do with homework, then we'll be happy to help you.
@Nitage; you can use the ending char of the string (we know it is here, and we know that its value is \0) instead of a temporary char.
However, your last questions smells more and more like homework questions: they are uncorrelated to each other (thus I don't think that they come from a book), and are very specific. You have to understand that coming here to have your answers prevents you from searching the answer by yourself, ans as a consequence you won't learn anything.
Moreover, if we answer homework questions on gamedev, it gives to the poster an unfair advantages in regard to his co-learners. This is comonly known as cheating, and that's why they are forbidden on gdnet.
I really suggest you to try to find the anwers by yourself. If you are stucked at a particular problem, and if this problem has really nothing to do with homework, then we'll be happy to help you.
@Nitage; you can use the ending char of the string (we know it is here, and we know that its value is \0) instead of a temporary char.
Quote:
@Nitage; you can use the ending char of the string (we know it is here, and we know that its value is \0) instead of a temporary char.
Then I'd still need a variable to keep track of the length of the string.
There's two options here:
- Use XOR swapping to avoid the temp variable (still need a variable to track how much of the string has been swapped)
- Point out to the interviewer that you haven't used a temporary variable - you've used a local variable. If he asks further, tell him the only way to do this without using either a local var(or a function that uses one) would be to use a global or static var to track the array length, which would make the function unsafe for a multithreaded environment
I still think TEUTON's quesiton sound more like interview practice questions than homework.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
