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/2001John 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 link -
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/2001John Simmons / outlaw programmer wrote:
(which seemed odd to me).
likewise. Unless he was counting Nish's implementation as sufficiently different (I wouldn't), I can't think of any other way to do it without using a temp string.
-- 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
-
John Simmons / outlaw programmer wrote:
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).
I know I tell my team there are a dozen ways to do any one operation, it is thinking that determines the best way for a given criteria.... but there is another way to do that without allocating another string? I would have done it exactly the same way. Though maybe with an extra variable 'j': for (int i = 0, j=len-1; i < delta; i++,j--) it is slightly more storage, but fewer math operations, a tighter loop for faster processing.
_________________________ Asu no koto o ieba, tenjo de nezumi ga warau. Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
Mine is easier to maintain.
"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 -
Mine is easier to maintain.
"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:
Mine is easier to maintain
depends on your point of view.... it has fewer variables, but with embedded systems sometimes you need those clock cycles back. If you don't need them, you do it your way, if you are desperate for every clock cycle, but memory is not an issue, you do it another way. The right tool for the right job. Even when it is the same job, different environment. :)
_________________________ Asu no koto o ieba, tenjo de nezumi ga warau. Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
-
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/2001Congrats, that's odd...that's how I would have done it, the only other way I can think of is with an extra variable. But that way is better because they probably only care about maintainability.
public static void DoSomething() { DoSomethingElse(); } public static void DoSomethingElse() { Dosomething(); }
-
John Simmons / outlaw programmer wrote:
Mine is easier to maintain
depends on your point of view.... it has fewer variables, but with embedded systems sometimes you need those clock cycles back. If you don't need them, you do it your way, if you are desperate for every clock cycle, but memory is not an issue, you do it another way. The right tool for the right job. Even when it is the same job, different environment. :)
_________________________ Asu no koto o ieba, tenjo de nezumi ga warau. Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
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/2001Did they also say it was acceptable for your code to crash on invalid input?
Todd Smith
-
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 wouldn't store the "delta":
for ( i = len / 2 - 1 ; i >= 0 ; i-- )-- modified at 17:03 Monday 23rd July, 2007 orint i = len / 2 ; while ( i-- ) ... -
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/2001This 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; } -
Did they also say it was acceptable for your code to crash on invalid input?
Todd Smith
They should have asked for that in the spec! :)
Mark Salsbery Microsoft MVP - Visual C++ :java:
-
John Simmons / outlaw programmer wrote:
(which seemed odd to me).
likewise. Unless he was counting Nish's implementation as sufficiently different (I wouldn't), I can't think of any other way to do it without using a temp string.
-- 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
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 ); }
-
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 ); }
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
-
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/2001John 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:
-
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
