Elixir of Life

HowEasy - Topcoder Arena

2009-09-25T20:38:00.002+05:30

Problem Statement :

Problem Statement

***Note: Please keep programs under 7000 characters in length. Thank you

Class Name: HowEasy
Method Name: pointVal
Parameters: String
Returns: int

TopCoder has decided to automate the process of assigning problem difficulty
levels to problems. TopCoder developers have concluded that problem difficulty
is related only to the Average Word Length of Words in the problem statement:

If the Average Word Length is less than or equal to 3, the problem is a 250
point problem.
If the Average Word Length is equal to 4 or 5, the problem is a 500 point
problem.
If the Average Word Length is greater than or equal to 6, the problem is a 1000
point problem.

Definitions:
Token - a set of characters bound on either side by spaces, the beginning of
the input String parameter or the end of the input String parameter.
Word - a Token that contains only letters (a-z or A-Z) and may end with a
single period. A Word must have at least one letter.
Word Length - the number of letters in a Word. (NOTE: a period is NOT a letter)

The following are Words :
"ab", "ab."

The following are not Words :
"ab..", "a.b", ".ab", "a.b.", "a2b.", "."

Average Word Length - the sum of the Word Lengths of every Word in the problem
statement divided by the number of Words in the problem statement. The
division is integer division. If the number of Words is 0, the Average Word
Length is 0.

Implement a class HowEasy, which contains a method pointVal. The method takes
a String as a parameter that is the problem statement and returns an int that
is the point value of the problem (250, 500, or 1000). The problem statement
should be processed from left to right.

Here is the method signature (be sure your method is public):
int pointVal(String problemStatement);

problemStatement is a String containing between 1 and 50 letters, numbers,
spaces, or periods. TopCoder will ensure the input is valid.

Examples:

If problemStatement="This is a problem statement", the Average Word Length is
23/5=4, so the method should return 500.
If problemStatement="523hi.", there are no Words, so the Average Word Length is
0, and the method should return 250.
If problemStatement="Implement a class H5 which contains some method." the
Average Word Length is 38/7=5 and the method should return 500.
If problemStatement=" no9 . wor7ds he8re. hj.." the Average Word Length is 0,
and the method should return 250.
Definition

Class: HowEasy
Method: pointVal
Parameters: string
Returns: int
Method signature: int pointVal(string param0)
(be sure your method is public)


#include 
#include 
#include 

const static 
std::string g_LegalCharacters =  "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

class HowEasy
{
    public:
        int pointVal(std::string problemStmt);

    private:
        inline bool isValid(std::string &token);
        inline int problemValue (unsigned int length);
};

bool HowEasy::isValid(std::string &token)
{
    if (token.empty()) return 0;

    size_t pos = token.find_first_not_of(g_LegalCharacters);
    return (pos == std::string::npos);
}

int HowEasy::pointVal(std::string problemStmt)
{
    std::istringstream iss;
    iss.str( problemStmt );

    std::string token;
    unsigned int nWords = 0;
    unsigned int lWords = 0;
    unsigned int average = 0;
    int points = 0;
    std::string validString;
    while (!iss.eof())
    {
        iss >> token;
        if (token.length())
        {
            if (token[token.length() - 1] == '.')
                token.erase(token.end() - 1);

            if (isValid(token))
            {
                ++nWords;
                lWords += token.length();
                validString += token;
            }
        }
    }
    
    if (lWords && nWords)
        average = lWords / nWords;
        
    points =  problemValue (average);        
 return points;    
}

int HowEasy::problemValue (unsigned int length)
{
    if (length <= 3)
        return 250;
    else if (length <= 5)
        return 500;
    else
        return 1000;
}

Happy Hacking :)

Compare Vector V1 and V2 for equality

2009-09-09T09:54:00.002+05:30

Here are the ways to compare two vectors.

Method 1:


#include < iostream >
using std::cout;
using std::endl;

#include < algorithm >
#include < vector >
#include < iterator >

int main()
{
   int a1[ 10 ] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
   int a2[ 10 ] = { 1, 2, 3, 4, 9, 6, 7, 8, 9, 10 };
   std::vector<> v1( a1, a1 + 10 );
   std::vector<> v2( a1, a1 + 10 );
   std::vector<> v3( a2, a2 + 10 );
   std::ostream_iterator<> output( cout, " " );

   cout << "Vector v1 contains: ";    
   std::copy( v1.begin(), v1.end(), output );    
   cout << "\nVector v2 contains: ";
   std::copy( v2.begin(), v2.end(), output );
   cout << "\nVector v3 contains: ";
   std::copy( v3.begin(), v3.end(), output );

   // compare vectors v1 and v2 for equality    
   bool result = std::equal( v1.begin(), v1.end(), v2.begin() );    
   cout << "\n\nVector v1 " << ( result ? "is" : "is not" )  << " equal to vector v2.\n";     
   return 0; 
}

Method 2:

Overload the == operator for comparision



inline bool operator == (const std::vector< std::string >, const std::vector< std::string >)
{
    if (lhs.size() != rhs.size())
        return false;

    int count = lhs.size();
    std::vector< std::string >::const_iterator lhsi = lhs.begin();
    std::vector< std::string >::const_iterator rhsi = rhs.begin();
    while (count--)
    {
        if ( *lhsi != *rhsi)
            return false;
        lhsi++; rhsi++;
    }
    return true;
}

Convert "man page" into text file

2009-07-27T20:14:00.003+05:30

Save a man page into text file

Option #1



man -P cat ls > man_ls.txt

Option #2:



man ls | col -b > ls.txt

First try in C#

2009-07-15T09:48:00.004+05:30

Here is my first try in C#


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace dotNet
{
    class Greeting
    {
        public static int displayGanesh()
        {
            Console.WriteLine("Ganesh Here !!");
            return 0;
        }
        public static int displayVishnu()
        {
            Console.WriteLine("Vishnu Here !!");
            return 1;
        }
    }

    delegate int delGreetings();

    class Program
    {
        static void Main(string[] args)
        {
            int choice = 1;
            delGreetings[] Greetings =
            {
              new delGreetings(Greeting.displayGanesh),
              new delGreetings(Greeting.displayVishnu)
            };
            int return_ = Greetings[choice - 1]();
            Console.Write("Return Value ");
            Console.WriteLine(return_);
            return;
        }
    }
}

delegate is basically defines the function pointer.
In the below snippet, it defines a function pointer which
takes no arguments and returns an int value.


delegate int delGreetings();

Happy Hacking !!

Visual Studio .Net 2008 Cheat sheet

2009-07-14T21:49:00.003+05:30

For all the C# fans out there, today I came across this excellent keyboard cheat sheet and Jeff's Summary Macro to generate the full list of VS 2008 cheat sheet in HTML format.

Here is the steps to generate the cheatsheet for yourself. Skip to down under if you wish to get the generated cheatsheet.

Download the Keyboard shortcut Summary macro

How to install and run the macro ??

go to Tools - Macros - IDE
Create a new Module named "KeyboardShortcuts" under "MyMacros"
Paste the above code into the module
Add a reference to the System.Data.dll and System.XML.dll ; make sure it builds with no errors
Close the macro IDE window
go to Tools - Macros - Macro Explorer
A new macro named "List" will be under "KeyboardShortcuts." Double-click it to run the macro
The macro will take a moment to write the keyboard shortcuts to a HTML file, then open the HTML file in the IDE.

This is tested against VS 2008 and the macro generates the HTML file :

C:\Users\mganesh\Documents\Visual Studio .NET 20xx Keyboard Shortcuts.htm

This is the file location in my Win 7 OS.

The cheat sheet result for the Visual Studio 2008 default C# keyboard shortcuts is posted to save people the trouble of getting the macro running. It's here.

Building Boost Lib 1.35 with VC++ 2008

2009-06-29T19:51:00.003+05:30

Version 1.35 of the Boost libraries was released on March 29th, 2008.

Below are the steps I followed to have everything working on Win 7.

If not already done, install the following development tools (in the prescribed order, please):

Visual C++ 2008 Express Edition
Microsoft Windows SDK
Microsoft Compute Cluster Pack SDK

The last one will only be needed if you plan to compile the Boost.MPI library.

Download and install Python. Download Boost 1.35 and the latest Boost Jam binary (3.1.17 at the time of this writing). Copy the bjam executable to the Boost root directory. Next, disable the automatic linking features of the Microsoft Visual C++ compiler by enabling the BOOST_ALL_NO_LIB macro on the file user.hpp (boost/config/user.hpp). We’re ready to go (type all the commands inside the Visual Studio 2008 Command Prompt):

“bjam stage”

Boost Jam auto detects the Visual C++ 2008 compiler!

If you want to compile the Boost.MPI library a couple of additional steps must be followed. Boost Jam is your friend as it prints it nicely for you:

warning: skipping optional Message Passing Interface (MPI) library.
note: to enable MPI support, add “using mpi ;” to user-config.jam.
note: to suppress this message, pass “–without-mpi” to bjam.
note: otherwise, you can safely ignore this message.

Follow the instructions. The user-config.jam is to be created in your “current” directory ($BOOST_ROOT_DIR\tools\build\v2).

Now build the Boost.MPI library by issuing:

“bjam –with-mpi stage”

The Microsoft MPI library is auto detected!

That is it! Happy Hacking :)

Anbe Vaa - Vijay TV's New serial

2009-06-28T19:52:00.001+05:30

Here you go. Me and Mani has become a big fan of this title song .. Thats a soft melody song .. Here is the lyrics for the song.

Guys, if u get a chance, hear this song in Vijay TV :)

Ah.. ah... (Female Voice)

(Male voice)
Oru paarvai paarkirai..
pudhidhai nan pookiren..
Idhayam idam maarudhe..
Idhu kaadhala...

Nilavodu theigiren..
Ninaivale karaigiren..
sugamana vedhanai..
Idhu kaadala...

Engeyo.. engeyo..
ennule engeyo..
vinmeengal sidharudhe
yaenadi..

Anbe vaa..
Anbe vaa..
Anbe vaa
Anbe vaa.. a...

Ah...

(Female)
Kannukule kannukule.. kaadhal vandhu nenjai thotu povathen..
(Male)
Enna idhu enna idhu.. vaanavillil vanam rendu koodudhe..
(Female)
Theendinal.. vaanile..
megamai alaigiren
(male)
neenginal dhoorathil..
pulliyai tholaigiren..

Nillarendral nillaamal
yenendru kelaamal
edhedho seigirai..
yaenadi..

Anbe vaa..
Anbe vaa..
Anbe vaa
Anbe vaa.. a...

(F)Enna solli enna solli kaadhal adhai unnidathil kaatuven..
(m)Sathamindri sathamindri mounamai nenjukulle pootuven..
(F)kavithaigal ezhudhida vaarthaigal thedinen..
(M)un peyar ezhudhinaal kavidhayai paadinen..

Enn ulle en ulle..
un kannin minsaram..
edhedho seiyudhe..
Yaenadi..

Anbe vaa..
Anbe vaa..
Anbe vaa
Anbe vaa.. a...

Secrets of std::map

2009-06-25T08:48:00.004+05:30

I should admit that I'm very poor in C++ Programming. Today, me and one of colleague was trying to understand a code writter by one of a pioneer in our team. We initially thought he wrote a crabby code but indeed we were wrong and he proved his expertness :)

Below is the snippet of similar case.



#include "stdafx.h"
#include < iostream >
#include < map >

int main()
{
 // 1. define the map
 typedef std::map Map;

 // 2. Create the object for it
 Map myMap;

 for (int i=0; i<10; ++i)
 {
    /**************************** 
      3. Whats going on here ???. 
         We just created the object.
         Could this be a buggy code ?? 

         Nope. When we reference an item in map 
         and if the item is not available, 
         it creates the object. Great :)

         I personally seen/used the creation
         of map on the left side,
         something like myMap[2] = 20
         But the below is of something which
         I am seeing new today :)
     **********************************************/
  
             int &ref = myMap[i];
             ref = i;
  
 }
 for (int i=0; i<10; ++i)
 {
             std::cout << myMap[i] << " ";
 }
 std::cout << std::endl;
 
 return 0;
}

Happy Hacking :)

C++ forward declaration error

2009-06-22T07:41:00.006+05:30

Problem:

I am trying to declare and use a class B inside of a class A and define B outside A.I know for a fact that this is possible because Bjarne Stroustrup uses this in his book "The C++ programming language" (page 293,for example the String and Srep classes). So this is my minimal piece of code that causes problems.


class A
{
    struct B; // forward declaration
    B* c; A()
    {
        c->i;
    }
};

struct A::B
{
    /** we define struct B like this
     ** becuase it was first declared
     ** in the namespace A */

    int i;
};
int main()
{

}

Error:

This code gives the following compilation errors in g++ : tst.cpp: In constructor ‘A::A()’: tst.cpp:5: error: invalid use of undefined type ‘struct A::B’ tst.cpp:3: error: forward declaration of ‘struct A::B’

Solution:

Define the constructor for A AFTER the definition of struct B.

2009-06-14T18:45:00.001+05:30

Sambhar Receipe

Step 1:
Put Onions, Tomato, Chilly, Coriander leaf, 1 Spn of Turmeric Cumin powder (from Amma) in a pressure cooker and keep 3 Whistle.

Step 2:

Put all the needed vegetables in the same pressure cooker and add 1/5 Spn of chilly power, salt to taste. Keep for one more whistle.

Sambhar is ready ;)

How to get the elapsed time in millisecs

2009-02-26T09:06:00.003+05:30

Finding an elapsed time of a function/API/method will help you to understand its performance and the most of our manager/management will hails u if you give them a nice performance graph/chart of an application :)

My Approach:
You can use gettimeofday at the start and end of your method and then the difference the two will give the elapsed time .. You'll get a structure like the one below:


struct timeval {
    time_t      tv_sec;  /* in secs */
    suseconds_t tv_usec; /* in Microseconds */
};

Code snippet:



#include 
#include 
#include 
int main()
{
    struct timeval start, end;
    long mtime, seconds, useconds;    

    // Get the start time
    gettimeofday(&start, NULL);
    
    // Here you go with your method call
    usleep(2000);

    // note the end time
    gettimeofday(&end, NULL);

    seconds  = end.tv_sec  - start.tv_sec;
    useconds = end.tv_usec - start.tv_usec;

    mtime = ((seconds) * 1000 + useconds/1000.0) + 0.5;

    printf("Elapsed time: %ld milliseconds\n", mtime);

    return 0;
}

Python: Human readable time span given total secs

2009-02-25T15:37:00.003+05:30

Problem:

Function takes an amount of time in seconds and returns a human readable time span.

Input: 14723 (in secs)
Output : 4h 5m 23s

Suffixes used:

y - year
w - week
d - days
h - hours
m - min
s - sec

Code:


#!/usr/bin/env python
def elapsed_time (seconds, suffixes=['y','w','d','h','m','s'], add_s=False, separator=' '):
    """
    Takes an amount of seconds and turns it into a human-readable amount of time.
    """
    # the formatted time string to be returned
    time = []

    # the pieces of time to iterate over (days, hours, minutes, etc)
    # - the first piece in each tuple is the suffix (d, h, w)
    # - the second piece is the length in seconds (a day is 60s * 60m * 24h)
    parts = [(suffixes[0], 60 * 60 * 24 * 7 * 52),
          (suffixes[1], 60 * 60 * 24 * 7),
          (suffixes[2], 60 * 60 * 24),
          (suffixes[3], 60 * 60),
          (suffixes[4], 60),
          (suffixes[5], 1)]

    # for each time piece, grab the value and remaining seconds, and add it to
    # the time string
    for suffix, length in parts:
        value = seconds / length
        if value > 0:
            seconds = seconds % length
            time.append('%s%s' % (str(value),
                           (suffix, (suffix, suffix + 's')[value > 1])[add_s]))
        if seconds < 1:
            break

    return separator.join(time)

if __name__ == '__main__':
    # 2 years, 1 week, 6 days, 2 hours, 59 minutes, 23 seconds
    # 2y 1w 6d 2h 59m 23s
    seconds = (60 * 60 * 24 * 7 * 52 * 2) + (60 * 60 * 24 * 7 * 1) + (60 * 60 * 24 * 6) + (60 * 60 * 2) + (60 * 59) + (1 * 23)
    print elapsed_time(seconds)
    print elapsed_time(seconds, [' year',' week',' day',' hour',' minute',' second'])
    print elapsed_time(seconds, [' year',' week',' day',' hour',' minute',' second'], add_s=True)
    print elapsed_time(seconds, [' year',' week',' day',' hour',' minute',' second'], add_s=True, separator=', ')

Output:

[10:13:34 gmuniyan@lnl43a-3102] /home/gmuniyan/python>./elapsedTime.py
2y 1w 6d 2h 59m 23s
2 year 1 week 6 day 2 hour 59 minute 23 second
2 years 1 week 6 days 2 hours 59 minutes 23 seconds
2 years, 1 week, 6 days, 2 hours, 59 minutes, 23 seconds

Honor: Original Post

Running a cmd from bash script

2009-02-24T12:27:00.005+05:30

Problem:

There are many situations in which you may want to run different command in your shell script depending on requirements and circumstances.

There are two approaches we can take from here on.

Approach #1:

Use either case statement or if..elif..else For example:



#!/bin/bash
if [ this -eq that ];then
   command1
else
   command2
fi

Approach #2:

BASH allows you to assign/store a command in a built-in variable called CMD. Build your command in this variable and execute $CMD.



#!/bin/bash
[ this -eq that ] && CMD=”/bin/ls” || CMD="/bin/date";
eval $CMD;

This is a very simple example and this approach is very much generic if you want to have a generic function to execute all the commands. For example:



#!/bin/bash

execute() {
  # $1 holds the arg to this function
  CMD="$1";
  eval $CMD;
}

## Here is your main function

if [ this -eq that]
then
    execute "/bin/ls | wc -l";
else
    execute "/bin/ls";
fi

NOTE: eval is required when you use "|" or redirection of cmd output.

Happy hacking :) !!

Python: Processing cmd line args

2009-02-23T20:34:00.003+05:30

Next thing that you might be interested to learn after the historic "Hello World" program is to know how to process the cmd line arguments.

Method #1: Using sys:


#! /usr/bin/python

import sys;

if __name__ == "__main__":
   for args in sys.argv:
       print args;

Output:

# cmdLine.py 1 2 3 4
cmdLine.py
1
2
3
4

Python: Hello World

2009-02-23T15:04:00.003+05:30

This is my first post against Python, watchout for more to come soon ...

Python way of saying "Hello world" :)


#!/usr/bin/env python

## In Python each module will have a name associated with it
## And here is the main module

if __name__ == "__main__":
    print "Hello World";

Show that 2^n is O(n!)

2009-02-01T19:12:00.001+05:30

This is an interview question from MS.

Answer:

n! = 2*3*...*n >= 2*2*...*2 = 2^(n-1)

Since 2^n <= 2*n! for all n, we have that 2^n = O(n!).

Test from Windows Live Writer

2009-01-15T20:55:00.000+05:30

Hi all, this is a just mail.


int main()
{
	return 0;
}

Arrange 0's & 1's

2009-01-05T20:50:00.001+05:30

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 ] ]);
                }
        }
}
</pre>


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

<pre name='code' class='cpp'>
#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;
}

</pre>


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.


<pre name='code' class='cpp'>
#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;
}

XOR Linkedlist

2008-12-29T20:33:00.000+05:30

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

2008-12-29T20:29:00.001+05:30

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

2008-12-27T19:40:00.000+05:30

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

2008-12-26T05:34:00.001+05:30

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

2008-12-24T12:57:00.000+05:30

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

2008-12-23T20:47:00.001+05:30

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

2008-12-22T21:54:00.001+05:30

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

2008-12-18T20:15:00.001+05:30

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

2008-12-18T15:25:00.001+05:30


#include<iostream>
using namespace std;

void preProcess(int *buf, const char *pattern)
{
    int j = -1;
    int i = 0;
    buf[i] = j;
    int len = strlen(pattern);
    
    while(i<len)
    {
        while(j >=0 && pattern[i] != pattern[j])
        {
            j=buf[j];
    
        }
    
        ++i;++j;
        buf[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))
            {
                cout<<"Match found at index: "<<m<<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)
        cout<<pre[i]<<" ";

    cout<<endl;


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

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

Matrix Filp

2008-12-18T13:03:00.003+05:30

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

2008-12-17T20:47:00.001+05:30

#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

2008-12-15T13:32:00.001+05:30

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

2008-12-04T19:33:00.000+05:30

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

2008-12-04T18:33:00.001+05:30

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

2008-12-03T20:49:00.000+05:30

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

2008-10-25T01:46:00.004+05:30

Writing a post after a very long time .. not because I dont have time but its basically I'm not a good writer :)

It is a very long day for me today .. yup the time is 4 AM in the morning .. and we are 3 people still awaken ..Just finished watching Saroja and Happy Days .. both the films are worth watching it again ..

I was thinking about Saran (probably becoz of his poor Telegu) when I was watching Happy Days, and we watched the same movie in PVR Hyderabad .. Missing all those days guys ..

Hey, i got a good print of these two movies .. if you need to watch this movie, I can start seeding ...

Hope everyone in Hyderabad would be heading home for Dewali, enjoy guys .. and Happy Dewali ..

Swap two pointers

2008-06-11T12:17:00.004+05:30

Our task is to two pointers which is pointing to two objects. The problem is very simple and remember to use pointer to pointer concept. Without that it is just a pass by value to the function.



#include<stdio.h&gt;
void swap(int **firstPtr, int **secondPtr)
{
 int *temp = *firstPtr;
 *firstPtr = *secondPtr;
 *secondPtr = temp;

 return;
}

int main()
{
 int a = 10;
 int b = 20;

 int *aPtr = &a;
 int *bPtr = &b;

 printf("Before Swapping, Address : %x %x, Value : %d %d\n", aPtr, bPtr, *aPtr, *bPtr);
 swap(&aPtr, &bPtr);
 printf("After  Swapping, Address : %x %x, Value : %d %d\n", aPtr, bPtr, *aPtr, *bPtr);
}

If you compile and see the result, the pointers would be swapped ..

Write your own tail -n implementation

2008-06-10T17:09:00.002+05:30

This is one of the question asked in Adobe to my friend. You need to implement your own tail function. read the man page for more information about tail command.

I could able to think of two ways to solve the problem. [tail -n 10 filename ]

Solution 1:

Keep 2 pointers, 1st points to the start of the file, the 2nd points to the n+1 th line :

if the file is not big enough [ less than n ] then dump the content of the file from the beginning to the end of the file and return
else move the second pointer by one line and move the 1st pointer by one until the second reaches EOF. One the 2nd pointer reaches the end of the file, dump the content from where the 1st pointer currently pointing till the end of the file.

This is one of the solution me and Arun discussed when I was there in Hyderabad. But there are lot of improvements that we can do in this and the companies expect such kind of answers (just for the interview sake)

Problem: One of the biggest problem with the above solution is the performance. Both the pointers are reading the same content (2 times reading the same content). Since disk I/O is costly this is a real performance issue.

Solution 2 :

The next solution is instead of reading from the file twice, create a buffer to hold the content, read the file from the end of the file and dump it into the buffer, also keep track of the no of lines read so far from the end. Once the required no of lines read, print the content of the buffer from the end.

My Implementation :



#include <stdio.h&gt;
#include <stdlib.h&gt;
#include <string.h&gt;
#include <sys types.h>
#include <sys stat.h>
#include <fcntl.h&gt;

void tail(int lines, char *file_name)
{
      struct stat file;
      int size = 0;
      char *ch = NULL;
      char *buf = NULL;

      FILE *fd = fopen(file_name, "r");

      if(fd == NULL)
      {
              printf("Not able to open the file : %s\n", file_name);
              return;
      }

      // Set the pointer to the end
      fseek(fd, 0, SEEK_END);

      // Find the size of the file
      size = ftell(fd);
      --size;

      // Allocate the buffer to hold the content
      ch = (char *)malloc(2);
      buf = (char *)malloc(80 * lines);
      memset(buf, 0, 80 * lines);

      char * start = buf;
      *buf++ = '\0';

      // Copy the file content from the end of the file in the reverse order into the buffer
      // Use fseek --> SEEK_SET to navigate the file from the back

      while(size && lines)
      {
              --size;
              fseek(fd, size , SEEK_SET);
              fread(ch, 1, 1, fd);
              *buf++ = *ch;
              if(*ch == '\n')
                      lines--;


      }
      close(fd);

      // Print the content of the buffer
      while( start != buf)
              printf("%c", *buf--);

      printf("\n");
      return;
}
int main(int argc, char **argv)
{
      if(argc != 3)
      {
              printf("Run exe file_name no_of_lines\n");
              return (-1);
      }

      char *file = argv[1];
      tail(atoi(argv[2]), file);

      return 0;
}

input file :cat ganesh
1 Ganesh
2 Vishnu
3 Ramak
4 Arun
5 Jerome

Output:

# ./a ganesh 2

4 Arun
5 Jerome

# ./a ganesh 4

2 Vishnu
3 Ramak
4 Arun
5 Jerome

./a ganesh 10
1 Ganesh
2 Vishnu
3 Ramak
4 Arun
5 Jerome

PS : Guys don't get envy that I wrote a big program for myself. I struggled a lot to make this program to work :-)

Reverse the bits in a number

2008-06-10T17:04:00.001+05:30

The problem is to reverse the bits in a number.
Example : 1011 should be reversed as 1101


#include <stdio.h>
void bit_form(unsigned int value)
{
            while(value)
            {
                   printf("%d", value & 0x01);
                    value = value >>1;
            }
            printf("\n");
            return;
}
int main()
{
        unsigned int value = 0;
        scanf("%d", &value);
        unsigned int return_value = value;
        int loop = sizeof(value) * CHAR_BIT - 1;

        bit_form(value);

        for(value >>= 1; value; value >>= 1)
        {
                return_value <<= 1;
                return_value |= value & 1;
                loop--;
        }

        return_value <<= loop;
        bit_form(return_value);
        return 0;
}

Fast Exponentation

2008-06-10T13:47:00.001+05:30

We need to compute the value of a^n, for some reasonable large value of n.

The simplest algorithm that we know is computing axaxax ... xa (up to n times). However we can do this better by observing that n = [n/2] * [n/2]. If n is even, then a^n = [a^n/2]^2. If n is odd, then a^n = a * [a^n/2]^2. In either case we have halved the size of our computation. so O(log n) multiplications suffice to compute the final value.

Code :



#include <stdio.h>
int power(int n, int e)
{
        int res;

        if(n == 0)
                return 0;
        if(e == 0)
                return 1;

        res = power(n, e/2);

        if( e%2 ) // ODD
        {
                return n * res * res;
        }
        else // Even
                return res * res;

}
int main()
{
        int number;
        int expon;
        int result;

        printf("Enter the number :");
        scanf("%d", &number);

        printf("Enter the exponent :");
        scanf("%d", &expon);
        result = power(number, expon);

        printf("%d ^ %d is : %d\n", number, expon, result);
        return 0;
}

2008-06-10T11:51:00.015+05:30

I am working hard to make my syntax highlighter to work .. this is yet another shot ..



#include <iostream.h>

int main()
{
  return 0;
}

Yeah !! It worked at last ..

Implement your own tail functionality

2008-06-09T19:43:00.002+05:30



#include <stdio.h&gt;
#include<stdlib.h&gt;
#include<string.h&gt;
#include<sys/types.h&gt;
#include<sys/stat.h&gt;
#include<fcntl.h&gt;

void tail(int lines, char *file_name)
{
       struct stat file;
       int size = 0;
       char *ch = NULL;
       char *buf = NULL;

       FILE *fd = fopen(file_name, "r");

       if(fd == NULL)
       {
               printf("Not able to open the file : %s\n", file_name);
               return;
       }

       // Set the pointer to the end
       fseek(fd, 0, SEEK_END);

       // Find the size of the file
       size = ftell(fd);
       --size;

       // Allocate the buffer to hold the content
       ch = (char *)malloc(2);
       buf = (char *)malloc(80 * lines);
       memset(buf, 0, 80 * lines);

       char * start = buf;
       *buf++ = '\0';

       // Copy the file content from the end of the file in the reverse order into the buffer
       // Use fseek --> SEEK_SET to navigate the file from the back

       while(size && lines)
       {
               --size;
               fseek(fd, size , SEEK_SET);
               fread(ch, 1, 1, fd);
               *buf++ = *ch;
               if(*ch == '\n')
                       lines--;


       }
       close(fd);

       // Print the content of the buffer
       while( start != buf)
               printf("%c", *buf--);

       printf("\n");
       return;
}
int main(int argc, char **argv)
{
       if(argc != 3)
       {
               printf("Run exe file_name no_of_lines\n");
               return (-1);
       }

       char *file = argv[1];
       tail(atoi(argv[2]), file);

       return 0;
}

2008-06-02T12:05:00.001+05:30
Aiyoo Aiyoo ..

One of the Ultimate comedies of TR :

2008-04-25T14:31:00.002+05:30
Commenting out large code in VIM.

Whenever I need to comment out (C++ style comment //) a large codes in VIM editor, I usually comment out the first line and then go to the next line, then press '.' to repeat the same. But today I found another way to do the same.

Ctrl-v
96[ press down arrow key]
Shift-i
# or //
[Esc]

This puts the editor into visual block mode, jumps down 96 lines, puts the editor into insert mode, and then inserts whatever you typed at the beginning of all 96 selected lines. All in 9 key-presses. Not bad!

You can also uncomment with the following:

Ctrl-v
96[down]
x
[Esc]

Nice hacking .. let me know if there are any other ways to do the same ..

2008-03-27T11:36:00.007+05:30

int main()
{
cout<<"Hello World";
}

Linux Chear Sheets

2008-02-18T17:40:00.001+05:30
The below site contains the Ultimate collection of cheat sheets :

http://www.scottklarr.com/topic/115/linux-unix-cheat-sheets---the-ultimate-collection/

Blogged with Flock

Gotta Digg

2007-12-27T20:35:00.001+05:30

The song, which is pretty damned good, is performed by Kina Grannis. Here are the lyrics (and hear Kina’s other songs here):

When I’m feeling lazy, at school or when I work
I sneak to my computer, and then I like to shirk
I don’t go online shopping, I don’t email with my mom
I open up my browser, and go to digg-dot-com

Chorus: Gotta digg, gotta digg, gotta digg
Gotta make this story big!
Did you hear that awful sound?
Another server’s down!

I always dig up Apple, and I bury Microsoft
But when I said I was a girl, all the diggers scoffed
And when I see those stories about Senator Ron Paul
I don’t even RTFA; I just digg them all!

Chorus: Gotta digg, gotta digg, gotta digg
Gotta make this story big!
Did you hear that awful sound?
Another server’s down!

The fanboys can be tiresome, they always are outspoken
And if you’re listening Kevin Rose, the comment system’s broken!
I know digg isn’t perfect, but be thankful for what we’ve got
It’s just like daddy always says: “At least it’s not Slashdot!!!”
Chorus: Gotta digg, gotta digg, gotta digg
Gotta make this story big!
Did you hear that awful sound?
Another server’s down!

Is Valid BST ?

2007-11-26T20:30:00.001+05:30

Given a tree, how t o find out if it is Binary Search Tree or not?

two methods

1. Run inorder traversal on the tree and check if the resulting array is sorted or not.

2. For every node check if the Max of left subtree < the value at node and if min of right subtree> value at root.

Simple Solution:

boolean isBST(Node *root)
{
return (root == null || (
(root->left == null || (root->left->data < root->data
&& isBST(root->left))) && (root->right == null ||
(root->right->data > root->data &&
isBST(root->right)))));
}

Powered by ScribeFire.

Simple Bash Scripts I find useful

2007-10-29T14:31:00.001+05:30

bash scriptlet to sort recursively by Time

find . -printf ‘%CY-%Cm-%Cd:%CT %p\n’ | sort

Found a great collection:

————————————————————————-

HANDY ONE-LINERS FOR SED (Unix stream editor) Apr. 26, 2004

compiled by Eric Pement - pemente[at]northpark[dot]edu version 5.4

Latest version of this file is usually at:

http://sed.sourceforge.net/sed1line.txt

http://www.student.northpark.edu/pemente/sed/sed1line.txt

This file is also available in Portuguese at:

http://www.lrv.ufsc.br/wmaker/sed_ptBR.html

FILE SPACING:

# double space a file

sed G

# double space a file which already has blank lines in it. Output file

# should contain no more than one blank line between lines of text.

sed ‘/^$/d;G’

# triple space a file

sed ‘G;G’

# undo double-spacing (assumes even-numbered lines are always blank)

sed ‘n;d’

# insert a blank line above every line which matches “regex”

sed ‘/regex/{x;p;x;}’

# insert a blank line below every line which matches “regex”

sed ‘/regex/G’

# insert a blank line above and below every line which matches “regex”

sed ‘/regex/{x;p;x;G;}’

NUMBERING:

# number each line of a file (simple left alignment). Using a tab (see

# note on ‘\t’ at end of file) instead of space will preserve margins.

sed = filename | sed ‘N;s/\n/\t/’

# number each line of a file (number on left, right-aligned)

sed = filename | sed ‘N; s/^/ /; s/ *$.\{6,\}$\n/\1 /’

# number each line of file, but only print numbers if line is not blank

sed ‘/./=’ filename | sed ‘/./N; s/\n/ /’

# count lines (emulates “wc -l”)

sed -n ‘$=’

TEXT CONVERSION AND SUBSTITUTION:

# IN UNIX ENVIRONMENT: convert DOS newlines (CR/LF) to Unix format

sed ’s/.$//’ # assumes that all lines end with CR/LF

sed ’s/^M$//’ # in bash/tcsh, press Ctrl-V then Ctrl-M

sed ’s/\x0D$//’ # gsed 3.02.80, but top script is easier

# IN UNIX ENVIRONMENT: convert Unix newlines (LF) to DOS format

sed “s/$/`echo -e \\\r`/” # command line under ksh

sed ’s/$’”/`echo \\\r`/” # command line under bash

sed “s/$/`echo \\\r`/” # command line under zsh

sed ’s/$/\r/’ # gsed 3.02.80

# IN DOS ENVIRONMENT: convert Unix newlines (LF) to DOS format

sed “s/$//” # method 1

sed -n p # method 2

# IN DOS ENVIRONMENT: convert DOS newlines (CR/LF) to Unix format

# Can only be done with UnxUtils sed, version 4.0.7 or higher.

# Cannot be done with other DOS versions of sed. Use “tr” instead.

sed “s/\r//” infile >outfile # UnxUtils sed v4.0.7 or higher

tr -d \r outfile # GNU tr version 1.22 or higher

# delete leading whitespace (spaces, tabs) from front of each line

# aligns all text flush left

sed ’s/^[ \t]*//’ # see note on ‘\t’ at end of file

# delete trailing whitespace (spaces, tabs) from end of each line

sed ’s/[ \t]*$//’ # see note on ‘\t’ at end of file

# delete BOTH leading and trailing whitespace from each line

sed ’s/^[ \t]*//;s/[ \t]*$//’

# insert 5 blank spaces at beginning of each line (make page offset)

sed ’s/^/ /’

# align all text flush right on a 79-column width

sed -e :a -e ’s/^.\{1,78\}$/ &/;ta’ # set at 78 plus 1 space

# center all text in the middle of 79-column width. In method 1,

# spaces at the beginning of the line are significant, and trailing

# spaces are appended at the end of the line. In method 2, spaces at

# the beginning of the line are discarded in centering the line, and

# no trailing spaces appear at the end of lines.

sed -e :a -e ’s/^.\{1,77\}$/ & /;ta’ # method 1

sed -e :a -e ’s/^.\{1,77\}$/ &/;ta’ -e ’s/$ *$\1/\1/’ # method 2

# substitute (find and replace) “foo” with “bar” on each line

sed ’s/foo/bar/’ # replaces only 1st instance in a line

sed ’s/foo/bar/4′ # replaces only 4th instance in a line

sed ’s/foo/bar/g’ # replaces ALL instances in a line

sed ’s/$.*$foo$.*foo$/\1bar\2/’ # replace the next-to-last case

sed ’s/$.*$foo/\1bar/’ # replace only the last case

# substitute “foo” with “bar” ONLY for lines which contain “baz”

sed ‘/baz/s/foo/bar/g’

# substitute “foo” with “bar” EXCEPT for lines which contain “baz”

sed ‘/baz/!s/foo/bar/g’

# change “scarlet” or “ruby” or “puce” to “red”

sed ’s/scarlet/red/g;s/ruby/red/g;s/puce/red/g’ # most seds

gsed ’s/scarlet\|ruby\|puce/red/g’ # GNU sed only

# reverse order of lines (emulates “tac”)

# bug/feature in HHsed v1.5 causes blank lines to be deleted

sed ‘1!G;h;$!d’ # method 1

sed -n ‘1!G;h;$p’ # method 2

# reverse each character on the line (emulates “rev”)

sed ‘/\n/!G;s/$.$$.*\n$/&\2\1/;//D;s/.//’

# join pairs of lines side-by-side (like “paste”)

sed ‘$!N;s/\n/ /’

# if a line ends with a backslash, append the next line to it

sed -e :a -e ‘/\\$/N; s/\\\n//; ta’

# if a line begins with an equal sign, append it to the previous line

# and replace the “=” with a single space

sed -e :a -e ‘$!N;s/\n=/ /;ta’ -e ‘P;D’

# add commas to numeric strings, changing “1234567″ to “1,234,567″

gsed ‘:a;s/\B[0-9]\{3\}\>/,&/;ta’ # GNU sed

sed -e :a -e ’s/$.*[0-9]$$[0-9]\{3\}$/\1,\2/;ta’ # other seds

# add commas to numbers with decimal points and minus signs (GNU sed)

gsed ‘:a;s/$^\|[^0-9.]$$[0-9]\+$$[0-9]\{3\}$/\1\2,\3/g;ta’

# add a blank line every 5 lines (after lines 5, 10, 15, 20, etc.)

gsed ‘0~5G’ # GNU sed only

sed ‘n;n;n;n;G;’ # other seds

SELECTIVE PRINTING OF CERTAIN LINES:

# print first 10 lines of file (emulates behavior of “head”)

sed 10q

# print first line of file (emulates “head -1″)

sed q

# print the last 10 lines of a file (emulates “tail”)

sed -e :a -e ‘$q;N;11,$D;ba’

# print the last 2 lines of a file (emulates “tail -2″)

sed ‘$!N;$!D’

# print the last line of a file (emulates “tail -1″)

sed ‘$!d’ # method 1

sed -n ‘$p’ # method 2

# print only lines which match regular expression (emulates “grep”)

sed -n ‘/regexp/p’ # method 1

sed ‘/regexp/!d’ # method 2

# print only lines which do NOT match regexp (emulates “grep -v”)

sed -n ‘/regexp/!p’ # method 1, corresponds to above

sed ‘/regexp/d’ # method 2, simpler syntax

# print the line immediately before a regexp, but not the line

# containing the regexp

sed -n ‘/regexp/{g;1!p;};h’

# print the line immediately after a regexp, but not the line

# containing the regexp

sed -n ‘/regexp/{n;p;}’

# print 1 line of context before and after regexp, with line number

# indicating where the regexp occurred (similar to “grep -A1 -B1″)

sed -n -e ‘/regexp/{=;x;1!p;g;$!N;p;D;}’ -e h

# grep for AAA and BBB and CCC (in any order)

sed ‘/AAA/!d; /BBB/!d; /CCC/!d’

# grep for AAA and BBB and CCC (in that order)

sed ‘/AAA.*BBB.*CCC/!d’

# grep for AAA or BBB or CCC (emulates “egrep”)

sed -e ‘/AAA/b’ -e ‘/BBB/b’ -e ‘/CCC/b’ -e d # most seds

gsed ‘/AAA\|BBB\|CCC/!d’ # GNU sed only

# print paragraph if it contains AAA (blank lines separate paragraphs)

# HHsed v1.5 must insert a ‘G;’ after ‘x;’ in the next 3 scripts below

sed -e ‘/./{H;$!d;}’ -e ‘x;/AAA/!d;’

# print paragraph if it contains AAA and BBB and CCC (in any order)

sed -e ‘/./{H;$!d;}’ -e ‘x;/AAA/!d;/BBB/!d;/CCC/!d’

# print paragraph if it contains AAA or BBB or CCC

sed -e ‘/./{H;$!d;}’ -e ‘x;/AAA/b’ -e ‘/BBB/b’ -e ‘/CCC/b’ -e d

gsed ‘/./{H;$!d;};x;/AAA\|BBB\|CCC/b;d’ # GNU sed only

# print only lines of 65 characters or longer

sed -n ‘/^.\{65\}/p’

# print only lines of less than 65 characters

sed -n ‘/^.\{65\}/!p’ # method 1, corresponds to above

sed ‘/^.\{65\}/d’ # method 2, simpler syntax

# print section of file from regular expression to end of file

sed -n ‘/regexp/,$p’

# print section of file based on line numbers (lines 8-12, inclusive)

sed -n ‘8,12p’ # method 1

sed ‘8,12!d’ # method 2

# print line number 52

sed -n ‘52p’ # method 1

sed ‘52!d’ # method 2

sed ‘52q;d’ # method 3, efficient on large files

# beginning at line 3, print every 7th line

gsed -n ‘3~7p’ # GNU sed only

sed -n ‘3,${p;n;n;n;n;n;n;}’ # other seds

# print section of file between two regular expressions (inclusive)

sed -n ‘/Iowa/,/Montana/p’ # case sensitive

SELECTIVE DELETION OF CERTAIN LINES:

# print all of file EXCEPT section between 2 regular expressions

sed ‘/Iowa/,/Montana/d’

# delete duplicate, consecutive lines from a file (emulates “uniq”).

# First line in a set of duplicate lines is kept, rest are deleted.

sed ‘$!N; /^$.*$\n\1$/!P; D’

# delete duplicate, nonconsecutive lines from a file. Beware not to

# overflow the buffer size of the hold space, or else use GNU sed.

sed -n ‘G; s/\n/&&/; /^$[ -~]*\n$.*\n\1/d; s/\n//; h; P’

# delete all lines except duplicate lines (emulates “uniq -d”).

sed ‘$!N; s/^$.*$\n\1$/\1/; t; D’

# delete the first 10 lines of a file

sed ‘1,10d’

# delete the last line of a file

sed ‘$d’

# delete the last 2 lines of a file

sed ‘N;$!P;$!D;$d’

# delete the last 10 lines of a file

sed -e :a -e ‘$d;N;2,10ba’ -e ‘P;D’ # method 1

sed -n -e :a -e ‘1,10!{P;N;D;};N;ba’ # method 2

# delete every 8th line

gsed ‘0~8d’ # GNU sed only

sed ‘n;n;n;n;n;n;n;d;’ # other seds

# delete ALL blank lines from a file (same as “grep ‘.’ “)

sed ‘/^$/d’ # method 1

sed ‘/./!d’ # method 2

# delete all CONSECUTIVE blank lines from file except the first; also

# deletes all blank lines from top and end of file (emulates “cat -s”)

sed ‘/./,/^$/!d’ # method 1, allows 0 blanks at top, 1 at EOF

sed ‘/^$/N;/\n$/D’ # method 2, allows 1 blank at top, 0 at EOF

# delete all CONSECUTIVE blank lines from file except the first 2:

sed ‘/^$/N;/\n$/N;//D’

# delete all leading blank lines at top of file

sed ‘/./,$!d’

# delete all trailing blank lines at end of file

sed -e :a -e ‘/^\n*$/{$d;N;ba’ -e ‘}’ # works on all seds

sed -e :a -e ‘/^\n*$/N;/\n$/ba’ # ditto, except for gsed 3.02*

# delete the last line of each paragraph

sed -n ‘/^$/{p;h;};/./{x;/./p;}’

SPECIAL APPLICATIONS:

# remove nroff overstrikes (char, backspace) from man pages. The ‘echo’

# command may need an -e switch if you use Unix System V or bash shell.

sed “s/.`echo \\\b`//g” # double quotes required for Unix environment

sed ’s/.^H//g’ # in bash/tcsh, press Ctrl-V and then Ctrl-H

sed ’s/.\x08//g’ # hex expression for sed v1.5

# get Usenet/e-mail message header

sed ‘/^$/q’ # deletes everything after first blank line

# get Usenet/e-mail message body

sed ‘1,/^$/d’ # deletes everything up to first blank line

# get Subject header, but remove initial “Subject: ” portion

sed ‘/^Subject: */!d; s///;q’

# get return address header

sed ‘/^Reply-To:/q; /^From:/h; /./d;g;q’

# parse out the address proper. Pulls out the e-mail address by itself

# from the 1-line return address header (see preceding script)

sed ’s/ *(.*)//; s/>.*//; s/.*[:<] *//'

# add a leading angle bracket and space to each line (quote a message)

sed 's/^/> /’

# delete leading angle bracket & space from each line (unquote a message)

sed ’s/^> //’

# remove most HTML tags (accommodates multiple-line tags)

sed -e :a -e ’s/<[^>]*>//g;/

# extract multi-part uuencoded binaries, removing extraneous header

# info, so that only the uuencoded portion remains. Files passed to

# sed must be passed in the proper order. Version 1 can be entered

# from the command line; version 2 can be made into an executable

# Unix shell script. (Modified from a script by Rahul Dhesi.)

sed '/^end/,/^begin/d' file1 file2 ... fileX | uudecode # vers. 1

sed '/^end/,/^begin/d' "$@" | uudecode # vers. 2

# zip up each .TXT file individually, deleting the source file and

# setting the name of each .ZIP file to the basename of the .TXT file

# (under DOS: the "dir /b" switch returns bare filenames in all caps).

echo @echo off >zipup.bat

dir /b *.txt | sed “s/^$.*$\.TXT/pkzip -mo \1 \1.TXT/” >>zipup.bat

TYPICAL USE: Sed takes one or more editing commands and applies all of

them, in sequence, to each line of input. After all the commands have

been applied to the first input line, that line is output and a second

input line is taken for processing, and the cycle repeats. The

preceding examples assume that input comes from the standard input

device (i.e, the console, normally this will be piped input). One or

more filenames can be appended to the command line if the input does

not come from stdin. Output is sent to stdout (the screen). Thus:

cat filename | sed ‘10q’ # uses piped input

sed ‘10q’ filename # same effect, avoids a useless “cat”

sed ‘10q’ filename > newfile # redirects output to disk

For additional syntax instructions, including the way to apply editing

commands from a disk file instead of the command line, consult “sed &

awk, 2nd Edition,” by Dale Dougherty and Arnold Robbins (O’Reilly,

1997; http://www.ora.com), “UNIX Text Processing,” by Dale Dougherty

and Tim O’Reilly (Hayden Books, 1987) or the tutorials by Mike Arst

distributed in U-SEDIT2.ZIP (many sites). To fully exploit the power

of sed, one must understand “regular expressions.” For this, see

“Mastering Regular Expressions” by Jeffrey Friedl (O’Reilly, 1997).

The manual (”man”) pages on Unix systems may be helpful (try “man

sed”, “man regexp”, or the subsection on regular expressions in “man

ed”), but man pages are notoriously difficult. They are not written to

teach sed use or regexps to first-time users, but as a reference text

for those already acquainted with these tools.

QUOTING SYNTAX: The preceding examples use single quotes (’…’)

instead of double quotes (”…”) to enclose editing commands, since

sed is typically used on a Unix platform. Single quotes prevent the

Unix shell from intrepreting the dollar sign ($) and backquotes

(`…`), which are expanded by the shell if they are enclosed in

double quotes. Users of the “csh” shell and derivatives will also need

to quote the exclamation mark (!) with the backslash (i.e., \!) to

properly run the examples listed above, even within single quotes.

Versions of sed written for DOS invariably require double quotes

(”…”) instead of single quotes to enclose editing commands.

USE OF ‘\t’ IN SED SCRIPTS: For clarity in documentation, we have used

the expression ‘\t’ to indicate a tab character (0×09) in the scripts.

However, most versions of sed do not recognize the ‘\t’ abbreviation,

so when typing these scripts from the command line, you should press

the TAB key instead. ‘\t’ is supported as a regular expression

metacharacter in awk, perl, and HHsed, sedmod, and GNU sed v3.02.80.

VERSIONS OF SED: Versions of sed do differ, and some slight syntax

variation is to be expected. In particular, most do not support the

use of labels (:name) or branch instructions (b,t) within editing

commands, except at the end of those commands. We have used the syntax

which will be portable to most users of sed, even though the popular

GNU versions of sed allow a more succinct syntax. When the reader sees

a fairly long command such as this:

sed -e ‘/AAA/b’ -e ‘/BBB/b’ -e ‘/CCC/b’ -e d

it is heartening to know that GNU sed will let you reduce it to:

sed ‘/AAA/b;/BBB/b;/CCC/b;d’ # or even

sed ‘/AAA\|BBB\|CCC/b;d’

In addition, remember that while many versions of sed accept a command

like “/one/ s/RE1/RE2/”, some do NOT allow “/one/! s/RE1/RE2/”, which

contains space before the ’s’. Omit the space when typing the command.

OPTIMIZING FOR SPEED: If execution speed needs to be increased (due to

large input files or slow processors or hard disks), substitution will

be executed more quickly if the “find” expression is specified before

giving the “s/…/…/” instruction. Thus:

sed ’s/foo/bar/g’ filename # standard replace command

sed ‘/foo/ s/foo/bar/g’ filename # executes more quickly

sed ‘/foo/ s//bar/g’ filename # shorthand sed syntax

On line selection or deletion in which you only need to output lines

from the first part of the file, a “quit” command (q) in the script

will drastically reduce processing time for large files. Thus:

sed -n ‘45,50p’ filename # print line nos. 45-50 of a file

sed -n ‘51q;45,50p’ filename # same, but executes much faster

Powered by ScribeFire.

Minimum Triplet

2007-10-01T17:37:00.001+05:30

Problem:
===========
You are given 3 integer arrays A, B and C of length n1, n2 and n3 respectively. All arrays are sorted. We define triplet of these 3 arrays as (x,y,z) where x is any integer from A, y from B and z from C. We define distance of triplet as maximum difference among triplet elements, i.e. Maximum of x – y, y – z or z – x. Write a program to find minimum triplet distance. (means there are n1*n2*n3 number of possible triplets are possible...among all triplets which triplet has minimum distance...Give only distance, but not triplet elements). Your program must be as much efficient as possible.

Solution:
=========
int incMin(int *i, int *j, int *k); helper function that will increase the minimum of the three input indexes of 3 arrays, e.g. if a[.i] is least out of a[.i], b[j], c[k] then it will do i++ and if any one goes out of bound, it will return ERROR

int windowSize(int i, int j, int k); helper function that returns the current window size = max(a[.i], b[j], c[k]) - min(a[.i], b[j], c[k])

now the concept goes as following:
we start with a window of 3 elements, one from each array. and keep altering the window as required and keep updating the minimum window found so far.

minWindow = 99999; // some very large value
returnVal = 0;
i = j = k =0;

while(returnVal != ERROR) //while one of the arrays does not exhaust
{
..currMinWindow = windowSize(i, j, k);

..if(currMinWindow < minWindow)
....minWindow = currMinWindow;

..returnVal = incMin(&i, &j, &k); // this will increase one of the i, j, k
}

int incMin(int *i, int *j, int *k)
{
..if(a[*i] < b[*j])
..{
....if(a[*i] < c[*k])
....{
......if(i<sizeof(A))
........(*i)++; //a[.i] is minimum, so inc i
......else
........return ERROR;
....}
....else
.....{
........if(k < sizeof(C))
..........(*k)++; //c[k] is minimum, so inc k
........else
..........return ERROR;
......}
..}
..else
..{
....if(b[*j] < c[*k])
....{
......if(j < sizeof(B))
........(*j)++; //b[j] is minimum, so inc j
......else
........return ERROR;
....}
....else
....{
......if(k < sizeof(C))
........(*k)++; //c[k] is minimum, so inc k
......else
........return ERROR;
....}
..}
}

Powered by ScribeFire.

2007-09-12T10:45:00.001+05:30

Solution:
------------

let a and b be given nos ( or values of given nodes )

common_ance( node )
{
........if( ( a <node && b > node ) || ( a > node && b < node ) || a == node || b== node)
........ return node

........else if ( a < node && b < node )
........ return common_ance( node - > left )

........ else
........ return common_ance ( node -> right )
}

initial call is common_ance( root )

Psudocode:
----------------

first condition checks if given nodes lie in left n right subtrees of root
if yes return root
else
if both lie in left subtree then call common_ance( root -> left )
else common_ance ( root - > right )

Powered by ScribeFire.

Division with using /,% operator

2007-09-12T10:36:00.001+05:30

Question:
--------------

Two integers a, b how to divde a/b without using /,% operator... (repeted subtraction is not the solution).

Solution:
-----------

#include<stdio.h>
int main()
{
printf("%d\n", divide(40,2));
return 0;
}

int divide(int num, int denom)
{
int a=0, b=0;
int i= 31; // CAREFUL: works only on int=32-bit machine!
/* Work from leftmost to rightmost bit in numerator */
while(i>=0) {
/* appends one bit from numerator to a */
a = (a << 1) + ((num & (1 << i)) >> i);
b = b << 1;
printf("After shifting a=%d and b=%d\n",a,b);
if (a >= denom) {
a -= denom;
b++;
}
printf("After subtraction a=%d and b=%d\n",a,b);
i--;
}
return b;
}

Powered by ScribeFire.

2007-09-09T23:07:00.000+05:30
One of the site which I came across

http://www.tekpool.com/?cat=9

Detect a loop in a linked list

2007-08-28T17:38:00.001+05:30

How would you detect a loop in a linked list? Write a C program to detect a loop in a linked list.

/*
Start two pointers at the head of the list
Loop infinitely
If the fast pointer reaches a NULL pointer
Return that the list is NULL terminated
If the fast pointer moves onto or over the slow pointer
Return that there is a cycle
Advances the slow pointer one node
Advances the fast pointer two node
*/

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

struct linkedList{
int element;
struct linkedList* next;
};

typedef struct linkedList* List;

/* Takes a pointer to the head of a linked list and determines
if the list ends in a cycle or is NULL terminated
*/

int DetermineTermination(List *head)
{
List *fast, *slow;
fast = slow = head;
while(1)
{
if(!fast || !fast->next)
return 0;
else if(fast == slow || fast ->next == slow)
return 1; // Loop detected
else{
slow = slow->next;
fast = fast->next->next;
}
}
}

Powered by ScribeFire.

2007-08-28T17:36:00.001+05:30

Given only a pointer to a node to be deleted in a singly linked list, how do you delete it?

struct linkedList{
int element;
struct linkedList* next;
};

typedef struct linkedList* List;

void deleteNode(List Node)
{
List tmp;
if(Node)
{ // If current node is not NULL

tmp = List->next; // take backup of next Node
Node->element = Node->next->element; // replace current node element with next Node element
Node->next = Node->next->next; // change next pointer to next to next
free(tmp); // free the next Node which was taken backup

}
return;
}

Powered by ScribeFire.

Reverse a linked list

2007-08-28T17:35:00.001+05:30

Here is the iterative and recursive solution:

struct linkedList{
int element;
struct linkedList *next;
};

typedef struct linkedList* List;

List reverseList(List L)
{
List tmp, previous=NULL;

while(L){
tmp = L->next;
L->next = previous;
previous = L;
L = tmp;
}
L = previous;
return L;

}

List recursiveReverse(List L)
{
List first, rest;
if(!L)
return NULL;
first = L;
rest = L->next;
if(!rest)
return NULL;
rest = recursiveReverse(rest);
first->next->next = first;
first->next = NULL;
L=rest;

return L;
}

Powered by ScribeFire.

memcpy function implementation

2007-08-20T15:51:00.001+05:30

//Most simplified copy function.
void *memcpy(void* dest, const void* src, size_t count)
{
char *s = (char *)src;
char *d = (char *)dest;
for(; count; count--)
{
*s++ = *d++; //usage of operator precendence
}
}

Powered by ScribeFire.

Card Shuffling Algorithm

2007-08-20T12:12:00.001+05:30

The Algorithm

Step 1: Initialize the cards. For each i in the [0...n-1] range, set card[i] = i.

Step 2 (optional): Seed the random number generator.

Step 3: Let i = 0.

Step 4: Let j = random_number MOD n.

Step 5: Exchange the values of card[i] and card[j].

Step 6: Let i = i + 1. If i is less than n, go to step 4.
Sample Source Code

Here is a sample C function implementing the algorithm:

void shuffle(int *card, int n) {
int i, j, k;

for (i = 0; i < n; i++)
card[i] = i;

for (i = 0; i < n; i++) {
j = rand() % n;
k = card[i];
card[i] = card[j];
card[j] = k;
}
}

Powered by ScribeFire.

2007-08-20T11:23:00.001+05:30

Question :

Write a C Program to reverse a stack "in place" using recursion ?
You can only use the following ADT functions on Stack:
IsEmpty
IsFull
Push
Pop
Top

Solution:

void reverse()
{
....int a = s.pop();
....if(s.count!=1)
........reverse();

....Push(a);
}

void Push(int a)
{
....int m = s.pop();
....if(s.count!=0)
........Push(a);
....Else
........s.push(a);

....s.push(m);
}

Powered by ScribeFire.

No of BTS's

2007-08-19T20:20:00.001+05:30

Question :

Given a number N, find the number of binary search trees(BST) possible with numbers 1,2....N

for E.g. if N = 2 , no. of BSTs with node-values 1 and 2 = 2
if N = 3 , no. of BSTs with node-values 1,2 and 3 = 5

Solution:

recursive sol for the same

int countTrees(int numKeys) {

if (numKeys <=1) {
return(1);
}
else
{
// there will be one value at the root, with whatever remains
// on the left and right each forming their own subtrees.
// Iterate through all the values that could be the root...

int sum = 0;
int left, right, root;

for (root=1; root<=numKeys; root++) {
left = countTrees(root - 1);
right = countTrees(numKeys - root);

// number of possible trees with this root == left*right
sum += left*right;
}

return(sum);
}
}

Powered by ScribeFire.

MS Question

2007-08-19T12:26:00.001+05:30

Question:
------------

Given an array having 16000 unique integers, each lying within the range 1<x<20000, how do u sort it. U can load only 1000 numbers at a time in memory.

Solution:

Have an array of 2500 bytes (memory equaivalent of 625 ints) - Each bit in the array will show the presence/absence of a num betw 1-20,000. Lets call this the "presence-bit-map".

Since you can store the presence of 8 nos in a byte, you need (20,000/8) = 2500 bytes.

Initialize all bytes in the presence-bit-map to 0, meaning 'absent'.

Iterate the large integer list(be it in file / mem) once. For every number encountered, set the corresponding bit to 1(indicating present) in the presence-bit-map.

Now, by scanning the presence-bit-map once, you can write the present numbers in sorted order.

complexity
===========
The soln has a complexity of 'order of n', where n is 20,000 in this particular case. O(n) is the best u can get for a sorting problem !

O(n) is possible here coz we have 2 facts that could be taken advantage of
1. Numbers are known to be unique
2. Nos. are known to be in a specific range.

In a generic sorting problem, O(n) is usually not achievable since we can't assume anything like this.

Powered by ScribeFire.

2007-08-19T12:20:00.000+05:30
I planned to maintain all the data structure and Algorithm questions which will surely benefit me and my friends .. So keep watching this page for more entries ..

Sivaji - The BOSS

2007-06-26T19:50:00.001+05:30

Excited. This is one word that explains the feeling when one gets while seeing the movie "Sivaji - The Boss". I can't imagine about a person other than shankar who showed Rajini with his real look. People who thinks that the age catches up him with time, then they must watch Sivaji for sure. What a style at this age, what a dialogue delivery, and no one can able to do a role with comedy, action and romance. But on the other side of the movie there's not much punch dialog from thalaivar but the team tried delivering the punch dialog through Vivek. And Vivek's first punch dialog was very good. The comedy and the love sequence is very good in the first half.

We are keep on trying to get tickets for another show during the weekends. Hope we will get atleast this weekend :-)

Powered by ScribeFire.

Sivaji - The Boss

2007-06-01T19:29:00.001+05:30

So the much awaited film of this year is going to hit the theaters soon. Thalaivar Rockzzzz ..

2007-05-23T14:50:00.000+05:30
Hey today I happened to find the improved yahoo messenger on Web. The interface looks pretty cool.. The last time I tried using this web interface was during my college days. Thats before 4 years I guess. Now the GUI is developed using Flash 9.

The advantage of using this is no download and it bypasses the Firewall :-).

See for yourself at http://webmessenger.yahoo.com, or simply http://web.im

2007-05-20T01:21:00.000+05:30
Life in 30 Secs

Have a look at it and you realize we are in a rat race.Found this video in Yahoo ..

2006-12-08T13:30:00.000+05:30
This is my first blog :-)