Wrox Programmer Forums

Need to download code?

View our list of code downloads.

Register | FAQ | Members List | Calendar | 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
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 tens of thousands of software programmers and website developers including Wrox book authors and readers. As a guest, you can read any forum posting. By joining today you can post your own programming questions, respond to other developers’ questions, and eliminate the ads that are displayed to guests. Registration is fast, simple and absolutely free .
DRM-free e-books 300x50
Reply
 
Thread Tools Display Modes
  #1 (permalink)  
Old March 29th, 2010, 11:15 PM
Registered User
 
Join Date: Mar 2010
Posts: 8
Thanks: 0
Thanked 8 Times in 8 Posts
Default 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
Reply With Quote
The Following User Says Thank You to MattCruikshank For This Useful Post:
WayneHeym (May 27th, 2011)
  #2 (permalink)  
Old April 11th, 2010, 12:41 PM
Registered User
 
Join Date: Apr 2010
Posts: 1
Thanks: 0
Thanked 1 Time in 1 Post
Default 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.
Reply With Quote
The Following User Says Thank You to KennyS For This Useful Post:
WayneHeym (May 27th, 2011)
  #3 (permalink)  
Old February 10th, 2013, 07:24 AM
Registered User
Points: 3, Level: 1
Points: 3, Level: 1 Points: 3, Level: 1 Points: 3, Level: 1
Activity: 0%
Activity: 0% Activity: 0% Activity: 0%
 
Join Date: Feb 2013
Posts: 1
Thanks: 0
Thanked 0 Times in 0 Posts
Default 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.
Reply With Quote
  #4 (permalink)  
Old June 16th, 2013, 06:06 PM
Registered User
Points: 9, Level: 1
Points: 9, Level: 1 Points: 9, Level: 1 Points: 9, Level: 1
Activity: 0%
Activity: 0% Activity: 0% Activity: 0%
 
Join Date: Jun 2013
Posts: 3
Thanks: 0
Thanked 0 Times in 0 Posts
Default 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?
Reply With Quote
  #5 (permalink)  
Old November 10th, 2013, 07:05 PM
Registered User
Points: 3, Level: 1
Points: 3, Level: 1 Points: 3, Level: 1 Points: 3, Level: 1
Activity: 0%
Activity: 0% Activity: 0% Activity: 0%
 
Join Date: Nov 2013
Posts: 1
Thanks: 0
Thanked 0 Times in 0 Posts
Smile recursion work?

Quote:
Originally Posted by lebanman View Post
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..
Reply With Quote
  #6 (permalink)  
Old May 26th, 2014, 12:02 AM
Registered User
Points: 12, Level: 1
Points: 12, Level: 1 Points: 12, Level: 1 Points: 12, Level: 1
Activity: 0%
Activity: 0% Activity: 0% Activity: 0%
 
Join Date: May 2014
Posts: 4
Thanks: 0
Thanked 1 Time in 1 Post
Default

Quote:
Originally Posted by lebanman View Post
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?
Reply With Quote
  #7 (permalink)  
Old May 26th, 2014, 12:10 AM
Registered User
Points: 12, Level: 1
Points: 12, Level: 1 Points: 12, Level: 1 Points: 12, Level: 1
Activity: 0%
Activity: 0% Activity: 0% Activity: 0%
 
Join Date: May 2014
Posts: 4
Thanks: 0
Thanked 1 Time in 1 Post
Default

What about this alternative solution without recursion:

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.
Reply With Quote
  #8 (permalink)  
Old December 19th, 2014, 05:03 PM
Registered User
Points: 16, Level: 1
Points: 16, Level: 1 Points: 16, Level: 1 Points: 16, Level: 1
Activity: 0%
Activity: 0% Activity: 0% Activity: 0%
 
Join Date: Dec 2014
Posts: 4
Thanks: 0
Thanked 0 Times in 0 Posts
Default

Quote:
Originally Posted by wmy512 View Post
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.
Reply With Quote
  #9 (permalink)  
Old March 14th, 2016, 12:45 PM
Registered User
Points: 18, Level: 1
Points: 18, Level: 1 Points: 18, Level: 1 Points: 18, Level: 1
Activity: 0%
Activity: 0% Activity: 0% Activity: 0%
 
Join Date: Mar 2016
Posts: 4
Thanks: 0
Thanked 0 Times in 0 Posts
Default

Quote:
Originally Posted by lebanman View Post
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.
Reply With Quote
Reply


Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off
Trackbacks are Off
Pingbacks are On
Refbacks are Off

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 02:58 PM
fill dropdown list with items when parent list isaac_cm Pro PHP 1 July 10th, 2006 06:41 AM
List tablesname from database & list databasename ittorget MySQL 3 September 10th, 2005 04:06 AM



All times are GMT -4. The time now is 04:48 AM.


Powered by vBulletin®
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
© 2013 John Wiley & Sons, Inc.