How free(pointer) works?

MMU(Memory Management Unit) simply stores the number of bytes allocated at say p location and then you get to store the content starting from p th position up till n bytes.
So when free(p) is to be used MMU simply sees the values stored at p and deallocates that much amount of bytes.

Quad Tree Algorithm

aGiven a city in the form of a square.There are various cell towers located at various points in the square city(say (x,y)).The distribution of towers is totally random.Now given an (x,y) point,design a data structure that help you tell whether the cell tower is present in the location or not.

Ans: We can solve it using quad tree.

sum two numbers using bitwise operators

Java code : 

public class AddTwoNumbers {

private static int myAdd(int a, int b)
{
int carry = a & b;
int result = a ^ b;
while(carry != 0)
{
int shiftedcarry = carry << 1;
carry = result & shiftedcarry;
result ^= shiftedcarry;
}
return result;
}

public static void main(String[] args){
System.out.println(myAdd(4, 5));
System.out.println(myAdd(4, -5));
System.out.println(myAdd(-4, -5));
System.out.println(myAdd(-4, 5));
System.out.println(myAdd(0, 5));
}
}

output :
9
-1
-9
1
5

Explanation : When you add two one-bit quantities, you get a two-bit
result :  0 + 0 = 00, 0 + 1 = 01, 1 + 0 = 01, and 1 + 1 = 10.
Note that the leftmost bit of sum of the the single-bit quantities A
and B, obeys the logic A & B, and the rightmost bit obeys A ^ B, where
& is the logical AND operation and ^ is the logical eXclusive OR
operation. When adding a multibit binary number, the leftmost bit
carries into the next bit position. So the code you presented just
does the multibit addition using the above two rules on all bits in
parallel. The first two statements determine the results using the
"leftmost bit" and "rightmost bit" rules above. If there are any
carries, then they must be added to the next position to the left.
Thus, shift the carries left one bit and repeat the addition process
using the leftmost and rightmost bit rules again. Do this until there
are no remaining carries.


Difference of two numbers : 
How to do subtraction of two integers widout using subtractn?? 
    The negative integer can be represented in 2's complement format.So sub_result=a+(~b+1) will perform the subtraction of a and b.
            -b=(~b+1). 


Refer : http://www.geeksforgeeks.org/archives/18324

Minimum distance between between two nodes of a binary tree

In Binary Search Tree,finding the distance between the nodes is easy.Travel up to the node where you need not take different paths.That node is called common ancestor node.From there calculate the distance of node1 as l1 and distance of node2 as l2.The distance between them is l1+l2.

In Binary Tree :
1)calculate the length from root to node1 as l1
2)calculate the length from root to node2 as l2
3)find the least common ancestor and calculate the distance up to that ancestor as l3.
4)resultant distance between the two nodes is l1+l2-2l3 (since we count the distance from root to least common ancestor twice)

Longest substring Palindrome in a given string

There are N strings that can start with the first letter.
There are N-1 strings that can start with the second letter.
Etc...
There is 1 string that can start with the Nth letter.

So we are going to be checking N(N+1)/2 strings in the worst case.


Write a program which finds the longest palindrome in a given string of characters.

Assumption1.
===========
So if it were of even length then the centre would be i and i+1 for example
KaaK
0123
so centers are 1,2
but for a odd length palindrome the centers are one and the same as in
KapaK
01234
so centers are 2,2

Assumption2:
============
If two strings have the same center and smaller one is not a palindrome then bigger can't be a palindrome

for example:abcddeba
index willb:01234567
since str[3,4] is a palindrome then [2,5] may be a palindrome
but since str[2,5] is not a palindrome [1,6] can't become palindrome.

Logic:
======
Here i take every index in the array as the center of the palindrome.
Now first loop searches for odd lenght palindromes in the string.
Taking the first 0,0 as the centers we try to expand our palindrome till we
encounter the boundaries or a mismatch. In such a way we can eliminate all
the strings with the same base which are not palindromes.



void longestPalindrome(char *input)
{
int len;
int i=0,j=0,k=0,l=0;
int lower=0,upper=0;
len = strlen(input);

/*Odd length Palindromes*/
while(i lessThan len && j lessThan len)
{
k=i;
l=j;
while(( k greaterThan =0 && l lessThan len) && (input[k] == input[l]))
{
if((upper - lower) lessThan = (l-k))
{
lower=k;
upper=l;
}
k--;
l++;
}
i++;
j++;
}

/*Even length Palindromes*/
i = 0;
j = 1;
while(i lessThan len && j lessThan len)
{
k=i;
l=j;
while(( k greaterThan =0 && l lessThan len) && (input[k] == input[l]))
{
if((upper - lower) lessThan = (l-k))
{
lower=k;
upper=l;
}
k--;
l++;
}
i++;
j++;
}

for(i=lower;i lessThan =upper;i++)
{
printf("%c",input[i]);
}
printf("\n");
}


*******************************************************************************
We can solve this in O(n) time using suffix tree algorithm.But the problem with the suffix tree algorithm is,it takes memory to store the tree.

Refer the below urls for more information on suffix tree construction and how it is helpful for operations on strings.

suffix tree construction doc

http://homepage.usask.ca/~ctl271/857/suffix_tree.shtml

http://flexaired.blogspot.com/2011/03/longest-palindrome-in-string.html

Multiply two numbers without using loops or multiplication or division

We can implement this by using recursive operation.

public static int multiply(int x, int y) {
  if (y == 0)
   return 0;
  
  // if y is positive,Add x one by one
  if (y > 0)
   return (x + multiply(x, y - 1));
  else
   return -multiply(x, -y);
 }

Spiral matrix

Given the size of input n,print a spiral matrix of size n*n
ex: n=3

9 2 3
8 1 4
7 6 5

By observing the above matrix,we can construct the matrix by building first left column after bottom column after right column after top column.
code looks like below:

// program to print spiral matrix
 public static void getSpiralMatrix(int n) {
  int count = n * n;
  int[][] a = new int[n][n];
  // we have to construct a spiral matrix of size n*n
  for (int lower = 0, upper = n; lower <= upper; lower += 1, upper -= 1) {

   // first we fill the left side of the column
   for (int i = lower, j = lower; i < upper && count > 0; i++) {
    a[i][j] = count--;
   }

   // fill the lower row
   for (int i = upper - 1, j = lower + 1; j < upper - 1 && count > 0; j++) {
    a[i][j] = count--;
   }

   // fill the right side of the column
   for (int i = upper - 1, j = upper - 1; i >= lower && count > 0; i--) {
    a[i][j] = count--;
   }

   // fill the upper row
   for (int i = lower, j = upper - 2; j > lower && count > 0; j--) {
    a[i][j] = count--;
   }
  }
  for (int i = 0; i < n; i++) {
   for (int j = 0; j < n; j++) {
    System.out.print(a[i][j] + " ");
   }
   System.out.println();
  }
 }

Refer : http://www.geeksforgeeks.org/archives/10768