Hashing And Different Techniques

What is hashing why we need it?

Consider it as a process of converting any input to an integer value.A string can have a hash value, a java Object can have hash value.

We need it to place these input to particular cell or bucket.So that whenever we need to find this object, we will find it in particular cell or bucket only.This will decrease the search time for an input object.

Click here to understand this part via youtube tutorial

Good Hashing Techniques

Since we need to convert the input value to some integer value, method or step to convert it should be simple and faster, as a user should not spend much time and effort on the secondary task.The second thing you should keep in mind is that your function should create different int value for different input for maximum cases.Otherwise, you will end up keeping elements in single or only a few buckets which will make search more problematic.

Two thing you have to learn is

  1. Event Distribution and Easy Computation
  2. Collision Detection and Resolution
  3. Collision resolution
    1. Linear Probing
    2. Quadratic Probing
    3. Double Hashing 

This is a minimum of hashing everyone should know.Will try to cover the hashing in depth in my upcoming blogs.

Stack implementation Algorithm

Stack Implementation

It works on first in last Out.

Youtube Video to understand Stack

 

Variables

top =0;

add to stack(push)
//boundary value:- if stack has a limit;
if(top<limit){
top ++;
add value to top
}else{
stack full
}

remove (pop)
if(top !=0){

take value from top
top–
}else{
stack Empty
}

Traversal

in order of first in

for (i = 1;i<=top;i++){
print element at i
}

 

WikiPedia Link  , refer for stack theory.

http://en.wikipedia.org/wiki/Stack_(abstract_data_type)

 

Rotate the matrix by 90 degree in java

We are rotating the content of a matrix by 90 degree.

Assumptions

a is the given matrix.

We will just print it in the rotated form.

///code

int a[][] = {{1,2,3,4,5,6},{7,8,9,10,11,12}};

//no. of column
int m = a[0].length;

//no. of rows
int n = a.length;

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
System.out.print(a[i][j]);
}
System.out.println();
}
for (int i = 0; i < m; i++) {
for (int j = n-1; j >=0; j–) {
System.out.print(a[j][i]+” .. “);
}
System.out.println();
}

How to check if string can be used to create a palindrome

This is a code to check if we can make a palindrome using all letters of string

Input: str is a given string.

NOTE: assumption every character have to be use present in the string, and only once.

Logic: only one alphabet can have odd occurence,rest should have even occurence.

 

ALGO:

 

public static void main(String asd[]){

 

int count= 0;

int odd_occurence = 0;

//str is given string.you can initialize str with ant input you want.

String str =  “apapqqqqjjk”;

Boolean output = true;

for(int i =0;i<str.length();i++){

                for(int j=0;j 1)

                {

                                output = false;

                                break;

                }

}

 

if(output){

                system.out.println(“palindrome can be created”);

}else{

                system.out.println(“palindrome cannot be created”);

}

 

}

To search in binary tree

Following function help to search element in binary tree
Pre Requisite: Java ,Binary tree.
Level: medium
It is a simple method which will return the Search result in binary tree.
We have followed the recursive approach to solve this problem.
Binary tree is tree , where each node have at most 2 child.

As the parameter ,we will pass the Object which is the root of the binary tree.
“searchVariable” is the value which we have to search
METHOD:

public boolean searchInBinaryTree(Node N){

boolean result = false;
if(N == null)
return false;

if(N.value == searchVariable)
return true;

if(N.left != null)
result = searchInBinaryTree(N.left);

if(N.right != null)
result = searchInBinaryTree(N.right);

return result;
}
Note : link below will give you more information and help you in understanding in better way.

Remove extra spaces from string in java

This is a code to remove extra spaces from string.
String str = “i  am     reading    this book  since yesterday.”;

String s1 = “”;
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == ' ' && str.charAt(i + 1) == ' ') {
str = str.substring(0, i).concat(
str.substring(i + 1, str.length()));
i–;

}

}
System.out.println("string without space :"+str);

Posted from WordPress for Android