in reply to (OT) Interview questions -- your response?

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;

[download]
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];
}

[download]
3 I have a column on that.

-- Randal L. Schwartz, Perl hacker

Replies are listed 'Best First'.
Re: &bull;SPOILERS Re: (OT) Interview questions -- your response?
by demerphq (Chancellor) on Sep 03, 2002 at 18:55 UTC
    merlyn your number two is _way_ too complex 
    @array[$_,-$_-1]=@array[-$_-1,$_] for 0..@array/2;

    [download]
    UPDATED
    As has been pointed out the above is incorrect. 
    @array[$_,-$_-1]=@array[-$_-1,$_] for 0..$#array/2;

    [download]
    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]

      Fencepost error. I think you mean:

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

      [download]

      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]
        I actually did #2 the way I did to avoid a fencepost error. And it's proveably correct.

        And think of the maintenance programmer. I'd not want to maintain your code.

        -- Randal L. Schwartz, Perl hacker

[reply]
        Busted.

        Oh well.

        I guess I didn't get the job.

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

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

      [download]
      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]
        Actually I disagree quite strongly. Its readable by people with a C background (ie who are used to the while() loops being disguised as for() loops) but to people who come from other backgrounds (such as Pascal) I think the above would cause some palpatations on first reading.

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

[reply]
      In Perl6, will ~= between two lists give their intersection in list context?
[reply]
Re: (OT) Interview questions -- your response?
by Abigail-II (Bishop) on Sep 04, 2002 at 12:21 UTC
    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;

    [download]
    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;

    [download]
    which has a running time of O (sizeof (input) + sizeof (output)), which is asymptotical optimal.

    Abigail

[reply]
[d/l]
[select]
Re: &bull;SPOILERS Re: (OT) Interview questions -- your response?
by ichimunki (Priest) on Sep 03, 2002 at 19:16 UTC
    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);
  }
}

    [download]
    This will handle duplicate entries in the arrays differently than the hash solution.
[reply]
[d/l]

In Section Meditations