Wrox Programmer Forums
|
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 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
 
Old March 29th, 2010, 09: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
The Following User Says Thank You to MattCruikshank For This Useful Post:
WayneHeym (May 27th, 2011)
 
Old May 27th, 2011, 02:06 PM
Authorized User
 
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





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 01: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 02:19 PM





Powered by vBulletin®
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.
Copyright (c) 2020 John Wiley & Sons, Inc.