•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 | [reply] [d/l] [select] |
|
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)
| [reply] [d/l] [select] |
|
@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 | [reply] [d/l] |
|
|
|
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. | [reply] [d/l] |
|
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. ;-)
()-()
\"/
`
| [reply] |
|
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.
| [reply] |
|
|
In Perl6, will ~= between two lists give their intersection in list context?
| [reply] |
|
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
| [reply] [d/l] [select] |
|
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. | [reply] [d/l] |
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)
| [reply] |
|
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.
| [reply] |
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.
| [reply] |
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.
| [reply] [d/l] [select] |
A reply falls below the community's threshold of quality. You may see it by logging in. |
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 | [reply] [d/l] [select] |
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.
| [reply] [d/l] |
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. | [reply] |
|
...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
| [reply] |
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!
| [reply] |
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?
| [reply] [d/l] |
|
| [reply] [d/l] |
|
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 :-)
| [reply] [d/l] |
|
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 | [reply] [d/l] [select] |
|
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.
| [reply] [d/l] [select] |
|
|
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. | [reply] [d/l] |
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? | [reply] |
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.
| [reply] [d/l] [select] |
|
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)
| [reply] [d/l] |
A reply falls below the community's threshold of quality. You may see it by logging in. |
A reply falls below the community's threshold of quality. You may see it by logging in. |
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.... | [reply] |
|
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
| [reply] [d/l] |
|
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....
| [reply] |