5 ms·

Aren't list-of-lists more like trees where values are only stored on the leaves? In this case, aren't {pre,in,post}order all the same?

by pcmonk 10y ago

brudgers 10y ago
The example input in the article is: [1,[2,3], [4, [5,6]]] It happens to be representable as a binary tree. Indeterminacy regarding whether or not that is accidental or intentional is due to underspecification of the interview problem. The first time I read a description of Linkedin using logs as the fundamental data structure (for what turns out to be Kafka I later learned) I had an epiphany that there is no such thing as a generic simple data structure living in the wild because data is data because it has semantics, without semantics it is just noise. To me, it looks like the root node is |1|.
- pcmonk 10y ago
  To me, "nested list structure" means list-of-lists, which implies a certain natural tree representation, where all elements in a list are siblings. But maybe I've just been poisoned by Lisp, which tries to use lists as the elusive generic simple data structure. (OT: https://en.wikipedia.org/wiki/List_of_lists_of_lists https://en.wikipedia.org/wiki/List_of_lists_of_lists)
cestith 10y ago
For the trivial case in which the nesting always gets deeper at the end like in the OP, perhaps. Take a look at nodes and leaves from my Perl5 example elsewhere in the thread. my $nested = [ 1, [ 2, 3 ], [ 4, [ 5, 6, [ 7, [ 8, [ 9, 10 ] ], 11, 12, [ 13, [ 14, [ 15, 16 ], 17 ], 18 ], 19 ], 20 ] ] ]; What the code does when there are leaves and nodes intermixed at arbitrary depths in arbitrary order from left to right determines the final order of your leaves. Are you pre-flattening all the more deeply nested lists and then building your flat list, or are you walking along a certain nesting level and deferring anything that's not a leaf to later flattening? I gave two examples. One produces a flattened list like this: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 The other products this: 1 2 3 4 5 6 20 7 11 12 19 8 13 18 9 10 14 17 15 16 Are either of those outside the specification set forth?
- pcmonk 10y ago
  Generally, "flatten" means the first of those two orders, but I see that the problem as given doesn't disambiguate those. If an interviewer wants to only accept one of those, he should clarify. Incidentally, the first of those is preorder and postorder traversal of the list-of-lists (inorder only exists for binary trees), while the second is none of those. I would describe that difference as depth-first (first) vs breadth-first (second).
  - cestith 10y ago
    I think "flatten" is kind of underdefined. In many situations, the order of the leaves doesn't matter at all. In others, it matters a great deal. The question should be clear if it does matter. Depth-first for breadth-first was not specified. Both preorder and postorder are subclasses of depth-first. Neither preorder nor postorder was specified. Still, it depends on what you consider a node and a leaf and how you build your tree how much the order matters. Is a deeper nesting level the child node of a value? Are all values leaves and their parent nodes the nesting level? Are nesting levels collapsed into single nodes or are different nested lists at the same level sibling nodes? [1,[2,3], [4, [5,6]]] [] / | 1 [[]]. / | | \ 2 3 4 [[[]]] | | 5 6 In preorder you're going to get: [], 1, [[]], 2, 3, 4, [[[]]], 5, 6 In postorder: 1, 2, 3, 4, 5, 6, [[[]]], [[]], [] Let me explode that initial root this time and make some values nodes if they are followed by an increased nesting level.: [1,[2,3], [4, [5,6]]] 1 / \ [] [] |\ | 2 3 4 | [[]] | | 5 6 Preorder? 1, [], 2, 3, [], 4, [[]], 5, 6 Postorder? Aah... 2, 3, [], 5, 6, [[]], 4, [], 1 So even after you splice out empty nodes, your values are suddenly out of sort order. It's still depth-first. Or maybe we just don't build the nesting levels into our tree because we don't care. But we still build the tree according to it. We're flattening, after all, and the spec doesn't say we need to retain a nesting level as some attribute of the objects in the flattened list. But what becomes a node vs. a leaf is left as an exercise. 1 / | \ 2 3 4 / \ 5 6 Preorder? 1, 2, 3, 4, 5, 6 Postorder? 2, 3, 5, 6, 4, 1 So yeah, it matters. The obvious recursive approach is preorder, especially if you want to maintain sorting. That's what I called "flatten" in my code example earlier. "flatten2" is breadth first as mentioned. Consider this depth-first Perl5 subroutine: sub flatten3 { my $n = shift; my $o; my @f; for ( @$n ) { if ( ref $_ eq 'ARRAY' ) { unshift @f, flatten3( $_ ); } else { push @f, $_; } } return @f; } In each level of recursion it's place the children at the beginning of the array (unshift) and the parent to the end of the array (push) even though it's actually considering them each whenever it reaches them. Given my expanded example input of: my $nested = [ 1, [ 2, 3 ], [ 4, [ 5, 6, [ 7, [ 8, [ 9, 10 ] ], 11, 12, [ 13, [ 14, [ 15, 16 ], 17 ], 18 ], 19 ], 20 ] ] ]; This produces output like this, which is definitely the absolute deepest nesting first in the output.: 15 16 14 17 13 18 9 10 8 7 11 12 19 5 6 20 4 2 3 1 Then there's a true postorder traversal, with an array holding the parent back until after its immediate children.: sub flatten4 { my $n = shift; my @p; my @f; for my $node ( @$n ) { if ( ref $node ) { push @f, flatten4( $node ); } else { push @p, $node; } } push @f, @p; return @f; } which provides output as such since it's considering the parent node after all its children every time.: 2 3 9 10 8 15 16 14 17 13 18 7 11 12 19 5 6 20 4 1 Whereas preorder depth-first keeps the numerical order for this input and the breadth-first traversal gives: 1 2 3 4 5 6 20 7 11 12 19 8 13 18 9 10 14 17 15 16 as previously shown. So no, preorder and postorder do not necessarily mean the same output just because the input started as a nested list. A nested list is not simply a list. It is a special representation of a tree. How you consider that tree to be represented by the nested list is important, as is how you traverse it. In fact, in Perl [] is an array reference, which is why this code is testing for references and recursing on them. So it's already traversing an actual tree structure.

Aren't list-of-lists more like trees where values are only stored on the leaves? In this case, aren't {pre,in,post}order all the same?

by pcmonk 10y ago

Aren't list-of-lists more like trees where values are only stored on the leaves? In this case, aren't {pre,in,post}order all the same?

brudgers 10y ago

The example input in the article is: [1,[2,3], [4, [5,6]]] It happens to be representable as a binary tree. Indeterminacy regarding whether or not that is accidental or intentional is due to underspecification of the interview problem. The first time I read a description of Linkedin using logs as the fundamental data structure (for what turns out to be Kafka I later learned) I had an epiphany that there is no such thing as a generic simple data structure living in the wild because data is data because it has semantics, without semantics it is just noise. To me, it looks like the root node is |1|.

pcmonk 10y ago
To me, "nested list structure" means list-of-lists, which implies a certain natural tree representation, where all elements in a list are siblings. But maybe I've just been poisoned by Lisp, which tries to use lists as the elusive generic simple data structure. (OT: https://en.wikipedia.org/wiki/List_of_lists_of_lists https://en.wikipedia.org/wiki/List_of_lists_of_lists)

cestith 10y ago

For the trivial case in which the nesting always gets deeper at the end like in the OP, perhaps. Take a look at nodes and leaves from my Perl5 example elsewhere in the thread. my $nested = [ 1, [ 2, 3 ], [ 4, [ 5, 6, [ 7, [ 8, [ 9, 10 ] ], 11, 12, [ 13, [ 14, [ 15, 16 ], 17 ], 18 ], 19 ], 20 ] ] ]; What the code does when there are leaves and nodes intermixed at arbitrary depths in arbitrary order from left to right determines the final order of your leaves. Are you pre-flattening all the more deeply nested lists and then building your flat list, or are you walking along a certain nesting level and deferring anything that's not a leaf to later flattening? I gave two examples. One produces a flattened list like this: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 The other products this: 1 2 3 4 5 6 20 7 11 12 19 8 13 18 9 10 14 17 15 16 Are either of those outside the specification set forth?

pcmonk 10y ago
Generally, "flatten" means the first of those two orders, but I see that the problem as given doesn't disambiguate those. If an interviewer wants to only accept one of those, he should clarify. Incidentally, the first of those is preorder and postorder traversal of the list-of-lists (inorder only exists for binary trees), while the second is none of those. I would describe that difference as depth-first (first) vs breadth-first (second).
- cestith 10y ago
  I think "flatten" is kind of underdefined. In many situations, the order of the leaves doesn't matter at all. In others, it matters a great deal. The question should be clear if it does matter. Depth-first for breadth-first was not specified. Both preorder and postorder are subclasses of depth-first. Neither preorder nor postorder was specified. Still, it depends on what you consider a node and a leaf and how you build your tree how much the order matters. Is a deeper nesting level the child node of a value? Are all values leaves and their parent nodes the nesting level? Are nesting levels collapsed into single nodes or are different nested lists at the same level sibling nodes? [1,[2,3], [4, [5,6]]] [] / | 1 [[]]. / | | \ 2 3 4 [[[]]] | | 5 6 In preorder you're going to get: [], 1, [[]], 2, 3, 4, [[[]]], 5, 6 In postorder: 1, 2, 3, 4, 5, 6, [[[]]], [[]], [] Let me explode that initial root this time and make some values nodes if they are followed by an increased nesting level.: [1,[2,3], [4, [5,6]]] 1 / \ [] [] |\ | 2 3 4 | [[]] | | 5 6 Preorder? 1, [], 2, 3, [], 4, [[]], 5, 6 Postorder? Aah... 2, 3, [], 5, 6, [[]], 4, [], 1 So even after you splice out empty nodes, your values are suddenly out of sort order. It's still depth-first. Or maybe we just don't build the nesting levels into our tree because we don't care. But we still build the tree according to it. We're flattening, after all, and the spec doesn't say we need to retain a nesting level as some attribute of the objects in the flattened list. But what becomes a node vs. a leaf is left as an exercise. 1 / | \ 2 3 4 / \ 5 6 Preorder? 1, 2, 3, 4, 5, 6 Postorder? 2, 3, 5, 6, 4, 1 So yeah, it matters. The obvious recursive approach is preorder, especially if you want to maintain sorting. That's what I called "flatten" in my code example earlier. "flatten2" is breadth first as mentioned. Consider this depth-first Perl5 subroutine: sub flatten3 { my $n = shift; my $o; my @f; for ( @$n ) { if ( ref $_ eq 'ARRAY' ) { unshift @f, flatten3( $_ ); } else { push @f, $_; } } return @f; } In each level of recursion it's place the children at the beginning of the array (unshift) and the parent to the end of the array (push) even though it's actually considering them each whenever it reaches them. Given my expanded example input of: my $nested = [ 1, [ 2, 3 ], [ 4, [ 5, 6, [ 7, [ 8, [ 9, 10 ] ], 11, 12, [ 13, [ 14, [ 15, 16 ], 17 ], 18 ], 19 ], 20 ] ] ]; This produces output like this, which is definitely the absolute deepest nesting first in the output.: 15 16 14 17 13 18 9 10 8 7 11 12 19 5 6 20 4 2 3 1 Then there's a true postorder traversal, with an array holding the parent back until after its immediate children.: sub flatten4 { my $n = shift; my @p; my @f; for my $node ( @$n ) { if ( ref $node ) { push @f, flatten4( $node ); } else { push @p, $node; } } push @f, @p; return @f; } which provides output as such since it's considering the parent node after all its children every time.: 2 3 9 10 8 15 16 14 17 13 18 7 11 12 19 5 6 20 4 1 Whereas preorder depth-first keeps the numerical order for this input and the breadth-first traversal gives: 1 2 3 4 5 6 20 7 11 12 19 8 13 18 9 10 14 17 15 16 as previously shown. So no, preorder and postorder do not necessarily mean the same output just because the input started as a nested list. A nested list is not simply a list. It is a special representation of a tree. How you consider that tree to be represented by the nested list is important, as is how you traverse it. In fact, in Perl [] is an array reference, which is why this code is testing for references and recursing on them. So it's already traversing an actual tree structure.