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/2001Just 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
-
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 -
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 linkThat'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
-
This kinda works too, without the extra char,but I don't think I'd want it production :)
char buf\[\] = "swap me you fool!!"; int len = strlen(buf)-1; int j=0; while(len > j) { \*(buf+j) -= \*(buf+len); \*(buf+len) += \*(buf+j); \*(buf+j) = \*(buf+len)-\*(buf+j); ++j; --len; }Tim Deveaux wrote:
This kinda works too, without the extra char,but I don't think I'd want it production
Now if you could rename buf to l1 and len to ll and j to l11, it would be much better!
Regards, Nish
Nish’s thoughts on MFC, C++/CLI and .NET (my blog)
My latest book : C++/CLI in Action / Amazon.com link -
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/2001The additional loop variable would land on the stack (if it doesn't remain in a secondary index register to begin with). When RAM is really tight - e.g. in micro controllers - stack is usually tuned to the worst case and so is usually less of an issue. But if you have to haggle for a local variable, you usually have to fine-tune your C code anyway.
We are a big screwed up dysfunctional psychotic happy family - some more screwed up, others more happy, but everybody's psychotic joint venture definition of CP
My first real C# project | Linkify!|FoldWithUs! | sighist -
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/2001John 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
-
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
