Amazon Interview Question on Doubly Linked List, Plz help

[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-

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

[pete]

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