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

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.                                                              

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

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

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;
}

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;
}

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;
}

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;
}

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

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

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;
}