http://www.perlmonks.org?node_id=42040

I'm often called upon to interview people for various technical positions. Whether we're hiring specifically for engineers or not, candidates should be able to be able to problem-solve and think logically. In fact, some of the best answers I've gotten have come from self-professed non-programmers.

I generally ask an "algorithm" question that can get progressively harder as I change inputs on them. I don't make the candidate code in a particular language (in fact, I encourage them to use pseudo-code). I'm only really interested in how they come up with the algorithm. As an example, I usually ask the candidate to reverse individual words in a sentence, maintaining word order (e.g., "THIS IS A SENTENCE" produces "SIHT SI A ECNETNES"). If they nail that, I change the input to "This is a sentence." and ask them to keep the capitalization and punctuation positions the same (e.g. "Siht si a ecnetnes."). And so on... I thought of a couple last night which I'll try out in the next few interviews (I'll post them if there's enough interest, otherwise just /msg me if you're curious).

Does anyone have any other interesting questions along these lines? I'm getting kind of tired of asking the same couple of questions. :-)

Replies are listed 'Best First'.
Re: Algorithm questions...
by larsen (Parson) on Nov 17, 2000 at 02:55 UTC
    I suggest visiting this link.
    Lots of problems, even very difficult to solve. They don't require knowing a specifical programming language. They measure (well, they're supposed to do) problem-solving skill. Tell me what do you think about them. See you
      Ah yes, the ACM. The University Of Waterloo (my current school and Albannach's alma matter) placed in the top three for the past 3 years.
      • 3rd in 1998
      • 1st in 1999
      • 2nd in 2000, but the only team to complete all the questions


      I think I'm done bragging now.



      FouRPlaY
      Learning Perl or Going To Die Trying
        ...mmm
        Strange... if I remember Contest Rules, final standings base upon the number of problems solved by each team. How did your team take 2nd position? Would you mind contacting the judges? :)

        By the way, I partecipated three times to regional contest. I've really had a good time. I suggest this experience to every student :)

        They apparently changed Contest Rules while I was looking somewhere else :). Well, I don't like new Rules: I think ACM Contest should answer the question: "Who can solve as many problems as possible, given 5 hours, a computer and a Judging System?". This question in some cases is supposed to mimic another question "Who is the best programming team?". In my opinion, and in that sense, Waterloo University is 1999's Contest Winner ;)
(jeffa) Re: Algorithm questions...
by jeffa (Bishop) on Nov 17, 2000 at 00:22 UTC

      Thanks for the pointer. Unfortunately, a lot of those are rather Perl-specific. I prefer more "theoretical" questions, or toy examples that show that a candidate can think of several ways to do something.

      My favorite followup question to programming questions is "Great. What's a different way to do that?"

Re: Algorithm questions...
by arturo (Vicar) on Nov 17, 2000 at 01:01 UTC

    Well, if it's thinking logically you're after:

    • Sketch Goedel's first incompleteness theorem.
    • Discuss how the Euthyphro dilemma raises a problem for the Divine Command theory of ethics.

    But seriously, folks ... how about "lateral thinking" tests too? e.g. "how would you use a barometer to measure the height of a building?" (one ans: drop it and see how long before it hits, height = 1/2gt^2)

    Philosophy can be made out of anything. Or less -- Jerry A. Fodor

      Replying to my own node, lemme say that I pass my own test. I think.

      A sketch of Gödel's Theorem

      Philosophy can be made out of anything. Or less -- Jerry A. Fodor

      "how would you use a barometer to measure the height of a building?" (one ans: drop it and see how long before it hits, height = 1/2gt^2)

      The problem with this question is that you didn't mention to the candidate that they are also in posession of a watch. Of course, they can still attempt the elegant and accurate "one-mississippi, two-mississippi, three-mississippi" solution.

      Anyway, wouldn't a barometer be useful in mesuring a building's height, since there would be a relative pressure difference between top and bottom? I'm sure a formula could be worked out...

        The point of this question is to answer the question in any way possible without using the barometer for its obvious purpose.

        For instance by going to the owner of the building and offering to trade one barometer for the answer to how tall the building is...

Re: Algorithm questions...
by ivory (Pilgrim) on Nov 17, 2000 at 03:34 UTC
    From what I've seen, reversing strings, etc. is one of the most popular algorithmic questions in tech interviews. In fact, a few years ago when I was getting advice from more seasoned programmers regarding my very first tech interview, each one said that I should review how to reverse strings (or particular words in a string).

    The problem I have with it is, there are generally really easy ways to do it (in C++, you'd only need to be familiar with the string library). Plus, most begining programming books seem to give examples of how to do things like this. I guess it just seems to me that questions like this don't so much test a person's ability to think logically, but rather how well they've read their begining programming book, or whether they've had a reason to look through libraries, etc.

    ivory

Re: Algorithm questions...
by Elias (Pilgrim) on Nov 23, 2000 at 16:09 UTC

    I think you will really enjoy reading

    The crest of the peacock, non-european roots of mathematics
    by George Gheverghese Joseph
    Penguin Books 2000 (new edition), 455 pages.
    ISBN: 0-14-027778-1

    It has nice examples of very logical, but completely different ways of performing calculations (have you ever multiplied 2x2 with Mayan numerals?) which range from the blatantly obvious (the Aztec representation of 5) to the bizarre (the way the Babylonians handled irrational numbers).

    If your interviewee can handle these, it is likely that he or she can also manage complex algorithms.

      Five and a half years later: How did the Babylonians handle irrational numbers? Or should I just look at the book?
        Apparently not wittingly, but they dit work on approximations to the root of 2. Babylonians had the basic concept of pythagoras's theorem, but the greeks gave birth to irrational numbers as such. It was one of pythagoras's pupils - Hipposus - who first struggled with the root of 2 and came to the conclusion that some numbers where irrational. Faced with such irrationality from one of his pupils, Pythagoras ordered Hipposus to be drowned.

        (I can think of a student or two I may have done something similar to for lesser reasons ;).

        http://www.geocities.com/mathimoh/irrational.html
        http://members.aol.com/bbyars1/first.html
        http://www-groups.dcs.st-and.ac.uk/~history/HistTopics/Real_numbers_1.html
Re: Algorithm questions...
by AgentM (Curate) on Nov 17, 2000 at 00:23 UTC
    How about asking something along the lines of nested for loops- that always weeds out the wimps: ask for a simple linear search of a char in a string OR something else with string manip: capitalize every third letter or some such nonsense. One gag that always gets me is matrix manipulation: see how they react to that! :-O
    AgentM Systems nor Nasca Enterprises nor Bone::Easy nor Macperl is responsible for the comments made by AgentM. Remember, you can build any logical system with NOR.
Re: Algorithm questions...
by clemburg (Curate) on Nov 17, 2000 at 20:58 UTC

    Expert C Programming by Peter van der Linden has some questions you might like to ask in the appendix. Some of them are rather difficult. If you ever read The Art of Computer Programming you will have noted it contains a large number of exercises suitable for this kind of game.

    And, please always remember you could meet somebody asking you these questions in an interview.

    Christian Lemburg
    Brainbench MVP for Perl
    http://www.brainbench.com

    A reply falls below the community's threshold of quality. You may see it by logging in.
Re: Algorithm questions...
by Anonymous Monk on Sep 30, 2007 at 06:56 UTC
    check out www.acetheinterview.com. they have tons of questions and most of them have answers.