Coding challenge - reverse a string

O(n log n), in Perl:

sub rstr {
        my $str = shift;
        my $l = length $str;
        if ($l == 1) {
                return $str;
        } else {
                my $m = int $l/2;
                return
                  rstr(substr $str, $m).
                  rstr(substr $str, 0, $m);
        }
}

Personally, I'd have typed "echo 'forward' | rev" and asked for the next question.

Not compiled or tested.

#include <stdio.h>
void reverse(const char *s)
{
  if(s && *s)
  {
    reverse(s+1);
    printf("%c",*s);
  }
}

 int main(int argc, char **argv)
{
  if(argc > 1)
  {
    reverse(argv[1];
    printf("\n");
  }
  return 0;
}

BTW that kind of candidates get on the sh*t list immediately. As interviewee I'd rather be asked about code than other stupid questions I have seen.

Any of those answers would have been accepted. Even this simple gcc-only solution would have been accepted:

#include <stdio.h>

int main(int a, void *b, void *c)
{
        typedef char *_;
        typedef _*__;
        typedef _(*___)[2];
        return
          a == 2 ?
            main(3, ((__)b)[1], 0) :
            a == 3 ?
              (*(_)b && main(3, (_)b + 1, &((_[2]){ (_)*(_)b, c })) ||
                main(4, c, 0)) :
              (b && (putchar((*(___)b)[0]), main(4, (*(___)b)[1], 0)) || 1);
}

You let them use a computer?

Many years back, I had an an interviewee who also refused a simple coding challenge. (It required mentally tracing the execution and optimizing it into as few lines of code as possible.) He instead offered to show me code samples (on disk).

Rule 1. Never refuse a coding challenge

Rule 2. Get your code peer reviewed before you include fugly code as a portfolio.

<?php echo strrev($_SYSTEM['argv'][1]);

echo $1 | rev

Regards, proclus http://www.gnu-darwin.org/

That problem doesn't seem very interesting as an interview question.. what were some of the other questions?

The other questions depend on how the interview went. Another guy had no qualms about answering it; since he also did free software, we didn't dwell too much on coding questions and just asked a few filler questions on *nix. Then, just for kicks, we asked (on the whiteboard) how he would simulate the game of Go, removing a group of stones from the board when it's completely surrounded (he knew how to solve flood fill). We're waiting for his answer.

#!/usr/bin/env python
import sys
print sys.argv[1].reverse()

hmmm... or maybe that's

sys.argv[1].reverse()
print sys.argv[1]

*shrugs* :)

Just had a look at the FizzBuzz questions and tried that on my son. He knows HTML/CSS reasonably well, but can't program.

I let him look at this piece, this is supposedly readable for people who can't program:

int a = 10; int b = 20; a = b;

But he couldn't figure this out as he reads the third line as "a equals b" and wondered what that would mean (stupid C syntax is certainly to blame here, I doubt he would have been confused by Eiffel/Pascal).

He wondered if a would equal b or b would equal a. So would the answer both be 10 or 20?

So clearly this example doesn't work if you don't know that '=' is not comparison but an assignment operator, and more over you need to know that right hand is assigned to left hand.

But I agree with the original poster that people applying for a programming job should be able to program. I wonder though how plumbers or carpenters would fare with a simple test. Isn't it the case that many people can't do their job?

Here's my Python version:

s = 'forward'
l = list(s)
l.reverse()
s = ''.join(l)


An interviewee would have to explain their code, so here goes:

First I create an instance of a mutable sequence (a 'list' object, very common in Python; it's like an array, but with possibly different datatypes). The list constructor automatically decomposes the given string into characters. I then use the list's built-in, optimized reversal method to invert the sequence in place (I'm told that internally, it just rearranges pointers). Then I use an empty string object's built-in concatenation method to join the list's members into a new string. I use the empty string because join() will be using it as a separator between each member. I don't bother with a print s because the challenge was to reverse a string, not print it!

lkcl's version wouldn't work because unlike in JavaScript, reverse() only reverses the sequence; it doesn't return it.

A long time ago, I was actually asked this string-reversal question during an interview, and I've asked it of someone else, but in both cases, the interview was basically over and we were just having fun, fully acknowledging how silly these questions can be...although there are definitely things to be learned from how someone responds to it, even when they're incapable of solving it right away.

I also once was called in to interview at a company that needed a mid-level programmer. I was confident when I walked in, but instead of asking me questions, talking to me or even acknowledging any of my skills, accomplishments, and code samples, an office assistant put me in an empty room and gave me a 12-page printed test consisting entirely of questions like these, and something like a 25-minute time limit. Some I could answer, many I couldn't. None of them had anything whatsoever to do with the actual code they were working on, or any code I've ever worked on, or any code any programmers senior to me had ever worked on. Was this how they treated all their future colleagues? In every way, it was a grossly typical dot-com, trying very, very hard to fit the mold. You name a cliché and they had it. The whole vibe was just weird and IMHO unprofessional. I started to answer the questions, or not answer them but explain how I'd deal with tasks beyond my current skill set, but the more I thought about it, the more it just felt like a bad fit. I walked out and didn't regret it one bit. The company was belly-up within a year.

So I almost sympathize with the candidate who turned up his nose at the question. But robocode is correct in that it doesn't bode well for the one who isn't even game for the challenge. But I have to say it's just as bad, maybe worse, when they're in over their head but are either too proud or too ashamed to ask for help. I've seen many-a 'creative' new hire fresh out of college agonize for hours over what were essentially wheel-reinvention problems, easy-to-understand solutions for which were a 3-word Google search or "hey, can you come look at this with me" away. I'd look at their code later and would find some colossally overengineered, untested, undocumented, unmaintainable spaghetti, and I'd wonder how they ever got hired. Yes, they could write code, and yes, it worked just well enough to close a bug report, but I really didn't want them on my team! They were too ready to be siloed, too accepting of everyone having their little fiefdom, not understanding that coding involves constant learning, teaching, and (gasp!) collaboration. They'd never be in a position of training someone else, because they never really learned anything new, except how to slowly crank out code that just barely works (which, admittedly, is all some companies want). So for non-senior programming positions, no matter which side of the interview I was on, I always focused less on quick-thinking/knowledge quizzes and more on demonstrations of general resourcefulness, being a quick study, knowing when to ask for help, asking intelligent questions and sharing their own knowledge, and being conscientiousness in making sure the job not only gets done, but gets done reasonably well, in a way that nobody's time or talent is wasted, now or in the future.

Back when I didn't know how exactly to do string reversal, my response was along these lines: "This sure sounds like the kind of thing that's been done before, and the exact solution is probably a quick web search away. So I'd probably just look it up. But if I don't find exactly what I'm looking for, I'd see if there's something kinda close that I could adapt. Or if I did find a whole bunch of possible solutions, I might make a little test suite and quickly see which one performs the best. If I couldn't figure anything out in a reasonable time, I'd ask for help. If I could tell right off the bat that it was well beyond my ability, but I knew we had a resident expert in, say, string manipulation, I might see if I could schedule time that day with that colleague to pair-program. If getting time-consuming, out-of-my-league tasks were an ongoing problem, I might notify the project manager that assigned this to me to let them know that maybe I need to work on something else, or get some formal training. If no one was available to help and nothing applicable could be found online, or if I could see that it was probably the kind of thing that wouldn't take too much time to learn, I'd likely start thumbing through a language reference to figure out what kinds of things I can do with strings and what built-in, optimized sequence reversal methods might exist." When asked "what if there were no such methods?", I replied, "OK, well, I guess I'd look into how the language would let me iterate through the characters in a string by position, either in reverse order, or using the forward-order position to address that far in from the end (e.g. getting the character at the length of the string minus the current position)."

It was not a complete or tangible solution, but it was obviously demonstrating some degree of competence, in stark contrast to the typical applicant who didn't know what questions to ask and didn't understand the explanations when the answers were given to them. Universally, they were the ones who didn't have any of their own code samples they could show and explain. I wouldn't have let them get that far, because I want to see someone's code before even talking to them. It wasn't always my choice as to who I had to interview, though.

(kindly ignore the fact that I forgot to use a command-line argument, and that the challenge actually did say to print the result; also I see lkcl did get it right... *sigh*)

I don't know whether it's worse that so many interview candidates can't do this, or the number of people replying here who either missed the requirement to reverse a command-line argument or that the challenge was to solve it "in a creative way"

Understanding requirements is a more useful skill than reversing a string!

perl -e 'print join("", reverse split //, shift @ARGV) . "\n"'

The problem was to write a C function that would do it, rather than a command-line program.

I don't have my solution online at the moment, but I expect I can dig it up eventually.

If I recall correctly, I kept two pointers, one to the beginning of the string, the other that found the end by searching for the NULL terminator. I then swapped characters, using a single-character temporary buffer. I then incremented the beginning pointer and decremented the end pointer. The process stopped when the begin pointer was larger than the end pointer.

If you try this yourself, you have to take into account whether the string has an odd or even number of characters, I think.

I didn't have a computer to work at - I had to write out the code on a whiteboard.

The hiring manager noted that my solution paid attention to efficiency, but neither of us spotted the fact that it had a bad bug.

I don't recall what it was, but I fixed the bug when I tried it out in a command-line test harness after I got home. I got the job, and presented the boss with the corrected code on my first day on the job.

But as for getting pissed off about having to solve problems... after I passed the bulk of the job interview, I was given the opportunity to take a written exam meant to determine how well I could follow instructions. The exam specified the assembly code for a fictitious computer, then had the assembly source listing for a program.

I was asked to write down what the output was. It was quite a complex program, with multiple nested loops. I had to work out the entire thing with just pencil and paper! I damn near went out of my tree.

The hiring manager never tells anyone if they get the answer right, but I must have come close enough because I got an offer.

you try to create an account 'hjclub#' where# can be any integer on advogato.org! I tried four times with no avail. It makes me wondering about dark energy and holy ghost.

you and I will never be the same.

I recently used the question on an interviewee. This guy yapped all about MVVM, features of the Visual Studio IDE and whatnot with our .NET guy for 30 minutes. When I got to him, my first question was this, only that he had to solve it on paper. He was allowed any language he wanted, and free to use anything in that language's standard library (e.g. some sort of reverse function if available).

He wrote a long and convoluted solution, saying it was in C#. This guy did not even know how to get the length of the string, let alone use any reverse function from the standard library. he later claimed this was pseudocode. At least his solution was correct as pseudocode (he was swapping characters inside a loop). So, just to verify he just wasn't writing the thing from memory, we gave him another simple problem (but not as common). He failed that horribly.

I know these questions are silly, and pointless if you think they are too easy for you or expect questions specifically about the project you'll be working on. But they are useful for the interviewer. They filter out the idiots who simply cannot write code, but have CVs loaded with meaningless degrees/certifications and they ensure that the candidate can solve a problem - not just write glue code for the API/framework you use for your latest CRUD. These problems force the candidate to think out a find the solution to a programming problem (I don't like puzzle questions (e.g. "n people in an island lie and m people tell the truth...")).