Linked List rearrangement Example 1

/* re-arrange nodes in the LL inplace as below
head : 1->2->3->4->5
output: 1->5->2->4->3
 */

#include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
    int num;
    struct Node *next;
} Node;

Node *newNode(int num)
{
    Node *temp = (Node*) malloc(sizeof(Node));
    temp->num = num;
    temp->next = NULL;
    return temp;
}

void reverse (Node** head)
{
    Node *prev = NULL,  *cur = *head, *next;
    while(cur) {
    next = cur->next;
    cur->next = prev;
    prev = cur;
    cur = next;
    }
    *head = prev;
}

void reArrangeNodes( Node** head)
{
    Node *slow = *head;
    Node *fast = slow->next;
    // find the mid point
    while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
    }
    Node *head1 = *head;
    Node *head2 = slow->next;
    slow->next = NULL;

    reverse(&head2);
    *head = newNode(0);
    Node* cur = *head;
    while(head1 || head2) {
    if (head1) {
        cur->next = head1;
        cur = cur->next;
        head1 = head1->next;
    }

    if (head2) {
        cur->next = head2;
        cur = cur->next;
        head2 = head2->next;
    }
    }
    *head = (*head)->next;
}
int main()
{
    Node *head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
    head->next->next->next->next = newNode(5);
    head->next->next->next->next->next = newNode(6);
    head->next->next->next->next->next = newNode(7);
    printf("Input: ");
    Node *temp = head;
    while(temp) {
    printf ("%d ", temp->num);
    temp = temp->next;
    }
    printf("\n");
    reArrangeNodes(&head);
    printf("output: ");
    while(head) {
    printf("%d ", head->num);
    head=head->next;
    }
    printf("\n");
    return 0;
}

compare two string represented as Linked List similar to strcmp

/* compare two string represented as LL similar to strcmp */

#include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
  char c;
  struct Node *next;
}Node;

Node* newNode(char c)
{
  Node *temp = (Node*) malloc (sizeof(Node));
  temp->c = c;
  temp->next = NULL;
  return temp;
};

int compare( Node *list1, Node *list2)
{
  while (list1 && list2 && (list1->c == list2->c))
      {
        list1 = list1->next;
        list2 = list2->next;
      }

   if (list1 && list2)
      return (list1->c >  list2->c) ? 1 : -1;

   if (list1 && !list2)
      return 1;
   if (!list1 && list2)
       return -1;
   return 0;
}

int main()
{
  Node *list1 = newNode('p');
  list1->next = newNode('e');
  list1->next->next = newNode('a');
  list1->next->next->next = newNode('c');

  Node *list2 = newNode('p');
  list2->next = newNode('e');
  list2->next->next = newNode('a');
  list2->next->next->next = newNode('c');
  list2->next->next->next->next = newNode('e');
  printf("compare result %d\n", compare(list1, list2));
  return 0;
}

remove all duplicates from the input string

/* remove all duplicates from the input string */

#include<stdio.h>
void removeDup(char *str) {
    int str_hash[256] ={0};
    int i;
    int count = 0;
    for (i=0; str[i] != '\0'; i++)
    {
    str_hash[str[i]]++;
        if (str_hash[str[i]] == 1)
            str[count++] = str[i];
    }
    str[count] = '\0';
}

int main() {
    char str[]= "pppppeeeeeeeeeeaaaaaaaaaaaccccccceeeeeee";
    removeDup(str);
    printf("the result string is %s\n", str);
    return 0;
}

remove spaces from a given string

/* remove spaces from a given string */

#include <stdio.h>
void removeSpaces(char *str)
{
 int count =0;
 int i;
 for (i =0; str[i] != '\0';i++){
      if(str[i] != ' ')
         str[count++]=str[i];
 }
 str[count] = '\0';
}
int main()
{
 char str[] = "A    w   eso m  e  ";
 removeSpaces(str);
 printf("result string is %s\n", str);
 return 0;
}

Given an array A[] and a number x, check for pair in A[] with sum as x

/* Given an array A[] and a number x, check for pair in A[] with sum as x */

#include <stdio.h>
void quickSort(int*, int, int);
void printSumPair(int A[], int arr_size, int sum) {
    int l, r;
    // sort in increasing order
    quickSort(A, 0, arr_size - 1);
    l = 0;
    r = arr_size-1;
    while (l < r) {
        if (A[l] + A[r] > sum)
            r --;
        else if (A[l] + A[r] < sum)
            l++;
        else {
            printf("%d + %d equals %d\n", A[l], A[r], sum);
            break;
        }
    }
}

int main() {
    int arr[] = {1,4,45,6,10,8};  // sorted would be : {1,4,6,8,10,45}
    int x = 16;
    int arr_size = sizeof(arr)/sizeof(arr[0]);
    printSumPair(arr, arr_size, x);
    return 0;
}

void exchange (int *a, int *b) {
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

int partition (int A[], int si, int ei ) {
    int x  = A[ei];
    int i = si - 1;
    int j;
    for (j = si; j <= ei - 1; j++) {
       if(A[j] <= x) {
         i++;
         exchange (&A[j], &A[i]);
       }
    }
    exchange (&A[i+1], &A[ei]);
    return (i+1);
}

void quickSort (int A[], int si, int ei) {
    int pi;
    if (si < ei ) {
       pi = partition(A, si, ei);
       quickSort(A, si, pi-1);
       quickSort(A, pi+1, ei);
    }
}

if binary representation of a given number is pallindrom or not

/*  test if binary representation of a given number is pallindrom */

#include<stdio.h>
#include <stdbool.h>
bool isBinPallindrom(unsigned int num) {
    if (num == 0)
       return true;
    int posL = 1;
    int posR = 1;
    int temp = num;
    while(temp>>1) {
        temp >>=1;
        posR++;
    }
    printf("num is %d, MSB pos %d\n", num, posR);
    while (posR > posL) {
        if (((num & (1 << (posR -1))) >> (posR -1)) != ((num & (1 << (posL -1))) >> (posL -1))) {
              printf ("not pallindrom\n");
              return false;
        }
        posL++;
        posR--;
    }
    return true;
}
int main()
{
    unsigned int x = 22;
    printf("The number %d is %s\n", x, isBinPallindrom(x) ? "pallindrom": "not pallindrom");
    x = 0xFF;
    printf("The number %d is %s\n", x, isBinPallindrom(x) ? "pallindrom": "not pallindrom");
    return 0;
}

Least Recently Used Cache working example implementation in C

/* program to implement Least Recently Used (LRU) Cache */

#include<stdio.h>
#include<stdlib.h>
// define node for doubly linked list holds pageNumber
typedef struct QNode
{
    struct QNode *prev, *next;
    unsigned int pageNumber;
} QNode;

// Queue - collection of QNodes
typedef struct Queue
{
    unsigned count;
    unsigned numberofFrames;
    QNode *front, *rear;
} Queue;

// hash as collection of pointers to Qnodes and size
typedef struct Hash
{
    int capacity;
    QNode* *array;
}Hash;

QNode* createQNode(int pageNumber)
{
    QNode* qNode = (QNode*) malloc (sizeof(QNode));
    qNode->pageNumber = pageNumber;
    qNode->prev = qNode->next = NULL;
    return qNode;
}

Queue* createQueue(int numberofFrames)
{
    Queue* queue = (Queue*) malloc (sizeof(Queue));
    queue->count = 0;
    queue->front = queue->rear = NULL;
    queue->numberofFrames = numberofFrames;
    return queue;
}

Hash* createHash(int capacity)
{
    Hash *hash = (Hash*) malloc (sizeof(Hash));
    hash->capacity = capacity;

    hash->array = (QNode**) malloc( hash->capacity * sizeof(QNode*));
    int i;
    for(i =0; i< hash->capacity;++i)
    hash->array[i] = NULL;
    return hash;
}

void deQueue (Queue* queue) {
    if (queue->count == 0)
        return ;
    if (queue->front == queue->rear)
        queue->front = queue->rear = NULL;
    QNode* temp = queue->rear;
    queue->rear = queue->rear->prev;

    if(queue->rear)
       queue->rear->next = NULL;

    free(temp);
    if (queue->count > 0)
    queue->count--;
}

void Enqueue (Queue* queue, Hash* hash, unsigned pageNumber)
{
    if (queue->count == queue->numberofFrames) {
        hash->array[queue->rear->pageNumber] = NULL;
        deQueue(queue);
    }

    QNode* temp = createQNode(pageNumber);
    temp->next = queue->front;

    if (queue->count == 0) {
        queue->rear = queue->front = temp;
    } else {
        queue->front->prev = temp;
        queue->front = temp;
    }

    hash->array[pageNumber] = temp;
    queue->count++;
}
// when a page with pageNumber is referenced from cache:
// 1) frame is not present in memory,which needs to be added
//in memory (add at front of queue)
// 2) if page is present with given page number then needs to
// be moved to the front of queue.
void ReferencePage(Queue* queue, Hash* hash, unsigned pageNumber)
{
    QNode* reqPage = hash->array[pageNumber];
    // page is not in cache, add to the queue
    if (reqPage == NULL)
        Enqueue( queue, hash, pageNumber);
    // page is there and not at front, need to move to front
    else if (reqPage != queue->front) {
        reqPage->prev->next = reqPage->next;
        if (reqPage->next)
            reqPage->next->prev =  reqPage->prev;
        if(reqPage == queue->rear)
         {
             queue->rear = reqPage->prev;
             queue->rear->next = NULL;
         }

         reqPage->next = queue->front;
         reqPage->prev = NULL;

         reqPage->next->prev = reqPage;
         queue->front = reqPage;
     }
}


int main()
{
    // create a queue for number of pages to be hold by cache
    Queue* q = createQueue(4);  // 4 pages

    // create hash to reference pages
    Hash* hash = createHash(10);

    ReferencePage( q, hash, 1);
    ReferencePage( q, hash, 2);
    ReferencePage( q, hash, 3);
    ReferencePage (q, hash, 1);
    ReferencePage (q, hash, 4);
    ReferencePage (q, hash, 5);

    // print the cache page frames after the referencing
    printf ("%d", q->front->pageNumber);
    printf("%d", q->front->next->pageNumber);
    printf("%d", q->front->next->next->pageNumber);
    printf("%d\n", q->front->next->next->next->pageNumber);

    return 0;
}