Join Our Email Alerts-Subscribe
Important Note:Login & Check Your Email Inbox and Activate Confirmation Link
Data Structure Materials-Free Download
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-1 and 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.
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.
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.
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.
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.
Give the example of validating the parenthesis of expression using stack.
What is Data Structure?
- Data structure is a group of data elements grouped together under one name.
- These data elements are called members. They can have different types and different lengths.
- Some of them store the data of same type while others store different types of data.
Which data structure is used to perform recursion?
- The data structure used for recursion is Stack.
- Its LIFO property helps it remembers its 'caller'. This helps it know the data which is to be returned when the function has to return.
- System stack is used for storing the return addresses of the function calls.
Does the Minimal Spanning tree of a graph give the shortest distance between any 2 specified nodes?
- No, it doesn’t.
- It assures that the total weight of the tree is kept to minimum.
- It doesn't imply that the distance between any two nodes involved in the minimum-spanning tree is minimum.
If you are using C language to implement the heterogeneous linked list, what pointer type will you use?
- A heterogeneous linked list contains different data types in its nodes. We can not use ordinary pointer to connect them.
- The pointer that we use in such a case is void pointer as it is a generic pointer type and capable of storing pointer to any type.
Differentiate between PUSH and POP?
- Pushing and popping refers to the way data is stored into and retrieved from a stack.
- PUSH – Data being pushed/ added to the stack.
- POP - Data being retrieved from the stack, particularly the topmost data.
When is a binary search algorithm best applied?
- It is best applied to search a list when the elements are already in order or sorted.
- The list here is searched starting in the middle. If that middle value is not the correct one, the lower or the upper half is searched in the similar way.
How do you reference all the elements in a one-dimension array?
- This is done using an indexed loop.
- The counter runs from 0 to the array size minus one.
- Using the loop counter as the array subscript helps in referencing all the elements in one-dimensional array.
What is Huffman’s algorithm?
- It is used in creating extended binary trees that have minimum weighted path lengths from the given weights.
- It makes use of a table that contains frequency of occurrence for each data element.
What is Fibonacci search?
- It is a search algorithm that applies to a sorted array.
- It uses divide-and-conquer approach that reduces the time needed to reach the target element.
Source: Contents are provided by Technicalsymposium Google Group Members. Disclaimer: All the above contents are provided by technicalsymposium.com Google Group members. Further, this content is not intended to be used for commercial purpose. Technicalsymposium.com is not liable/responsible for any copyright issues.
Technicalsymposium.com-Download All Technical Interview Materials