tag:blogger.com,1999:blog-4228859841453048938.post7401794477710123974..comments2024-03-28T19:53:14.045+08:00Comments on Coding Interview Questions: No. 10 - K-th Node from EndHarry Hehttp://www.blogger.com/profile/10363303096963693183noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-4228859841453048938.post-59008156388360741832016-11-26T00:55:52.448+08:002016-11-26T00:55:52.448+08:00Ref. Kunal's suggestion - "We can use onl...Ref. Kunal's suggestion - "We can use only one loop to traverse the list and find the node" is not a bad but unfortunately the fact (problem) remains ! <br />Please understand that this is just a mere aberration in some sense and does nothing in effect to get rid of second traversal since the second pointer is indispensable here too. <br />But nevertheless, the simplest and yet elegant approach going with the original solution given by Harry is quite ornamental. The other solutions that suggest to maintain the addresses of individual nodes as we traverse along the first time and so on still steal away the coding elegance and not to mention the overheads to maintain in my opinion.<br /><br />Anonymoushttps://www.blogger.com/profile/09275509938541101354noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-50570412049737989442016-03-13T17:49:58.784+08:002016-03-13T17:49:58.784+08:00We can use only one loop to traverse the list and ...We can use only one loop to traverse the list and find the node.<br />Means, We will iterate the loop i < k && list!= NULL and in that we will increment one ptr by 1 ans second ptr by 2. then we the get the kth node. Anonymoushttps://www.blogger.com/profile/18137988331952498720noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-48057582725682104412016-03-13T16:24:18.198+08:002016-03-13T16:24:18.198+08:00We can use only one loop to traverse the list and ...We can use only one loop to traverse the list and find the node.<br />Means, We will iterate the loop i < k && list!= NULL and in that we will increment one ptr by 1 ans second ptr by 2. then we the get the kth node. Anonymoushttps://www.blogger.com/profile/18137988331952498720noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-81438541241489092312015-10-23T02:44:00.844+08:002015-10-23T02:44:00.844+08:00When we have 5 we can use (n-k+1)-1 right but stil...When we have 5 we can use (n-k+1)-1 right but still we have to traverse for size which makes it two computations unless we are using some language like Java as Asu commented.<br /><br />So now:<br /><br />if(n.size == even){<br /> return (n-k+1)-1;<br />}else{<br /> return (n-k+1);<br />}<br /><br />I know I added one more computation just to keep it more generic for all lists.TheTechGeekhttps://www.blogger.com/profile/16051736037525586107noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-91609317705235532562015-01-28T03:05:40.105+08:002015-01-28T03:05:40.105+08:00In some languages you can get the size of the list...In some languages you can get the size of the list I mean the number of nodes by simple statements using sizeof kind of functions. That would save one traversal. <br /><br />It could be good idea to use the arrays as a temp storage for elements while first pass and then use the indexes for kth element.Asuhttps://www.blogger.com/profile/04163155913537503035noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-7754754854399396502015-01-28T03:05:18.342+08:002015-01-28T03:05:18.342+08:00In some languages you can get the size of the list...In some languages you can get the size of the list I mean the number of nodes by simple statements using sizeof kind of functions. That would save one traversal. <br /><br />It could be good idea to use the arrays as a temp storage for elements while first pass and then use the indexes for kth element.Asuhttps://www.blogger.com/profile/04163155913537503035noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-76686092106330575252014-07-29T15:56:28.559+08:002014-07-29T15:56:28.559+08:00Like someone said above, this method basically imp...Like someone said above, this method basically implements traversing twice and only gives the illusion of one traversal; except in the case of a small value of K. My advice would be to tell the interviewer that if such a requirement is known beforehand, we can create an additional head node which will store the number of nodes in the list. When a new node is added, we can simply incement this count. That way we need to traverse the list only once and the problem is solved while designing the list itself.Anonymoushttps://www.blogger.com/profile/12172437534490822263noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-90023953223922235452013-09-19T02:16:03.336+08:002013-09-19T02:16:03.336+08:00Damn, why can't you edit comments here :D... I...Damn, why can't you edit comments here :D... I actually looked at your code. It sounded much more obscure in the description so in this instance, you may have one advantage of writing it like this and that is for low "K" your CPU cache will still have the delayed list entries of the second pointer in the cache and thus your argument of "doing all at once" might actually fly, but not with your explanation and also only for small "K".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-64892001994106689182013-09-19T02:05:48.787+08:002013-09-19T02:05:48.787+08:00Not to mention that using linkedlists in context o...Not to mention that using linkedlists in context of optimization is a bit ironic :D. If your interviewer asks you for optimizations, tell him not to use linkedlists and he will be pleasently surprised, especially if you can also explain the: Why?!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-33392666951230398482013-09-19T02:02:58.333+08:002013-09-19T02:02:58.333+08:00"We get the total number of nodes with the fi..."We get the total number of nodes with the first scan, and reach the kth node from end with the second scan. Unfortunately, interviewers usually expect a solution which only scans a list once."<br /><br />And unfortunately obscuring the algorithm does not make it any faster. Obviously you need to scan the list once, simply because you need to find the end (the size). Then with a second iteration you go the required amount of steps to the final node. Now, if you count the computational steps, how is that any different to using two pointers "at the same time"? You can't use two pointers at the same time. If you use two pointers you still scan the list twice, isn't that obvious? What you do is simply doing both computations at once, with the full cost and absolutely no optimization and maybe even worse performance, due to potential caching and code flow issues.<br /><br />As Knuth put it: premature optimization is the root of all evil...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-84707110937392059052013-09-16T07:29:58.239+08:002013-09-16T07:29:58.239+08:00That would be a question for your interviewer. It ...That would be a question for your interviewer. It would depend on what behavior was desired. I'd say return null myself, that would indicate no such node exists.Will Morrisonhttps://www.blogger.com/profile/01681705261984219352noreply@blogger.comtag:blogger.com,1999:blog-4228859841453048938.post-32167340891899603942013-08-08T04:09:50.402+08:002013-08-08T04:09:50.402+08:00if there are total 5 nodes instead of six then how...if there are total 5 nodes instead of six then how will your method work?Anonymoushttps://www.blogger.com/profile/01028825389317815375noreply@blogger.com