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, 10:59 PM
Registered User
 
Join Date: Mar 2010
Posts: 8
Thanks: 0
Thanked 8 Times in 8 Posts
Default Page 39 - insertAfter

I'm curious if you can explain why, in the listed answer for insertAfter on Page 39, you decide to traverse the list, using curPos, rather than just trust that the elem provided is actually in the list, and merely insert a new Element with the value data after it?

By traversing, you produce O(n) code. If you trust that elem is in the list, you produce O(1) code. I'm as paranoid as the next coder, but it seems a bit, er - cynical - to not trust that elem is in the list referenced by head and tail.

I realize that this is just a difference in how exhaustively the coder does error checking; but considering the emphasis in the book on efficiency, it seems an odd choice.

Regards,
-Matt
Reply With Quote
The Following User Says Thank You to MattCruikshank For This Useful Post:
WayneHeym (May 27th, 2011)
  #2 (permalink)  
Old May 27th, 2011, 03:06 PM
Authorized User
Points: 68, Level: 1
Points: 68, Level: 1 Points: 68, Level: 1 Points: 68, Level: 1
Activity: 0%
Activity: 0% Activity: 0% Activity: 0%
 
Join Date: May 2011
Posts: 15
Thanks: 11
Thanked 0 Times in 0 Posts
Default Expressing a contract could help

It may be useful to provide the client programmer two versions of insertAfter (named differently from each other, then, probably): one that assumes that elem is present in the list, and one that does not. Each of these versions has a different contract with its client. The first requires of the client that elem really is present in the list and promises no reliable behavior if this requirement is not met. The second relaxes this requirement and reliably reports the failure if elem is not present in the list. The first can be made to run in constant time; the second must run in at least linear time. A well-behaved client (one that knows for sure that elem is in the list), then, can choose to call the faster of these two operations.

Because different contracts are possible, it can be useful to express the contract, to write it down as part of the comments describing the operation.

Of course, one wouldn't have to provide two versions. Providing one version is okay if you express its contract, even if that one version is the fast one that assumes that elem is in the list.

Thank you for your contribution, Matt.

Regards,

Wayne
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
Chapter 2, pg 39 Bodman@live.ca BOOK: Beginning PHP 6, Apache, MySQL 6 Web Development ISBN: 9780470391143 2 April 21st, 2009 02:42 AM
Undefined session variables Ch.2 pg. 38-39 outtaMyBlood BOOK: Beginning PHP 6, Apache, MySQL 6 Web Development ISBN: 9780470391143 2 March 14th, 2009 03:19 PM



All times are GMT -4. The time now is 09:19 PM.


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