Check leap year

/** determine if the given year is a leap year.<p>
 
     The Gregorian calendar rule states that a leap year occurs
     every fourth year, except every 100 years, except every 400
     years.<p>
 
     @param year The year to be tested.  Make sure this is a four digit year\!<p>
     @return true if "year" is a leap year.<p>
*/
boolean isLeapYear(int year) {
  boolean y4 = ( (year % 4) == 0 );
  boolean y100 = ( (year % 100) == 0 );
  boolean y400 = ( (year % 400) == 0 );
  return ( y400 || (y4 && ! y100) );
}

Important sites

http://javapapers.com/site-map/
puzzles collection

Nth prime number

Created an array to hold all the discovered primes. For a given a number, check if it already is in the list or not. If yes, it is a prime. If not, check if any of the primes in the list, less than square root of the number, is a factor of this number or not.
             The solution proposed by the Project Euler authors improvised on this. They used an additional fact that any prime greater than 3 is of the form 6k+/-1.
              If you know the upper bound of the prime number, then the Sieve of Eratosthenes gives the answer much quickly.

import java.util.ArrayList;
import java.util.List;

public class NthPrimeNumber {
 public static void main(String[] args) {
  int index = 5;

  if (index == 1) {
   System.out.println(2L);
   return;
  }

  // An array of all the discovered primes
  List<Long> primes = new ArrayList<Long>();
  primes.add(2L);

  Long num = 3L;

  // Search for primes by dividing num with all the known prime numbers
  while (primes.size() != index) {
   boolean isComposite = false;
   double sqrt = Math.sqrt(num);
   for (Long p : primes) {
    if (p > sqrt)
     break;
    if (num % p == 0) {
     isComposite = true;
     break;
    }
   }
   if (!isComposite)
    primes.add(num);
   num++;
  }
  System.out.println(primes.get(index - 1));
 }
}

Maximum of two values using abs

Given two number a and b,find out the maximum of two numbers?
max(a,b) = (abs(a+b)+abs(a-b))/2;

Count the number of numbers up to n which are both square and cube

Count the number of numbers up to n which are both square and cube.
e.g., for 1 < n < 1000 answer is 2 (64, 729)

The numbers 0 and 1 are self-squares and self-cubes, all exponentials being 0 and 1 respectively. Only a few other numbers are both squares and cubes of integers.

For any given square and cube, the numerical relation is n3 = [n(sqrt n)]2
so for the value n where (sqrt n) is whole number, the cube of n is also a square.
After 0 and 1, the next 4 are 64, 729, 4096, and 15625.

64 = 43 = 82 . (4x2)2
729 = 93 = 272 . (9x3)2
4096 = 163= 642 . (16x4)2
15625 = 253 = 1252 . (25x5)2

You can find the others easily. There are each the sixth power of any integer,
such that x6 = (x2)3 = (x3)2 e.g. 26 = 64, 36 = 729, 46 = 4096, etc. - Besides 64, another easy one is the number one million, 106, which is 1003 and 10002.

We can say that these numbers are the cube of a square, or the square of a cube, for any given integer.

Find the 8digit number

Find a 8-digit number, where the first figure defines the count of zeros in this number, the second figure the count of numeral 1 in this number and so on....  

Start with 8 digit number, starting from left to right, 
first digit indicate number of 0's in 8 digit number, 
second digit indicate number of 1's in 8 digit number. 
Similary 7th digit indicate number of 7's in 8 digit number.


70000000 //8 digit number 7 indicate number of 0's in the number.
70000001 //As number of 7's = 1 so 7th place is 1
60000001 //As due to 1 on 7th place number of zeros = 6
60000010 //As 6 is present so 7th place, number of 6's = 1; number of 7's = 0
61000010 //As 1 is present on 7th place ; number of 1's = 1 so 2nd place there should be 1
51000010 //As number of 0's = 5 
51000100 //As 5 is present so 6th place is 1 number of 6's = 0; number of 7's = 0 
52000100 //As number of 1's = 2  
52100100 //As 2 is present on 1st place so 3rd place is 1
42100100 // As number of  0's = 4 so 1st place is 4
42101000 // As 4 is present so 5th place is 1; number of 5's, 6's and 7's = 0;
We got the answer as 4210 1000.


Source : http://anandtechblog.blogspot.com/2011/07/find-8digit-number-microsoft-interview.html

What really happens when you navigate to a URL

As a software developer, you certainly have a high-level picture of how web apps work and what kinds of technologies are involved: the browser, HTTP, HTML, web server, request handlers, and so on.

In this article, we will take a deeper look at the sequence of events that take place when you visit a URL.

http://igoro.com/archive/what-really-happens-when-you-navigate-to-a-url/

Standups in scrum

Standups offer a quick check on what’s happening, what’s changed, who ‘s working on what, who needs help. The meeting is supposed to be short and sweet, no more than 15 minutes a day. Martin Fowler lists some good reasons to hold standups:
Share commitment
Communicate status
Identify obstacles to be solved
Set direction and focus
Help to build a team.

Refer : http://www.javacodegeeks.com/2011/09/standups-take-them-or-leave-them.html

Ten Ways to Check if an Integer Is a Power Of Two in C

http://www.exploringbinary.com/ten-ways-to-check-if-an-integer-is-a-power-of-two-in-c/

Swap two variables without using temporary variable

Swap x and y without using temp variable

tmp = x
  x = y
  y = tmp
  -----------------
  x=x+y
  y=x-y
  x=x-y

Drawbacks : 
1) It can cause overflow in the operation (+) 

                     2) It can cause underflow on operation (-)  -----------------  x=x*y   y=x/y   x=x/y

----------------------

x = x xor y
  y = x xor y
  x = x xor yWe don't have problem of either underflow or overflow! but it fails for swapping of same value results 0.

Modulus(%) operation

Modulus operator is costly.
The modulus operator (%) in various languages is costly operation. Ultimately every operator/operation must result in processor instructions. Some processors won’t have modulus instruction at hardware level, in such case the compilers will insert stubs (predefined functions) to perform modulus. It impacts performance.
Refer : http://geeksforgeeks.org/?p=9057

LeftShift fiddle in java

int: The int data type is a 32-bit signed two's complement integer. It has a minimum value of -2,147,483,648 and a maximum value of 2,147,483,647 (inclusive). For integral values, this data type is generally the default choice unless there is a reason (like the above) to choose something else. This data type will most likely be large enough for the numbers your program will use, but if you need a wider range of values, use long instead.

     When we shift a variable beyond it's width,then output becomes dependent on the compiler,so it is undefined behavior.

public class BitFiddle {
 public static void main(String[] args) {
  Integer i = 3;
  i = i << 31;
  System.out.println(i);// -2147483648
  System.out.println(Integer.toBinaryString(i));//10000000000000000000000000000000
  

  int j = 3;
  j = j << 32;
  System.out.println(j);// 3
  System.out.println(Integer.toBinaryString(j));//11

  int k = 3;
  k = k << 33;
  System.out.println(k);// 6
  System.out.println(Integer.toBinaryString(k));//110
 }
}

Infinite stream of Bits Divisible by 3

Given an infinite stream of bits with bits being appended at the  highest significant position. Give an algorithm to say whether the number formed by sequence of bits that had been processed till then is divisible by 3 or not ?

Solution from Algogeeks group :

Divisibility of 3 of numbers in base 2 can be seen same as divisibility of numbers by 11 in base 10.
Maintain two variable even_sum & odd_sum, both initialized to 0.When an odd location in the number is set increment odd_sum.When an even location in the number is set increment even_sum.

if(abs(even_sum-odd_sum)%3==0) number is divisible by 3.
Hence keep the track of even_sum and odd_sum as the bits are getting appended.

Number of bits set in odd position - Number of bits set in even position 'll be divisible by 3
For example, take 9. 1001. No. of bits set in odd position-number of bits set in even position is 0.Hence divisible by 3.
For 21, 10101. Difference is 3.. SO just keep count of the number of bits set in odd position and even position as the stream.

If the stream contains numbers :
For calculating the sum, no need to store all the elements sum.After adding a number each time,take modulus and store the remainder in sum.So it will not become more and will be less than 3.

Find XpowerY in O(logN)

It will keep on dividing the power by 2.If it is odd divide by 2 and multiply with x

public class RecursiveXpowerY {
 public static void main(String[] args) {
  int pow = recursiveXpowY(2, 5);
  System.out.println(pow);
 }
 /**
  * It finds the value in O(logN)
  * @param x
  * @param y
  * @return
  */
 public static int recursiveXpowY(int x, int y) {
  if (x == 0)
   return 1;
  if (y % 2 == 1) {// y is odd
   return recursiveXpowY(x * x, y / 2) * x;
  } else {
   return recursiveXpowY(x * x, y / 2);
  }
 }
}

GCD

public static int getGcd(int a,int b){
  int temp;
  while(b!=0){
   temp = a%b;
   a=b;
   b=temp;
  }  
  return a;
 }

Recursive approach :

public static int getGCDRecursively(int a,int b){
  if(b==0) return a;
  else if(b>a) return getGCDRecursively(b,a);
  else return getGCDRecursively(b, a%b);
 }

Co-prime numbers : Two numbers are called relatively prime, or coprime if their greatest common divisor equals 1. For example, 9 and 28 are relatively prime.

How to sort 4GB files

Using merge sort.

Refer here

Ugly Number

Ugly numbers are numbers whose only prime factors are 2, 3 or 5. First 10 ugly numbers are:

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, ...

By convention, 1 is included. Write a program to find and print the first 1000 ugly numbers.

http://tech-queries.blogspot.com/2011/03/ugly-number.html

Which Loop Is Faster?

A very basic programming puzzle is being asked in programming interviews since last few years. The question is that out of below two lops, which will run faster?

public class FasterLoop {

 public static void main(String[] args) {
  int k = 0, l = 0, i, j;
  for (i = 0, l++; i < 10; i++, k++)
   for (j = 0, l++; j < 100; j++, k++);
  System.out.println(k + "   " + l);
  k = 0;
  l = 0;
  for (i = 0, l++; i < 100; i++, k++)
   for (j = 0, l++; j < 10; j++, k++);
  System.out.println(k + "  " + l);
 }
}

  o/p:    1010   11
            1100  101
Refer :http://tech-queries.blogspot.com/2010/09/which-loop-is-faster.html

Number conversions

Convert an roman integer in its decimal equivalent : http://tech-queries.blogspot.com/2010/03/convert-roman-integer-in-decimal.html


Convert IP Address From String To HexaDecimal : http://tech-queries.blogspot.com/2010/03/convert-ip-address-from-string-to-int.html

public static void convertToHexaDecimal(String s) {    
  StringTokenizer st = new StringTokenizer(s,".");
  System.out.print("0x");
  int i = Integer.parseInt(st.nextToken()); 
  System.out.print(Integer.toHexString(i));
  
  i = Integer.parseInt(st.nextToken());
  System.out.print(Integer.toHexString(i));
  
  i = Integer.parseInt(st.nextToken());
  System.out.print(Integer.toHexString(i));
  
  i = Integer.parseInt(st.nextToken());
  System.out.print(Integer.toHexString(i));
 }

The letters used in Roman numbers are:

• I = 1
• V = 5
• X = 10
• L = 50
• C = 100
• D = 500
• M = 1000

Convert Decimal number into roman number :

public class ConvertDecimalToRoman {

 public static void main(String[] args) {

  long num = 50;
  // convert decimal number into roman number
  StringBuilder roman = new StringBuilder("");

  long count = 0;

  if (num >= 1000) {
   count = num / 1000;
   while (count-- != 0)
    roman.append("M");
   num %= 1000;
  }

  if (num >= 500) {
   count = num / 500;
   while (count-- != 0)
    roman.append("D");
   num %= 500;
  }

  if (num >= 100) {
   count = num / 100;
   while (count-- != 0)
    roman.append("L");
   num %= 100;
  }

  if (num >= 50) {
   count = num / 50;
   while (count-- != 0)
    roman.append("L");
   num %= 50;
  }

  if (num >= 10) {
   count = num / 10;
   while (count-- != 0)
    roman.append("X");
   num %= 10;
  }

  if (num >= 5) {
   count = num / 5;
   while (count-- != 0)
    roman.append("V");
   num %= 5;
  }

  while (num != 0) {
   roman.append("I");
   num--;
  }
  System.out.println(roman);
 }
}

Matching Braces Using Tail Recursion

Write a function to generate all possible n pairs of balanced parentheses.
For example, if n=1
{}
for n=2
{}{}
{{}}
Use tail recursion

public class GeneratePairedParanthesis {

 public static void main(String[] args) {
  generate("", 0, 0, 3);
 }

 public static void generate(String s, int open, int close, int n) {
  if (open == n && close == n) {
   System.out.println("" + s);
   return;
  }
  if (close > open)
   return;

  if (open >= close && open < n) {
   generate(s + "{", open + 1, close, n);
  }
  if (close < open) {
   generate(s + "}", open, close + 1, n);
  }
 }
}

Refer : http://tech-queries.blogspot.com/2009/01/valid-parenthesis-sequences.html