Quote:Original post by Sneftel
Pro-tip: If you're ever asked for a zero-temporary swap, for maximum points, explain to the interviewer exactly _why_ it's slower on modern processors.
Quote:Original post by ukdeveloper
This is actually bugging me, it doesn't seem right. Where did I go wrong?
#include <stdio.h>#include <stdlib.h>#include <string.h>/* Just because the standard library uses cryptic names for functions doesn't mean you should. On the other hand, there's not much sense elaborating that the char* you're passing in is a "String" in the variable name... */void reverse(char* original) { /* We reverse the string in place, by swapping around the chars within it. */ /* First, set up two pointers, to the first and last characters (not including the null terminator). There will be no need to do anything special with the terminator; we just leave it in place, because the reverse of a string is the same length as the original. */ char* begin = original; char* end = original + strlen(original) - 1; /* Notice that C allows you to initialize variables at declaration, even with complicated expressions. Don't declare something and then assign it on the next line, or "initialize" to a "zero" value and then assign on the next line. The point of *initial*ization is to initialize something with its *initial* value. :) */ /* Also notice the pointer arithmetic used to find the end pointer. */ /* Now we can iteratively swap pairs of characters: the first and last, second and second-last, etc. until we get to the middle. You should be able to convince yourself that this reverses the string. Notice that we don't iterate each pointer over the whole string, since that would re-reverse it. ;) So how do we find the middle? We could do some math, but the simple way is to note that both pointers "move" at the same rate, so 'begin' will reach or overtake 'end' exactly in the middle. So now we are ready: */ while (begin < end) { /* To swap, we assign the pointed-at characters to each other. But we can't just do one assignment and then the other, because the first assignment would mess up the second. Instead, we need to go through a temporary variable. Its type is 'char', because those are what we're swapping. */ char temp = *begin; *begin = *end; *end = temp; /* Move the pointers towards each other. */ begin++; end--; }}int main() { /* Again, initialize when you can. */ /* Note that we are not allowed to modify string literals, so we can't pass "hello" to reverse() directly. But we can do it if the string is copied into an array. In C, the following syntax implicitly does the trick: */ char[] source = "hello"; /* There is a string literal which is "baked" into the executable, but at runtime, the program will make an array on the stack and copy in the literal. */ printf("original: %s\n", source); reverse(source); printf("reversed: %s\n", source); /* We don't need to return 0 explicitly. But even then, don't put parentheses around return values: return is a keyword, not a function. (If it were a function, how would it return? */ return 0;}Quote:Original post by Zahlman
Here's a reasonable "answer key" for C. Note how few lines of actual code there are.
*** Source Snippet Removed ***
Quote:I'd also add that Visual Studio 2005 (what I used) barked like a pack of dogs when I didn't declare everything at the top of the function in advance of actually initialising and/or assigning it. It wouldn't compile if I tried to do inline initialisation like you did apart from setting the tempString pointer to null.
Apparently it's a requirement of C99 but maybe it's just the VS compiler being picky? I don't normally use C so I probably had the compiler options set up wrong.
Quote:Original post by loufoque
In C++ the more efficient and elegant way to solve that is to simply use a range adaptor that reverses the range.
make_reversed_range(your_range) and there you go, you get a range that you traverse in reverse order.
The old variable is kept unmodified, and it is O(1). An access to the first element will simply automatically be translated to an access to the last element.
A pipe syntax is nice too, your_range | adaptors::reversed.
All of this is doable with the range algorithms and adaptors available in Boost.
(For those who do not know about the range concepts, a range can be any container, a pair of iterators, or any other type that allows extracting of a begin and an end iterator)
By the way, note that your code is not const-correct, and that's bad.
Quote:NB: His code is const correct - the intention is to modify the string.
Quote:I don’t know if there are compilers with 100% C99 support. It isn’t a very successful standard.
Quote:Original post by loufoque
That's not over-engineering. That's using the right generic tool to do the job, so that the tool only needs to be implemented once and can be reused anywhere providing you use the right abstraction.
Quote:
If they're against boost, you can rewrite it yourself. It's fairly easy. But if they have the NIH syndrome, that's another reason not to work there anyway.
Quote:Original post by loufoque
That's one of the best solutions.
Quote:I can't think of any case where the eager solution would be a better choice however.
Quote:
I personally wouldn't want to work on a job that has so lame interviews anyway.
Quote:It's such a trivial problem, and they expect a really specific non-elegant solution that a sane person wouldn't ever use in real life.
