How to change the default crontab editor value

export EDITOR=vim

23-02-2009

On 23rd Feb 2009 around 6 PM, Shaju went and asked divya whether she have any plans for her marriage. And the conversation goes like ..

Divya: ella not now, yethuva erunthalum oru 6 maasam agatum.
Shaju: Yen apathan Ganesh Indiaku varana ?
Divya: (She admitted) yes, I wanted to marry Ganesh

PS: dialogue are all my own. But the matter is same

And after this, as usual her mom was started crying. Actually I feel very very bad for her. I like her a lot and I feel very sad that becoz of me she is crying today . Sorry aunty.

Shaju was not happy with the way I handled the matter when we get caught last time. So this time he is not going to call me.

To be continued ..

Customized ‘use lib’ in perl

When you have restriction to install your perl module under c:\program file\perl, try to install it under your local directory. Suppose, your perl module is installed under C:\mydir\perlmodules\lib, then you should let your perl script to load/use your local perl module.

# this will include the below directory for loading the modules.
use lib "C:\mydir\perlmodules\lib";

Bit count

Problem:
Given a number, count the number of bits set in that number. There are 2 methods represented below.
First solution does the calculation in constant time, but it assumes it is a 32-bit machine.
Second solution doesnot assume anything such that and it works for both 32 & 64-bit machine. But the runtime of that machine is O(M) where M is the number of bit set in that number.

Soultion:

#include <iostream.h>
using namespace std;

typedef unsigned long long uint64;  //assume this gives 64-bits
unsigned long m1  = 0x5555555; //binary: 0101...
const uint64 m2  = 0x33333333; //binary: 00110011..
const uint64 m4  = 0x0f0f0f0f; //binary:  4 zeros,  4 ones ...
const uint64 m8  = 0x00ff00ff; //binary:  8 zeros,  8 ones ...
const uint64 m16 = 0x0000ffff; //binary: 16 zeros, 16 ones ...
const uint64 hff = 0xffffffff; //binary: all ones
const uint64 h01 = 0x01010101; //the sum of 256 to the power of 0,1,2,3...

//This is a naive implementation, shown for comparison,
//and to help in understanding the better functions.
//It uses 24 arithmetic operations (shift, add, and).
int popcount_1(uint64 x) {
    x = (x & m1 ) + ((x >>  1) & m1 ); //put count of each  2 bits into those  2 bits
    x = (x & m2 ) + ((x >>  2) & m2 ); //put count of each  4 bits into those  4 bits
    x = (x & m4 ) + ((x >>  4) & m4 ); //put count of each  8 bits into those  8 bits
    x = (x & m8 ) + ((x >>  8) & m8 ); //put count of each 16 bits into those 16 bits
    x = (x & m16) + ((x >> 16) & m16); //put count of each 32 bits into those 32 bits
    return x;
}

int countNaive(int number)
{
    int count = 0;
    while(number)
    {
        count++;
        number = number & (number -1);
    }

    return count;
}
int main()
{
    cout<<"Enter the number: ";
    int number;
    cin>>number;
    cout<<"Number of bits: "<<popcount_1(number)<<endl;
    cout<<"Number of bits(Naive Method): "<<countNaive(number)<<endl;
    return 0;
}

Arrange 0′s & 1′s

Problem Statement:
——————–

An array of size n among which there are n/2 0s and n/2 1s arranged in random order. Arrange all the 1s to left and all 0s to right but it needs to be stable i.e., the order of 1s and 0s in the i/p array should be maintained.

Expected Complexity:
——————–
O(N) with constant space.

Pseudocode:
———–
1. Have two counters, count1 = 0 and count2 = (n/2)+1
2. Traverse thru the array, if(arr[ i ] == 1) { arr[ i ] = count1++;} else { arr[ i ] = count2++ };

3) At the end of the traversal, you have array filled with numbers 0 to n-1

Now the problem reduces to sorting and array of n numbers which has elements from 0 to n-1 occuring only once which can be done in O(n).

for(j = 0; j <= 1; j++)
{
	for(i = 0; i<n; i++)
	{
		if(arr[ i ] != i)
		{
			swap(arr[ i ], arr[ arr[ i ] ]);
		}
	}
}

Note: j loop runs only twice irrespective on ‘n’ and has constant complexity. The order of this whole loop is 2*n = O(n).

4) After the array is sorted, Again traverse thru the array and make elements arr[0] to arr[n/2] to ’1′ and arr[(n/2)+1] to arr[n] as ’0′.

Space complexity is constant and time complexity is O(step2) + O(step3) + O(step4) = n + 2n +n = 4*n = O(n).

Solution #1 (Stable):
———————-

#include<iostream.h>
int a[] = { 1,0,0,0,1,1,1,0,0,1};
#define _SIZE sizeof(a)/sizeof(a[0])

/* Helper Function */
void printArray()
{
    for(int i=0;i<_SIZE; ++i)
        cout<<a[i]<<" ";

    cout<<endl;
}

int main()
{
    int countOne = 0;
    int countZero = (_SIZE)/2;

    int i=0;

	/* Fill the array with numbers from 1 to N */
    for(i=0; i < _SIZE; ++i)
    {
        if(a[i] == 1)
        {
            a[i] = countOne;
            countOne++;
        }
        else
        {
            a[i] = countZero;
            countZero++;
        }
    }
    printArray();

	/* Swap the number and make it a sorted one */
    for(int j = 0; j< 2; ++j)
    {
        for(i=0; i < _SIZE; ++i)
        {
            if(a[i] != i)
            {
                int temp = a[i];
                a[i] = a[a[i]];
                a[temp] = temp;
            }
        }
    }

    printArray();

	/* Fill the 1st N/2 elements with 1 */
    for(i=0; i<_SIZE/2; ++i)
        a[i] = 1;

	/* Fill the last N/2 elements with 1 */
    for(i=_SIZE/2; i<_SIZE; i++)
        a[i] = 0;

        printArray();

		return 0;
}

Solution #2 (UnStable):
———————-

Here is a small variation of the quick sort to solve the same problem but this solution is not stable. So I prefer #1.

#include<iostream.h>
using namespace std;
#define _SIZE sizeof(a)/sizeof(a[0])
void swap(int *a, int l, int r)
{
    cout<<"Swaping "<<l<<" "<<r<<endl;
    if(a[l] != a[r])
        a[l] ^= a[r] ^= a[l] ^= a[r];

    return;
}
bool compare_1_upper(int *a, int u, int p)
{
    return (a[u] == p);
}
bool compare_1_lower(int *a, int l, int p)
{
    return (a[l] < p);
}

bool compare_0_upper(int *a, int u, int p)
{
    return (a[u] > p);
}
bool compare_0_lower(int *a, int u, int p)
{
    return (a[u] == p);
}
bool (*funcPtr_upper)(int *, int, int) = 0;
bool (*funcPtr_lower)(int *, int, int) = 0;
void qPartition(int *a, int low, int upper)
{
    int pivot = a[low];
    int l = low - 1;
    int u = upper + 1;

    if(a[low])
    {
        funcPtr_upper = compare_1_upper;
        funcPtr_lower = compare_1_lower;
    }
    else
    {
        funcPtr_upper = compare_0_upper;
        funcPtr_lower = compare_0_lower;
    }

    while(1)
    {
        while(funcPtr_upper(a, --u, pivot));

        while(funcPtr_lower(a, ++l, pivot));

        if(l<u)
            swap(a, l, u);
        else
            return;

    }
    return;

}

int a[] = { 1,1,1,1,1,0,0,1};

void print()
{
    for(int i=0; i< _SIZE; ++i)
        cout<<a[i]<<" ";

    cout<<"\n";
}

int main()
{
    print();
    qPartition(a, 0, _SIZE - 1);
    print();
    return 0;
}

Min/Max/Search in circular array

/* Problem: An array is shifted N times, so we get a circular shifted array.
 * 1. Search for a number in an efficient way
 * 2. Find the start index ie. MIN element in the array
 * 3. Find the   end index ie. MAX element in the array
 */

#include<iostream.h>

int array[] = { 7,8,9,0,1,2,3,4,5,6};
#define SIZE sizeof(array)/sizeof(array[0])

void search(int key)
{
    int left = 0;
    int right = SIZE;
    int mid;
    while(left<right)
    {
        if(right-left == 1)
        {
            if(array[left] == key)
                cout<<"Match found\n";
            else if(array[right] == key)
                cout<<"Match found\n";
            else
                cout<<"Match not found\n";
            break;
        }
        mid = (right-left)/2 + left;

        if(array[mid] == key)
        {
            cout<<"Key found: "<<key<<endl;
            break;
        }
        if(array[left] <= array[mid])
        {
            // sub case #1
            if(key >= array[mid] && array[right]>=key)
            {
                left = mid;
            }
            else
                right = mid;
        }
        else
        {
            // right sub arrary is sorted
            if(key >= array[mid] && key <= array[right])
                left = mid;
            else
                right = mid;
        }
    }

}
void findMax()
{
    int left = 0;
    int right = SIZE - 1;
    int mid;

    while(left<right)
    {
        mid = (right-left) /2 + left;
        if(right-left == 1) {
            cout<<"Max :"<< (array[right] > array[left] ? array[right]:array[left])<<endl;
            return;
        }
        if(array[mid] > array[left] && array[mid] > array[right])
            left = mid;
        else if(array[mid] < array[left] && array[mid] < array[right])
            right = mid;
        else
            left = mid;
    }

    cout<<"Max element: "<<array[mid] <<" "<<array[left]<<" "<<array[right]<<endl;
    return;
}

void findMin()
{
    int l = 0;
    int r = SIZE -1;
    int m;

    while(l<r)
    {
        m = (r-l)/2+l;
        if(r-l == 1)
        {
            cout<<"Min: "<<(array[r]<array[l] ? array[r]:array[l])<<"\n";
            return;
        }
        if (array[l]  > array[m] && array[r] > array[m])
            r = m;
        else if(array[l] < array[m] && array[r] < array[m])
            l =  m;
        else
            r = m;
    }
    cout<<"Minimum: "<<array[m]<<"\n";
}
int main()
{
    cout<<"Enter the no you want to search!! ";
    int key;
    cin>>key;

    search(key);
    findMax();
    findMin();
    return 0;
}

XOR Linked List

/* Problem Statement :
 * -------------------
 * Implement a memory efficient Doubly Linked List
 * which means you are allowed to use only one pointer
 * to indicate both next and the previous pointers
 *
 * Soultion 
 * ---------
 * The possible solution involves using a XOR Linked list compresses the same
 * information in one address field by storing the bitwise XOR of the address
 * for the previous and the address for next in one field.
 * A B C D E ... <-> A⊕C <-> B⊕D <-> C⊕E <-> 
 * When you traverse the list from left to right: supposing you are at C, 
 * you can take the address of the previous item, B, 
 * and XOR it with the value in the link field (B⊕D). 
 * You will then have the address for D and you can continue traversing the list. 
 * The same pattern applies in the other direction.
 * 
 * Limitation:
 * ------------
 * 1. The list cannot be traversed from the middle unless we get the address of the previous element.
 * 2. General-purpose debugging tools cannot follow the XOR chain, making debugging more difficult.
 * 3. The price for the decrease in memory usage is an increase in code complexity, making maintenance more expensive; 
 * 4. Most garbage collection schemes do not work with data structures that do not contain literal pointers;
 * 5. 
 */

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

/* pointer stored the address of the node 
 * since address is a mere number, we can store it happily
 */
typedef unsigned long pointer;

struct link
{
    pointer next_prev;
    int payload;
};
typedef struct link link;

link* add_data(int payload, struct link* Prevlist)
{
    struct link * new_link = (struct link*)malloc(sizeof(link));
    assert(new_link);

    /* Assigning the address of the previous element
     * in the current NODEs pointer
     */
    new_link->next_prev = (pointer)Prevlist;
    new_link->payload = payload;
    
    if (Prevlist != NULL)
    {
        /* If the previous Prevlist is not NULL, which means this is not the head
         * then XOR the Prevlist's previous node address with this New NODEs address
         * (ie) consider a list A<->B<->C<->D
         *  we are creating a new node C.
         * B's next_prev would have A's address.
         * so while creating C, update (B->next_prev = A ^ C)
         */
         
        Prevlist->next_prev = (pointer) list->next_prev ^ (pointer)new_link;
    }
    return new_link;
}

void walk_list(link *list)
{
    struct link* prev = 0;
    while (list != NULL)
    {
        pointer next = ((pointer)prev) ^ list->next_prev;
        printf("%d ", list->payload);
        prev = (struct link*)list;
        list = (link*)next;
    }
    printf("\n");
}

int main(void)
{
    /* Add the elements in the linked list
     * Remember you have to give the address of the previous node
     * while adding the current node
     */
    link *l1 = add_data(1, NULL);
    link *l2 = add_data(2, l1);
    link *l3 = add_data(3, l2);
    link *l4 = add_data(4, l3);
    link *l5 = add_data(5, l4);

    /* Walk from the head */
    walk_list(l1);
    
    /* Walk from the tail */
    walk_list(l5);

    return 0;
}

Reverse every Nth node in LL

/* Problem Statement :
 * Given a Linked List, reverse every Nth node in the Linked List
 */
#include<iostream.h>

struct node
{
    int data;
    struct node *next;
};
typedef struct node NODE;

NODE *form_LL(int limit)
{
    NODE *head = NULL;
    for(int i = limit;i ; --i)
    {
        NODE *temp = new NODE;
        temp->data = i;
        temp->next = head;
        head = temp;
    }
    return head;
}
void print_LL(NODE *start)
{
    while(start)
    {
        cout<<start->data<<" ";
        start = start->next;
    }
    cout<<endl;
}
NODE *KReverse(NODE *head, int k)
{
    int count = 0;

    if(!head)
        return NULL;
    NODE *prev = NULL;
    NODE *current = head;
    NODE *next = NULL;
    while(current && count < k)
    {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
        count++;
    }
    NODE *rest = KReverse(next, k);
    head->next = rest;
    return prev;
}

int main()
{
    int num;
    cout<<"How many number of Nodes : ";
    cin>>num;
    NODE *head = form_LL(num);
    print_LL(head);

    int k = 0;
    cout<<"How many rotations : ";
    cin>>k;
    NODE *new_node = KReverse(head, k);
    print_LL(new_node);
}

Convert BST to LL

/* Problem Statement :
 * Write a C code to conert a binary search tree to a linked list
 */

#include<iostream.h>
#include<queue.h>

struct node {
    int data;
    int newline;
    struct node *left;
    struct node *right;
};
typedef struct node NODE;

void insert_element(NODE **head, NODE *temp)
{
    if(*head == NULL)
    {
        *head = temp;
        cout<<"Head is : "<<(*head)->data<<endl;
        return;
    }
    NODE *prev = NULL;
    NODE *current = *head;
    while(current)
    {
        prev = current;
        if(current->data > temp->data)
        {
            current = current->left;
        }
        else
            current = current->right;
    }
    cout<<"Inserting : "<<temp->data<<endl;
    if(prev->data > temp->data)
        prev->left = temp;
    else
        prev->right = temp;
}

NODE * form_BST(int *input, int size)
{
    NODE *head = NULL;
    NODE *temp = NULL;
    int count = 0;
    while(count < size)
    {
        temp = new NODE;
        temp->data = input[count];
        temp->left = NULL;
        temp->right = NULL;
        temp->newline = 0;
        insert_element(&head, temp);
        count++;
    }
    return head;
    cout<<"end of BST\n";
}
NODE * convert(NODE *start)
{
    NODE *current = start;
    NODE *Left = NULL;
    NODE *Right = NULL;

    if(current == NULL)
    {
        return NULL;
    }

    Left = convert(current->left);
    Right = convert((current->right));

    current->right = Right;
    if (Left)
    {
        NODE *temp = Left;
        while(temp->right)
            temp = temp->right;

        temp->right = current;
        return Left;
    }
    else
        return current;
}

void print_BST(NODE *head)
{
    if(head == NULL)
        return;
    print_BST(head->left);
    cout<<head->data<<" ";
    print_BST(head->right);
}
void print_LL(NODE *start)
{
    while(start)
    {
        cout<<start->data<<" ";
        start = start->right;
    }
    cout<<endl;
}

void LevelOrderTraversal(NODE *root)
{
    queue<NODE *> Q;
    NODE *pop1 = NULL;

    if(root == NULL)
        return ;

    Q.push(root);

    while(!Q.empty())
    {
        pop1 = Q.front();
        Q.pop();

        if(pop1->newline == 0)
        {
            if(pop1->left)
                Q.push(pop1->left);
            if(pop1->right)
                Q.push(pop1->right);

            cout<<pop1->data<<" ";
        }
        else
            cout<<endl;

    }
    cout<<endl;
}
void printPath(int *path, int range)
{
    int i =0;
    while(i<= range)
    {
        cout<<path[i++]<<" ";
    }
    cout<<endl;
}
static int path[100];
void hasSum (NODE *root, int sum, int index)
{
    static int originalSum = sum;

    if(root == NULL)
        return;

    if(root->data == sum)
    {
        path[index] = root->data;
        printPath(path, index);
        index = 0;
        return;
    }
    else if (root->data < sum )
    {
        path[index] = root->data;
        hasSum(root->left, sum - root->data, index+1);
        hasSum(root->right, sum - root->data, index+1);
    }

    hasSum(root->left, originalSum, 0);
    hasSum(root->right, originalSum, 0);

    return;
}
int main() {

    NODE *head = NULL;
    NODE *start = NULL;
    int input[] = { 4, 2, 6, 1, 3, 5, 7};
    int size = sizeof(input)/sizeof(input[0]);

    head = form_BST(input, size);

    print_BST(head);

    cout<<endl;
    LevelOrderTraversal(head);
    hasSum(head, 6, 0);
    start = convert(head);
    print_LL(start);

    return 0;
}

Find the prime numbers up to 100

Make a chart of the first one hundred positive integers (1-100):

             1   2   3   4   5   6   7   8   9  10
            11  12  13  14  15  16  17  18  19  20
            21  22  23  24  25  26  27  28  29  30
            31  32  33  34  35  36  37  38  39  40
            41  42  43  44  45  46  47  48  49  50
            51  52  53  54  55  56  57  58  59  60
            61  62  63  64  65  66  67  68  69  70
            71  72  73  74  75  76  77  78  79  80
            81  82  83  84  85  86  87  88  89  90
            91  92  93  94  95  96  97  98  99 100

1. Cross out 1, because it is not prime.
2. Circle 2, because it is the smallest positive even prime. Now cross out every multiple of 2; in other words, cross out every second number.
3. Circle 3, the next prime. Then cross out all of the multiples of 3; in other words, every third number. Some, like 6, may have already been crossed out because they are multiples of 2.
4. Circle the next open number, 5. Now cross out all of the multiples of 5, or every 5th number.

Continue doing this until all the numbers through 100 have either been circled or crossed out. You have just circled all the prime numbers from 1 to 100!

#include <iostream.h>
#include <bitset>
using namespace std;
#define MAX 1000
void firstNPrime(int N)
{
    bitset<MAX> bitMap;
    bitMap.reset();

    cout<<"Printing Prime Numbers"<<endl;
    for(int i = 2; i< N; )
    {
        for(int j=i+i; j< N; j=j+i)
        {
            bitMap[j] = 1;
        }
        while(bitMap[++i]) ;
    }

    for(int k = 1; k<N; k++)
    {
        if(!bitMap[k])
        {
            cout<<k<<" ";
        }
    }
    cout<<endl;

}
int main()
{
    cout<<"Enter a no upto which u need the Prime Numbers: ";
    int number;
    cin>>number;
    firstNPrime(number);
    return 0;
}