Clone linked list with arbit pointer

Problem statement

Given a linked list with next and arbitrary pointer, clone the given linked list.

Given linked list will be something like below figure.

Linked list with arbitrary pointer

Analysis

This problem can be solved using extra N spaces where we store the next and arbitrary pointer mapping of the given linked list. However, challenge is to do it in O(1) space complexity.

Idea here is to add a node between each two nodes of original list which will eventually become node in clone linked list. For example, in above list, a new node will be added between 1 and 2 with value 1, between 2 and 3 with value as 2 and so on.
After this step linked list looks like

After adding nodes in between

Code for  above step
Now we can access the clone node with
and arbitrary pointer of clone node can be set as

Code for above step
Last step will be to segregate two linked list.
Code for above step

Code

Complexity Analysis

Time complexity of above code is O(N) and space complexity is O(1).

Re-arrange array elements in-place.

Problem statement

Given an array in A = [a1,a2,a3,….an, b1, b2,b3,…bn,c1,c2,c3,…..cn] form
Rearrange above array in below manner: A = [a1,b1,a2,b3,a3,b3,……an,bn]
For example,
If input A =[1,2,3,4,5,6,7,8,9,10],
Output should A =[1,6,2,7,3,8,4,9,5,10]

Analysis

Above problem can be solved easily using extra space. However, let’s optimize the space requirement. Algorithm is based on rotation of  array.
We will process each group from right to left. Put last element of group at the start of the array and rotate the array till that point., repeat till all elements are not processed.
Algorithm
  1. Take each group one by one.
  2. Take the last element of the current group and save it.
  3. Rotate the given array from 0 to index of last element of current group.
  4. Put last element saved in step 2 at start of the array.
  5. Repeat above steps till all elements are processed.

Let’s take an example
A = [1,2,3,,x,y,z, 4,5,6]
There are three groups [1,2,3], [x,y,z] and [4,5,6]
Now we will take last element of group [4,5,6] i.e 6
And we will right rotate the entire array till position of 6. So A becomes
A = [6,1,2,3,x,y,z,4,5]
Now we take last element of group [x,y,z] i.e. z
Now right rotate array till position of z. So array becomes
A = [z,6,1,2,3,x,y,4,5]
Similarly for group [1,2,3] i.e 3
Array becomes.
A= [3,z,6,1,2,x,y,4,5]
Now last element of group [4,5,6] is 5 as we have considered 6 earlier. After doing processing which we did for 6, array will be
A = [5,3,z,6,1,2,x,y,4]
After processing y.
A = [y,5,3,z,6,1,2,x,4]
After processing 2
A = [2,y,5,3,z,6,1,x,4]
In similar fashion we will process remaining 4,x, and 1.
Output will be A = [1,x,4,2,y,5,3,z,6]

Code

Complexity Analysis

Complexity of code will be O(N^2) and space complexity is O(1)

Find median of stream of integers

Find median of stream of integers

Given continuous stream of integers, find median of all integers received till a given point of time. Median can be asked at multiple times.

For example:
Input           Median
12                12
7                 9.5
8                 8
11                9.5
And so…

Median of array of integers is middle of those integers if number of elements are odd and average of middle elements if number of elements is even.

Let’s consider array to store integers as they are received. Array will be unsorted. Finding median will take O(N), insertion as O(1).

How about sorted array? Insertion will take O(N) as we need to shift elements once we identify place for new integer. Median can be found O(1)
Linked list will have same complexity as unsorted array.

So let’s consider some advance data structure. Here, we need some kind of order of elements. We can divide integers in two groups:  all the elements which are less than median, let it be group 1  and all elements which are greater, be it group 2.
So greatest element on group 1 should be less than group 2. We have to find the greatest on one side and smallest on other side. Which data structure gives us that kind of information in constant time.
Maximum can be found using max heap while minimum using min heap in constant time.
So it is evident that we need two heaps. One max heap and other min heap.
Max heap contain all elements which are less than current median and min heap which are greater than current median.

Now how we can insert an integer and what should be properties they should have?

Since median is middle of all integers if number for elements are odd, we need to keep size difference of two heaps either equal  0 or  1.
If size difference increases, we need to adjust elements in two heaps.
If size of max heap is 2 more than min heap, extract maximum element from max heap and put it in min heap.
If size of min heap is 2 more than min heap, extract minimum element from max heap and put it in max heap.

Median of stream of numbers

If number of elements in both heaps is equal, take average of max and minimum elements in both heaps and that would be median.

If sizes of two heaps different, then maximum element of max heap will be the median.

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

#define MAX_SIZE 100
#define true 1
#define false 0

// Data structure to store heap array as well as current count.
typedef struct heap_t {
    int count;
    int a[MAX_SIZE];
}heap;

void add_integer(heap *min_heap, heap * max_heap, int value);
void print_median(heap min_heap, heap max_heap);

/* To find children of a given element */
int left_child(int i){
        return (i*2);
}
int right_child(int i){
        return (2*i)+ 1;
}

int swap(int a[], int i, int j){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
}
/* This function heapifies max heap after deleting maximum
element from it */
void heapify(int a[], int i, int len){
    int largest = i;
    int left, right;

    left = left_child(i);
    right = right_child(i);
    if(left <= len && a[i]>a[left]){
        largest = left;
    }
    if(right <= len && a[largest] > a[right]){
        largest = right;
    }
    if(largest != i){
        swap(a, i, largest);
        heapify(a, largest, len);
    }
}

/* This function heapifies min heap after deleting maximum
element from it */
void min_heapify(int a[], int i, int len){
    int smallest = i;
    int left, right;

    left = left_child(i);
    right = right_child(i);
    if(left <= len && a[i]>a[left]){
        smallest = left;
    }
    if(right <= len && a[smallest] > a[right]){
        smallest = right;
    }
    if(smallest != i){
        swap(a, i, smallest);
        min_heapify(a, smallest, len);
    }
}

/* This function heapifies min heap after inserting an
element from it */
void shift_up_min(int heap[], int i){

    int parent  =  i/2;
    if(i > 1){
        if(heap[parent] > heap[i]){
            swap(heap, parent, i);
            shift_up_min(heap, parent);
        }
    }
}

/* This function inserts an element in min heap  */
void insert_min(heap *min_heap, int val){
    if((min_heap->count) >= MAX_SIZE){
        printf("\n Underlying data structure gone full\n");
        return;
    }
    else{
        min_heap->count++;
        min_heap->a[min_heap->count] = val;
        shift_up_min(min_heap->a, min_heap->count);
    }
    return;
}

/* This function heapifies max heap after inserting an
element from it */
void shift_up_max(int heap[], int i){

    int parent  =  i/2;
    if(i > 1){
        if(heap[parent] < heap[i]){
            swap(heap, parent, i);
            shift_up_max(heap, parent);
        }
    }
}

/* This function inserts an element in min heap  */
void insert_max(heap *max_heap, int val){
    if((max_heap->count) >= MAX_SIZE){
        printf("\n Underlying data structure gone full\n");
        return;
    }
    else{
        max_heap->count++;
        max_heap->a[max_heap->count] = val;
        shift_up_max(max_heap->a, max_heap->count);

    }
    return;
}

/* This function deletes an element in max heap  */
void delete_max(heap *heap){
    if(heap->count == 0 ){
        printf("\n Cannot be deleted");
        return;
    }
    heap->a[1] = heap->a[heap->count--];
    heapify(heap->a, 1,heap->count);

    return;
}

/* This function deletes an element in min heap  */
void delete_min(heap *heap){
    if(heap->count == 0 ){
        printf("\n Cannot be deleted");
        return;
    }
    heap->a[1] = heap->a[heap->count--];
    printf("\n Minimum heap size : %d", heap->count);
    min_heapify(heap->a,1, heap->count);

    return;
}

/*
1. Add to max heap.
2. Check if max_heap.count- min_heap.count >=2 
   remove top of max heap and add it to min_heap
*/
void add_integer(heap *min_heap, heap * max_heap, int value){
    
    // Insert in max heap 
    insert_max(max_heap,value);
    /* If difference between two heap size is more than 1
    or the maximum element in more than least 
    element in min heap then remove from max heap 
    and add to min heap*/
    if((max_heap->count - min_heap->count) >1 ||
        (min_heap->count != 0
         && max_heap->a[1]>min_heap->a[1])){
        int top = max_heap->a[1];
        delete_max(max_heap);
        insert_min(min_heap,top);
    }
    /* If difference between two heap size is more than 1 */
    if((min_heap->count !=0 
        && (min_heap->count - max_heap->count) >1)){
        int top = min_heap->a[1];
        delete_min(min_heap);
        insert_max(max_heap,top);
    }
}

void print_median(heap min_heap, heap max_heap){

    if(max_heap.count == min_heap.count){
        printf("\n Median  %d",
               (max_heap.a[1] + min_heap.a[1])/2 );
    }
    else{
        if(max_heap.count > min_heap.count){
            printf("\n Median : %d ", max_heap.a[1]);
        }
        else{
            printf("\n Median : %d ", min_heap.a[1]);
        }
    }
}

void print_menu(){
        printf("\n1. Add integer");
        printf("\n2. Median");
        printf("\n3. Exit");
}

void main(){
    heap min_heap, max_heap;
    min_heap.count =0;
    max_heap.count =0;

    int choice,n,i;

    do {
        print_menu();
        scanf("%d", &choice);

        switch(choice){
            case 1 :
                printf("\n Enter integer : ");
                scanf("%d", &n);
                add_integer(&min_heap,
                            &max_heap,n );
                printf("\n Max heap  : ");
                break;

            case 2 :
                print_median(min_heap,
                             max_heap);
                break;
            case 3:
                break;
        }
    }while(choice != 3);
}

Complexity of finding median of stream of numbers is O(1) and insertion will be O(log N).

Please comment if you could not understand or something is not correct in post.

Strings : Find if any anagram of string is palindrome.

Problem statement

Given a string, find out if any anagram of given string is palindrome.
For example, “AABBC” has an anagram “ABCBA” which is palindrome.

Analysis

Brute force solution will be to find all anagrams of string and then check each one if that is palindrome. For N character long string, we will have n! anagrams and checking each one of that for palindrome will be computation intensive task, so not a good solution.
What is required for a string to be palindrome string?
We need first half of the string to contain same characters as second half. In case of odd length string we can safely ignore the middle character.
In other terms, each character should occur even number of time except one which is middle character which may occur odd number of times.
Best way to check if character occurs even number of times is to increment to count when it is zero and decrement when it is 1.If at the end we have count corresponding to that character as zero, that means we have even number of occurrence of this character, if not then we have odd number of occurrence.
Extending the same idea from previous post: we will be using a hash table and increment- decrement corresponding count of character in hash.
At the end we will sum the array and if sum of array is greater than 1, then we cannot have any anagram which will be palindrome else at least anagram of string will be palindrome.

Code

Complexity Analysis

Complexity of above code is O(N) with constant amount of memory required.

Strings : Find if two strings are anagrams

Check if strings are anagram

Given two strings, find out if they are anagrams of each other. Strings are said to be anagrams if they have same characters but in different order.For example, abcd and dcba are anagrams.

Analysis

It’s actually a simple problem, we need to just check if both the strings contain same characters. 
First approach will be to sort both the string and compare if they are same. While sorting all the characters will come in lexicographical order and string with same characters will have same order of characters.
Best we can achieve using sort is O(N log N).
Can we do better? We have to keep track of character in one string in another. So if we find what all characters (count of each character) are there in first string, we can easily do that using hash table and compare with characters (count again) present in second string. If both the hash tables are equal, we can say that strings are anagrams.
Here we are using two hash tables. We can do away with on hash table. How?
While traversing the first string we will increment the count against character. While traversing the second string, we will decrement the count against character in the same hash table. If at any time if count of any character goes less than zero, it means, character is present in second string but not in first, so we can say strings are not anagrams.
If we finish complete scanning of second string, we return true.
To avoid check the hash table at the end for non zero count, we can first have a check on length of two strings, if lengths are not equal, straightforwardly say non anagrams. (Think how it avoids check of non zero count at the end :))

Code to find if strings are anagrams

Complexity Analysis

Complexity of algorithm to identify to strings as anagrams is O(N) where N is length of string.