One of My Interview Questions Today
-
Write a function that reverses the contents of a null-terminated string in place. The only limitation is that you can't allocate a new string during any part of the process. This is what I gave them:
void ReverseString(char* str)
{
int len = strlen(str);
int delta = len / 2;
char pivot;
for (int i = 0; i < delta; i++)
{
pivot = str[i];
str[i] = str[len - i - 1];
str[len - i - 1] = pivot;
}
}I know, it's not all that impressive, but the interviewer told me I'm the only person he's seen do it that way (which seemed odd to me). BTW, I feel that both of the interviews I did today went well. I fully expect to get offers on from each company.
"Why don't you tie a kerosene-soaked rag around your ankles so the ants won't climb up and eat your candy ass..." - Dale Earnhardt, 1997
-----
"...the staggering layers of obscenity in your statement make it a work of art on so many levels." - Jason Jystad, 10/26/2001The STL way: ----------------------
// CommandLine.cpp : Defines the entry point for the console application.
//
#include "StdAfx.h"
#include <iostream>
#include <algorithm>
void main()
{
char reverse_me[] = "!desrever neeb evah I";
char *pEnd = reverse_me + sizeof(reverse_me)-1;
using namespace std;
reverse(reverse_me, pEnd);
cout << reverse_me << endl;
}My point is that perhaps it's a good idea to use standard STL algorithms if possible. A programmer should know how to roll their own but they should also know what's in their language's libraries. I probably would have given two versions: one like this to prove I know STL and a home-spun one to prove I'm not a nitwit.
Steve
-
Write a function that reverses the contents of a null-terminated string in place. The only limitation is that you can't allocate a new string during any part of the process. This is what I gave them:
void ReverseString(char* str)
{
int len = strlen(str);
int delta = len / 2;
char pivot;
for (int i = 0; i < delta; i++)
{
pivot = str[i];
str[i] = str[len - i - 1];
str[len - i - 1] = pivot;
}
}I know, it's not all that impressive, but the interviewer told me I'm the only person he's seen do it that way (which seemed odd to me). BTW, I feel that both of the interviews I did today went well. I fully expect to get offers on from each company.
"Why don't you tie a kerosene-soaked rag around your ankles so the ants won't climb up and eat your candy ass..." - Dale Earnhardt, 1997
-----
"...the staggering layers of obscenity in your statement make it a work of art on so many levels." - Jason Jystad, 10/26/2001I am surprised they even asked you such a kind of question. They should have gone to CP to see this was pointless... :) I also happened to face a surprised interviewer who hadn't seen the solution I was proposing before. Sounds like when your resume starts to be long enough they should think of a "never seen before" way of interviewing those hard-core coders... :) :) :) (Odd is the word)
-
dan neely wrote:
I can't think of any other way to do it without using a temp string.
This would be different flip( s, s + strlen( s ) - 1 ); flip( char *h, char *t ) { char temp; if( h >= t ) return; temp = *h; *h = *t; *t = temp; flip( h+1, t-1 ); }
Interesting use of recursion.
Roger Irrelevant "he's completely hatstand"
-
Write a function that reverses the contents of a null-terminated string in place. The only limitation is that you can't allocate a new string during any part of the process. This is what I gave them:
void ReverseString(char* str)
{
int len = strlen(str);
int delta = len / 2;
char pivot;
for (int i = 0; i < delta; i++)
{
pivot = str[i];
str[i] = str[len - i - 1];
str[len - i - 1] = pivot;
}
}I know, it's not all that impressive, but the interviewer told me I'm the only person he's seen do it that way (which seemed odd to me). BTW, I feel that both of the interviews I did today went well. I fully expect to get offers on from each company.
"Why don't you tie a kerosene-soaked rag around your ankles so the ants won't climb up and eat your candy ass..." - Dale Earnhardt, 1997
-----
"...the staggering layers of obscenity in your statement make it a work of art on so many levels." - Jason Jystad, 10/26/2001It's interesting that you swapped characters around; however VS2005 was crashing on me when I was walking through it with the debugger. Unhandled exception at 0x00412e00 in TestConsole4.exe: 0xC0000005: Access violation writing location 0x004156a4. It seems like the pointer is expected to be declared in a different manner with VS2005.
Jon
-
John Simmons / outlaw programmer wrote:
Memory must have been an issue. Otherwise, the requirement would not have been stated the way it was.
Maybe they just wanted to have you think about a solution from a different perspective? Not sure why they would have a seasoned programmer like yourself write code example to prove yourself.
"I've seen more information on a frickin' sticky note!" - Dave Kreskowiak
Actually, it's not so much a "can-you-do-it" question as much as it is a "how-would-you-approach-it" question.
"Why don't you tie a kerosene-soaked rag around your ankles so the ants won't climb up and eat your candy ass..." - Dale Earnhardt, 1997
-----
"...the staggering layers of obscenity in your statement make it a work of art on so many levels." - Jason Jystad, 10/26/2001 -
Did they also say it was acceptable for your code to crash on invalid input?
Todd Smith
They just wanted the string reversed. They didn't ask for validation code. :)
"Why don't you tie a kerosene-soaked rag around your ankles so the ants won't climb up and eat your candy ass..." - Dale Earnhardt, 1997
-----
"...the staggering layers of obscenity in your statement make it a work of art on so many levels." - Jason Jystad, 10/26/2001 -
John Simmons / outlaw programmer wrote:
Write a function that reverses the contents of a null-terminated string in place. The only limitation is that you can't allocate a new string during any part of the process.
You apply for C jobs? :~ :confused:
Ummmm, I apply for any job I'm qualified for (which would include C), but in this case (and curiously enough) it's not even a job that requires C++.
"Why don't you tie a kerosene-soaked rag around your ankles so the ants won't climb up and eat your candy ass..." - Dale Earnhardt, 1997
-----
"...the staggering layers of obscenity in your statement make it a work of art on so many levels." - Jason Jystad, 10/26/2001 -
Just don't pass that code a DBCS or UTF-8 string!
--Mike-- Visual C++ MVP :cool: LINKS~! Ericahist | PimpFish | CP SearchBar v3.0 | C++ Forum FAQ
Ya gotta look at it in context - it's a C question. C doesn't know unicode.
"Why don't you tie a kerosene-soaked rag around your ankles so the ants won't climb up and eat your candy ass..." - Dale Earnhardt, 1997
-----
"...the staggering layers of obscenity in your statement make it a work of art on so many levels." - Jason Jystad, 10/26/2001 -
It's interesting that you swapped characters around; however VS2005 was crashing on me when I was walking through it with the debugger. Unhandled exception at 0x00412e00 in TestConsole4.exe: 0xC0000005: Access violation writing location 0x004156a4. It seems like the pointer is expected to be declared in a different manner with VS2005.
Jon
Usage:
char\* sTemp = new char\[6\]; strcpy(sTemp, "string"); reverse(sTemp); delete\[\] sTemp;"Why don't you tie a kerosene-soaked rag around your ankles so the ants won't climb up and eat your candy ass..." - Dale Earnhardt, 1997
-----
"...the staggering layers of obscenity in your statement make it a work of art on so many levels." - Jason Jystad, 10/26/2001 -
That's the way i've usually seen it done, i use something like:
bool strrev_ip( char *s )
{
if( !s ) return(false);char *e = s + strlen(s)-1;
for( ; s < e; s++, e-- ) {
*s ^= *e;
*e ^= *s;
*s ^= *e;
}return(true);
}[EDIT] ... ummm, post order is screwed up, this was in reply to Nish ... and Dan didn't reply to this [/EDIT]
...cmk Save the whales - collect the whole set
cmk wrote:
That's the way i've usually seen it done, i use something like: bool strrev_ip( char *s ){ if( !s ) return(false); char *e = s + strlen(s)-1; for( ; s < e; s++, e-- ) { *s ^= *e; *e ^= *s; *s ^= *e; } return(true);}
Nice touch adding the xor way of swapping variables...that's usually a separate interview question in its own right! Also, precludes using a temp variable, which could come across as a loophole (ie; instead of allocating another string)...Hmm can't imagine how they would do it vastly differently than whats outlined in the original posting, all seem to be some variation of swapping chars till the pointers cross over
-
John Simmons / outlaw programmer wrote:
but the interviewer told me I'm the only person he's seen do it that way (which seemed odd to me).
I believe it's more common to have a char* to firstPos and a char* to lastPost, and then increment firstPos while decrementing lastPos. You basically did the same except that you avoided pointers and used the array index directly. Depending on his attitude he could take that in a good way (you know how to simplify algorithms and avoid unwanted pointer complexity) but he could also take it in a bad way (as in you were nervous about using pointers directly). Good luck anyhow. :)
Regards, Nish
Nish’s thoughts on MFC, C++/CLI and .NET (my blog)
My latest book : C++/CLI in Action / Amazon.com linkThe compiler will quite likely turn the array indexing into pointer arithmetic operations anyway. This is quite a simple optimization. I prefer to write array-indexing syntax as I find it less confusing.
Stability. What an interesting concept. -- Chris Maunder
-
Write a function that reverses the contents of a null-terminated string in place. The only limitation is that you can't allocate a new string during any part of the process. This is what I gave them:
void ReverseString(char* str)
{
int len = strlen(str);
int delta = len / 2;
char pivot;
for (int i = 0; i < delta; i++)
{
pivot = str[i];
str[i] = str[len - i - 1];
str[len - i - 1] = pivot;
}
}I know, it's not all that impressive, but the interviewer told me I'm the only person he's seen do it that way (which seemed odd to me). BTW, I feel that both of the interviews I did today went well. I fully expect to get offers on from each company.
"Why don't you tie a kerosene-soaked rag around your ankles so the ants won't climb up and eat your candy ass..." - Dale Earnhardt, 1997
-----
"...the staggering layers of obscenity in your statement make it a work of art on so many levels." - Jason Jystad, 10/26/2001 -
Write a function that reverses the contents of a null-terminated string in place. The only limitation is that you can't allocate a new string during any part of the process. This is what I gave them:
void ReverseString(char* str)
{
int len = strlen(str);
int delta = len / 2;
char pivot;
for (int i = 0; i < delta; i++)
{
pivot = str[i];
str[i] = str[len - i - 1];
str[len - i - 1] = pivot;
}
}I know, it's not all that impressive, but the interviewer told me I'm the only person he's seen do it that way (which seemed odd to me). BTW, I feel that both of the interviews I did today went well. I fully expect to get offers on from each company.
"Why don't you tie a kerosene-soaked rag around your ankles so the ants won't climb up and eat your candy ass..." - Dale Earnhardt, 1997
-----
"...the staggering layers of obscenity in your statement make it a work of art on so many levels." - Jason Jystad, 10/26/2001 -
On a long string, you will exhaust available stack space , not to mention the time overhead involved in repeatedly calling the function. Therefore, a recursive function is not an appropriate answer. -- modified at 11:08 Tuesday 24th July, 2007
"Why don't you tie a kerosene-soaked rag around your ankles so the ants won't climb up and eat your candy ass..." - Dale Earnhardt, 1997
-----
"...the staggering layers of obscenity in your statement make it a work of art on so many levels." - Jason Jystad, 10/26/2001 -
recursive, how WTFworthy. :rolleyes:
-- You have to explain to them [VB coders] what you mean by "typed". their first response is likely to be something like, "Of course my code is typed. Do you think i magically project it onto the screen with the power of my mind?" --- John Simmons / outlaw programmer
-
Actually, it's not so much a "can-you-do-it" question as much as it is a "how-would-you-approach-it" question.
"Why don't you tie a kerosene-soaked rag around your ankles so the ants won't climb up and eat your candy ass..." - Dale Earnhardt, 1997
-----
"...the staggering layers of obscenity in your statement make it a work of art on so many levels." - Jason Jystad, 10/26/2001I had to look up null terminated. I suck.. :( Seriously, I've been programming for 8 years (not including the 10,20 basic way back in the day), yet every time I see something like this I wonder what the hell I've really learned in all that time. It's discouraging.
Michael J. Collins Web Application Programmer
-
Actually, it's not so much a "can-you-do-it" question as much as it is a "how-would-you-approach-it" question.
"Why don't you tie a kerosene-soaked rag around your ankles so the ants won't climb up and eat your candy ass..." - Dale Earnhardt, 1997
-----
"...the staggering layers of obscenity in your statement make it a work of art on so many levels." - Jason Jystad, 10/26/2001John Simmons / outlaw programmer wrote:
it is a "how-would-you-approach-it" question
That would make more sense. To see what kind of thinker one is.
"The clue train passed his station without stopping." - John Simmons / outlaw programmer
-
I had to look up null terminated. I suck.. :( Seriously, I've been programming for 8 years (not including the 10,20 basic way back in the day), yet every time I see something like this I wonder what the hell I've really learned in all that time. It's discouraging.
Michael J. Collins Web Application Programmer
Michael, Back in ancient times (ca.1966) my friend Richard Pratt and I had a little contest, coding a binary search in IBM 360 assembler. At the end we were fighting to remove individual cycles from the loop. When we agreed he had won, reaching the irreducible minimum loop time, Dick Giering showed up with a faster method in hand. His algorithm wasted "lots" of time at the start building a halving table. Once he had the table built, his search ran almost twice as fast as our best effort, because he didn't have a divide instruction inside the loop. Don't feel bad. As the saying goes, "Ve get too soon oldt, und too late schmart." JimT
-
Memory must have been an issue. Otherwise, the requirement would not have been stated the way it was. I could have knocked two more cycles off the cpu load, but it would have cost them 4 more bytes of memory.
"Why don't you tie a kerosene-soaked rag around your ankles so the ants won't climb up and eat your candy ass..." - Dale Earnhardt, 1997
-----
"...the staggering layers of obscenity in your statement make it a work of art on so many levels." - Jason Jystad, 10/26/2001 -
Write a function that reverses the contents of a null-terminated string in place. The only limitation is that you can't allocate a new string during any part of the process. This is what I gave them:
void ReverseString(char* str)
{
int len = strlen(str);
int delta = len / 2;
char pivot;
for (int i = 0; i < delta; i++)
{
pivot = str[i];
str[i] = str[len - i - 1];
str[len - i - 1] = pivot;
}
}I know, it's not all that impressive, but the interviewer told me I'm the only person he's seen do it that way (which seemed odd to me). BTW, I feel that both of the interviews I did today went well. I fully expect to get offers on from each company.
"Why don't you tie a kerosene-soaked rag around your ankles so the ants won't climb up and eat your candy ass..." - Dale Earnhardt, 1997
-----
"...the staggering layers of obscenity in your statement make it a work of art on so many levels." - Jason Jystad, 10/26/2001I don't have a c++ compiler on hand to prove it, but I think this code does the trick for single-byte character sets: void ReverseString(char* str) { char* end = strrchr(str, 0); while(str < --end) { str ^= end; end ^= str; str++ ^= end--; } }
