What is hashing technique? Describe in brief.
In general, in all searching techniques, search time is dependent on the number of items. Sequential search, binary search and all the search trees are totally dependent on number of items and many key comparisons are involved.
Hashing is a technique where search time is independent of the number of items or elements. In this technique a hash function is used to generate an address from a key. The hash function takes a key as input and returns the hash value of that key which is used as an address index in the array.
We can write hash function as follows
Where h is hash function, k is the key, a is the hash value of the key.
While choosing a hash function we should consider some important points.
- It should be easy to compute
- It should generate address with minimum collision.
What are different techniques for making hash function? Explain with example.
Techniques for making hash function.
- Truncation Method
- Midsquare Method
- Folding Method
- Division Method
This is the simplest method for computing address from a key.In this method we take only a part of the key as address.
Let us take some 8 digit keys and find addresses for them. Let the table size is 100 and we have to take 2 rightmost digits for getting the hash table address. Suppose the keys are. 62394572,87135565,93457271,45393225.
So the address of above keys will be 72,65,71 and 25 respectively.
This method is easy to compute but chances of collision are more because last two digits can be same in more than one keys.
In this method the key is squared and some digits from the middle of this square are taken as address.
Suppose that table size is 1000 and keys are as follows
Square of key
In this technique the key is divided into different part where the length of each part is same as that of the required address, except possibly the last part.
Let key is 123945234 and the table size is 1000 then we will broke this key as follows
123945234 ----> 123 945 234
Now we will add these broken parts. 123+945+234=1302. The sum is 1302, we will ignore the final carry 1, so the address for the key 123945234 is 302.
Division Method (Modulo-Division)
In Modulo-Division method the key is divided by the table size and the remainder is taken as the address of the hash table.
Let the table size is n then
H (k) =k mod n
Let the keys are 123, 945,234 and table size is 11 then the address of these keys will be.
123 % 11=2
So the hash address of above keys will be 2,10,4.
Note: - Collisions can be minimized if the table size is taken to be a prime number.
What are different methods of collision resolution in hashing.
A collision occurs whenever a key is mapped to an address that is already occupied. Collision Resolution technique provides an alternate place in hash table where this key can be placed. Collision Resolution technique can be classified as:
1) Open Addressing (Closed Hashing)
a) Linear Probing
b) Quadratic Probing
c) Double Hashing
2) Separate Chaining (Open Hashing)
Describe Linear Probing with an example.
In this method if address given by hash function is already occupied, then the key will be inserted in the next empty position in hash table. Let the table size is 7 and hash function returns address 4 for a key then we will search the empty location in this sequence.
4, 5, 6, 7, 0, 1, 2, 3
Let the keys are 28, 47, 20, 36, 43, 23, 25, 54 and table size is 11 then
Describe the following term in a tree.
a) Level b) Height c) Degree.
Let’s take an example to define the above term.
Level of any node is defined as the distance of that node from the root. The level of root node is always zero. Node B, C, M, E are at level 1.Nodes K,G,H,I,J,F,L are at level 2.Nodes A,N,O,P,D,S are at level 3.
Height is also known as depth of the tree. The height of root node is one. Height of a tree is equal to one more than the largest level number of tree. The height of the above tree is 4.
The number of children of a node is called its degree. The degree of node R is 4, the degree of node B is 3.The degree of node S is 0.The degree of a tree is the maximum degree of the node of the tree. The degree of the above given tree is 4.
Describe binary tree and its property.
In a binary tree a node can have maximum two children, or in other words we can say a node can have 0,1, or 2 children.
Properties of binary tree.
1) The maximum number of nodes on any level i is 2i where i>=0.
2) The maximum number of nodes possible in a binary tree of height h is 2h-1.
3) The minimum number of nodes possible in a binary tree of height h is equal to h.
4) If a binary tree contains n nodes then its maximum possible height is n and minimum height possible is log2 (n+1).
5) If n is the total no of nodes and e is the total no of edges then e=n-1.The tree must be non-empty binary tree.
6) If n0 is the number of nodes with no child and n2 is the number of nodes with 2 children, then n0=n2+1.
Describe full binary tree and complete binary tree.
Full binary tree: A binary tree is full binary tree if all the levels have maximum number of nodes.
A full binary tree of height h has (2h– 1) nodes.
Complete binary tree:In a complete binary tree all the levels have maximum number of nodes except possibly the last level.
The minimum no of nodes in a complete binary tree is 2h-1and the maximum number of nodes possible is (2h– 1).Where h is the height of the tree.
Explain Extended Binary tree.
A binarytree can be converted to an extended binary tree by adding special nodes to leaf nodes and nodes that have only one child.Extended binary tree is also called 2-tree.
In the above figure external nodes are shown by squares and internal nodes by circles. The extended binary tree is a strictly binary tree means each node has either 0 or 2 children. The path length of any node is the number of edges traversed from that node to the root node. Internal path length of a binary tree is the sum of path lengths of all internal nodes and external path length of a binary tree is the sum of path lengths of all external nodes.
What are different dynamic memory allocation technique in C .
The process of allocating memory at run time is called dynamic memory allocation. The allocation and release of this memory space can be done with the help of some predefined function. These functions allocate memory from a memory area called heap and free this memory whenever not required. The functions that are used to allocate memory at runtime are as follows:
This function allocates memory dynamically. It is generally used as:
ptr= (datatype *) malloc(specified size);
Here ptr is a pointer of type datatype ( can be int, float, double….) and specified size is the size in bytes. The expression (datatype *) is used to typecast the pointer returned by malloc().
It allocates the memory space to hold four integer values and the address of first byte is stored in the pointer variable ptr. The allocated memory contains garbage value.
The calloc() function is used to allocate multiple blocks of memory.
ptr=(int *)calloc(4, sizeof(int));
It allocates 4 blocks of memory and each block contains 2 bytes.
We can increase or decrease the memory allocated by malloc() or calloc() function. The realloc() function is used to change the size of the memory block. It changes the memory block without destroying the old data.
This function takes two argument, first is a pointer to the block of memory that was previously allocated by malloc() or calloc() and second argument is the new size of memory block.
ptr=(int *)realloc(ptr, 4*sizeof(int)); // newsize
Q.2 What are the difference between malloc() and calloc()?
Following are the main difference between malloc() and calloc().
- calloc() function takes two parameters but malloc() function takes only one parameter.
- Memory allocated by calloc() is initialized to zero while memory allocated by malloc() contains garbage value.
Q.3 How will you free the memory that is allocated at run time?
Memory is one of the most important resources and it is limited. The dynamically allocated memory is not automatically released; it will exist till the end of program. So it is programmer’s responsibility to free the memory after completion. The free() function is used to release the memory that is allocated at run time.
Here ptr is a pointer variable that contains the base address of a memory block created by malloc() or calloc() function.
Q.4 What are different application of stack.
Some of the applications of stack are as follows:
- Function calls.
- Reversal of a string.
- Checking validity of an expression containing nested parenthesis.
- Conversion of infix expression to postfix.
Q.5 How will you check the validity of an expression containing nested parentheses?
One of the applications of stack is checking validity of an expression containing nested parenthesis. An expression will be valid if it satisfies the two conditions.
- The total number of left parenthesis should be equal to the total number of right parenthesis in the expression.
- For every right parenthesis there should be a left parenthesis of the same time.
The procedure for checking validity of an expression containing nested parenthesis:
1. First take an empty stack
2. Scan the symbols of expression from left to right.
3. If the symbol is a left parenthesis then push it on the stack.
4. If the symbol is right parenthesis then
If the stack is empty then the expression is invalid because Right parentheses are more
than left parenthesis.
Pop an element from stack.
If popped parenthesis does not match the parenthesis being scanned then it is invalid
because of mismatched parenthesis.
5. After scanning all the symbols of expression, if stack is empty then expression is valid else it is invalid because left parenthesis is more than right parenthesis.
Q.6 Give the example of validating the parenthesis of expression using stack.
Q.7 Describe AVL tree or height balanced binary search tree.
An AVL tree is binary search tree (BST) where the difference in the height of left and right subtrees of any node can be at most one. The technique for balancing the binary search tree was introduced by Russian Mathematicians G. M. Adelson and E. M. Landis in 1962. The height balanced binary search tree is called AVL tree in their honor.
For the leaf node 12, 40, 65 and 98 left and right subtrees are empty so difference of heights of their subtrees is zero.
For node 20 height of left subtree is 2 and height of right subtree is 3 so difference is 1.
For node 15 height of left subtree is 1 and height of right subtree is 0 so difference is 1.
For node 57 height of left subtree is 1 and height of right subtree is 2 so difference is 1.
For node 78 height of left subtree is 1 and height of right subtree is 1 so difference is 0.
Each node of an AVL tree has a balance factor, which is defined as the difference between the heights of left subtree and right subtree of a node.
Balance factor of a node=Height of its left subtree - Height of its right subtree.
In AVL tree possible values for the balance factor of any node are -1, 0, 1.
Q.8 Describe Tree Rotation in AVL tree.
After insertion or deletion operation the balance factor of the nodes in AVL tree can be changed and the tree may not be balanced. We can balance this tree by performing tree rotations. We know that AVL tree is binary search tree. Rotation of the tree should be in such a way that the new converted tree maintain the binary search tree property with inorder traversal same as that of the original tree. There are two types of tree rotation
- Right Rotation
- Left Rotation
Fig: Right Rotation
Q.9 Give one example of Right Rotation.
Right Rotation about node 25.