Are given characters of a string form palindrome?

Using the all characters of a given String how to specify either a palindrome or not.
Ex:-
1) String="teste"
After arrange all character we can made a palindrome String as "teset"
So output is TRUE.
2)String="hello"
we can not made a palindrome String
output is FALSE

Sort the given string and after call the below method

boolean isFormingPalindrome(String s) {

//Assume we are taking sorted string as an argument

  if (s == null || s.length() == 0 || s.length() == 1)
   return true;
  int length = s.length();
  // if it has even number of characters,it should have zero non repeated
  // characters. else it should have one non repeated character
  boolean isFirstNonRepeated = false;
  if (length % 2 == 0) {
   // for even length,there will not be any
   // non repeated characters
   isFirstNonRepeated = true;
  }

  char[] characters = s.toCharArray();
  for (int i = 1; i < length; i = i + 2) {
   if (characters[i - 1] != characters[i]) {
    if (isFirstNonRepeated) {
     return false;
    } else {
     i = i - 1;
     isFirstNonRepeated = true;
    }
   }
  }
  return true;
 }

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

LinkedList traversal

How will you find the middle node in a linked list?
Sol :  Take two pointers.Move one pointer at x speed and second pointer at 2x speed.When second pointer reaches the end of the linked list,first pointer reaches middle of the linked list.
1st with head->next
2nd with head->next->next


How will you find the node with position 3/4 of the total number of nodes ?
fast pointer : slow pointer = 4:3
slow = ptr->next->next->next
fast = ptr->next->next->next->next

ptr1 should move 4 nodes at a time

ptr2 should move 3 nodes at a time,

When the ptr1 reaches the end the ptr2 will be pointing to 3/4t.

For M/N th node,move first pointer at Mx speed and second pointer at Nx speed.When fast pointer reached the end of the list,slow pointer will be at required position.But this works best for even number of nodes in list.

For odd numbers we need to compromise like finding the middle node.

Find repeated and missing number

Given an array of size n. It contains numbers in the range 1 to n.Each number is present at least once except for 2 numbers. Find the missing numbers ?
Method I :
Assume array a ={1,2,3,3,5};
element n=3 is repeated and m=4 is missed.
Sum of the elements  actual = 1+2+3+3+5
Sum of the elements  expected = 1+2+3+4+5
Diff expected-actual = 4-3=m-n   ==> m-n=1     ----------------- Eq1
expected product = 1*2*3*3*5;
actual product     = 1*2*3*4*5;
expected/actual = 3/4=n/m ===> 3m=4n;   --------------------Eq2
We have two equations.We can find m and n now.


Method II : We can solve it using bitwise opertions.

1.Calculate XOR of all the array elements.
2.XOR the result with all numbers from 1 to n =>x1
3.After 2nd step, all elements would nullify each other except 2 missing elements(let x and y) and x1 will contain XOR of x and y
4.All the bits that are set in x1 will be set in either x or y. Get the rightmost set bit from x1.
5.divide the elements of the array in two sets – one set of elements with same bit set and other set with same bit not set. By doing so, you will get x in one set and y in another set. 
6.XOR all the elements of 1st set with the numbers between 1 to n which have same bit set and XOR the 2nd set with the numbers between 1 to n which have same bit not set. Now result of both set will have the desired result
Method III : We can solve it using hashmap also.

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.