Linked List

Discussion in 'C++' started by source, Apr 4, 2004.

  1. source

    source Guest

    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.

    And please dont think this is my homework.
    Can anybody simple tell me how this can be done. I am preparing for an
    interview and wanted to know how to go about implementing this.
    Or atleast tell me where I can find few examples on traversing Lists.
    Even if I can get any good resources which explains lists properly my
    job will be done.
     
    source, Apr 4, 2004
    #1
    1. Advertising

  2. source

    Siemel Naran Guest

    "source" <> wrote in message

    > 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.


    Show us your best effort so far. Also try to write a function that finds
    the 5th element in a container matching a certain condition (for example,
    the element is >10).
     
    Siemel Naran, Apr 4, 2004
    #2
    1. Advertising

  3. source

    osmium Guest

    source writes:

    > 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.
    >
    > And please dont think this is my homework.
    > Can anybody simple tell me how this can be done. I am preparing for an
    > interview and wanted to know how to go about implementing this.
    > Or atleast tell me where I can find few examples on traversing Lists.
    > Even if I can get any good resources which explains lists properly my
    > job will be done.


    If I understand the question, it can't be done; at least on a bare bones
    linked list. You will have to count the elements so you can subtract five
    from that. And then traverse the list again, which would be easiest from
    the head end. I call that two passes, not one that you asked for. My
    default meaning for end is the far end; I call the other end the beginning.

    For test cases, test for within range, each valid boundary and one beyond
    each valid boundary. Valid because numbering might start with zero or one.
     
    osmium, Apr 4, 2004
    #3
  4. source

    Siemel Naran Guest

    "osmium" <> wrote in message news:c4pnvn$2kbbqu$1@ID-

    > > 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.


    > If I understand the question, it can't be done; at least on a bare bones
    > linked list. You will have to count the elements so you can subtract five
    > from that. And then traverse the list again, which would be easiest from
    > the head end. I call that two passes, not one that you asked for. My
    > default meaning for end is the far end; I call the other end the

    beginning.

    You can do it in one pass. The first way to implement it could actually be
    slower than the 2 pass method, and the second way would probably be faster.


    > For test cases, test for within range, each valid boundary and one beyond
    > each valid boundary. Valid because numbering might start with zero or

    one.

    I'd say the empty list, list of 1 element, list of 5 elements, list of >5
    elements.
     
    Siemel Naran, Apr 4, 2004
    #4
  5. source

    David Harmon Guest

    On 4 Apr 2004 12:05:51 -0700 in comp.lang.c++,
    (source) wrote,
    >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.


    This sentence no verb.

    What I consider the usual approach to that kind of thing is what I call
    a "following pointer". That is, you have two iterators, one points to
    where you are looking in the list and the other five items behind it.
    You advance both of them at the same time. When you get to what you
    were looking for (in this case, the end) the "following" iterator points
    to what you wanted.

    No doubt you can write the C++ code based on that.
     
    David Harmon, Apr 4, 2004
    #5
  6. source

    Pete Guest

    source wrote:
    > 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.
    >
    > And please dont think this is my homework.
    > Can anybody simple tell me how this can be done. I am preparing for an
    > interview and wanted to know how to go about implementing this.
    > Or atleast tell me where I can find few examples on traversing Lists.
    > Even if I can get any good resources which explains lists properly my
    > job will be done.


    P-code, and without error checking (assumes list is at least 5 long):

    node* node = yourfirstnode;
    node* node5 = node->next->next->next->next;

    for(;;)
    {
    if(node5->next == 0)
    {
    return node->val;
    }
    node = node->next;
    node5 = node5->next;
    }

    - Pete
     
    Pete, Apr 4, 2004
    #6
  7. osmium wrote:

    > source writes:
    >
    >
    >>function that would: return the 5th element from the end in a singly
    >>linked list of integers, in one pass,

    >
    >
    > If I understand the question, it can't be done; at least on a bare bones
    > linked list. You will have to count the elements so you can subtract five
    > from that. And then traverse the list again, which would be easiest from
    > the head end. I call that two passes, not one that you asked for. My
    > default meaning for end is the far end; I call the other end the beginning.
    >


    Keep two pointers. Begin traversing the list with the first. 5 elements
    in, begin traversing with the second. Once the first reaches the end,
    the second will be 5 elements from the end.

    -Kevin
    --
    My email address is valid, but changes periodically.
    To contact me please use the address from a recent posting.
     
    Kevin Goodsell, Apr 4, 2004
    #7
  8. source

    Siemel Naran Guest

    "Pete" <> wrote in message news:yKZbc.14870

    > node* node = yourfirstnode;
    > node* node5 = node->next->next->next->next;


    What happens on a list of 0 to 4 elements?
     
    Siemel Naran, Apr 5, 2004
    #8
  9. Siemel Naran wrote:

    > "Pete" <> wrote in message news:yKZbc.14870
    >
    >
    >>node* node = yourfirstnode;
    >>node* node5 = node->next->next->next->next;

    >
    >
    > What happens on a list of 0 to 4 elements?


    As he noted:

    "P-code, and without error checking (assumes list is at least 5 long):"

    mark
     
    Mark A. Gibbs, Apr 5, 2004
    #9
  10. source

    Siemel Naran Guest

    "Pete" <> wrote in message news:yKZbc.14870

    > node* node = yourfirstnode;
    > node* node5 = node->next->next->next->next;
    >
    > for(;;)
    > {
    > if(node5->next == 0)
    > {
    > return node->val;
    > }
    > node = node->next;
    > node5 = node5->next;
    > }


    Is it really faster than the 2 pass method? In the 2 pass method, first
    visit all N elements for a total of N calls to const_iterator::eek:perator++.
    Then you perform N-5 more calls to operator++. But in the 1 pass method,
    you perform N calls to const_iterator::eek:perator++ on node, and N-5 on node5.
    So don't they both have the same running time?
     
    Siemel Naran, Apr 5, 2004
    #10
  11. source

    Pete Guest

    Siemel Naran wrote:
    > "Pete" <> wrote in message news:yKZbc.14870
    >
    >> node* node = yourfirstnode;
    >> node* node5 = node->next->next->next->next;
    >>
    >> for(;;)
    >> {
    >> if(node5->next == 0)
    >> {
    >> return node->val;
    >> }
    >> node = node->next;
    >> node5 = node5->next;
    >> }

    >
    > Is it really faster than the 2 pass method? In the 2 pass method,
    > first visit all N elements for a total of N calls to
    > const_iterator::eek:perator++. Then you perform N-5 more calls to
    > operator++. But in the 1 pass method, you perform N calls to
    > const_iterator::eek:perator++ on node, and N-5 on node5. So don't they
    > both have the same running time?


    No, it really wouldn't be faster much if at all, but it's much more
    "elegant" IMHO.

    - Pete
     
    Pete, Apr 5, 2004
    #11
  12. source

    David Harmon Guest

    On Mon, 05 Apr 2004 00:42:42 GMT in comp.lang.c++, "Siemel Naran"
    <> wrote,
    >Is it really faster than the 2 pass method? In the 2 pass method, first
    >visit all N elements for a total of N calls to const_iterator::eek:perator++.
    >Then you perform N-5 more calls to operator++. But in the 1 pass method,
    >you perform N calls to const_iterator::eek:perator++ on node, and N-5 on node5.
    >So don't they both have the same running time?


    Nobody said it was faster. The problem spec said "in one pass".
    The question is, with both pointers running through the list like that
    does it count as one pass, or two passes running not quite in parallel?
     
    David Harmon, Apr 5, 2004
    #12
  13. source

    Pete Guest

    Siemel Naran wrote:
    > "Pete" <> wrote in message news:yKZbc.14870
    >
    >> node* node = yourfirstnode;
    >> node* node5 = node->next->next->next->next;
    >>
    >> for(;;)
    >> {
    >> if(node5->next == 0)
    >> {
    >> return node->val;
    >> }
    >> node = node->next;
    >> node5 = node5->next;
    >> }

    >
    > Is it really faster than the 2 pass method? In the 2 pass method,
    > first visit all N elements for a total of N calls to
    > const_iterator::eek:perator++. Then you perform N-5 more calls to
    > operator++. But in the 1 pass method, you perform N calls to
    > const_iterator::eek:perator++ on node, and N-5 on node5. So don't they
    > both have the same running time?


    BTW, this exercise is a good example of a good reason to use a doubly linked
    list, because it's easy to go either forwards or back depending on the
    situation. The extra memory used for the extra pointer per node really isn't
    an issue, usually.

    - Pete
     
    Pete, Apr 5, 2004
    #13
  14. * (source) schriebt:
    > 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 is your definition of "one pass", and does this need to be
    non-destructive?

    --
    A: Because it messes up the order in which people normally read text.
    Q: Why is top-posting such a bad thing?
    A: Top-posting.
    Q: What is the most annoying thing on usenet and in e-mail?
     
    Alf P. Steinbach, Apr 5, 2004
    #14
  15. source

    Siemel Naran Guest

    "Pete" <> wrote in message news:yF2cc.15284
    > Siemel Naran wrote:


    > node* node = yourfirstnode;
    > node* node5 = node->next->next->next->next;
    >
    > for(;;)
    > {
    > if(node5->next == 0)
    > {
    > return node->val;
    > }
    > node = node->next;
    > node5 = node5->next;
    > }


    > > Is it really faster than the 2 pass method? In the 2 pass method,
    > > first visit all N elements for a total of N calls to
    > > const_iterator::eek:perator++. Then you perform N-5 more calls to
    > > operator++. But in the 1 pass method, you perform N calls to
    > > const_iterator::eek:perator++ on node, and N-5 on node5. So don't they
    > > both have the same running time?


    Seems the 2 pass method you maintain an index for looping from [0, N-5) but
    in the 1 pass method you don't. So based on that the 1 pass method might be
    faster, though the improvement is probably negligible.


    > BTW, this exercise is a good example of a good reason to use a doubly

    linked
    > list, because it's easy to go either forwards or back depending on the
    > situation. The extra memory used for the extra pointer per node really

    isn't
    > an issue, usually.


    If going back is not a common operation, the single list could be better.
    Anyway, the point of these 'clever' interview questions is not always to
    mimic reality, but to see how you think through problems, especially the
    logic questions.

    Anyway, I think if you just store the value of the pointer in one pass, you
    could get better


    node* node = yourfirstnode;
    node* node5 = node->next->next->next->next;

    T * last[5] = { &node->val, &node->next->val, ... };

    for(int i=0; ; i = (i==5 ? 0 : 5))
    {
    if(node5->next == 0)
    {
    return last;
    }
    last = &node5->val;
    node5 = node5->next;
    }
     
    Siemel Naran, Apr 5, 2004
    #15
  16. > Is it really faster than the 2 pass method?

    If the time for retrieval of one element is high, then a one pass approach
    is faster than a two pass.
    However the method of using two pointers are actually a two pass algorithm
    in that case (each element is loaded/passed twice).
    A one pass algorithm, that would save time, would cache the elements once
    loaded and maintain a local 5 element list.

    Niels Dybdahl
     
    Niels Dybdahl, Apr 5, 2004
    #16
  17. osmium wrote:
    >
    > source writes:
    >
    > > 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.
    > >
    > > And please dont think this is my homework.
    > > Can anybody simple tell me how this can be done. I am preparing for an
    > > interview and wanted to know how to go about implementing this.
    > > Or atleast tell me where I can find few examples on traversing Lists.
    > > Even if I can get any good resources which explains lists properly my
    > > job will be done.

    >
    > If I understand the question, it can't be done; at least on a bare bones
    > linked list. You will have to count the elements so you can subtract five
    > from that. And then traverse the list again, which would be easiest from
    > the head end. I call that two passes, not one that you asked for. My
    > default meaning for end is the far end; I call the other end the beginning.


    Or simply:
    Use a queue to store exactly 5 pointers to nodes as you traverse the list.
    When you have reached the end of the list, the queue will contain pointers
    to the last 5 list elements.


    --
    Karl Heinz Buchegger
     
    Karl Heinz Buchegger, Apr 5, 2004
    #17
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Chris Ritchey
    Replies:
    7
    Views:
    488
    emerth
    Jul 10, 2003
  2. Chris Ritchey

    Generating a char* from a linked list of linked lists

    Chris Ritchey, Jul 9, 2003, in forum: C Programming
    Replies:
    7
    Views:
    477
    emerth
    Jul 10, 2003
  3. fool
    Replies:
    14
    Views:
    518
    Barry Schwarz
    Jul 3, 2006
  4. joshd
    Replies:
    12
    Views:
    678
    John Carson
    Oct 2, 2006
  5. jawdoc
    Replies:
    9
    Views:
    770
    Chris Thomasson
    Mar 10, 2008
Loading...

Share This Page