(OT) Interview questions -- your response?

[Ovid]

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.

[merlyn]

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

[demerphq]

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)

[Zaxo]

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

[Dog and Pony]

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.

[ignatz]

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. ;-)

()-()
 \"/
  `                                                     

[perrin]

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.

[John M. Dlugosz]

In Perl6, will ~= between two lists give their intersection in list context?

[Abigail-II]

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

[ichimunki]

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.

[demerphq]

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)

[Ovid]

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.

[dws]

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.

[Aristotle]

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.

[John M. Dlugosz]

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

[rir]

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.

[andye]

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.

[rdfield]

...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

[FoxtrotUniform]

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!

[Anonymous Monk]

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?

[merlyn]

@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

[Anonymous Monk]

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 :-)

[bbfu]

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

[Anonymous Monk]

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.

[sfink]

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.

[Anonymous Monk]

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?

[tadman]

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.

[demerphq]

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)

[seeken]

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....

[blakem]

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

[seeken]

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....