Why ConcurrentHashMap doesn't allow null keys and null values ?

Reason #1. Purpose of null key
 If map.get(key) returns null, you can't detect whether the key explicitly maps to null or the key isn't mapped.

Reason #2. Ambiguities
In the ConcurrentHashMap implementation, map can be changed in between.

If it supports null key, in below code key k may be deleted in between get and containsKey calls and code will return null instead of KeyNotPresentException (expected)

if (map.containsKey(k)) {

     return map.get(k);

} else {

     throw new KeyNotPresentException();

}

Linear search vs. Binary search

Linear search

• Complexity : O(n)
• Suited for unordered array
• Loop starts from first element till the item found or end of the array.
• In Worst case, it will take 2^20 comparisons for 2^20 records.
• Easy to implement
• Takes longer time (in average) to find an item than Binary search

for (int i=0; i<array.length(); i++) {
  if (array[i] == value) {
       return i;  // item found, return the index
  }
}

return -1;  // Not found


Binary search

• Complexity : O(log n)
• Very efficient than Linear search
• Only applied on ordered array ; cannot be applied on unordered array
• Little complex algorithm than Linear search
• In Worst case, it will take only 20 comparisons for 2^20 records.

int low = 0;

int high = len - 1;

while (low <= high) {

   mid = (low+high) / 2;   // Find the mid index

   
   if (array[mid] == value)
        return mid;       // Found, return mid index

   else if (array[mid] > value)  // If value is lesser than mid element

        high = mid - 1;   // Search before mid - Adjust 'high'

   else if (array[mid] < value)  // If value is greater than mid element

        low = mid + 1;    // Search after mid - Adjust 'low'

}

return -1;  // Not found

How to check if a number is the perfect square ?

Note : A Perfect square is the Sum of all consecutive add numbers
Example of perfect squares : 1+3+5....

Algorithm

boolean isPerfectSquare = false;

int sum = 0;

// iterate from 1 to n incremented by 2

for(int i=1; sum<num; i+=2) {

    // Calculate the sum and check for perfect square

    sum += i;

    if (sum == num)

        isPerfectSquare = true;

        break;

    }

}

How to check if a number is power of 2 ?

Solution #1. Divide num by 2 recursively
Time complexity : O(log2n)


Solution #2. Using Bitwise & operator with num and num-1
boolean isPowerOf2 = (num & (num-1))==0;

Time complexity : O(1)

Example : 
num = 8
n    = 8 = 1000
n-1 = 7 = 0111
-------------------
               0000 => Power of 2, Yes.

Check if the number is odd ?

Solution #1. Check if num % 2 == 0
boolean isOdd = (num % 2 == 1);

Problem. It will not return correct result for -ve number


Solution #2. Same approach but use absolute value of num
if(num<0) {
   num = -(num);
}
boolean isOdd = (num % 2 == 1);

Solution #3. Check using bitwise & with 1 (Binary = 000000...1)

boolean isOdd = (num & 1) != 0;

Example

21 = 10101

  1 = 00001

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

        00001  => Odd, Yes.

Fastest and most optimized solution.

How to swap 2 numbers without using 3rd variable ?

Solution #1. Addition and Subtraction method
a = a+b;
b = a-b;
a = a-b;

Problem. Incorrect result when sum of numbers will exceed the integer range


Solution #2. Multiplication and Division method
a = a*b;
b = a/b;
a = a/b;

Problem. Same problem with multiplication result
                Additionally, Incorrect result when a or b is 0


Solution #3. XOR method
a = a^b;
b = a^b;

a = a^b;

Best approach without any problem

How to increment a number by 1 without using + operator ?

Use Bitwise operator to add 1 to binary representation
Check the each bit and flip it using bitwise operator


Here, number is input and output both

int one = 1;

/* Flip all the set bits until we find a 0 */

while((number & one)!=0 ) {

   number = number^one;

   one <<= 1;

}

/* flip the rightmost 0 bit */

number = number^one;