468,253 Members | 1,241 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,253 developers. It's quick & easy.

Amazon Interview Question on Doubly Linked List, Plz help

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");
----------------------------------------------------------------------------------------------------------------
Mar 19 '08 #1
1 1991
Mahesh wrote:
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.

/* BEGIN bubble_llist.c */

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

#define N 8

typedef struct list_node {
struct list_node *next;
void *data;
struct list_node *prev;
} llist_type;

llist_type *llist_append
(llist_type **head, llist_type *tail, void *data, size_t size);
int u_fprintf(const llist_type *head, FILE *stream);
void llist_free(llist_type *node, void (*free_data)(void *));
llist_type *bubble_llist(llist_type *head);

int main(void)
{
unsigned count;
llist_type *head, *tail;

puts("/* BEGIN bubble_llist.c output */\n");
head = tail = NULL;
for (count = 1; count != N + 1u; ++count) {
tail = llist_append(&head, tail, &count, sizeof count);
if (tail == NULL) {
puts("malloc trouble!");
break;
}
}
u_fprintf(head, stdout);
putchar('\n');
head = bubble_llist(head);
u_fprintf(head, stdout);
llist_free(head, free);
puts("\n/* END bubble_llist.c output */");
return 0;
}

llist_type *bubble_llist(llist_type *head)
{
llist_type *ret;

if (head != NULL && head -next != NULL) {
ret = head -next;
for (;;) {
const llist_type first = *head;
const llist_type second = *first.next;

second.prev -prev = first.next;
second.prev -next = second.next;
first.next -prev = first.prev;
first.next -next = second.prev;
head = second.next;
if (head != NULL) {
head -prev = second.prev;
if (head -next != NULL) {
second.prev -next = head -next;
} else {
break;
}
} else {
break;
}
}
} else {
ret = head;
}
return ret;
}

llist_type *llist_append
(llist_type **head, llist_type *tail, void *data, size_t size)
{
llist_type *node;

node = malloc(sizeof *node);
if (node != NULL) {
node -prev = tail;
node -next = NULL;
node -data = malloc(size);
if (node -data != NULL) {
memcpy(node -data, data, size);
if (*head != NULL) {
tail -next = node;
} else {
*head = node;
}
} else {
free(node);
node = NULL;
}
}
return node;
}

int u_fprintf(const llist_type *head, FILE *stream)
{
int rc = 0;

while (head != NULL) {
const unsigned *const u_ptr = head -data;

if (0 (rc = fprintf(stream, "%u\n", *u_ptr))) {
break;
}
head = head -next;
}
return rc;
}

void llist_free(llist_type *node, void (*free_data)(void *))
{
llist_type *next_node;

while (node != NULL) {
next_node = node -next;
free_data(node -data);
free(node);
node = next_node;
}
}

/* END bubble_llist.c */
--
pete
Jun 27 '08 #2

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

54 posts views Thread by Spammay Blockay | last post: by
3 posts views Thread by surrealtrauma | last post: by
4 posts views Thread by dssuresh6 | last post: by
5 posts views Thread by free2cric | last post: by
1 post views Thread by drewy2k12 | last post: by
2 posts views Thread by murali | last post: by
3 posts views Thread by maruf.syfullah | last post: by
5 posts views Thread by adam.kleinbaum | last post: by
reply views Thread by kermitthefrogpy | last post: by
reply views Thread by zattat | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.