Reverse of a string

class Reverse {

    static void reverse(String s, int i) {
        if(i == s.length()) {
            return;
        } else {
            reverse(s, i+1);
            System.out.print(s.charAt(i));
        }
    }

    public static void main(String s[]) {
        String str = "Manish";
        System.out.print("Reverse of '" + str + "' is :: ");
        reverse(str, 0);
        System.out.println();
    }
}

--

Thanks & Regards
Manish Kumar

मेरी छत पर तिरंगा रहने दो.

ये पेड़ ये पत्ते ये शाखें भी परेशान हो जाएं !
अगर परिंदे भी हिन्दू और मुस्लमान हो जाएं !

सूखे मेवे भी ये देख कर हैरान हो गए..,

न जाने कब नारियल हिन्दू और खजूर मुसलमान हो गए......

न मस्जिद को जानते हैं , न शिवालों को जानते हैं
जो भूखे पेट होते हैं,वो सिर्फ निवालों को जानते हैं.

मेरा यही अंदाज ज़माने को खलता है.
की मेरा चिराग हवा के खिलाफ क्यों जलता है......

मैं  अमन पसंद हूँ ,मेरे शहर में दंगा रहने दो...
लाल और हरे में मत बांटो ,मेरी छत पर तिरंगा रहने दो....

बात अच्छी है, मगर अधूरी है, मेरे यार, 

अगर चाहिए तुम्हे दुनिया में अमन और प्यार, 

तो अपनी छत पर तिरंगा भी मत रहने दो, 

ये आखिरी दीवार है, इसे भी ढहने दो। 

इन झंडों ने भी इंसान को बाँटा है, 

दुनिया को टुकड़ों में काटा है। 

उस दिन दुनिया में सचमुच अमन हो जायेगा, 

जब इंसानियत मजहब और सारा जहाँ वतन हो जायेगा।

--

Thanks & Regards
Manish Kumar

Thread creation using Executor

import java.util.concurrent.ExecutorService;

import java.util.concurrent.Executors;

public class ManuThread {

public static class Counter implements Runnable {

int count;

Counter(int count) {

this.count = count;

}

public void run() {

System.out.println(Thread.currentThread().getId() + " : Count : "

+ count);

}

}

/**

* @param args

*/

public static void main(String[] args) {

// TODO Auto-generated method stub

ExecutorService executor = Executors.newFixedThreadPool(Integer

.parseInt("100"));

for (int i = 0; i < 100; i++) {

Runnable worker = new Counter(i);

executor.execute(worker);

}

executor.shutdown();

while (!executor.isTerminated()) {

}

System.out.println("\nFinished all threads ");

}

}

in/on

On for days and dates, in for duration, at for precise times, including full dates that include the time:

Created in 3 hours and 15 minutes.

Created on the 13th of July

Created on 2013-07-13

Created at 14:35

Created at 2013-07-13 14:35

--

Thanks & Regards
Manish Kumar

Java Basic Lesson 2

Code:

package man;
public class Test {
 public void test(boolean a) {
  try {
   if (a) {
    while (true)
     ;
   } else {
    System.out.println("Ramayan");
    // System.exit(1);
   }
  } finally {
   System.out.println("Mahabharat");
  }
 }

 public static void main(String[] args) {
  Test t1 = new Test();
  t1.test(false);
 }
}

Output :

Ramayan
Mahabharat

Code:

package man;
public class Test {
 public void test(boolean a) {
  try {
   if (a) {
    while (true)
     ;
   } else {
    System.out.println("Ramayan");
    System.exit(1);
   }
  } finally {
   System.out.println("Mahabharat");
  }
 }

 public static void main(String[] args) {
  Test t1 = new Test();
  t1.test(false);
 }
}

Output :

Ramayan

Java Basic Lesson 1

Code:

package java.basics;

public class Test {
	public static void main(String[] args) {
		System.out.println("Mahabharat");
	}

}

Output :

Exception in thread "main" java.lang.SecurityException: Prohibited package name: java.basics
	at java.lang.ClassLoader.preDefineClass(Unknown Source)
	at java.lang.ClassLoader.defineClass(Unknown Source)
	at java.security.SecureClassLoader.defineClass(Unknown Source)
	at java.net.URLClassLoader.defineClass(Unknown Source)
	at java.net.URLClassLoader.access$100(Unknown Source)
	at java.net.URLClassLoader$1.run(Unknown Source)
	at java.net.URLClassLoader$1.run(Unknown Source)
	at java.security.AccessController.doPrivileged(Native Method)
	at java.net.URLClassLoader.findClass(Unknown Source)
	at java.lang.ClassLoader.loadClass(Unknown Source)
	at sun.misc.Launcher$AppClassLoader.loadClass(Unknown Source)
	at java.lang.ClassLoader.loadClass(Unknown Source)
	at sun.launcher.LauncherHelper.checkAndLoadMain(Unknown Source)

Sum the digits of a given number without using loop

Problem Statement :

Sum the digits of a given number without using loop.

Solution :

Recursion.

Java Code :

package api.recursion;
public class Numbers { 

        int sumDigits(int no) {
  return no == 0 ? 0 : no%10 + sumDigits(no/10) ;
 }

 public static void main(String s[]) {
  System.out.println((new Numbers()).sumDigits(1342));
 }

}

Print numbers from 1 to 100 without using loop

Problem Statement :

Print numbers from 1 to 100 without using loop.

Solution :

Recursion.

Java Code :

package api.recursion;
public class Numbers {
 void printNos(int n) {
  if (n > 0) {
   printNos(n - 1);
   System.out.println(n);
  }
 }

 public static void main(String s[]) {
  (new Numbers()).printNos(100);
 }
}

String pool and garbage collector

package api.test;

public class MyString {
    public static void main(String[] args) {
        try {
            String s = "";
            int i;
            long start = System.currentTimeMillis();
            for (i = 0; i < 1000000; i++) {
                s += i + "";
            }
            System.out.println(s);
            System.out.println(System.currentTimeMillis() - start);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}
Interesting facts -

1. No OutOfMemory Exception (Executed in 15150132 ms)
2. jconsole shows that garbage collector is reclaiming the memory. 
3. Graph (using jconsole) is given below ( X - Time, Y - Memory)

LG Optimus L3 E400 hard reset If you have forgotten PIN or Password

All data will be lost! Remember to back up any important data before doing a hard reset.

When the phone is turned off, press and hold the Home key + Volume down key + Power key for over 10 seconds. When the screen shows the LG logo, release the Power key.

After the screen shows the hard reset screen, release the other keys.
Leave your phone for at least a minute while it performs the hard reset, then your phone will be turned on.

--

Thanks & Regards
Manish Kumar

Download any video from youtube facebook metacafe and more in one link

Flash Video Down loader helps you to download any video (flv, mp4, HD) from YouTube-like, Facebook, Break, Metacafe and more in one click. You can download mp3, music (iPod), avi and more.

https://addons.mozilla.org/en-us/firefox/addon/flash-video-downloader/

Education Cess Collection Figures for the perion from 2011-12 to 2012-13

--

Thanks & Regards
Manish Kumar

Project Euler - Sum square difference

Problem Statement :

The sum of the squares of the first ten natural numbers is,
12 + 22 + ... + 102 = 385
The square of the sum of the first ten natural numbers is,
(1 + 2 + ... + 10)2 = 552 = 3025
Hence the difference between the sum of the squares of the 
first ten natural numbers and the square of the sum is 
3025 − 385 = 2640.

Find the difference between the sum of the squares of the first
one hundred natural numbers and the square of the sum.

Solution :

Sum of n numbers = [n * (n + 1) / 2]
Square of Sum of n numbers = [n * (n + 1) / 2] ^ 2
Sum of squares of n numbers = [n * (n + 1) * (2n + 1) / 6] 
Difference 
 = [n * (n + 1) / 2] ^ 2 - [n * (n + 1) * (2n + 1) / 6] 
 = [n * (n + 1) * n * (n + 1)/ 4] - [n * (n + 1) * (2n + 1) / 6] 
 = n * (n + 1) * [n * (n + 1) / 4 - (2n + 1) / 6]
 = n * (n + 1) * [3 * n ^ 2 + 3n - 4n - 2 ] / 12
 = n * (n + 1) * [3 * n ^ 2 - n - 2 ] / 12
 = n * (n + 1) * [3 * n ^ 2 - 3n + 2n - 2 ] / 12
 = n * (n + 1) * [3n (n - 1) + 2 * (n - 1)] / 12
 = n * (n + 1) * [(n-1) * (3n + 2)] / 12
 = n * (n + 1) * (n - 1) * (3n + 2) / 12

Java Code :

package math;
public class Solution6 {
        public long difference(int n) {
                long l = 1;
                long r = l*n*(n+1)*(n-1)*(3*n+2)/12;
                return r;
        }

        public static void main(String[] args) {
                Solution6 a = new Solution6();
                long start = System.currentTimeMillis();
                System.out.println(a.difference(10000000));
                System.out.println(
                        System.currentTimeMillis() - start);  
        }
} 

Output:

228213335568242410
0

Project Euler - Smallest multiple

Problem Statement :

2520 is the smallest number that can be divided by each of the 
numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible 
by all of the numbers from 1 to 20?

Solution :

Result is LCM of 1, 2, 3, 4, 5, 6, 7, 8, 9, 10  ....... n.

Java Code :

package euler;

public class Solution5 {
    private long lcm(long a, long b) {
        long p = a * b;
        return p / gcd(a, b);
    }

    private long gcd(long a, long b) {
        // base case
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

    public long reduce(int n) {
        long r = lcm(1, 2);
        for (int i = 3; i <= n; i++) {
            r = lcm(r, i);
        }
        return r;
    }

    public static void main(String[] args) {
        Solution5 a = new Solution5();
        long start = System.currentTimeMillis();
        System.out.println(a.reduce(10));
        System.out.println(a.reduce(20));
        System.out.println(a.reduce(100));
        System.out.println("Time taken : "
            + (System.currentTimeMillis() - start));
    }
}

Output:

    
    2520
    232792560
    1170615464648030300
    Time taken : 0

Project Euler - Largest Palindrome Product

Problem Statement :

A palindromic number reads the same both ways. The largest 
palindrome made from the product of two 2-digit numbers is 
9009 = 91 × 99.

Find the largest palindrome made from the product of two 
3-digit numbers.

Java Code :

package euler;

public class Solution4 {

        public long reverse(long number) {
            long result = 0;
            while (number != 0) {
                long lastDigit = number % 10;
                result = result * 10 + lastDigit;
                number = number / 10;
            }
            return result;
        }

        public boolean isPalindrome(long number) {
            return number == reverse(number);
        }

        public long getNumber() {
            long r = 1;
            for (int i = 100; i <= 999; i++) {
                for (int j = i; j <= 999; j++) {
                    long prod = (long) i * j;
                    if (isPalindrome(prod)) {
                        if(prod > r) r = prod;
                    }
                }
            }
            return r;
        }

        public static void main(String[] args) {
            Solution4 a = new Solution4();
            long start = System.currentTimeMillis();
            System.out.println(a.getNumber());
            System.out.println("Time taken : "
                + (System.currentTimeMillis() - start));
        }

}

Output:

        906609
        Time taken : 139

Project Euler - Largest prime factor

Problem Statement :

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

Java Code :

package euler;

public class Solution3 {

    public long solve() {
        long n = 600851475143L;
        long lastfactor = n;
        int s = (int) Math.sqrt(n);
        int i = 2;
        while(n > 1 && i < s) {
            if(n % i == 0) {
                n = n / i;
                lastfactor = i;
                while (n % i == 0) {
                    n = n / i;
                }
                s = (int) Math.sqrt(n);
            }
            if(i == 2) {
                i++;
            } else {
                i += 2;
            }
        }
        if (n != 1) lastfactor = n; 
        return lastfactor;
    }


    public static void main(String[] args) {
        Solution3 a = new Solution3();
        long start = System.currentTimeMillis();
        System.out.println(a.solve());
        System.out.println("Time taken : "
                + (System.currentTimeMillis() - start));
    }

}

Output:

        6857
        Time taken : 0

Project Euler - Even Fibonacci numbers

Problem Statement :

Each new term in the Fibonacci sequence is generated by adding
the previous two terms. By starting with 1 and 2, the first 10
terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values
do not exceed four million, find the sum of the even-valued terms.

Java Code :

package euler;
public class Solution2 {
    public long fibSumEvenValuedTerms() {
        long sum = 0;
        long a = 0, b = 1;
        while(b < 4000000) {
            long c = a + b;
            if(c % 2 == 0) sum += c;
            a = b;
            b = c;
        }
        return sum;
    }

    public static void main(String[] args) {
        Solution2 a = new Solution2();
        long start = System.currentTimeMillis();
        System.out.println(a.fibSumEvenValuedTerms());
        System.out.println(
            System.currentTimeMillis() - start);
    }

}

Output:

        
        4613732
        0

Project Euler - Multiples of 3 and 5 less than 1000

Problem Statement :

If we list all the natural numbers below 10 that are multiples
of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is
23. Find the sum of all the multiples of 3 or 5 below 1000.

Solution :

We can avoid iteration while finding sum of multiples of x less
than y by using the following -

Sum of Arithmetic Progression = n * [2a + (n - 1) * d] / 2. 
In this case a = x, d = x and
n = y / x  if y is not a multiple of x
n = y / x - 1 if y is  a multiple of x
Again,
    Sum of Multiples of 3 and 5 less than 1000 = 
        Sum of multiples of 3 less than 1000
        + Sum of multiples of 5 less than 1000
        - Sum of multiple of 15 less than 1000.
i.e.
    result = a.sumOfMultiplesOfXLessThanY(3, 1000)
        + a.sumOfMultiplesOfXLessThanY(5, 1000)
        - a.sumOfMultiplesOfXLessThanY(15, 1000);

Java Code :

public class Solution1 {
    public long sumOfMultiplesOfXLessThanY(int x, int y) {
        // no. of multiples less than or equal to y
        long n = y / x;
        // no. of multiples less than y
        if (y % x == 0)
        n--;
        // sum of arithmetic progression where x is initial 
        // term, x is difference and t is number of terms
        long sum = n * (2 * x + (n - 1) * x) / 2;
        return sum;
    }

    public static void main(String[] args) {
        Solution1 a = new Solution1();
        long start = System.currentTimeMillis();
        System.out.println(
            "Sum of multiples of 3 less than 1000 : "
                + a.sumOfMultiplesOfXLessThanY(3, 1000));
        System.out.println(
            "Sum of multiples of 5 less than 1000 : "
                + a.sumOfMultiplesOfXLessThanY(5, 1000));
        System.out.println(
            "Sum of multiples of 15 less than 1000 : "
                + a.sumOfMultiplesOfXLessThanY(15, 1000));
        long result = 
            a.sumOfMultiplesOfXLessThanY(3, 1000)
                + a.sumOfMultiplesOfXLessThanY(5, 1000)
                - a.sumOfMultiplesOfXLessThanY(15, 1000);
        System.out.println(
            "Final result : " + result);
        System.out.println(
            "Time taken : "
                + (System.currentTimeMillis() - start));
    }
}

Output:

    Sum of multiples of 3 less than 1000 : 166833
    Sum of multiples of 5 less than 1000 : 99500
    Sum of multiples of 15 less than 1000 : 33165
    Final result : 233168
    Time taken : 0

How to save income tax!

At the end of every financial year, many tax payers frantically make investments to minimize taxes, without adequate knowledge of the various available options. The Income Tax Act offers many more incentives and allowances, apart from the popular 80C, which could reduce tax liability substantially for the salaried individuals. Here are seven smart tips to help you save more and reduce taxes.
            
1. Salary Restructuring

Restructuring your salary may not always be possible. But if your company permits, or if you are on good terms with your HR department, restructuring a few components could reduce your tax liability.

• Opt for food coupons instead of lunch allowances, as they are exempt from tax up to Rs. 60,000 per year
• Include medical allowance, transport allowance, education allowance, uniform expenses (if any), and telephone expenses as part of salary. Produce bills of actual expenses incurred for these allowances to reduce tax
• Opt for the company car instead of using your own car, to reduce high prerequisite taxation.

   
2. Utilizing Section 80C
Section 80C offers a maximum deduction of up to Rs. 1,00,000. Utilize this section to the fullest by investing in any of the available investment options. A few of the options are as follows:

•     Public Provident Fund
•     Life Insurance Premium
•     National Savings Certificate
•     Equity Linked Savings Scheme
•     5 year fixed deposits with banks and post office
•     Tuition fees paid for children's education, up to a maximum of 2 children

3. Options beyond 80C
If you have exhausted your limit of Rs. 1,00,000 under section 80C, here are a few more options:

• Section 80D - Deduction of Rs. 15,000 for medical insurance of self, spouse and dependent children and Rs. 20,000 for medical insurance of parents above 65 years
• Section 80CCF- Deduction of Rs. 20,000, in addition to the Rs.1,00,000 under 80C, for investments in notified infrastructure bonds
• Section 80G- Donations to specified funds or charitable institutions.

   
4. House Rent Allowance
Are you paying rent, yet not receiving any HRA from your company? The least of the following could be claimed under Section 80GG:

•  25 per cent of the total income or
• Rs. 2,000 per month or
• Excess of rent paid over 10 per cent of total income

This deduction will however not be allowed, if you, your spouse or minor child owns a residential accommodation in the location where you reside or perform office duties.
    

If HRA forms part of your salary, then the minimum of the following three is available as exemption:

•     The actual HRA received from your employer
• The actual rent paid by you for the house, minus 10 per cent of your salary (this includes basic  dearness allowance, if any)
• 50 per cent of your basic salary (for a metro) or 40 per cent of your basic salary (for non-metro).

5. Tax Saving from Home Loans
Use your home loan efficiently to save more tax. The principal component of your loan, is included under Section 80C, offering a deduction up to Rs. 1,00,000. The interest portion offers a deduction up to Rs. 1,50,000 separately under Section 24.

6. Leave Travel Allowance
Use your Leave Travel Allowance for your holidays, which is available twice in a block of four years. In case you have been unable to claim the benefit in a particular four- year block, you could now carry forward one journey to the succeeding block and claim it in the first calendar year of that block. Thus, you may be eligible for three exemptions in that block.

7. Tax on Bonus
A bonus from your employer is fully taxable in the year in which you receive it. However request your employer for the following:

•  If you anticipate tax rates to be reduced or slabs to be modified in the subsequent year, see if you could push the bonus payment to the subsequent year
• Produce your tax investment details well before, to prevent your employer from deducting tax on bonus before handing it over

A Final Word
Keep in mind the below points, to avoid the hassles of last minute tax planning.

• Give your employer details of loans and tax saving investments beforehand, to prevent any excess deduction
• Check the Form 16 received at the end of each year from your employer thoroughly
• It is important to start your tax planning well before 31st March, and to file your returns before the 31st of July each year

--
Thanks & Regards
Manish Kumar

Product array problem - EverNote challenge

Given a list of integers, your task is to write a program to output an integer-valued list of equal length such that the output element at index 'i' is the product of all input elements except for the input element at 'i'.
In other words, let inputArray by an integer array of length 'n'. The solution,computed into outputArray, would be:
for each j from 1 to n-2:
outputArr[ j ] = inputArray[0] * inputArray[1] * inputArray[2] * ... * inputArray[j-1] * inputArray[j+1] * inputArray[j+2] *...* inputArray[n-1]
for j = 0
outputArray[0] = inputArray[1] * outputArray[2] * ... * outputArray[n-1]
for j = n-1
outputArray[n-1] = outputArray[0] * outputArray[1] * outputArray[2] * ... * outputArray[n-2]
As an example, if inputArray = { 1, 2, 3, 4 }, then
outputArray = { 2*3*4, 1*3*4, 1*2*4, 1*2*3 }.
Your program should run in O(n) time and should be space efficient.

Input format

First line of input contains N , number of elements in list.
Next N lines will each contain an element (a signed integer)

Output format

Print the output list of numbers.

Sample input

4
5
2
2
3

Sample output

12
30
30
20

Constraint

You may assume that:

• The input array size will always have at least two elements in it, that is, n >= 2.
• The product of any subset of the input will never exceed the value of a 64 bit integer.
• The maximum length of input array is 1000.

Solution:
Space complexity : O(1).
Time complexity : O(N)

import java.io.*;

public class Solution {
 public static void main(String[] args) throws 
     RuntimeException, IOException {
  BufferedReader br = 
    new BufferedReader(
      new InputStreamReader(System.in));
  int N = Integer.parseInt(br.readLine());
  long a[] = new long[N];
  long prod = 1;
  int zerocount = 0;
  for (int i = 0; i < N; i++) {
   a[i] = Long.parseLong(br.readLine());
   if (a[i] == 0) {
    zerocount++;
   } else {
    prod *= a[i];
   }
  }
  if (zerocount > 1) {
   for (int i = 0; i < N; i++) {
    System.out.println(0);
   }
   // none or only one zero in array
  } else {
   for (int i = 0; i < N; i++) {
    if (a[i] == 0) {
     System.out.println(prod);
    } else {
     // one zero in array
     if (zerocount > 0) {
      System.out.println(0);
      // no zeroes in array
     } else {
      System.out.println(prod / a[i]);
     }
    }
   }
  }
 }
}

--
Thanks & Regards
Manish Kumar

Enable Java in a web browser on Ubuntu

http://java.com/en/download/help/enable_browser_ubuntu.xml
--
Thanks & Regards
Manish Kumar

Stack with getMin() and getMax() in O(1)

import java.util.Stack;


public class StackWithMinMax extends Stack<Integer> {

    /**
     *
     */
    private static final long serialVersionUID = 1L;
    private Stack<Integer> minStack;
    private Stack<Integer> maxStack;

    public StackWithMinMax() {
        minStack = new Stack<Integer>();
        maxStack = new Stack<Integer>();
    }

    public void push(int value) {
        if (value <= min()) { // Note the '=' sign here
            minStack.push(value);
        }

        if (value >= max()) {
            maxStack.push(value);
        }

        super.push(value);
    }

    public Integer pop() {
        int value = super.pop();

        if (value == min()) {
            minStack.pop();
        }

        if (value == max()) {
            maxStack.pop();
        }

        return value;
    }

    public int min() {
        if (minStack.isEmpty()) {
            return Integer.MAX_VALUE;
        } else {
            return minStack.peek();
        }
    }

    public int max() {
        if (maxStack.isEmpty()) {
            return Integer.MIN_VALUE;
        } else {
            return maxStack.peek();
        }
    }
}

--
Thanks & Regards
Manish Kumar

Convert a Binary Search Tree into a sorted doubly linked list.

package cs.ds.amazon;

class Node {
    int data;
    Node left;
    Node right;

    public Node(int data) {
        this.data = data;
        left = null;
        right = null;
    }
}

public class TreeList {
    public static void join(Node a, Node b) {
        a.right = b;
        b.left = a;
    }

    public static Node append(Node a, Node b) {
        // if either is null, return the other
        if (a == null)
            return (b);
        if (b == null)
            return (a);
        // find the last node in each using the .previous pointer
        Node aLast = a.left;
        Node bLast = b.left;
        // join the two together to make it connected and circular
        join(aLast, b);
        join(bLast, a);
        return (a);
    }

    /*
     * --Recursion-- Given an ordered binary tree, recursively change it into a
     * circular doubly linked list which is returned.
     */

    public static Node treeToList(Node root) {
        // base case: empty tree -> empty list
        if (root == null)
            return (null);
        // Recursively do the subtrees (leap of faith!)
        Node aList = treeToList(root.left);
        Node bList = treeToList(root.right);
        // Make the single root node into a list length-1
        // in preparation for the appending
        root.left = root;
        root.right = root;
        // At this point we have three lists, and it's
        // just a matter of appending them together
        // in the right order (aList, root, bList)
        aList = append(aList, root);
        aList = append(aList, bList);
        return (aList);
    }

    /*
     * Given a non-empty tree, insert a new node in the proper place. The tree
     * must be non-empty because Java's lack of reference variables makes that
     * case and this method messier than they should be.
     */

    public static void treeInsert(Node root, int newData) {
        if (newData <= root.data) {
            if (root.left != null)
                treeInsert(root.left, newData);
            else
                root.left = new Node(newData);
        } else {
            if (root.right != null)
                treeInsert(root.right, newData);
            else
                root.right = new Node(newData);
        }
    }

    // Do an inorder traversal to print a tree
    // Does not print the ending "\n"

    public static void printTree(Node root) {
        if (root == null)
            return;
        printTree(root.left);
        System.out.print(Integer.toString(root.data) + " ");
        printTree(root.right);
    }

    // Do a traversal of the list and print it out
    public static void printList(Node head) {
        Node current = head;
        while (current != null) {
            System.out.print(Integer.toString(current.data) + " ");
            current = current.right;
            if (current == head)
                break;
        }
        System.out.println();
    }

    // Demonstrate tree->list with the list 1..5
    public static void main(String[] args) {
        // first build the tree shown in the problem document
        Node root = new Node(4);
        treeInsert(root, 2);
        treeInsert(root, 1);
        treeInsert(root, 3);
        treeInsert(root, 5);
        System.out.println("tree:");
        printTree(root);
        // 1 2 3 4 5
        System.out.println();
        System.out.println("list:");
        Node head = treeToList(root);
        printList(head);
        // 1 2 3 4 5
    }
}
--
Thanks & Regards
Manish Kumar

Random number between two integers

/* Random number between lower and higher, inclusive */
public static int randomNumber(int lower, int higher) {
            return lower + (int)(Math.random() * (higher - lower + 1));
}

--
Thanks & Regards
Manish Kumar

Codejam 2013 - Problem C. Fair and Square

Little John likes palindromes, and thinks them to be fair (which is a fancy word for nice). A palindrome is just an integer that reads the same backwards and forwards - so 6, 11 and 121 are all palindromes, while 10, 12, 223 and 2244 are not (even though 010=10, we don't consider leading zeroes when determining whether a number is a palindrome).
He recently became interested in squares as well, and formed the definition of a fair and square number - it is a number that is a palindrome and the square of a palindrome at the same time. For instance, 1, 9 and 121 are fair and square (being palindromes and squares, respectively, of 1, 3 and 11), while 16, 22 and 676 are not fair and square: 16 is not a palindrome, 22 is not a square, and while 676 is a palindrome and a square number, it is the square of 26, which is not a palindrome.
Now he wants to search for bigger fair and square numbers. Your task is, given an interval Little John is searching through, to tell him how many fair and square numbers are there in the interval, so he knows when he has found them all.

Solving this problem

Usually, Google Code Jam problems have 1 Small input and 1 Large input. This problem has 1 Small input and 2 Large inputs. Once you have solved the Small input, you will be able to download any of the two Large inputs. As usual, you will be able to retry the Small input (with a time penalty), while you will get only one chance at each of the Large inputs.

Input

The first line of the input gives the number of test cases, T. T lines follow. Each line contains two integers, A and B - the endpoints of the interval Little John is looking at.

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the number of fair and square numbers greater than or equal to A and smaller than or equal to B.

Limits

Small dataset

1 ≤ T ≤ 100.
1 ≤ A ≤ B ≤ 1000.

First large dataset

1 ≤ T ≤ 10000.
1 ≤ A ≤ B ≤ 10¹⁴.

Second large dataset

1 ≤ T ≤ 1000.
1 ≤ A ≤ B ≤ 10¹⁰⁰.

Sample

Input	Output
3 1 4 10 120 100 1000	Case #1: 2 Case #2: 0 Case #3: 2

Codejam 2013 - Problem A. Tic-Tac-Toe-Tomek

Problem

Tic-Tac-Toe-Tomek is a game played on a 4 x 4 square board. The board starts empty, except that a single 'T' symbol may appear in one of the 16 squares. There are two players: X and O. They take turns to make moves, with X starting. In each move a player puts her symbol in one of the empty squares. Player X's symbol is 'X', and player O's symbol is 'O'.

After a player's move, if there is a row, column or a diagonal containing 4 of that player's symbols, or containing 3 of her symbols and the 'T' symbol, she wins and the game ends. Otherwise the game continues with the other player's move. If all of the fields are filled with symbols and nobody won, the game ends in a draw. See the sample input for examples of various winning positions.

Given a 4 x 4 board description containing 'X', 'O', 'T' and '.' characters (where '.' represents an empty square), describing the current state of a game, determine the status of the Tic-Tac-Toe-Tomek game going on. The statuses to choose from are:

• "X won" (the game is over, and X won)
• "O won" (the game is over, and O won)
• "Draw" (the game is over, and it ended in a draw)
• "Game has not completed" (the game is not over yet)

If there are empty cells, and the game is not over, you should output "Game has not completed", even if the outcome of the game is inevitable.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of 4 lines with 4 characters each, with each character being 'X', 'O', '.' or 'T' (quotes for clarity only). Each test case is followed by an empty line.

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is one of the statuses given above. Make sure to get the statuses exactly right. When you run your code on the sample input, it should create the sample output exactly, including the "Case #1: ", the capital letter "O" rather than the number "0", and so on.

Limits

The game board provided will represent a valid state that was reached through play of the game Tic-Tac-Toe-Tomek as described above.

Small dataset

1 ≤ T ≤ 10.

Large dataset

1 ≤ T ≤ 1000.

Sample

Input	Output
6 XXXT .... OO.. .... XOXT XXOO OXOX XXOO XOX. OX.. .... .... OOXX OXXX OX.T O..O XXXO ..O. .O.. T... OXXX XO.. ..O. ...O	Case #1: X won Case #2: Draw Case #3: Game has not completed Case #4: O won Case #5: O won Case #6: O won

Using a single array to implement three stacks.

Divide the array in three equal parts and allow the individual stack to grow in that limited space (note: "[" means inclusive, while "(" means exclusive of the end point).

»» for stack 1, we will use [0, n/3)

»» for stack 2, we will use [n/3, 2n/3)

»» for stack 3, we will use [2n/3, n)

This solution is based on the assumption that we do not have any extra information about the usage of space by individual stacks and that we can't either modify or use any extra space. With these constraints, we are left with no other choice but to divide equally.

int stackSize = 300;

int[] buffer = new int [stackSize * 3];

int[] stackPointer = {0, 0, 0}; // stack pointers to track top element

void push(int stackNum, int value) {

/* Find the index of the top element in the array + 1, and

increment the stack pointer */

int index = stackNum * stackSize + stackPointer[stackNum] + 1;

stackPointer[stackNum]++;

buffer[index] = value;

}

int pop(int stackNum) {

int index = stackNum * stackSize + stackPointer[stackNum];

stackPointer[stackNum]--;

int value = buffer[index];

buffer[index]=0;

return value;

}

int peek(int stackNum) {

int index = stackNum * stackSize + stackPointer[stackNum];

return buffer[index];

}

boolean isEmpty(int stackNum) {

return stackPointer[stackNum] == stackNum*stackSize;

}

--
Thanks & Regards
Manish Kumar

Database indexes

Discussed at : 
http://stackoverflow.com/questions/1108/how-does-database-indexing-work

Answered by : http://stackoverflow.com/users/264/xenph-yan 

"Why is it needed?

When data is stored on disk based storage devices, it is stored as blocks of data. These blocks are accessed in their entirety, making them the atomic disk access operation. Disk blocks are structured in much the same way as linked lists; both contain a section for data, a pointer to the location of the next node (or block), and both need not be stored contiguously.

Due to the fact that a number of records can only be sorted on one field, we can state that searching on a field that isn't sorted requires a Linear Search which requires N/2 block accesses (on average), where N is the number of blocks that the table spans. If that field is a non-key field (i.e. doesn't contain unique entries) then the entire table space must be searched at N block accesses.

Whereas with a sorted field, a Binary Search may be used, this has log2 N block accesses. Also since the data is sorted given a non-key field, the rest of the table doesn't need to be searched for duplicate values, once a higher value is found. Thus the performance increase is substantial.

What is indexing?

Indexing is a way of sorting a number of records on multiple fields. Creating an index on a field in a table creates another data structure which holds the field value, and pointer to the record it relates to. This index structure is then sorted, allowing Binary Searches to be performed on it.

The downside to indexing is that these indexes require additional space on the disk, since the indexes are stored together in a MyISAM database, this file can quickly reach the size limits of the underlying file system if many fields within the same table are indexed.

How does it work?

Firstly, let's outline a sample database table schema;

Field name       Data type      Size on disk 

id (Primary key) Unsigned INT   4 bytes 

firstName        Char(50)       50 bytes 

lastName         Char(50)       50 bytes 

emailAddress     Char(100)      100 bytes  

Note: char was used in place of varchar to allow for an accurate size on disk value. This sample database contains five million rows, and is unindexed. The performance of several queries will now be analyzed. These are a query using the id (a sorted key field) and one using the firstName (a non-key unsorted field).

Example 1

Given our sample database of r = 5,000,000 records of a fixed size giving a record length of R = 204 bytes and they are stored in a MyISAM database which is using the default block size B = 1,024 bytes. The blocking factor of the table would be bfr = (B/R) = 1024/204 = 5 records per disk block. The total number of blocks required to hold the table is N = (r/bfr) = 5000000/5 = 1,000,000 blocks.

A linear search on the id field would require an average of N/2 = 500,000 block accesses to find a value given that the id field is a key field. But since the id field is also sorted a binary search can be conducted requiring an average of log2 1000000 = 19.93 = 20 block accesses. Instantly we can see this is a drastic improvement.

Now the firstName field is neither sorted, so a binary search is impossible, nor are the values unique, and thus the table will require searching to the end for an exact N = 1,000,000 block accesses. It is this situation that indexing aims to correct.

Given that an index record contains only the indexed field and a pointer to the original record, it stands to reason that it will be smaller than the multi-field record that it points to. So the index itself requires fewer disk blocks that the original table, which therefore requires fewer block accesses to iterate through. The schema for an index on the firstName field is outlined below;

Field name       Data type      Size on disk 

firstName        Char(50)       50 bytes 

(record pointer) Special        4 bytes  

Note: Pointers in MySQL are 2, 3, 4 or 5 bytes in length depending on the size of the table.

Example 2

Given our sample database of r = 5,000,000 records with an index record length of R = 54 bytes and using the default block size B = 1,024 bytes. The blocking factor of the index would be bfr = (B/R) = 1024/54 = 18 records per disk block. The total number of blocks required to hold the table is N = (r/bfr) = 5000000/18 = 277,778 blocks.

Now a search using the firstName field can utilise the index to increase performance. This allows for a binary search of the index with an average of log2 277778 = 18.08 = 19 block accesses. To find the address of the actual record, which requires a further block access to read, bringing the total to 19 + 1 = 20 block accesses, a far cry from the 277,778 block accesses required by the non-indexed table.

When should it be used?

Given that creating an index requires additional disk space (277,778 blocks extra from the above example), and that too many indexes can cause issues arising from the file systems size limits, careful thought must be used to select the correct fields to index.

Since indexes are only used to speed up the searching for a matching field within the records, it stands to reason that indexing fields used only for output would be simply a waste of disk space and processing time when doing an insert or delete operation, and thus should be avoided. Also given the nature of a binary search, the cardinality or uniqueness of the data is important. Indexing on a field with a cardinality of 2 would split the data in half, whereas a cardinality of 1,000 would return approximately 1,000 records. With such a low cardinality the effectiveness is reduced to a linear sort, and the query optimizer will avoid using the index if the cardinality is less than 30% of the record number, effectively making the index a waste of space".

--
Thanks & Regards
Manish Kumar

Google Certification

http://www.google.co.in/analytics/iq.html
http://www.google.com/intl/en_uk/adwords/professionals/


--
Thanks & Regards
Manish Kumar

My question to the government of Bihar - Cabinet Secretariat and Department of Information & Technology

1. Which portals are maintained by government of Bihar and what are the services given through them to the citizens?
2. How much money is spend annually for maintaining each of the portals?
3. Whom should a citizen contact if any of the service is not available?
4. Whom should a citizen contact if webmaster is not contactable?
5. Where should the citizen complain if he does not get the answer from the contact numbers of Beltron office?
6. How many application were received through these portals and how many certificates were delivered? Please give the bifurcation for individual services e.g. birth registration, death registration, RTI Application and others if any.
   

--
Thanks & Regards
Manish Kumar

Truth of e-Governance in Bihar - Part 1

Portal : http://www.biharonline.gov.in/

Facility - Links to download forms to get different type of services - http://www.biharonline.gov.in/Site/Core/Government/MangCont/List.aspx?typ=f
 Click on any link, you will be greeted with a page similar to the page below -

Facility -  Online services

http://www.biharonline.gov.in/Site/Core/Login.aspx
Register  here.
Status- Success.

Login happily.


Try to use a facility ( Say birth registration) -  Will work fine if you have 4-5 years of experience filling the forms online, you are preferably a programmer (Recommended format for date of birth is DD/MM/YYYY, but it accepts YYYY-MM-DD).

You will get the screen for payment like -

Try to proceed. You will be greeted with -

Enjoy surfing.


More Comong soon ...........

--
Thanks & Regards
Manish Kumar

Connect AWS instance with a standalone SSH Client

To access your instance:

1. Open an SSH client.
2. Locate your private key file (**********.pem). The wizard automatically detects the key you used to launch the instance.
3. Your key file must not be publicly viewable for SSH to work. Use this command if needed:
   chmod 400 **********.pem
4. Connect to your instance using its Public DNS. [e.g. ec2-46-137-194-79.ap-southeast-1.compute.amazonaws.com].

Example

Enter the following command line:

ssh -i hackathon.pem ubuntu@ec2-46-137-194-79.ap-southeast-1.compute.amazonaws.com

--
Thanks & Regards
Manish Kumar

Cool

<!DOCTYPE html>
<html>
<head>
<script src="//ajax.googleapis.com/ajax/libs/jquery/1.8.3/jquery.min.js">
</script>

<style type="text/css">
#dropdown-1,#dropdown-2,#dropdown-3
{
padding:5px;
text-align:left;
background-color:#e5eecc;
border:solid 1px #c3c3c3;
}

</style>

<script>
$(document).ready(function(){

  $('div.dropdown').each(function() {
    var $dropdown = $(this);

    $("a.dropdown-link", $dropdown).click(function(e) {
      e.preventDefault();
      $div = $("div.dropdown-container", $dropdown);
      $div.slideToggle("slow");
      $("div.dropdown-container").not($div).hide();
      return false;
    });

});
  
  $('html').click(function(){
    $("div.dropdown-container").hide();
  });
   
});


</script>
</head>
<body>
   <div id="dropdown-1" class="dropdown dropdown-processed">
  <a class="dropdown-link" href="#">Options</a>
  <div class="dropdown-container" style="display: none;">
    <ul>
      <li>Item 1</li>
      <li>Item 2</li>
      <li>Item 3</li>
    </ul>
  </div>
</div>

<div id="dropdown-2" class="dropdown dropdown-processed">
  <a class="dropdown-link" href="#">Options</a>
  <div class="dropdown-container" style="display: none;">
    <ul>
      <li>Item 1</li>
      <li>Item 2</li>
      <li>Item 3</li>
    </ul>
  </div>
</div>

<div id="dropdown-3" class="dropdown dropdown-processed">
  <a class="dropdown-link" href="#">Options</a>
  <div class="dropdown-container" style="display: none;">
    <ul>
      <li>Item 1</li>
      <li>Item 2</li>
      <li>Item 3</li>
    </ul>
  </div>
</div>

</body>
</html>

--
Thanks & Regards
Manish Kumar

Dog bite treatment

After a dog bite, you may need up to two types of vaccinations. Or you may need none at all. The first vaccine you may need is a single tetanus booster. But you don't need it if your last tetanus shot was less than 5 years before. Any puncture wound can lead to tetanus, so animal bites are always considered a potential source of tetanus infection, regardless of the animal's heath or vaccination status.
The second vaccine you might need is a rabies vaccine. Because this vaccine is expensive, and you need about 5 rabies vaccines in total (plus a 6th injection of rabies immunoglobulin in your buttocks), your doctor will not give you this vaccine unless the animal is shown to be rabid. Usually a dog or cat that bites a person will be monitored by a vet for 10 days, even if it's up-to-date on it's vaccines (because not every vaccine is 100% effective). If the animal doesn't show any signs of illness during that period, then there is absolutely no way it could have infected you with rabies, so you wouldn't need any of this. The only other main health risk from an animal bite is a local infection of the bite area. A lot of doctors will prescribe a week's worth of antibiotics, just to prevent a nasty infection.

Anti-rabies Vaccine : There are many types of anti-rabies vaccine available: The Human Diploid Cell Vaccine, Vero-Cell Purified Vaccine, Purified Chick Embryo Vaccine and the less expensive Nerve Tissue Vaccine. The human diploid cell vaccine or the Purified Vero-Cell Rabies vaccine is most often recommended for post-exposure prophylaxis. It is given in 5 doses on days 0, 3, 7, 14 and 28. This is usually sufficient to protect a person from rabies, but people in whom the immune system is weak, may need an extra dose on the 90th day.

Question : In the past, why was injection administered in the stomach for dog bite?
Answers : http://www.hindu.com/seta/2004/04/08/stories/2004040800221900.htm,
http://wiki.answers.com/Q/Why_are_rabies_treatment_shots_given_in_the_stomach



--
Thanks & Regards
Manish Kumar

Flipkart programming test question

• Question 1 / 1 (Dollar Rate)
  Assuming we have data of how dollar rates are changing. Now given a data range, you need to find out during that range what was the rate that remained maximum duration?
  eg.
  day | dollar value
  1          52
  2          55
  9          60
  10        57
  12        55
  
  - for day range (3:5), value remained constant at 55, so solution is 55
  - for day range (7:13), break up is
  7-9 (2 day) -> 55
  9-10 (1 days) -> 60
  10-12 (2 days) -> 57
  12-13 (1 days) -> 55
  
  So, 55 stayed for max no. of days (3)
  
  Input format:
  First line contains no. of data points N, followed by N lines contains space separated 2 numbers. 1st is the day index and 2nd is the new dollar rate effective from that day.
  Last line contains space separated 2 numbers p and q.
  Output format
  One number representing dollar rate that remained for max number of days between p and q.
  
  Sample Input 1
  5
  1          52
  2          55
  9          60
  10        57
  12        55
  
  3  5
  
  Sample Output 1
  55
  
  Sample Input 2
  5
  1          52
  2          55
  9          60
  10        57
  12        55
  
  7  13
  
  Sample Output
  55

--
Thanks & Regards
Manish Kumar

Navratri in 2012 October dates

Navratri Day 1 – October 16, 2012 – Ghatsthapana

Navratri Day 2 – October 17, 2012 – Chandra Darshan

Navratri Day 3 – October 18, 2012 – Sindoor Tritiya

Navratri Day 4 – October 18, 2012 – Varad Vinayak Chaturthi and Lalit Panchami

Navratri Day 5 – October 19, 2012 – Upang Lalita Vrat

Navratri Day 6 – October 20, 2012 – Saraswati Awahan in some regions

Navratri Day 7 – October 21, 2012 – Saraswathi Puja - Maha Lakshmi Puja

Navratri Day 8 – October 22, 2012 – Saraswathi Puja ends – Mahashtami - Annapoorna Parikrama

Navratri Day 9 – October 23, 2012 – Saraswati Visarjan - Mahanavami

October 24, 2012 - The tenth day is celebrated as Dasara or Vijaya Dashami. Vidyarambham in Kerala.
Note - Navratri day 3 and 4 are marked on same date in calendars followed in Gujarat and Maharashtra.
Note - Navratri day 5 and 6 are marked on same date in calendars followed in North India and other regions. (This clubbing of dates is due to two tithi falling on same date as per Gregorian calendar)


--
Thanks & Regards
Manish Kumar

Change default search engine of Firefox address bar

In Firefox type about:config in the address bar and press ENTER.
Search for Keyword
Locate and double-click the entry for keyword.URL
Modify it by add the below set of values :
Yahoo: http://search.yahoo.com/search?p=
Ask: http://www.ask.com/web?q=
Bing: http://www.bing.com/search?ie=UTF-8&oe=UTF-8&sourceid=navclient&gfns=1&q=
Google: http://www.google.com/search?&q=
DONE


--
Thanks & Regards
Manish Kumar

Maximum length path (sum of edges from root to leaf ) of a binary tree - Asked by Amazon

Note : Edges have weight (positive/negative).
/*

********************* MyNode.java *******************

package mysolution;

class MyNode {

        String label;
        MyNode left;
        MyNode right;
        int edgeToRightChild;
        int edgeToLeftChild;
        int pathWeight; // sum of weights from root to this node
        String pathStr; // path from root to this node

        public String getLabel() {
                return label;
        }

        public void setLabel(String label) {
                this.label = label;
        }

        public MyNode getLeft() {
                return left;
        }

        public void setLeft(MyNode left) {
                this.left = left;
        }

        public MyNode getRight() {
                return right;
        }

        public void setRight(MyNode right) {
                this.right = right;
        }

        public int getEdgeToRightChild() {
                return edgeToRightChild;
        }

        public void setEdgeToRightChild(int edgeToRightChild) {
                this.edgeToRightChild = edgeToRightChild;
        }
        public int getEdgeToLeftChild() {
                return edgeToLeftChild;
        }

        public void setEdgeToLeftChild(int edgeToLeftChild) {
                this.edgeToLeftChild = edgeToLeftChild;
        }

        public int getPathWeight() {
                return pathWeight;
        }

        public void setPathWeight(int pathWeight) {
                this.pathWeight = pathWeight;
        }

        public String getPathStr() {
                return pathStr;
        }

        public void setPathStr(String pathStr) {
                this.pathStr = pathStr;
        }
}


*/
_________________________________________________________________

package mysolution;
import mysolution.MyNode;
import java.util.Stack;// Stack to hold the Nodes of tree

class Solution {


        String maxLengthPath(MyNode root)  {

                Stack s = new Stack();
                root.setPathWeight(0);
                root.setPathStr(root.getLabel());
                s.push(root);
                double max = -999999;
                String path = "";
                while(!s.empty()) {
                        MyNode curr = s.pop();
                        if(curr.getRight() != null) {
                                curr.getRight().setPathWeight(curr.getPathWeight() + curr.getEdgeToRightChild());
                                curr.getRight().setPathStr(curr.getPathStr() + curr.getRight().getLabel());
                                s.push(curr.getRight());
                        }
                        if(curr.getLeft() != null) {
                                curr.getLeft().setPathWeight(curr.getPathWeight() + curr.getEdgeToLeftChild());
                                curr.getLeft().setPathStr(curr.getPathStr() + curr.getLeft().getLabel());
                                s.push(curr.getLeft());
                        }
                        if(curr.getLeft() == null && curr.getRight() == null && curr.getPathWeight() > max) {
                                max = curr.getPathWeight();
                                path = curr.getPathStr();
                        }

                }
                return path;
        }

        public static void main(String args[]) {
                Solution obj = new Solution();
                MyNode root
                // root =  code/function call to create tree;
                String desiredPath = obj.maxLengthPath(root);
                System.out.println(desiredPath);
        }

}

--
Thanks & Regards
Manish Kumar