What Technical Tests Do You Give Potential Hires?
I’m amazed at how many candidates I’ve interviewed cannot provide an elegant solution to the following test:
Write a routine, in your favorite language or even a mock language, without using an intrinsic function to solve the problem for you, to reverse the contents of a string. The routine should take an input of a string and output a string. For example, if the input is “hello” the output should be “olleh”.
I inform the candidate that it is a simple problem and invite them to talk through their logic as they write their solution on the whiteboard. I let them know it does not have to be syntactically correct; I am more interested in their approach.
It is enlightening, to say the least, to watch interviewees attack this problem. I’ve actually had so many people fail that I’ve been questioned if my “test” was too difficult. I understand there are abnormal pressures in play due to the setting but employees should ultimately perform decently under some pressure.
Silently I watch and listen to the candidate attempt to solve the problem. When the candidate is finished I usually ask, with good reason, are you certain this solution is correct? The response is often a “yes.” This usually gives us ample opportunity to talk about different strategies and try to understand why it was coded in a particular method.
I notice lots of issues that should not occur; for example, the candidate:
- does not understand the chosen language or it’s string libraries.
- has issues with zero-based arrays depending on chosen language.
- overly complicates the approach and never sits back to re-evaluate.
- can not come up with a solution.
- chooses a complicated approach involving math and gets the math wrong.
- uses too many variables.
- writes unnecessary code that essentially does nothing.
- can not validate the output of the routine they wrote correctly.
- writes more than ten lines of code to solve the problem.
- does not know how to swap values in to variables properly.
- … and many more.
I’d appreciate others offering this simple test and sharing your results with me and everyone else. I’d also like to know your thoughts the validity of this test and how you would let the results affect your view of the candidate.
Before reading on to see my solution, try it for yourself. Let me know how you do.
Here is my solution:
static string reverse(string s)
{
string r = "";
for (int i = s.Length - 1; i >= 0; i--)
r += s[i];
return r;
}
Can it be more simple? Let me know?
May 3rd, 2008 at 2:31 pm
The code is short coz you used C++ class. How about just using C? You may almost need 10 lines
May 15th, 2008 at 3:15 pm
In ruby,
“your_string”.reverse gives you the result.
And thing why C++ gives a Length function but not reverse. !!! And I am ok with using operator+ for reversing.
May 15th, 2008 at 3:15 pm
Sorry.. I am NOT ok with using operator+ for reversing.
May 28th, 2008 at 5:29 am
@Prabhakar:
If you really want a builtin use
reverse(str.begin(), str.end());
Btw there’s nothing wrong in using overloaded operators. Isn’t it easy to implement them?
@Rick:
I think the reversal can be done inplace and using only half of the string
unsigned int len=strlen(str);
for(int i=0;i<len/2;i++)
swap(str[i], str[len-i-1]);
May 28th, 2008 at 5:32 am
@Will: Even c uses the same number of lines.
@Rick: Since you’re an interviewer and I’m a “going to be an interviewee” and there’re many more like me, can we have more articles from interviewers perspective. Whatever articles I’ve read in the net have been written either by ex-interviewees or a wannabe interviewer or an interviewee himself.
June 9th, 2008 at 10:01 pm
I doubt C will have short program like this. Once can always argue about the power of a language in writing a code which is simple or complex.
For instance perl may be hell of a language to fiddle with strings while C may create issues.
Then there are programming techniques. Using global variables or static variable inside functions is sometime the deciding factor. Then again its all language dependent.
I believe more important than the code is the approach. Following is a code in C which should be shorter than the C++ code.
print_reverse(char * str)
{
if (str == ”)
return ;
print_reverse( str++);
printf (“%c”, str);
return;
}
Simple recursive approach.
An interesting problem which is made simple by language is finding all permutations of a given string (special case “Unique Permutations”). I believe perl makes life simpler.
If I ask you, just give me a function which takes a string and prints all its permutations the choice of using globals is gone.
Can a simple generic approach be given for this which doesn’t use internal language tools.?
September 2nd, 2008 at 7:00 am
Hello,
We are interested in placing some gps-related links/articles in your blog. Please respond.
November 9th, 2009 at 12:52 am
Hi Rick, it’s very cute task for the interview. You have interesting observations about it. Here is Java version for your collection. It was nice to meet you at SPS Philly. Mark.
private static String reverse(String string) {
String result = “”;
for(int i=0; i<string.length(); i++)
result = string.charAt(i) + result;
return result;
}
November 24th, 2009 at 2:32 pm
CAN WE DO IT WITHOUT USING ANOTHER STRING?
I mean, what if the input string is large say 1000 chars long than according to the solutions provided above you are using extra space(in bytes) of equal to length of the string.
@Rick
How can we please come out of the space time complexity tread-off?
@Mark
You are just copying the input string and returning it back!!
@Anuj
You are just printing it reversely!!
December 11th, 2009 at 10:16 am
@Rajendra – Mark actually has it correct. This pattern is also very common in recursive functions: depending on when you call yourself, it completely changes the output (start vs end of routine). So by saying “string.charAt(i) + result” reverses the string; if he would have put “result + string.charAt(i)” then he would have reproduced the string.
December 11th, 2009 at 10:20 am
@Rajendra – Jigsaw actually the in-place solution correct – and it works for both even and odd length strings.
December 14th, 2009 at 4:33 am
10 Lines code:
void rev(char *in)
{
char *en = in;
while(*en) en++;
en–;
while(in<en)
{
char temp=*en;
*en– = *in;
*in++=temp;
}
}
December 15th, 2009 at 5:09 pm
That works well but limits itself to the type of input – won’t work well on a static string.
March 30th, 2010 at 11:49 am
What about this?
char* mystrrev(char* s)
{
char* start = s;
char* left = s;
char c;
while (*s++);
s -= 2;
while (left < s)
{
c = *left;
*left++ = *s;
*s– = c;
}
return start;
}
April 9th, 2010 at 9:49 am
That is basically identical to Shyam’s posting with the same problem; it doesn’t work on static strings. As soon as you attempt to change the string, an exception is raised:
Program received signal EXC_BAD_ACCESS, Could not access memory.
Reason: KERN_PROTECTION_FAILURE at address: 0x0000000100000eda
June 11th, 2010 at 10:56 am
Using a fictional english based language …
Function RevStr(GetStr as String)
For i=1 to Length(GetStr)
NewStr = NewStr & Left(Right(GetStr,i),1)
Next i
Return(NewStr)
End Function
June 13th, 2010 at 9:00 pm
@David, creativity is key…languages are generally easily learned-the concepts are important.