Amazon Interview Question on Doubly Linked List, Plz help

Discussion in 'C Programming' started by Mahesh, Mar 19, 2008.

  1. Mahesh

    Mahesh Guest

    Hi Coders,

    I was asked to write a program to interchange numbers using doubly
    linked list @ Amazon.

    Here is the details with Code that i wrote.

    i/p: 1 2 3 4 5 6 7 8 .....n,n-1.
    o/p: 2 1 4 3 6 5 8 7.....n,n-1.

    I wanted this code to make as small and it should be algorithmically
    fit. The following is just plain without any logic. plz help me to
    solve this algorithmically i.e big oh etc. and it should run fast for
    millions of numbers.

    Thanks a lot.

    Code:
    --------------------------------------------------------------------------------------------
    #define TravelNode 8
    #include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>

    /*
    * Doubly linked Node with Data
    */

    struct node {

    int data;
    struct node *prev;
    struct node *next;
    };

    typedef struct node NODE;

    int main(void) {

    NODE *tempHead,
    *mainHead,
    *head,
    *tail,
    *temp;

    int i=1;

    /*
    * Memory Allocation for head node
    */

    head = (NODE*)malloc(sizeof(NODE));

    /*
    * Save First Node
    */

    tempHead = head;
    temp = head;

    /*
    * Fill data in very first node
    */
    head->data = i++;
    head->next = (NODE*)malloc(sizeof(NODE));
    head->prev = NULL;
    head = head->next;
    head->prev = tempHead;

    printf("\n Begin.... \n");

    /*
    * Fill Data in the Nodes
    */

    while(i < TravelNode ){

    head->data = i++;
    head->prev = temp;
    temp = head;
    head->next = (NODE*)malloc(sizeof(NODE));
    head = head->next;
    head->prev = temp;
    }

    head->data = i;
    head->prev = temp;
    head->next = NULL;

    head = tempHead; // head pointing to
    First Node Now.
    tail = head->next; // tail pointing to
    Second Node.
    mainHead = tail->next; // mainHead Points to 3rd Node.

    /*
    * First Two Node Exchange
    */

    temp = (NODE*)malloc(sizeof(NODE));

    temp = head->prev;
    head->prev = head->next;
    head->next = tail->next->next;
    tail->next = tail->prev;
    tail->prev = temp;

    temp = head->prev;
    mainHead = temp; // This will be used
    for final printing of Data
    from resulted db list

    /*
    * Node interchange Kernel
    */

    while(head->next != NULL){

    head = head->next->prev;
    tail = head->next;
    temp = head->prev;

    if(head->next == NULL){

    head->prev = head->next;
    head->next = tail->next;
    tail->next = tail->prev;
    tail->prev = temp;
    head->next = NULL;
    }

    else {

    head->prev = head->next;
    if(!(tail->next))
    head->next = tail->next;
    else
    head->next = tail->next-
    >next;

    tail->next = tail->prev;
    tail->prev = temp;
    }
    }

    printf("\n");

    i = TravelNode;
    while(i-- > 0){

    printf(" R = %d ", mainHead->data);
    mainHead = mainHead->next;
    }

    free(mainHead);
    printf("\n End.... \n");
    ----------------------------------------------------------------------------------------------------------------
     
    Mahesh, Mar 19, 2008
    #1
    1. Advertising

  2. Mahesh said:

    > Hi Coders,
    >
    > I was asked to write a program to interchange numbers using doubly
    > linked list @ Amazon.
    >
    > Here is the details with Code that i wrote.


    Lose all the casts, and lose malloc.h. Neither are necessary.

    >
    > i/p: 1 2 3 4 5 6 7 8 .....n,n-1.
    > o/p: 2 1 4 3 6 5 8 7.....n,n-1.
    >
    > I wanted this code to make as small and it should be algorithmically
    > fit. The following is just plain without any logic. plz help me to
    > solve this algorithmically i.e big oh etc. and it should run fast for
    > millions of numbers.


    I can't see any way to avoid it being an O(n) problem. So your best bet is
    simply to crank through the nodes.

    What you've posted doesn't actually compile, by the way. But this does:

    #include <stdio.h>
    #include <stdlib.h>

    #define NUM_NODES 8

    /* simple linked list node type */
    struct node_
    {
    int data;
    struct node_ *prev;
    struct node_ *next;
    };

    typedef struct node_ node;

    /* function prototypes */
    node *node_new(int n);
    int list_splice(node *left, node *right);
    int node_demote(node *shovee);
    int list_iterate(node *list, int exec(int, void *), void *extra);
    int list_dump(int data, void *extra);
    void list_destroy(node **head);

    /* create a new node for a linked list */
    node *node_new(int n)
    {
    node *new = malloc(sizeof *new);
    if(new != NULL)
    {
    new->data = n;
    new->prev = NULL;
    new->next = NULL;
    }
    return new;
    }

    /* join two lists together, given the tail
    * of the first and the head node of the second.
    */
    int list_splice(node *tail, node *head)
    {
    int rc = 0;
    if(tail->next != NULL || head->prev != NULL)
    {
    rc = 1; /* error */
    }
    else
    {
    tail->next = head;
    head->prev = tail;
    }
    return rc;
    }

    /* move this node one place nearer the tail */
    int node_demote(node *this)
    {
    int rc = 0;
    if(this != NULL && this->next != NULL)
    {
    node *prev = this->prev;
    node *next = this->next;
    if(prev != NULL)
    {
    prev->next = next;
    }
    next->prev = prev;
    if(next->next != NULL)
    {
    next->next->prev = this;
    }
    this->next = next->next;
    next->next = this;
    this->prev = next;
    }
    else
    {
    rc = 1; /* nowhere to shove - already at tail */
    }
    return rc;
    }

    /* iterate through every node in the list, executing
    * the function to which a pointer is supplied, and
    * passing it the node data and an 'extra' pointer
    * for anything else the function might need.
    * The function thus indicated must be of type
    * int(int, void *), and must return 0 for a
    * successful invocation. The iteration will halt
    * when the called function returns non-zero or
    * all nodes have been visited.
    */
    int list_iterate(node *list, int exec(int, void *), void *extra)
    {
    int rc = 0;
    while(rc == 0 && list != NULL)
    {
    rc = (*exec)(list->data, extra);
    list = list->next;
    }
    return rc;
    }

    /* an iteration function for displaying the list */
    int list_dump(int data, void *extra)
    {
    FILE *fp = extra;
    fprintf(fp, " %d", data);
    return ferror(fp);
    }

    /* destroy the list, making the pointer explicitly
    * invalid (NULL), which is why we need node **
    */
    void list_destroy(node **head)
    {
    if(*head != NULL)
    {
    node *cur = *head;
    while(cur != NULL)
    {
    node *tmp = cur->next;
    free(cur);
    cur = tmp;
    }
    *head = NULL;
    }
    }

    int main(void)
    {
    node *head = NULL;
    node *new = NULL;
    node *tail = NULL;
    node *curr = NULL;

    int i = 1;

    /* start off by building the list */
    tail = head = node_new(i++);
    if(head != NULL)
    {
    while(i <= NUM_NODES)
    {
    new = node_new(i++);
    if(new != NULL)
    {
    list_splice(tail, new);
    tail = tail->next;
    }
    }

    /* display the unmodified list */
    printf(" List is now built:");
    list_iterate(head, list_dump, stdout);
    putchar('\n');

    /* demote every other node */
    curr = head;

    while(node_demote(curr) == 0)
    {
    if(curr != NULL)
    {
    curr = curr->next;
    }
    }
    /* head is no longer at the beginning of the list! So "rewind" it */
    while(head->prev != NULL)
    {
    head = head->prev;
    }

    /* display the modified list */
    printf("List is now swapped:");
    list_iterate(head, list_dump, stdout);
    putchar('\n');

    /* clean up */
    list_destroy(&head);
    }
    return 0;
    }

    Here's a trial run.

    me@here> ./foo
    List is now built: 1 2 3 4 5 6 7 8
    List is now swapped: 2 1 4 3 6 5 8 7

    Change NUM_NODES to 9 to ensure that it works for odd numbers.

    According to gprof, each invocation of the demotion function takes about 40
    nanoseconds to execute (on a test list of 1,000,000 nodes, with the
    program modified throughout to use long int rather than int for the data).

    --
    Richard Heathfield <http://www.cpax.org.uk>
    Email: -http://www. +rjh@
    Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
    "Usenet is a strange place" - dmr 29 July 1999
     
    Richard Heathfield, Mar 19, 2008
    #2
    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. murali@pune

    doubly linked list

    murali@pune, Mar 23, 2006, in forum: Java
    Replies:
    3
    Views:
    954
    bugbear
    Mar 24, 2006
  2. darth
    Replies:
    0
    Views:
    480
    darth
    Apr 30, 2004
  3. chand
    Replies:
    7
    Views:
    336
    Terry Reedy
    Sep 5, 2005
  4. Daniel
    Replies:
    5
    Views:
    401
  5. zoro
    Replies:
    2
    Views:
    315
Loading...

Share This Page