Monday, December 29, 2008

XOR Linkedlist

Problem:


Implement a doubly linked list with a single pointer.


Solution:


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

/* pray that a long is the size of a struct link* */

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

typedef struct link link;
link* add_data(int payload, struct link* list)
{
struct link * new_link = (struct link*)malloc(sizeof(link));
assert(new_link);
new_link->next_prev = (pointer)list;
new_link->payload = payload;
if (list != NULL)
{
list->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)
{
link *l1 = add_data(1, NULL);
link *l2 = add_data(2, l1);
/* add something to the front ... */
/* add something to the back ... */
link *l3 = add_data(3, l2);
link *l4 = add_data(4, l3);
link *l5 = add_data(5, l4);

/* walk from front to back */
walk_list(l1);
/* walk from back to front */
walk_list(l5);

return 0;
}

Dutch Nation Flag Problem

Problem:

Given an array of red, green and blue balls arrange them in groups of all red together, greens together and blue together. Do in a single scan of the array.

This is same as You have an array containing only '0's, '1's and '2's. Club same items together in single scan.

Solution:

<br />#include<iostream.h><br />#define _SIZE sizeof(a)/sizeof(a[0])<br />using namespace std;<br />void printArray(int *array, int size)<br />{<br />    for(int i=0; i<size; ++i)=""><br />        cout<<array[i]<<" ";<br />    cout<<endl;<br />    return;<br />}<br />void swap(int *a, int left, int right)<br />{<br />    if(a[left] != a[right])<br />    {<br />        a[left] ^= a[right] ^= a[left] ^= a[right];<br />    }<br />}<br />void reArrange(int *a, int length)<br />{<br />    int low, mid, high = length -1;<br />    low =0; mid = 0;<br />    while(mid <= high)<br />    {<br />        switch(a[mid])<br />        {<br />            case 0 :<br />                swap(a, low, mid);<br />                low++;<br />                mid++;<br />                break;<br />            case 1 :<br />                mid++;<br />                break;<br />            case 2 :<br />                swap(a, mid, high);<br />                high--;<br />                break;<br />            default:<br />                cout<<">>> Error \n";<br />        }<br />    }<br />}<br />int main()<br />{<br />    int a [ ] = { 1,1,1,0,1,2,2,1,0,2,1,2,0 };<br />    printArray(a, _SIZE);<br />    reArrange(a, _SIZE);<br />    printArray(a, _SIZE);<br />    return 0;<br />}<br /><br />

Saturday, December 27, 2008

Create encrypted tar file

one of the way to create a encrypted tar file under linux

  $ tar -zcvf - stuff|openssl des3 -salt -k secretpassword | dd of=stuff.des3           
                                                                                                 
          This will create stuff.des3...don't forget the password you                            
          put in place of  secretpassword. This can be done interactive as                       
          well.                                                                                  
                                                                                                 
            $ dd if=stuff.des3 |openssl des3 -d -k secretpassword|tar zxf -                      
                                                                                                 
     NOTE:  above there is a "-" at the end... this will                                         
            extract everything.                                                              

Friday, December 26, 2008

Mount error in Ubuntu

I got a wired error in my ubuntu today, when I tried to mount my Windows Partition. So I tried to reboot the machine in windows, and thought OS will do a filesystem check so that the error got wiped out. But no luck after rebooting the machine so many times. And below is the solution what I found:



Error Message:



Solution:




1. sudo apt-get install ntfsprogs



2. sudo ntfsfix /dev/sda2



mganesh@bluegene:~$ sudo ntfsfix /dev/sda3

Mounting volume... FAILED

Attempting to correct errors...

Processing $MFT and $MFTMirr...

Reading $MFT... OK

Reading $MFTMirr... OK

Comparing $MFTMirr to $MFT... OK

Processing of $MFT and $MFTMirr completed successfully.

Setting required flags on partition... OK

Going to empty the journal ($LogFile)... OK

NTFS volume version is 3.1.

NTFS partition /dev/sda3 was processed successfully.

mganesh@bluegene:~$ sudo ntfsfix /dev/sda2

Mounting volume... FAILED

Attempting to correct errors...

Processing $MFT and $MFTMirr...

Reading $MFT... OK

Reading $MFTMirr... OK

Comparing $MFTMirr to $MFT... OK

Processing of $MFT and $MFTMirr completed successfully.

Setting required flags on partition... OK

Going to empty the journal ($LogFile)... OK

NTFS volume version is 3.1.

NTFS partition /dev/sda2 was processed successfully.





Happy Ubuntu :) !! .. This solves the problem









Wednesday, December 24, 2008

Search in the Matrix


We a Matrix where every ROW and COL are sorted something like the below:

1 4 5 6
2 5 7 9
3 6 8 10

Problem: give a number, you need to search whether it is there in the Matrix or not.

Solution:

The below solution's complexity is O(m+n) where m - ROW, n - COL

<br />#include<iostream><br />using namespace std;<br />#define ROW 4<br />#define COL 5<br /><br />int Matrix[ROW][COL] = {<br />    { 1, 3, 5, 7,  9},<br />    { 2, 4, 6, 8, 10},<br />    {11,13,15,17, 19},<br />    {20,40,60,80,100}<br />};<br />bool isValid(int row, int col)<br />{<br />    if(row >= 0 && col < COL)<br />    {<br />        return true;<br />    }<br />    return false;<br />}<br />int main()<br />{<br />    int i = ROW-1;<br />    int j = 0; // Zeroth Column<br />    int searchItem = 0;<br /><br />    cout<<"enter the number to be searched: ";<br />    cin >> searchItem;<br /><br />    while(isValid(i, j))<br />    {<br />        if(Matrix[i][j]== searchItem)<br />        {<br />            cout<<"Item found @ ("<< i<<","<< j << ") :"<< searchItem<< endl;<br />            return 0;<br />        }<br />        else if (Matrix[i][j] > searchItem)<br />        {<br />            //go up, which means reduce the row<br />            i--;<br />        }<br />        else<br />        {<br />            // itea is lesser than the index, go right<br />            j++;<br />        }<br />    }<br />    cout<<"Item not found :("<< endl;<br />    return 0;<br />}<br />

Tuesday, December 23, 2008

Palindrome Number

Check whether a number is palindrome or not ..


#include<iostream>
using namespace std;
bool isPanlindrome(int n)
{
int rev = 0;
int num = n;
while(n)
{
rev = rev * 10 + (n%10);
n = n /10;
}
if(num && num == rev)
return true;

return false;
}
int main()
{
int number = 0;

cout<<"Enter the number: ";
cin>>number;

cout<<number<<" is Panlindrome ?."<< (isPanlindrome(number)? "Yes !!": "No :(!!");
cout<<endl;
return 0;
}

Monday, December 22, 2008

String Manipulation

Given a string : abbbccddddeee
Encode it to : ab3c2d4e3


#include<iostream>
#include <strstream>
#include<stdlib.h>
#include<string.h>
using namespace std;
void convert(char *input)
{
char *start = input;
char *s1 = input;
char *s2 = input + 1;

int len = strlen(input);
int count = 0;
char *end = start;
while(--len && *s1 && *s2 )
{
while(*s1 && *s2 && len && *s1 == *s2)
{
++count;
s2++;
--len;
}
if(count)
{
ostrstream str;
str<<(count+1);
*start = *s1;
*++start = *(str.str());
start = start + strlen(str.str()) - 1;
count = 0;
}
else
*start = *s1;
start++;
s1 = s2;
s2++;
}
if(*s1 != *(s1-1))
*start++ = *s1;
*start = *s2;
cout<<"Magic: "<<end<<endl;
return;
}
int main()
{
char input[100];
memset(input, 0, 100);
cout<<"Enter the string: ";
scanf("%s", input);
cout<<"You entered: "<<input<<"!!\n";
convert(input);
return 0;
}

Thursday, December 18, 2008

Array Rotation

A[M][N] is an array rotated in anti clock wise that is A'[N][M]. then mapping A[j]=A'[ _ ][ _ ] in terms of M,N

A
1 2 3
4 5 6

A'
3 6
2 5
1 4


A[j]=A'[ _ ][ _ ] ??


Solution:


i' = N-j-1
j' = i
thus after rotation
A'[i ][j] = A[N-j-1][ i]

KMP string matching

 
 
#include<iostream>

void preProcess(int *kmpNext, 
                const char *pattern) {
    int j = -1;
    int i = 0;
    kmpNext[i] = j;
    int len = strlen(pattern);

    while(i<len) {
        while(j >=0 && pattern[i] != pattern[j]) 
            j=kmpNext[j];    

        ++i;++j;
        kmpNext[i] = j;

        if (pattern[i] == pattern[j])
            kmpNext[i] = kmpNext[j];
        else
            kmpNext[i] = j;
    }
    
    return;    
}

void match(const char *str,
           const char *pattern,
           const int *pre) {
    int m = 0;
    int i = 0;
    int len = strlen(str);
    
    while(m+i < len) {
        if(str[m+i] == pattern[i]) {
            i++;

            if(i == strlen(pattern)) {
                std::cout << "Match found at index: " 
                          << m << std::endl;
            }
        }
        else {
            m = m + i - pre[i];
            if(i > 0) {
                i = pre[i];
            }
        }
    }    
    return;
}

void KMP() {
    char String [] = "abcabcabdewqabcabd";
    char pattern [] = "abcabd";
    
    int *pre = new int [strlen(pattern)+1];
    memset(pre, 0, (strlen(pattern)+1) * sizeof(int));
    
    /* Preprocess the table */
    preProcess(pre, pattern);

    for(int i =0; i<strlen(pattern)+1; ++i)
        std::cout << pre[i] << " ";
    std::cout << std::endl;

    /* Match the string */
    match(String, pattern, pre);

    delete pre;
    return;
}

int main() {
    KMP();
    return 0;
}

Matrix Filp

Matrix Flip


void BitFlip()
{
int c = 1;
int r = 1;
int i, j;

print();
for(i=0; i<5; ++i)
r &= BitArray[0][i];

for(i=0; i<5; ++i)
c &= BitArray[i][0];

for(i=1; i<5; ++i)
{
for(j=1; j<5; ++j)
{
if(! BitArray[i][j] )
{
BitArray[i][0] = 0;
BitArray[0][j] = 0;
}
else
{
BitArray[i][j] = 0;
}
}
}

for(i=1; i<5; ++i)
{
for(j=1; j<5; ++j)
{

if(BitArray[i][0] && BitArray[0][j])
BitArray[i][j] = 1;
}
}

if(r == 0)
for(i=0; i<5; ++i)
BitArray[i][0] = 0;

if(c ==0)
for(i=0; i<5; ++i)
BitArray[0][i] = 0;

print();

return;
}

Wednesday, December 17, 2008

Max sum in the array

#include<iostream>
using namespace std;

#define _SIZE sizeof(array)/sizeof(array[0])
#define max(a,b) a>b ? a:b
int main()
{
    int array[] = { 0, 1, 2, -3, 5, 6, -5, 1, };
    int MaxSoFar = 0;
    int MaxCurrent = 0;
    for(int i = 0; i<_SIZE; ++i)
    {
        MaxCurrent = max(MaxCurrent+array[i], 0);
        MaxSoFar = max(MaxCurrent, MaxSoFar);
    }
    std::cout<<"Max sum in the array: "<< MaxSoFar<<"\n";
    return 0;
}

Monday, December 15, 2008

Perl code to initiate a shutdown from website

#!/app/perl5005/bin/perl -w

use lib "/Progra~1/Perl/site/lib";

use HTTP::Request::Common qw(POST);
use LWP::UserAgent;
use vars qw($MP);

$| = 1; # unbuffer output

# Shutdown the Matrix Pricer first
$ua = LWP::UserAgent->new;
my $response = $ua->request(POST "http://localhost:8251/shutdown", [username => 'rdgadmin', confirm => 'yes']);

if(!$response->is_success)
{
        print STDERR "ERROR - could not shut down DMSwaps MatrixPricer\n";
}

# sleep for a minute so the PMT has no chance to restart it.
sleep(60);

exit(0);


Thursday, December 04, 2008

Find the start in the circular shifted array

A sorted array, with over a million elements in it, is rotated clockwise. Find out the index where the sorted list starts.



int find_index(int *a,int start,int end)
{
int mid = (start+end)/2;
if (a[start] < a[mid] < a[end])
return start;
else if(a[start] > a[mid])
return find_index(a, start, mid);
else if(a[mid] > a[end])
return find_index(a, mid, end);
}

Compute no of digits after '.' in float

Compute the number of digits after '.' in a floating point number.

e.g. if given 3.554 output=3
for 43.000 output=0


double no = 3.44;
int count = 0;
while(no!=((int)no))
{
count++;
no=no*10;
}
printf("%d",count);

Wednesday, December 03, 2008

Reduce the comparisons in Binary Search

Normally there will be 2 comparisons that will be made in Binary Search Algorithm like

if(value > array[mid])
   low = mid
else (value < array[mid])
   high = mid
else (value == array[mid])
   found the value

we have to reduce the number of comparisons made in the above code.

#include <stdio.h>

int array [ ] = { 0, 1,2,3,4,5,6,7,8,9 };
int bin_search(int val)
{
    int low=0;
    int high = sizeof(array)/sizeof(array[0]) - 1;
    int mid;
    while(low < high)
    {
            mid = (low+high)/2 ;
            if(array[mid]<val)
               low = mid+1;
            else
               high = mid;
    }
    if(array[low] == val)
    {
       return val; // found the value
    }
    else
       return -1; // not found
}
int main()
{
    int i;
    for( i=0; i< 11; ++i)
            printf("Return: %d\n", bin_search(i));
   
    return 0;
}