No idea what might constitute a "good" answer. but the following may be of interest:

use strict;
use warnings;

my @original = (1, 2, 3, 4, 5, 6, 7, 8, 3, 5, 6, 3, 8, 1, 7, 8);
my @lists = [shift @original];

for my $value (@original) {
    push @lists, [] if $value < $lists[-1][-1];
    push @{$lists[-1]}, $value;
}

print join (', ', map {"[@$_]"} @lists), "\n";

my @result;

while (@lists) {
    my ($smallest) = sort {$lists[$a][0] <=> $lists[$b][0]} 0 .. $#lis
+ts;
    
    push @result, shift @{$lists[$smallest]};
    @lists = grep{scalar @$_} @lists;
}

print "@result";
[download]

Prints:

[1 2 3 4 5 6 7 8], [3 5 6], [3 8], [1 7 8]
1 1 2 3 3 3 4 5 5 6 6 7 7 8 8 8
[download]

Not that I'm suggesting I'd have produced that in an interview mind you!

Not that I'm suggesting I'd have produced that in an interview mind you!

They gave me two questions and this was the 2nd one. I am not sure what they expected to see in 45 minutes.

Thanks for the code. I see what I could have done differently to have given them not "naive" solution. I suppose being succinct is important as well.

It's not so much being succinct, although clean code often is. The key bits are:

• Handle the initial empty list case outside the loop to make the loop cleaner.
• Use Perl's "last element index" (-1) so you don't need to count stuff.
• Handle "time for a new segment" and "add a value" as independent operations.
• Work with the index of the next interesting value, not the value.
• Clean up as you go.

although upon reflection I'd change @lists = grep{scalar @$_} @lists; to splice @lists, $smallest, 1 if !@{$lists[$smallest]};.

Perl is the programming world's equivalent of English

Not necessarily recommended for an interview response, but gives a rare opportunity to employ List::MoreUtils::part():

c:\@Work\Perl>perl -wMstrict -le
"use Test::More 'no_plan';
 use Test::NoWarnings;
 ;;
 use List::MoreUtils qw(part);
 ;;
 sub ascending_runs {
   my $prev = $_[0];
   my $i = 0;
   return part { ++$i if $_ < $prev;  $prev = $_;  $i; } @_;
   };
 ;;
 VECTOR:
 for my $ar_vector (
   [ [ 1..8,     3, 5, 6,     3, 8,     1, 7, 8 ],
     [ 1..8 ], [ 3, 5, 6 ], [ 3, 8 ], [ 1, 7, 8 ],
     ],
   [ [], ],
   [ [ 0 ], [ 0 ] ],   [ [ 1 ], [ 1 ] ],  [ [ -7 ], [ -7 ] ],
   [ [ 0, 7 ], [ 0, 7 ] ],  [ [ 7, 0 ], [ 7 ], [ 0 ] ],
   [ [ -1, 0], [ -1, 0 ] ],  [ [ 0, -1 ], [ 0 ], [ -1 ] ],
   ) {
   my ($ar_in, @expected) = @$ar_vector;
   is_deeply [ ascending_runs(@$ar_in) ], \@expected;
   }
"
ok 1
ok 2
ok 3
ok 4
ok 5
ok 6
ok 7
ok 8
ok 9
ok 10 - no warnings
1..10
[download]

Well, just looking at it I think your first given output is wrong. Shouldn't it be this:

It appears that the goal is to start a new array each time the next value is lower than the previous one.

That said, it would help if you would give the desired goal as described to you since I am only guessing at it for now.

That is correct. Sorry there was a typo in the square bracket entity. Fixed it now.

Without knowing the exact question posed, you did not need to push stuff onto @array3. All you had to do was this for that: my @array3 = sort(@array1);

As for generating the sub-arrays, give me a few minutes and I'll have something different than using indexes.

Update: working code.

#!/usr/bin/perl

use warnings;
use strict;

use Data::Dumper;
$Data::Dumper::Indent = 1;

my @array1 = (1,2,3,4,5,6,7,8,3,5,6,3,8,1,7,8);
my @array3 = sort(@array1);

my @subarrays = ( [] );
my $last = 0;
for ( @array1 ) {
    push(@subarrays, []) if $_ < $last;
    push(@{$subarrays[-1]},$_);
    $last = $_;
}

print Dumper(\@array1);
print Dumper(\@subarrays);
print Dumper(\@array3);

exit;

__END__
[download]

You must always remember that the primary goal is to drain the swamp even when you are hip-deep in alligators.

What was the interview question? The hints from your post suggest a merge sort to me which is likely to be used when combining large presorted files into a single new sorted file.

In the first case, the code is naive in many a few ways, not the least of which, it gets the output wrong -- not including the final sequence of the input. In the second case, it could all be combined into a single pass as below, but it is correct to call the complexity O(n), it will scale linearly with the number of elements.

Update: I see you fixed the desired output, but the code still gets it wrong.

but it is correct to call the complexity O(n), it will scale linearly with the number of elements

Actually, probably not true. As far as I can tell @array3 = sort @array3; is O(N*log N) so it's unlikely the overall code is better than that.

Perl is the programming world's equivalent of English

Of course. I had another line to push the last set. Missed it in here. So how would you tackle the fist question.

I also thought about recursively splicing but I am not sure whether it would improve.

I did not think of using map for the 2nd part. Very neat indead! Thank you.