Velocity Reviews > Amazon Interview Question on Doubly Linked List, Plz help

# Amazon Interview Question on Doubly Linked List, Plz help

Mahesh
Guest
Posts: n/a

 03-19-2008
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");
----------------------------------------------------------------------------------------------------------------

Richard Heathfield
Guest
Posts: n/a

 03-19-2008
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

 Thread Tools

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post zoro C++ 2 11-20-2006 12:53 PM murali@pune Java 3 03-24-2006 09:30 AM Andersen Java 17 11-01-2005 12:02 PM alkzy Microsoft Certification 0 10-31-2004 10:04 PM Nick Computer Support 0 06-04-2004 08:50 PM

Advertisments