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 3rd Edition
This is the forum to discuss the Wrox book Programming Interviews Exposed: Secrets to Landing Your Next Job, 3rd Edition by John Mongan, Noah Kindler, Eric Giguere; ISBN: 978-1-118-26136-1
Welcome to the p2p.wrox.com Forums.

You are currently viewing the BOOK Programming Interviews Exposed: Secrets to Landing Your Next Job 3rd Edition 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 April 2nd, 2013, 04:00 PM
Registered User
Points: 30, Level: 1
Points: 30, Level: 1 Points: 30, Level: 1 Points: 30, Level: 1
Activity: 0%
Activity: 0% Activity: 0% Activity: 0%
 
Join Date: Mar 2013
Posts: 7
Thanks: 0
Thanked 0 Times in 0 Posts
Default Lower Common Ancestor Problem (pg 73)

Hi,

I agree 90% with the solution to this problem. However, it is not explicit what the answer would be for the LCA of nodes with value 12 and 14 in the picture. The implementation suggested would place 12 as the solution.

It seems 8 would be a more fitting LCA, so I stored the previousNode for each iteration. If the two are not both greater or both less than, then I check for if the currentNode is A or B. If so, then use previousNode (convergence). Otherwise currentNode is LCA(divergence).

Thoughts?

Erich
Reply With Quote
  #2 (permalink)  
Old April 3rd, 2013, 07:37 AM
Wrox Author
Points: 51, Level: 1
Points: 51, Level: 1 Points: 51, Level: 1 Points: 51, Level: 1
Activity: 0%
Activity: 0% Activity: 0% Activity: 0%
 
Join Date: Oct 2012
Posts: 10
Thanks: 0
Thanked 1 Time in 1 Post
Default

It all hinges on what you consider to be the definition of "ancestor". If a node is an ancestor of itself (which is what the definition in the book implies) then the book's assertion is correct. If you say that a node cannot be its own ancestor, then your assertion is correct.

But if a node is not an ancestor of itself, you'll have problems dealing with finding the LCA of any set of nodes that includes the root node....

Eric
Reply With Quote
  #3 (permalink)  
Old April 3rd, 2013, 07:52 AM
Wrox Author
Points: 51, Level: 1
Points: 51, Level: 1 Points: 51, Level: 1 Points: 51, Level: 1
Activity: 0%
Activity: 0% Activity: 0% Activity: 0%
 
Join Date: Oct 2012
Posts: 10
Thanks: 0
Thanked 1 Time in 1 Post
Default

The point I wanted to make was that in an interview you should make it clear what you mean by "ancestor". In your scenario, for example, returning null would make the most sense for any set of nodes that included the root node. But the interviewer might be confused unless you told them what your interpretation of "ancestor" was.

Eric
Reply With Quote
  #4 (permalink)  
Old April 4th, 2013, 12:55 AM
Registered User
Points: 30, Level: 1
Points: 30, Level: 1 Points: 30, Level: 1 Points: 30, Level: 1
Activity: 0%
Activity: 0% Activity: 0% Activity: 0%
 
Join Date: Mar 2013
Posts: 7
Thanks: 0
Thanked 0 Times in 0 Posts
Default

that's an excellent point! i did not consider a pair of nodes including the root node.... should have saw that edge case :P thanks for the reply!
Reply With Quote
  #5 (permalink)  
Old April 4th, 2013, 07:38 AM
Wrox Author
Points: 51, Level: 1
Points: 51, Level: 1 Points: 51, Level: 1 Points: 51, Level: 1
Activity: 0%
Activity: 0% Activity: 0% Activity: 0%
 
Join Date: Oct 2012
Posts: 10
Thanks: 0
Thanked 1 Time in 1 Post
Default

Quote:
Originally Posted by erichlin View Post
that's an excellent point! i did not consider a pair of nodes including the root node.... should have saw that edge case :P thanks for the reply!
No problem, and thanks for the question!

Eric
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
coding problem in common dialog box cancertropica Visual Basic 2005 Basics 0 July 30th, 2008 10:38 AM
parent/ancestor nmnm XSLT 1 April 24th, 2007 06:25 AM
Common question, not so common answer? flyin ADO.NET 5 March 24th, 2004 06:50 PM



All times are GMT -4. The time now is 01:24 AM.


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