425,611 Members | 1,642 Online
Need help? Post your question and get tips & solutions from a community of 425,611 IT Pros & Developers. It's quick & easy.

 P: n/a Hello, I got an interview question and didn't understand a concept being asked for. Here is the question: Write a function that would: return the 5th element from the end in a singly linked list of integers, in one pass, and then provide a set of test cases against that function. What does "in one pass" mean and can you give an example????? Thanks Jami Apr 24 '06 #1
14 Replies

 P: n/a "jamihuq" writes: I got an interview question and didn't understand a concept being asked for. Here is the question: Write a function that would: return the 5th element from the end in a singly linked list of integers, in one pass, and then provide a set of test cases against that function. What does "in one pass" mean and can you give an example????? One way to do this is to go through the linked list counting the number of elements, then go back through it again and return the 5th from the end. That takes two passes. The interview question is asking you to find a way to do so without making the second pass. I can think of two ways, off-hand; one requires modifying the list, the other does not. -- int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\ \n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\ );while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\ );}return 0;} Apr 24 '06 #2

 P: n/a jamihuq wrote On 04/24/06 11:37,: Hello, I got an interview question and didn't understand a concept being asked for. Here is the question: Write a function that would: return the 5th element from the end in a singly linked list of integers, in one pass, and then provide a set of test cases against that function. What does "in one pass" mean and can you give an example????? This is an algorithms question, not a C language question, so a forum like comp.programming would be a better place to ask it. "One pass," in this context, probably means that you may traverse the list only once. Imagine that each reference to the "next" pointer in a node of the list costs you a dollar, and look for a solution that minimizes your out-of-pocket expense. By contrast, a "two-pass" solution might walk the entire list once to count the number of nodes, N, and then start over at the beginning of the list again and walk over the first N-5 nodes. This costs 2N-5 dollars (with a quibble about whether getting a pointer to the first node is or isn't free); can you find a cheaper solution? -- Er*********@sun.com Apr 24 '06 #3

 P: n/a jamihuq wrote: Hello, I got an interview question and didn't understand a concept being asked for. Here is the question: Write a function that would: return the 5th element from the end in a singly linked list of integers, in one pass, and then provide a set of test cases against that function. What does "in one pass" mean and can you give an example????? Exactly what it sounds like -- "in one pass". In other words, you are not allowed to go through the list more than once (ie: "more than one pass".) An example of a two-pass solution: Pass one: Go through the list and count the number of items in the list. Pass two: Go through the list again, until you hit the 5th element from the last (ie: item N-4). The question at hand is "how do you do it without using a second pass?" -- +-------------------------+--------------------+-----------------------------+ | Kenneth J. Brody | www.hvcomputer.com | | | kenbrody/at\spamcop.net | www.fptech.com | #include | +-------------------------+--------------------+-----------------------------+ Don't e-mail me at: Apr 24 '06 #4

 P: n/a Kenneth Brody wrote: jamihuq wrote: Hello, I got an interview question and didn't understand a concept being asked for. Here is the question: Write a function that would: return the 5th element from the end in a singly linked list of integers, in one pass, and then provide a set of test cases against that function. What does "in one pass" mean and can you give an example????? Exactly what it sounds like -- "in one pass". In other words, you are not allowed to go through the list more than once (ie: "more than one pass".) An example of a two-pass solution: Pass one: Go through the list and count the number of items in the list. Pass two: Go through the list again, until you hit the 5th element from the last (ie: item N-4). The question at hand is "how do you do it without using a second pass?" [OT] Is it cheating if your linked-list stores its current size in a struct member? I almost always do that so that I can implement various "Count" functions trivially. That is, I assume the small amount of time and space to update the count on insert (and decrement on remove) pays off if you can minimize walking the entire list (or a portion thereof) for some actions. Apr 24 '06 #5

 P: n/a "void * clvrmnky()" writes: Is it cheating if your linked-list stores its current size in a struct member? I almost always do that so that I can implement various "Count" functions trivially. That is, I assume the small amount of time and space to update the count on insert (and decrement on remove) pays off if you can minimize walking the entire list (or a portion thereof) for some actions. There's a tradeoff: * If you make the "count" operation constant-time, by storing and updating the item count explicitly, then the "splice" operation that moves an arbitrary number of items from one list to another becomes O(n) in the number of items. * If you make "count" O(n), then "splice" is easy to make O(1). I suppose there's the possibility of making each iterator know where it is in the list, so that both operations can be O(1), but that sounds difficult to implement reliably and would increase the cost of traversal. -- "IMO, Perl is an excellent language to break your teeth on" --Micah Cowan Apr 24 '06 #6

 P: n/a Kenneth Brody wrote: The question at hand is "how do you do it without using a second pass?" Can't someone tell how to do it? I'm curious :) Apr 24 '06 #7

 P: n/a edware wrote: Kenneth Brody wrote: > > The question at hand is "how do you do it without using a second pass?" > Can't someone tell how to do it? I'm curious :) It's simple to find the fifth item from last in singlelink list in singlepass. I shall give u logic here. counter = 0; fifthnode = list->getnode(); //assigning firstnode while(list->getNext() != null) { if(counter >= 5) fifthnode = fifthnode -> next(); else counter++; list->goNext(); } if(counter < 5) return -1; //list contains less then five else return fifthnode->getVallue(); Apr 24 '06 #8

 P: n/a Ben Pfaff wrote: "void * clvrmnky()" writes: Is it cheating if your linked-list stores its current size in a struct member? I almost always do that so that I can implement various "Count" functions trivially. That is, I assume the small amount of time and space to update the count on insert (and decrement on remove) pays off if you can minimize walking the entire list (or a portion thereof) for some actions. There's a tradeoff: * If you make the "count" operation constant-time, by storing and updating the item count explicitly, then the "splice" operation that moves an arbitrary number of items from one list to another becomes O(n) in the number of items. * If you make "count" O(n), then "splice" is easy to make O(1). Ah. Therein lies my ignorance. I've never implemented a splice operation. My typical usage is a single list maintained for some smallish amount of time. Point taken. Apr 24 '06 #9

 P: n/a -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 edware wrote: Kenneth Brody wrote: The question at hand is "how do you do it without using a second pass?" Can't someone tell how to do it? I'm curious :) As the old joke goes: "Watch for the end, and get off 5 stops before." Think about it. - -- Lew Pitcher, IT Specialist, Corporate Technology Solutions, Enterprise Technology Solutions, TD Bank Financial Group (Opinions expressed here are my own, not my employer's) -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.2.2 (MingW32) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFETQ+hagVFX4UWr64RAp8dAKDIiJ8eYbkqIS5VB1hWN0 66qezvZgCdHVkz MaHshI2P+WA/jGrRFvbktho= =Rqu9 -----END PGP SIGNATURE----- Apr 24 '06 #10

 P: n/a pr*******@gmail.com wrote On 04/24/06 13:50,: edware wrote:Kenneth Brody wrote: > > The question at hand is "how do you do it without using a second pass?" >Can't someone tell how to do it? I'm curious :) It's simple to find the fifth item from last in singlelink list in singlepass. I shall give u logic here. counter = 0; fifthnode = list->getnode(); //assigning firstnode while(list->getNext() != null) { if(counter >= 5) fifthnode = fifthnode -> next(); else counter++; list->goNext(); } if(counter < 5) return -1; //list contains less then five else return fifthnode->getVallue(); I would not call this a single pass, but two passes that execute in parallel. Of course, "pass" is imprecisely defined, and it's possible the O.P.'s interlocutor might have been pleased with this solution. I don't think so, though, since there is at least one solution that visits each node just once. -- Er*********@sun.com Apr 24 '06 #11

 P: n/a -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 edware wrote: Kenneth Brody wrote: The question at hand is "how do you do it without using a second pass?" Can't someone tell how to do it? I'm curious :) Here's a second hint... Assuming a list node defined something like struct node { struct node *next; int valu; }; and a cursor into the list that looks like struct node *cursor; then cursor points to the current node cursor->next points to the 1st node after the current one cursor->next->next points to the 2nd node cursor->next->next->next points to the 3rd node cursor->next->next->next->next points to the 4th node cursor->next->next->next->next->next points to the 5th node If cursor->next->next->next->next->next points to the end of the list, then cursor must point to the entry that is fifth from the end of the list. Go to the end of the list, and get off five nodes before. - -- Lew Pitcher, IT Specialist, Corporate Technology Solutions, Enterprise Technology Solutions, TD Bank Financial Group (Opinions expressed here are my own, not my employer's) -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.2.2 (MingW32) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFETRmnagVFX4UWr64RAjBhAKCgGYKivyDfhuXkSG+6z/d5f/BCzgCghwxo FlBMeW/AXNHsDRPgaLDC2pY= =p7Oi -----END PGP SIGNATURE----- Apr 24 '06 #12

 P: n/a Lew Pitcher wrote: -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 edware wrote: Kenneth Brody wrote: The question at hand is "how do you do it without using a second pass?" Can't someone tell how to do it? I'm curious :) Here's a second hint... Assuming a list node defined something like struct node { struct node *next; int valu; }; and a cursor into the list that looks like struct node *cursor; then cursor points to the current node cursor->next points to the 1st node after the current one cursor->next->next points to the 2nd node cursor->next->next->next points to the 3rd node cursor->next->next->next->next points to the 4th node cursor->next->next->next->next->next points to the 5th node If cursor->next->next->next->next->next points to the end of the list, then cursor must point to the entry that is fifth from the end of the list. Go to the end of the list, and get off five nodes before. But when incrementing the cursor pointer to the next node, (it has to do that right? in order to traverse the list), wont the cursor->next->next->next... statement dereference the next pointer five additional times? Doesn't that break the rule Eric Sosman pointed out? Anyway, if I'm wrong, how do one accomplish this with an arbitrary number instead of 5? Apr 24 '06 #13

 P: n/a Ben Pfaff wrote: "void * clvrmnky()" writes: Is it cheating if your linked-list stores its current size in a struct member? I almost always do that so that I can implement various "Count" functions trivially. That is, I assume the small amount of time and space to update the count on insert (and decrement on remove) pays off if you can minimize walking the entire list (or a portion thereof) for some actions. There's a tradeoff: * If you make the "count" operation constant-time, by storing and updating the item count explicitly, then the "splice" operation that moves an arbitrary number of items from one list to another becomes O(n) in the number of items. * If you make "count" O(n), then "splice" is easy to make O(1). or 3) have splice set count to -1, and recalculate when needed. Apr 24 '06 #14

 P: n/a edware wrote: Kenneth Brody wrote: > > The question at hand is "how do you do it without using a second pass?" > Can't someone tell how to do it? I'm curious :) Here's a "gedanken experiment" for you to help figure it out. Picture the singly-linked list as a series of rooms, each with a door to the next. (You can't go back out the door you came in, and you can't go out the "out" door until you have closed the "in" door.) The end-of-list is signalled by a locked "out" door. Each room has a piece of paper with an address written on it. Tell me the address written down in the next- to-last room. (Remember, you can't peek into the previous room, as you already closed the door.) How would you go about doing that? What if you needed the one before the next-to-last room? What if you needed the fifth-from-last room, as in the original post? -- +-------------------------+--------------------+-----------------------------+ | Kenneth J. Brody | www.hvcomputer.com | | | kenbrody/at\spamcop.net | www.fptech.com | #include | +-------------------------+--------------------+-----------------------------+ Don't e-mail me at: Apr 24 '06 #15

### This discussion thread is closed

Replies have been disabled for this discussion.