Amazon Interview Question on Doubly Linked List, Plz help


M

Mahesh

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-
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");
----------------------------------------------------------------------------------------------------------------
 
Ad

Advertisements

R

Richard Heathfield

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.

[email protected]> ./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).
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads


Top