Wrox Programmer Forums List Unflattening
 | Search | Today's Posts | Mark Forums Read
BOOK Programming Interviews Exposed: Secrets to Landing Your Next Job 2nd Ed ISBN: 978-0-470-12167-2
 This is the forum to discuss the Wrox book Programming Interviews Exposed: Secrets to Landing Your Next Job, 2nd Edition by John Mongan, Noah Suojanen, Eric GiguĂ¨re; ISBN: 9780470121672 Read more about Programming Interviews Exposed: Secrets to Landing Your Next Job, 2nd Edition or buy the book from your favorite retailer Download the code for Programming Interviews Exposed: Secrets to Landing Your Next Job, 2nd Edition
 Welcome to the p2p.wrox.com Forums. You are currently viewing the BOOK Programming Interviews Exposed: Secrets to Landing Your Next Job 2nd Ed ISBN: 978-0-470-12167-2 section of the Wrox Programmer to Programmer discussions. This is a community of software programmers and website developers including Wrox book authors and readers. New member registration was closed in 2019. New posts were shut off and the site was archived into this static format as of October 1, 2020. If you require technical support for a Wrox book please contact http://hub.wiley.com

March 29th, 2010, 10:15 PM
 Registered User Join Date: Mar 2010 Posts: 8 Thanks: 0 Thanked 8 Times in 8 Posts
List Unflattening

On page 49, the book shows an example of how to unflatten. I feel that it is an odd choice to select recursion to do the work, especially considering the many references to memory efficiency. By using recursion, the algorithm can reach a peak memory inefficiency of O(n).

Instead, you can start from the tail, looking to prev until you find an element that has a child. Then, adjust the tail to point to the prev of the child.

Code:
```void unflatten(Node** head, Node** tail)
{
if (!(*tail)) return;
Node* track = *tail;
while (track)
{
if (track->child)
{
*tail = track->child->prev;
track->child->prev = NULL;
(*tail)->next = NULL;
}
track = track->prev;
}
}```
In my examples, I continued to pass a Node** for both head and tail, allowing the implementation to choose which variables to possibly update, but I realize that is a matter of taste.

Also, in your example code, you changed the name head to start, in this example only.

Regards,
Matt
 The Following User Says Thank You to MattCruikshank For This Useful Post: WayneHeym (May 27th, 2011)

April 11th, 2010, 11:41 AM
 Registered User Join Date: Apr 2010 Posts: 1 Thanks: 0 Thanked 1 Time in 1 Post
Agreed!

Yes! I'm glad to have found your comment to validate what I was already thinking. It seems to me that the key insight is that the flattening and unflattening problems (pages 44-49) are symmetric and invertible. The algorithm you posted is the inverse of the author's flattening solution. It is simpler and more efficient than the recursive unflattening presented in the book. I'm surprised that the authors overlooked it.
 The Following User Says Thank You to KennyS For This Useful Post: WayneHeym (May 27th, 2011)

February 10th, 2013, 07:24 AM
Registered User
 Points: 3, Level: 1
 Activity: 0%

Join Date: Feb 2013
Posts: 1
Thanks: 0
Thanked 0 Times in 0 Posts
Good solution suitable for specific flattening orders only

The suggested alternative solution that does not use recursion is nice. It is suitable for a specific flattening order that the authors used specifically.

I expect that the authors wanted to solve the unflattening problem regardless of the order of the flattened list. The authors suggested another ordering in which child elements appear after their parents in the flattened list. The suggested alternative solution not using recursion does not work for this ordering for example.

Last edited by lebanman; March 1st, 2013 at 06:37 AM..

June 16th, 2013, 05:06 PM
Registered User
 Points: 9, Level: 1
 Activity: 0%

Join Date: Jun 2013
Posts: 3
Thanks: 0
Thanked 0 Times in 0 Posts
Small problem

If you see the code for
Code:
`exploreAndSeparate`
,
there seems to be a potential null pointer access problem in cases where traversal will revisit the nodes multiple times with children whose back pointers are already snipped off by a previous traversal. So it seems prudent to add the following check before snipping the links:

Code:
```...
if (curNode->child)
{
if (curNode->child->prev) {   //add check for null
curNode->child->prev->next=NULL;
curNode->child->prev=NULL;
}
}
...```
What do you say?

November 10th, 2013, 07:05 PM
Registered User
 Points: 3, Level: 1
 Activity: 0%

Join Date: Nov 2013
Posts: 1
Thanks: 0
Thanked 0 Times in 0 Posts
recursion work?

Quote:
 Originally Posted by lebanman The suggested alternative solution that does not use recursion is nice. It is suitable for a specific flattening order that the authors used specifically. I expect that the authors wanted to solve the unflattening problem regardless of the order of the flattened list. The authors suggested another ordering in which child elements appear after their parents in the flattened list. The suggested alternative solution not using recursion does not work for this ordering for example.
But if the ordering in which child elements appear after their parents in the flattened list. The recursion does not work neither..

May 25th, 2014, 11:02 PM
Registered User
 Points: 12, Level: 1
 Activity: 0%

Join Date: May 2014
Posts: 4
Thanks: 0
Thanked 1 Time in 1 Post

Quote:
 Originally Posted by lebanman The suggested alternative solution that does not use recursion is nice. It is suitable for a specific flattening order that the authors used specifically. I expect that the authors wanted to solve the unflattening problem regardless of the order of the flattened list. The authors suggested another ordering in which child elements appear after their parents in the flattened list. The suggested alternative solution not using recursion does not work for this ordering for example.
Maybe i don't fully understand the problem, but i don't see how the list can be unflattened at all (unambiguously) if the child list inserted after the parent node. E.g. in the author's example if we insert 6,25,6 after 5 (assume 6,25,6 has no children) the it will be 5, 6, 25, 6, 33, 17, ... Then how do we know that the child list of 5 has only 3 elements and not more?

May 25th, 2014, 11:10 PM
Registered User
 Points: 12, Level: 1
 Activity: 0%

Join Date: May 2014
Posts: 4
Thanks: 0
Thanked 1 Time in 1 Post

Traverse list from the start. If a node has a child, set the child's prev pointer to null (but do not change the next pointer of the node pointing to this child yet so we can continue to traverse).
Also during traversing, keep track of both current and previous nodes. If current->prev is null, set previous->next to null as well.

December 19th, 2014, 05:03 PM
Registered User
 Points: 16, Level: 1
 Activity: 0%

Join Date: Dec 2014
Posts: 4
Thanks: 0
Thanked 0 Times in 0 Posts

Quote:
 Originally Posted by wmy512 But if the ordering in which child elements appear after their parents in the flattened list. The recursion does not work neither..
I came to this conclusion as well.

I've been attempting the problems before I read how the author would solve them, so I flattened the list in a child-to-next algorithm instead of the author's child-to-end. I'm not sure that it's impossible to unflatten a list that's been flattened child-to-next, but certainly a lot harder since you're scrambling the sublists up.

My takeaway here is if the interview asks you to do something, expect that they might ask you to reverse it in a subsequent question.

March 14th, 2016, 11:45 AM
Registered User
 Points: 18, Level: 1
 Activity: 0%

Join Date: Mar 2016
Posts: 4
Thanks: 0
Thanked 0 Times in 0 Posts

Quote:
 Originally Posted by lebanman I expect that the authors wanted to solve the unflattening problem regardless of the order of the flattened list.
Correct me if I'm wrong, but I don't think it is possible to find an algorithm that unflattens independently of the flattening algorithm.

 Similar Threads Thread Thread Starter Forum Replies Last Post Dim list As New List(Of Testclass) dotnetDeveloper General .NET 1 January 6th, 2009 08:19 PM Dim list As New List(Of Testclass) dotnetDeveloper Visual Basic 2008 Essentials 0 January 6th, 2009 04:04 PM multi-column list box values moved to 2nd list box sbmvr Access VBA 1 May 14th, 2007 01:58 PM fill dropdown list with items when parent list isaac_cm Pro PHP 1 July 10th, 2006 05:41 AM List tablesname from database & list databasename ittorget MySQL 3 September 10th, 2005 03:06 AM