Monday, July 23, 2012

Power of 2 or not ?

How to find a number is power of 2 or not ?


bool IsPowerOfTwo(unsigned long x)
{
    return (x != 0) && (x & (x - 1)) == 0);
}


Explanation:


The above function returns bool (true/false) and accepts one incoming parameter of type unsigned long (x, in this case). Lets take an example, that someone has passed value 4 to the function like:

bool b = IsPowerOfTwo(4);

Now replace each occurance of x with 4:

return (4 != 0) && ((4 & (4-1)) == 0); 


We already know (4 != 0) , so the evaluation of the expression is true.


((4 & (4-1)) == 0 translates to:


((4 & (3)) == 0


But what exactly is  4&3 ? The binary representation of 4 is 100 and of 3 is 011. The & operation says that if both values are equal to 1, then the result is 1. Otherwise it is 0.

100
011

----
000


The result is simply 0. So we go back and look at what our return statement now translates to:

return (4 != 0) && ((4 & 3) == 0);

Which translates now to:

return true && (0 == 0);

return true && true;

We all know that true && true is simply true, and this shows that for our example, 4 is a power of 2.

const


What is the difference between char const * and char * const ?

According to the standard, const modifies the element directly to its left. The use of
 const  at the beginning of a declaration is just a convenient mental shortcut. So the following two statements are equivalent:

char const * pointerToConstantContent;
const char * pointerToConstantContent;

In order to ensure the pointer itself is not modifiable,  const  should be placed after the asterisk:

char * const constantPointerToMutableContent;

To protect both the pointer and the content to which it points, we should use two consts as below:

char const * const constantPointerToConstantContent;

Monday, July 16, 2012

Search in a Circular Sorted Array

Given a circular sorted array say A = { 2,3,4,5,6,7,8,9,0,1 }, find a number in it.

If the array is not circular, we can use binary search to find the key. But if the array is circular we don't know where is the starting point (pivot element). Obviously we can do a linear search to find the element. But if the input array is very large the worst case performance will be very bad. We can take advantage of the fact that the array is sort and use binary search algorithm to find the element in O(N log N).

Approach:



  • Find the middle value of the input array a.
  • If a[0] < a[mid], then all values in the first half of the array are sorted.
  • If a[mid] < a[last], then all values in the second half of the array are sorted.
  • Take the sorted half, and check whether your value lies within it (key lies between the sorted half).

    • If so, binary search that half.
    • If it doesn't, it must be in the unsorted half. Take that half and repeat this process


     
    #include <iostream>
    #include <vector>
    #include <assert.h>
    
    template<typename T, typename type>
    int binary_search(const T& a, int left, 
                      int right, type key) {
    
        while (left <= right) {
            int mid = (right-left)/2 + left;
    
            // base case 1
            if (a[mid] == key)
                return mid;
    
            // mid less than key. Move to right
            if (a[mid] < key) {
                left = mid+1;
            }
            else {
                right = mid-1;
            }
        }
    
        return -1;
    }
    
    template<typename T, typename type>
    int circular_search(const T& a, int left, 
                        int right, type key) {
    
        // base case 1
        int mid = (right-left)/2 + left;
        if (a[mid] == key)
            return mid;
    
        // left array is sorted.
        if (a[0] < a[mid]) {
    
            if (key > a[left] && key < a[mid]) {
                return binary_search(a, left, mid-1, key);
            }
            else {
                return circular_search(a, mid+1, right, key);
            }
        }
        // right array is sorted
        else if (a[mid] < a[right]) {
            if (key > a[mid] && key < a[right])
                return binary_search(a, mid+1, right, key);
            else
                return circular_search(a, left, mid-1, key);
    
        }
    
        return -1;
    
    }
    
    template<typename T>
    void print(const T&a) {
        typedef typename T::const_iterator iterator;
        iterator start = a.begin();
        iterator end = a.end();
        for(; start!=end; ++start)
            std::cout << *start << " ";
        std::cout << std::endl;
    }
    
    int main() {
        typedef std::vector<int> Input;
        Input temp;
        int n =0;
        
        // get n from user
        std::cin >> n;
    
        for(int i=0; i<n; ++i) {
            temp.push_back(i*2);
        }
        Input data;
        data.resize(temp.size());
    
        // Rotate the input sequence
        std::rotate_copy(temp.begin(), temp.begin()+4, 
                         data1.end(), data.begin());
        print(data);
    
        // get key from user
        int key=0;
        std::cin >> key;
    
        int found = circular_search<Input, int>(data, 0, n-1, key);
        if (found)
        {
            assert(key == data[found]);
            std::cout << data[found] 
                      << " found @ pos " 
                      << found << std::endl;
        }
        else
            std::cout << key 
                      << " not found" 
                      << std::endl;
    
        return 0;
    
    }
    
    

    Friday, July 13, 2012

    Hamming sequence

    Hamming's Problem

    Hamming wants an efficient algorithm that generates the list, in ascending order, of all numbers of the form 2i3j5k for i,j,k at least 0. This list is called the Hamming sequence. The list begins like this:
    1 2 3 4 5 6 8 9 10 12 15 16 18 ...

    Brute force technique:

    Take the first number you haven't checked yet, divide it by 2's, 3's and 5's until you can't do that any more, and if you're left with 1, then the number should go on the list; otherwise throw it away and try the next number. So:
    • Is 19 on the list? No, because it's not divisible by 2, 3, or 5.
    • Is 20 on the list? Yes, because after we divide it by 2, 2, and 5, we're left with 1.
    • Is 21 on the list? No, because after we divide it by 3, we're left with 7, which isn't divisible by 2, 3, or 5.
    This obvious technique has one problem: it's unbelievably slow. The problem is that most numbers aren't on the list, and you waste an immense amount of time discovering that. Although the numbers at the beginning of the list are pretty close together, the 2,999th number in the list is 278,628,139,008. Even if you had enough time to wait for the brute-force algorithm to check all the numbers up to 278,628,139,008, think how much longer you'd have to wait for it to finally find the 3,000 number in the sequence, which is 278,942,752,080.

    Linear Solution:

    The idea is that to calculate a[i], we can use a[j]*2 for some j < i. But we also need to make sure that:
    1) a[j]*2 > a[i - 1] and
    2) j is smallest possible.

    Then, a[i] = min(a[j]*2, a[k]*3, a[t]*5)

     
    #include <iostream>
    #include <algorithm>
    #include <vector>
    using namespace std;
    
    int main(void) {
      // get n from user
      unsigned n;
      cout <<"n: ";
      cin >>n;
    
      // list of ugly numbers
      vector <uint64_t> ugly;
      uint64_t x = 1;
      ugly.push_back(x);
    
      // index of next multiple
      unsigned i2 = 0, i3 = 0, i5 = 0;
    
      // value of next multiple
      uint64_t x2 = 2, x3 = 3, x5 = 5;
    
      // loop through ugly numbers
      for(unsigned a = 1; a < n; a++) {
    
        x = std::min(x2, std::min(x3,x5));
    
        ugly.push_back(x);
        if (x == x2) { i2++; x2 = ugly[i2] * 2; }
        if (x == x3) { i3++; x3 = ugly[i3] * 3; }
        if (x == x5) { i5++; x5 = ugly[i5] * 5; }
      }
    
      // return last ugly number found
      cout << x << endl;
      return 0;
    
    }
    

    Friday, September 25, 2009

    HowEasy - Topcoder Arena

    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 <iostream>
    #include <sstream>
    #include <string>
    
    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;
    }
    
    

    Wednesday, September 09, 2009

    Compare Vector V1 and V2 for equality

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


    Monday, July 27, 2009

    Convert "man page" into text file

    Save a man page into text file

    Option #1



    man -P cat ls > man_ls.txt


    Option #2:



    man ls | col -b > ls.txt

    Wednesday, July 15, 2009

    First try in C#

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