Beefy Boxes and Bandwidth Generously Provided by pair Networks
Do you know where your variables are?
 
PerlMonks  

(OT) Interview questions -- your response?

by Ovid (Cardinal)
on Sep 03, 2002 at 18:16 UTC ( #194839=perlmeditation: print w/ replies, xml ) Need Help??

Time for another "interview question" post. We're in the process of hiring some programmers. Naturally, we go through the typical interview process and as them some questions to assess the Perl knowledge, but we're also interested in their programming knowledge. I've been somewhat disappointed with some of their answers, so I'm curious as to how Monks would respond to these questions and how you would change them. These questions are deliberately language agnostic as we're focusing on aptitude here.


1. The following code snippet works, but has been identified as a significant performance problem in a production program.

a. Why is it a problem?
b. What would you do to fix it?

foreach a_item in a_array foreach b_item in b_array if a_item equals b_item put a_item in c_array end if end for end for

The order of elements is not important.

2. Write a function (language of your choice) to do an in-place reversal of array elements. For example:

array = ( 'foo', 'bar', 'baz', 'cheeze whiz' )

Becomes:

array = ( 'cheeze whiz', 'baz', 'bar', 'foo' )

If the "language of your choice" has a built-in method for doing array reversal, disregard it.

3. Briefly sketch out how you would implement a program/system to handle multiple requests (perhaps from Web forms), query a database based upon the request and display the results. There are multiple request sources and multiple display formats.

Code is not required for this one. We're looking for how you would organize this.


I'd give a list of what we're looking for on these, but that would be giving you hints. Many of the programmers that we have interviewed have plenty of experience, but fail miserably when faced with the above questions, though they seem fair to me.

Cheers,
Ovid

Join the Perlmonks Setiathome Group or just click on the the link and check out our stats.

Comment on (OT) Interview questions -- your response?
Select or Download Code
•SPOILERS Re: (OT) Interview questions -- your response?
by merlyn (Sage) on Sep 03, 2002 at 18:43 UTC
    SPOILERS AHEAD

    1a The runtime scales with the product of the sizes of the two arrays.
    1b You'll want some sort of more linear indexing function on one of the hashes to save time. In Perl, it'd look a bit like this:
    my %b_hash = map { $_ => 1 } @b_array; my @new_array = grep $b_hash{$_}, @a_array;
    2
    my @array = ( 'foo', 'bar', 'baz', 'cheeze whiz' ); for (my $left = 0, my $right = $#array; $left < $right; $left++, $righ +t--) { @array[$left, $right] = @array[$right, $left]; }
    3 I have a column on that.

    -- Randal L. Schwartz, Perl hacker

      merlyn your number two is _way_ too complex
      @array[$_,-$_-1]=@array[-$_-1,$_] for 0..@array/2;
      UPDATED
      As has been pointed out the above is incorrect.
      @array[$_,-$_-1]=@array[-$_-1,$_] for 0..$#array/2;
      Is what it should have been

      I must have been halucinating when I tested it.

      But frankly I stand by my too complex comment regardless.

      Yves / DeMerphq
      ---
      Software Engineering is Programming when you can't. -- E. W. Dijkstra (RIP)

        Why not go for truly ugly? ;-)
        @array[0..$#array] = @array[map{-$_}(1..@array)];

        You have moved into a dark place.
        It is pitch black. You are likely to be eaten by a grue.

        Fencepost error. I think you mean:

        @array[$_,-$_-1]=@array[-$_-1,$_] for 0..$#array/2;

        The middle pair was swapped twice to no effect for even sized arrays, the middle element swapped with itself for odd.

        After Compline,
        Zaxo

        I'm not sure if treating an interview question like a golf challenge is such a good idea. Well... this guy was good, but this other guy did it in just 14 characters. Not gonna happen. ;-)
        ()-()
         \"/
          `                                                     
        
        I like merlyn's answer because it's readable, even by people who are not hardcore perl programmers. It's not tricky, but it doesn't need to be.
        In Perl6, will ~= between two lists give their intersection in list context?
      So how about solving the array union question without hashes? I'd sort the arrays and use something like:
      while( @sort_a and @sort_b ){ if( $sort_a[0] < $sort_b[0]){ shift(@sort_a); } elsif( $sort_a[0] > $sort_b[0]{ shift(@sort_b); } else{ push @new_array, $sort_a[0]; shift(@sort_a); shift(@sort_b); } }
      This will handle duplicate entries in the arrays differently than the hash solution.
      The runtime scales with the product of the sizes of the two arrays.
      So? ;-) No matter what method you choose, worst case, the runtime will be at least proportional to the product of the sizes of the two array, if only because that can be the output size. See below.
      my %b_hash = map { $_ => 1 } @b_array; my @new_array = grep $b_hash{$_}, @a_array;
      You (and I think all of the others who answered this question) just failed question 1b. This will only work if the elements of @b_array are unique - but that's not given, and you shouldn't make that assumption; at least not without mentioning it.

      I'd do something like:

      my %b_hash; $b_hash {$_} ++ for @b_array; my @c_array = map {($_) x ($b_hash {$_} || 0)} @a_array;
      which has a running time of O (sizeof (input) + sizeof (output)), which is asymptotical optimal.

      Abigail

Re: (OT) Interview questions -- your response?
by demerphq (Chancellor) on Sep 03, 2002 at 18:52 UTC
    I wonder if your results arent just the effect of interview jitters. Except for the last one which is IMO so vague as to deserve a quite vague response (a request parser, a db interface layer, a templating system, and lots of hand waving).

    The first seems like it should be answerable by anybody who has finished first year CS if not just some basic math skills, the second is so easy is that I triple checked my solution thinking that I must of missed some weird case. (apparently I didnt)

    Hmm, are there any openings?

    :-)

    Yves / DeMerphq
    ---
    Software Engineering is Programming when you can't. -- E. W. Dijkstra (RIP)

      You're right that number is three is vague. That's deliberate. Candidates are allowed to ask questions for clarification and, if they haven't worked in a given environment (Web development, for example), then the vagueness allows them to not be tied to domain specific issues. Your's is exactly the sort of answer I was looking for: does the applicant know enough to break things out into different tiers?

      And while your answer for number two (in response to merlyn) was correct, it's less easy to immediately understand. I prefer very clear code, though you definitely would have passed the test :)

      Cheers,
      Ovid

      Join the Perlmonks Setiathome Group or just click on the the link and check out our stats.

Re: (OT) Interview questions -- your response?
by dws (Chancellor) on Sep 03, 2002 at 19:22 UTC
    Time for another "interview question" post ... we're also interested in their programming knowledge. I've been somewhat disappointed with some of their answers, ...

    If you're trying to extract a lot of info out of relatively short interview, consider the approach I sketch out in On Interviewing Candidates. It's a technique that dives in from a higher level, exposes thinking, and is less sensitive to false negatives if a candidate doesn't happen to see the trick in a trick questions. It also gets you to a point where you can say "now, show me code".

    The risk of relying soley on programming problems is that you'll get false negatives if you catch someone on a bad day.

Re: (OT) Interview questions -- your response?
by Anonymous Monk on Sep 03, 2002 at 21:28 UTC
    My full answers would be the following:
    1 a) nested linear scans b) use a hash 2) @array[0..$#array] = @array[reverse 0..$#array]; That's *not* a built-in array-reversal method. 3) Modularize into the three primary layers: requests, db queries, output templates.

    Questions?

      @array[0..$#array] = @array[reverse 0..$#array]; That's *not* a built-in array-reversal method.
      Nor it it an "in-place" reversing method, failing the requirements of the question. You've made an entire copy of the array in a different part of memory.

      -- Randal L. Schwartz, Perl hacker

        True enough, and not an unexpected claim. Though one *could* argue that:
        @array[$left,$right] = @array[$right,$left];

        Isn't any more "in-place", as it is the same thing when the array is only two elements. And I didn't see where using a constant amount of additional memory was part of the requirement :-)

      2) @array[0..$#array] = @array[reverse 0..$#array]; That's *not* a built-in array-reversal method.

      Well, technically, doesn't 0..$#array create an (anonymous) array, which reverse then reverses? :)

      bbfu
      Black flowers blossum
      Fearless on my breath
      Teardrops on the fire
      Fearless on my breath

        Well, technically, doesn't 0..$#array create an (anonymous) array, which reverse then reverses? :)
        Technically no. The 0..$#array just creates a list from zero to the last index, reverse 0..$#array is the list of indices reversed. So we are not reversing the array, just creating a slice with with reversed indices and assigning that slice to the a slice with all the indices in order. I imagine a built-in array reversal would be more like Ruby's array.reverse! method.
Re: (OT) Interview questions -- your response?
by John M. Dlugosz (Monsignor) on Sep 03, 2002 at 21:47 UTC
    Before reading any other replies,

    1 a) it's an Order of N-squared algorithm, so it scales poorly.
    1 b) Change the approach to N*log(N), which I think is the best possible. A couple sorts and then a linear pass (merge-like logic) would do.

    2) $last=$#array;  @array[0..$last] @array[reverse $last..0]; does that still count as cheating because reverse can also be used to reverse an array? for (int loop= 0;  loop < array.elcount()/2;  ++loop)    swap (array[loop], array[-loop]); for something I might actually use in C++. A zillion fun ways to do it, though, and a few jokes.

    3) Too vague. Can I assume the existance of a general multi-threaded server for the database? In that case, I just need to abstract the multiple input/output formats. Did you want to know how to write a multithreaded server? If so, what OS, etc.?

    —John

Re: (OT) Interview questions -- your response?
by Anonymous Monk on Sep 03, 2002 at 23:29 UTC
    The questions look fine for people who claim to be competent programmers. And would you prefer to be disappointed in people in the interview or after you have hired them?
Re: (OT) Interview questions -- your response?
by FoxtrotUniform (Prior) on Sep 03, 2002 at 23:34 UTC

    My last place of work had a rather long case study, followed by a fairly short interview (which didn't focus as much on programming capability). It seemed to work well; I never had a co-worker, hired under this system, who wasn't up to par. They tried to saddle the candidate with an unfamiliar language and several straightforward problems, but letting them use the language of their choice and making the problems a bit harder might work just as well.

    --
    F o x t r o t U n i f o r m
    Found a typo in this node? /msg me
    The hell with paco, vote for Erudil!

Re: (OT) Interview questions -- your response?
by rir (Vicar) on Sep 04, 2002 at 01:06 UTC
    I'm new here.

    I agree these are fair questions. Answers follow.

    1. a.
    The problem is that there are roughly a_array_size * b_array_size operations happening here. Bad big o.

    1. b.
    I'd sort the one array, running through the
    other as an unordered list and using a binary search
    on the first.

    2.

    sub reverse_array { my $ar = shift; my ( $head, $tail) = ( 0, $#$ar); while ( $head < $tail) { ($ar->[$head], $ar->[$tail]) = ( $ar->[$tail],$ar->[$head]); $head++; $tail--; } }

    3.
    This one is pretty open ended.
    It is not clear whether or not the requestors are
    under our authorship. Assuming not.
    The requestor initially generates some request.
    This is put to a connector which will attempt to identify
    the input "language", choose a translator, identify the
    default or requested output style, choose
    a formatter, and create a unique dialog with these
    components.

    There will be translators defined for each input "language",
    formatters for each output style. The translators
    will convert requests to one "language". The dialogs
    will contain a hopefully much simplified dialog, a backend,
    to talk to the actual datasources.

    This is generalized to ease expansion beyond the initial
    request. Early implementations should stub out some of
    these components.

Re: (OT) Interview questions -- your response?
by andye (Curate) on Sep 04, 2002 at 01:40 UTC
    Think about what *else* you're doing with them, too.

    'A UK Software Firm' (*cough*, Data Connection, *cough*), puts candidates through about 5 hours of written exams to fry their brain directly before they get to the programming interview.

    Maybe it might be wise (and, indeed, even-handed!) to look at your own interview skills, if you're not getting the results you expect from what appear to be able candidates. I've been interviewed by programmers who - and I can tell by your posts that you're *not* one of these - had all the interviewing skills of a blind molerat. Interviewing really well is so much more difficult than it looks.

    andye.

      ...that's 5 hours of written exams, specifically designed to take longer than 5 hours to complete, and also immediately after a 2 hour tube ride and being forced to miss lunch (there ain't no buffet car on the tube). And then just to demoralise you completely before the final rejection, the post-programming exercise is adjudicated by a bloke that has poor eyesight and can only read a program one character at a time - and can still spot all of the algorithmic errors. Not that I sat the test or anything...

      rdfield

Re: (OT) Interview questions -- your response?
by Aristotle (Chancellor) on Sep 04, 2002 at 03:31 UTC
    1a) Essentially O(n2) runtime. (O(n*m) to be precise.)
    1b) Either use some sort of hashing function or sort the b_array and use binary search to cut down on the cost of looking up an element. In Perl, a hash is the natural approach.
    my %b_value; @b_value{@b_array}=(); my @c_array = grep exists $b_value{$_}, @a_array;
    2)
    my $i; while($i < $#array/2) { my $copy = $array[$i]; $array[$i] = $array[-$i]; $array[-$i] = $copy; ++$i; }
    3) It requires a database capable of handling concurrent requests. They need to be transformed into some common query lanague, probably SQL. Results will be churned through a templating system depending on the desired result format.


    I think the questions are more than fair; in fact, they're close to trivial. I wouldn't want to employ anyone who fails on these. I remember reading about an interview question Michael Abrash uses:
    Implement in-order walking of a binary tree. Do not use recursion.

    Hardly surprising, though saddening, that as he noted, failure rates on this one are pretty spectacular.

    Update: see ++Abigail-II's comment on excercise 1b.

    Makeshifts last the longest.

      Sorry pal, but the answers have been given already repeatedly ... comments on the actual questions would still be valid at this point, but trying to sound like you have intelligent answers now is simply sad.

        You missed the point. I did note that I find these questions close to trivial; answering them was to lend weight to that claim, and just so you know I'm not copypasting, the answers all do contain points that hadn't previously appeared.

        The bottom line is it would be sad if anyone thought they'd sound intelligent by answering these questions correctly. I certainly don't. Maybe you didn't notice the Abrash interview question I mentioned?

        Makeshifts last the longest.

Re: (OT) Interview questions -- your response?
by tadman (Prior) on Sep 04, 2002 at 07:32 UTC
    Here's my take on Q1, which isn't entirely original, but is self-contained:
    my @c = do { my %tmp = map { $_ => 1 } @a; grep {$tmp{$_}} @b };
    Here's my take on Q2 which ended up the same as others:
    for (1..@foo/2) { @foo[$_-1,-$_] = @foo[-$_,$_-1]; }
    The first thing that came to mind was:
    @foo = map { pop(@foo) } 1..@foo;
    But that's not precisely an in-place version, even though you could argue that the temporary "array" only holds things that have been removed from @foo.
      Man! the magical disappearing then reappearing section of a post! Please try to remember that others are reading and composing and when you just rewrite your history entirely within a few minutes what the fuck are we supposed to do? Are you going to actually participate in a "conversation" or not! Please give us a fricking break!
        Big words from an anonymous monk....
        English is a language with a lot of words. I am sure you can find appropriate ones to express your concerns without profanities.

        Makeshifts last the longest.

      And again it is changed no less than two times since my last post. Once to acknowledge the actual thrust of the change, and then again to remove that acknowledgement and post something entirely different. Please tadman, if you are going to edit things then edit them with an eye to history and don't leave subsequent posts just hanging (no matter how good it might feel at the time).
        After sitting down and reflecting on my rather scathingly sarcastic reply, I decided, that in the interest of civility, I would retract my words. Obviously, they have been read, and so, are no longer required.

        This tactic of switching to Anonymous Monk just to fire off some heated complaint is really quite irritating. If you have any specific comments that can be expressed in a civil manner, I'm sure you wouldn't need to bother with such tactics. I'd like to think that a simple /msg could do the job, as this is really just cluttering up the main thread.

        I honestly don't understand why the removal and reinsertion of less than a half-dozen lines of text is causing so much fuss. The end result contains everything the original did, and more.
        This tactic of switching to Anonymous Monk just to fire off some heated

        Nobody switched, I *am* an anonymous monk.

        I honestly don't understand why the removal and reinsertion of less than a half-dozen lines of text is causing so much fuss. The end result contains everything the original did, and more.

        Changing history is never a good idea. I read a thread, see something I wish to discuss (correct, disagree with, concur with, whatever), and by the time I've composed my response and refreshed the page, an entire chunk of your dialogue is no longer there, and my response no longer makes any sense. But I still have some thing to say, so I recompose, and you re-edit, and again I'm left talking to a ghost.

        I may be anonymous, but I have better things to do with my time than to chase your changing words. So I ask you, will you stand behind your words or should I (and anyone else who values their time) simply ignore your ephermal scratchings on this site?

      If your going to use $_ anyway you might as well use the more efficient modifier form (no scope handling overhead).
      @foo[$_-1,-$_] = @foo[-$_,$_-1] for (1..@foo/2);
      BTW: I think this is probably the best implementation (starting at one instead of zero) of all that have been present along this line (especially including my embarrasing fencepost error version) so ++ to you.

      Yves / DeMerphq
      ---
      Software Engineering is Programming when you can't. -- E. W. Dijkstra (RIP)

Re: (OT) Interview questions -- your response?
by sfink (Deacon) on Sep 04, 2002 at 22:13 UTC
    I know! I know!

    1a. Because the compiler ignored the mismatched 'end for' and instead put all of the code up to the next 'end foreach' into the inner loop.

    1b. Get a compiler with better error handling.

    2.

    sub sum { return md5sum(join('',@_)); } my @non_in_place = reverse @array; my $correct = sum(@non_in_place); while ($correct ne sum(@array)) { ($a,$b)=(rand(@array),rand(@array)); @array[$a,$b] = @array[$b,$a]; }
    3. <FORM ACTION="http://www.perlmonks.org/">...</FORM> It seems to satisfy your criteria, as long as you're not too picky about whose database you're querying.
Re: (OT) Interview questions -- your response?
by seeken (Novice) on Sep 10, 2002 at 04:22 UTC
    I'm coming late to this here thread...
    
    But I think the point is being missed by the responses to:
    
      foreach a_item in a_array
        foreach b_item in b_array
          if a_item equals b_item
            put a_item in c_array
          end if
        end for
      end for
    
    What does this code do? 
    
    @a = ( a c f r f z t  );
    @b = ( e c s f r f) ;
    
          @a   a c f r f z t 
    @b  @c = ( 
    e          _ _ _ _ _ _ _          
    c          _ c _ _ _ _ _        
    s          _ _ _ _ _ _ _
    f          _ _ f _ f _ _
    r          _ _ _ r _ _ _ 
    f          _ _ f _ f _ _
             ) 
    where an underscore is ignored - read left-right-top-bottom
      c f f r f f 
    
    If we hash either, a or b, we always will lose something-
    the r will be out of place, values repeated in both the a
    and b will overrepresented or overrepresented.
    
    What do you do about your performance problems? Cry, cus 
    it's not going to get much better than as it's presented in 
    the initial question. (removing items from a that aren't in 
    b and vice versa might do some good, depending on the data.)
    
    
    
    surfing the net and other cliches....
      If we hash either, a or b, we always will lose something
      Take another look at Abigail-II's solution and note that the question specifically states that the order of the results is unimportant.
      #!/usr/bin/perl -wT use strict; my @a_array = qw( a c f r f z t ); my @b_array = qw( e c s f r f) ; my %b_hash; $b_hash {$_} ++ for @b_array; my @c_array = map {($_) x ($b_hash {$_} || 0)} @a_array; print "@c_array\n"; __END__ c f f r f f

      -Blake

        Well if there was one thing I should have learned in school, it was to read the danged question all the way through.

        surfing the net and other cliches....

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlmeditation [id://194839]
Approved by ignatz
Front-paged by hsmyers
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others pondering the Monastery: (7)
As of 2014-12-21 08:50 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (104 votes), past polls