3 ms·
This is pretty trivial. It doesn't require recursion, although the recursive implementation is much simpler. The spec doesn't specify breadth-first or depth-fir
by cestith 10y ago
This is pretty trivial. It doesn't require recursion, although the recursive implementation is much simpler. The spec doesn't specify breadth-first or depth-first. The example input offered comes out the example output offered either way. The spec in the article also doesn't mention making it generic, so I don't see how that's points away for programmers who tackle the input and output given as integers only.
Here's some pretty trivial Perl5 to do recursive or iterative versions.:
use strict;
use warnings;
use Data::Dumper ();
my $nested = [ 1, [ 2, 3 ], [ 4, [ 5, 6, [ 7, [ 8, [ 9, 10 ] ], 11, 12, [ 13, [ 14, [ 15, 16 ], 17 ], 18 ], 19 ], 20 ] ] ];
sub flatten {
my @f;
push @f, (ref $_ ? flatten( $_ ) : $_ ) for @{ $_[0] };
return @f;
}
sub flatten2 {
my $n = shift;
my ( @f, @queue1, @queue2 );
my $pass = 0;
for ( @$n ) {
if ( ref $_ ) {
push @queue1, $_;
} else {
push @f, $_;
}
}
until ( $pass > 0 && scalar @queue1 == 0 && scalar @queue2 == 0 ) {
for ( @queue1 ) {
if ( ref $_ ) {
push @queue2, @{ $_ };
} else {
push @f, $_;
}
}
@queue1 = @queue2;
@queue2 = ();
$pass++;
}
return @f;
}
print STDOUT (join ' ', flatten( $nested )) . "\n";
my @flat = flatten( $nested );
print Data::Dumper::Dumper \@flat;
print STDOUT (join ' ', flatten2( $nested )) . "\n";
my @flat2 = flatten2( $nested );
print Data::Dumper::Dumper \@flat2;
- zzzcpan 10y agoYou can make it nicer and more reliable with Perl: sub flatten { map { ref $_ eq 'ARRAY' ? flatten(@$_) : $_ } @_ } However, this is not something a Java/OO programmer would be comfortable with, especially under the stress of the interview. As it's a bit higher level and closer to a functional way of thinking, than OO.
- cestith 10y agoI started to use map, but I've been told time and again anything that does is not a trivial example because you start by explaining what map does. Anyway, I'm glad the first response to "this is trivial in Perl" is another, simpler Perl response rather than "Perl is dead".
- alain_gilbert 10y agoNon recursive algo with python: def flatten(array): queue = [array] result = [] while len(queue) > 0: item = queue.pop(0) if isinstance(item, list): for sub_item in item: queue.append(sub_item) else: result.append(item) return result a = [1,[2,3], [4, [5,6]]] print 'input:', a, '\noutput:', flatten(a)