Delete every mth element in a linked list ??

Discussion in 'C Programming' started by Aditya, Dec 20, 2006.

  1. Aditya

    Aditya Guest

    This is a normal interview question, which goes like this
    "Given a linked list of integers, delete every mth node and return the
    last remaining node."

    eg: Linked list = 4->6->7->3->5->6->10->1->23->17
    Delete every 3rd node (m = 3) and return the last remaining node
    meaning...
    4->6->3->5->10->1->17
    4->3->5->1->17
    3->5->17
    3->17
    3

    after deleting every 3rd node the last remaining node is 3, so node
    with data 3 is returned.
    function prototype:

    node* deleteEveryMth(node** head, int m)
    {
    // .... your code

    }

    thanks
    A
     
    Aditya, Dec 20, 2006
    #1
    1. Advertising

  2. Aditya said:

    > This is a normal interview question, which goes like this
    > "Given a linked list of integers, delete every mth node and return the
    > last remaining node."
    >
    > eg: Linked list = 4->6->7->3->5->6->10->1->23->17
    > Delete every 3rd node (m = 3) and return the last remaining node
    > meaning...
    > 4->6->3->5->10->1->17
    > 4->3->5->1->17
    > 3->5->17
    > 3->17
    > 3
    >
    > after deleting every 3rd node the last remaining node is 3, so node
    > with data 3 is returned.
    > function prototype:
    >
    > node* deleteEveryMth(node** head, int m)
    > {
    > // .... your code


    No, yours.

    --
    Richard Heathfield
    "Usenet is a strange place" - dmr 29/7/1999
    http://www.cpax.org.uk
    email: rjh at the above domain, - www.
     
    Richard Heathfield, Dec 20, 2006
    #2
    1. Advertising

  3. Aditya

    Ian Collins Guest

    Aditya wrote:
    > This is a normal interview question, which goes like this
    > "Given a linked list of integers, delete every mth node and return the
    > last remaining node."
    >

    Please don't post to multiple groups, cross post if you must, or better
    still, post to one group.

    --
    Ian Collins.
     
    Ian Collins, Dec 20, 2006
    #3
  4. Aditya

    jaysome Guest

    On 20 Dec 2006 01:36:00 -0800, "Aditya" <> wrote:

    >This is a normal interview question, which goes like this


    I've never asked this question in an interview, nor do I ever plan to.
    I guess I must be abnormal.

    >"Given a linked list of integers, delete every mth node and return the
    >last remaining node."
    >
    >eg: Linked list = 4->6->7->3->5->6->10->1->23->17
    >Delete every 3rd node (m = 3) and return the last remaining node
    >meaning...
    >4->6->3->5->10->1->17
    >4->3->5->1->17
    >3->5->17
    >3->17
    >3
    >
    >after deleting every 3rd node the last remaining node is 3, so node
    >with data 3 is returned.
    >function prototype:
    >
    >node* deleteEveryMth(node** head, int m)
    >{
    > // .... your code
    >
    >}


    I have no clue.

    But if, and when, I ever need to know how to delete every mth node in
    a linked list of integers, I'll spend the time to learn how to do it
    right, and I'll get it right. And the customer will pay me dearly for
    it.

    At an interview, I start off with asking very simple questions, like
    what's wrong with the following statements?

    void main(void);
    i = i++ % MAX_VAL;
    p = (int*)malloc(4 * 4);
    int main(void) {return -1;}
    goto ERROR;
    gets(s);
    fflush(STDIN);
    #define N X+1
    unsigned i; for(i=1;i>=0;i--)
    while(1)

    Once they answer those questions, it's usually easy to determine where
    the interview is headed.

    --
    jay
     
    jaysome, Dec 20, 2006
    #4
  5. jaysome said:

    <snip>
    >
    > At an interview, I start off with asking very simple questions,


    Ooh, ooh, I love these...

    > like
    > what's wrong with the following statements?
    >
    > void main(void);


    It's not a statement.

    > i = i++ % MAX_VAL;


    MAX_VAL is undefined, so you can't take its percentage.

    > p = (int*)malloc(4 * 4);


    (int*): malloc returns a pointer, and you can't multiply ints by pointers.

    > int main(void) {return -1;}


    The actual program has been left out.

    > goto ERROR;


    goto can't be an error; it's a keyword, so it's built into the language.

    > gets(s);


    Should be: s = gets(s);

    > fflush(STDIN);


    Ah, good old case sensitivity. This should of course be FFLUSH(STDIN);

    > #define N X+1


    As everyone knows, X stands for unknown, so X+1 is meaningless.

    > unsigned i; for(i=1;i>=0;i--)


    i is a lousy name for a variable. Better:

    unsigned eternity_ring; for(eternity_ring = 1;
    eternity_ring >= 0;
    eternity_ring --)

    Note the cool formatting, which should ensure that I get 11/10 for this
    quiz.

    > while(1)


    Should be while(2), as it is the second loop in this test.

    > Once they answer those questions, it's usually easy to determine where
    > the interview is headed.


    How did I do? :)

    --
    Richard Heathfield
    "Usenet is a strange place" - dmr 29/7/1999
    http://www.cpax.org.uk
    email: rjh at the above domain, - www.
     
    Richard Heathfield, Dec 20, 2006
    #5
  6. Richard Heathfield <> writes:

    > jaysome said:
    >> At an interview, I start off with asking very simple questions,

    ....
    >> Once they answer those questions, it's usually easy to determine
    >> where the interview is headed.

    >
    > How did I do? :)


    Considering your answers as a coherent whole, I'd hire you.

    mlp
     
    Mark L Pappin, Dec 20, 2006
    #6
  7. Aditya

    Barry Guest

    "Aditya" <> wrote in message
    news:...
    > This is a normal interview question, which goes like this
    > "Given a linked list of integers, delete every mth node and return the
    > last remaining node."
    >
    > eg: Linked list = 4->6->7->3->5->6->10->1->23->17
    > Delete every 3rd node (m = 3) and return the last remaining node
    > meaning...
    > 4->6->3->5->10->1->17
    > 4->3->5->1->17
    > 3->5->17
    > 3->17
    > 3
    >
    > after deleting every 3rd node the last remaining node is 3, so node
    > with data 3 is returned.
    > function prototype:
    >
    > node* deleteEveryMth(node** head, int m)
    > {
    > // .... your code
    >
    > }
    >
    > thanks
    > A
    >


    The example looks broken. And how do you delete the 3rd node
    from a list with two entries?
     
    Barry, Dec 20, 2006
    #7
  8. Aditya

    Barry Guest

    "Richard Heathfield" <> wrote in message
    news:...
    > jaysome said:
    >
    > <snip>
    > >
    > > At an interview, I start off with asking very simple questions,

    >
    > Ooh, ooh, I love these...
    > > unsigned i; for(i=1;i>=0;i--)

    >
    > i is a lousy name for a variable. Better:
    >
    > unsigned eternity_ring; for(eternity_ring = 1;
    > eternity_ring >= 0;
    > eternity_ring --)
    >
    > Note the cool formatting, which should ensure that I get 11/10 for this
    > quiz.
    >
    > > while(1)

    >
    > Should be while(2), as it is the second loop in this test.
    >

    I would have missed this one I would have said it should be:
    unsigned i; for(i=1;i>=0;i--)
     
    Barry, Dec 20, 2006
    #8
  9. Barry said:

    <snip>

    > The example looks broken. And how do you delete the 3rd node
    > from a list with two entries?


    Like this.

    --
    Richard Heathfield
    "Usenet is a strange place" - dmr 29/7/1999
    http://www.cpax.org.uk
    email: rjh at the above domain, - www.
     
    Richard Heathfield, Dec 20, 2006
    #9
  10. Aditya

    Random832 Guest

    2006-12-20 <>,
    jaysome wrote:
    > void main(void);


    Nothing, assuming that main is never used in the scope in which this
    declaration appears.

    > p = (int*)malloc(4 * 4);

    There's several things wrong with it. The most obvious one is casting
    malloc, but there's also the assumption that int has a size of 4.

    > int main(void) {return -1;}


    The range of values that main may return is implementation-defined. On
    some implementations (this answer is appropriate if interviewing for
    a position where you know you'll be programming for windows or unix), it
    must be between 0 and 255. For portable code, it must be 0,
    EXIT_SUCCESS, or EXIT_FAILURE.

    > goto ERROR;


    ERROR is a reserved identifier. (I hope this is what you were looking
    for, rather than some trite condemnation of the use of "goto" without
    seeing the context)

    > fflush(STDIN);


    Nothing, assuming that STDIN is of type FILE * and points to a file
    opened for output. However, isn't that a bit of a trick question? It'd
    be bad programming practice to use that name anyway I guess.

    > unsigned i; for(i=1;i>=0;i--)


    i will wrap around to at least 65535 after reaching 0; it will never
    become less than 0.

    > while(1)


    Not sure I see the problem here. for(;;) might be better style.

    If you think it's less efficient, this says more about the interviewer
    than the interviewee.

    > Once they answer those questions, it's usually easy to determine where
    > the interview is headed.
     
    Random832, Dec 20, 2006
    #10
  11. Aditya

    jaysome Guest

    On Wed, 20 Dec 2006 10:42:51 +0000, Richard Heathfield
    <> wrote:

    >jaysome said:
    >
    ><snip>
    >>
    >> At an interview, I start off with asking very simple questions,

    >
    >Ooh, ooh, I love these...
    >
    >> like
    >> what's wrong with the following statements?
    >>
    >> void main(void);

    >
    >It's not a statement.
    >
    >> i = i++ % MAX_VAL;

    >
    >MAX_VAL is undefined, so you can't take its percentage.
    >
    >> p = (int*)malloc(4 * 4);

    >
    >(int*): malloc returns a pointer, and you can't multiply ints by pointers.
    >
    >> int main(void) {return -1;}

    >
    >The actual program has been left out.
    >
    >> goto ERROR;

    >
    >goto can't be an error; it's a keyword, so it's built into the language.
    >
    >> gets(s);

    >
    >Should be: s = gets(s);
    >
    >> fflush(STDIN);

    >
    >Ah, good old case sensitivity. This should of course be FFLUSH(STDIN);
    >
    >> #define N X+1

    >
    >As everyone knows, X stands for unknown, so X+1 is meaningless.
    >
    >> unsigned i; for(i=1;i>=0;i--)

    >
    >i is a lousy name for a variable. Better:
    >
    > unsigned eternity_ring; for(eternity_ring = 1;
    > eternity_ring >= 0;
    > eternity_ring --)
    >
    >Note the cool formatting, which should ensure that I get 11/10 for this
    >quiz.
    >
    >> while(1)

    >
    >Should be while(2), as it is the second loop in this test.
    >
    >> Once they answer those questions, it's usually easy to determine where
    >> the interview is headed.

    >
    >How did I do? :)


    Further interrogation would be required to determine that. I must
    admit that, based on your answers, I would need to excuse myself for a
    moment while I grabbed my Schildt hard-copy of the standard. I'd
    recite a good number of carefully chosen passages from the text of the
    book, and simply ask you after each citation: "Am I reading from the
    left or the right page"? Answer them all and you'd score an 11.

    Happy Holidays
    --
    jay
     
    jaysome, Dec 21, 2006
    #11
  12. jaysome said:

    > On Wed, 20 Dec 2006 10:42:51 +0000, Richard Heathfield
    > <> wrote:


    <snip>

    >>How did I do? :)

    >
    > Further interrogation would be required to determine that. I must
    > admit that, based on your answers, I would need to excuse myself for a
    > moment while I grabbed my Schildt hard-copy of the standard. I'd
    > recite a good number of carefully chosen passages from the text of the
    > book, and simply ask you after each citation: "Am I reading from the
    > left or the right page"? Answer them all and you'd score an 11.


    Easy-peasy. "Yes. Yes. Yes." (Watching interviewer's eyes carefully...) "No,
    you just made that one up. Yes. Yes. No. ..."

    --
    Richard Heathfield
    "Usenet is a strange place" - dmr 29/7/1999
    http://www.cpax.org.uk
    email: rjh at the above domain, - www.
     
    Richard Heathfield, Dec 21, 2006
    #12
    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:
    510
    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:
    501
    emerth
    Jul 10, 2003
  3. fool
    Replies:
    14
    Views:
    541
    Barry Schwarz
    Jul 3, 2006
  4. joshd
    Replies:
    12
    Views:
    699
    John Carson
    Oct 2, 2006
  5. Aditya
    Replies:
    5
    Views:
    472
    Mark P
    Dec 20, 2006
Loading...

Share This Page