Data Structure interview answers
What are the various data-structures available?
Data structure availability may vary by programming languages. Commonly available data structures are the list, arrays, stack, queues, graph, tree, etc.
What is the difference between PUSH and POP?
Push and pop refer to the way data are stored into and retrieved from a stack.
- Push – Data being pushed/ added to the stack.
- Pop – Data is retrieved from the stack, particularly the topmost data.
Why do we need to do algorithm analysis?
A problem can be solved in more than one ways. So, many solution algorithms can be derived for a given problem. We analyze available algorithms to find and implement the best suitable algorithm.
What is the difference between malloc() and calloc()?
Following are the main difference between malloc() and calloc() functions
- 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() is garbage
- calloc() allocates the memory in block format whereas malloc() in byte format
What is a hashing technique?
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 the 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.
What is a divide and conquer method?
The basic idea is to divide the problem into several subproblems beyond which cannot be further subdivided. Then solve the subproblems efficiently and join them together to get the solution for the main problem.
What are asymptotic notations?
Asymptotic analysis can provide three levels of mathematical binding of the execution time of an algorithm − Best case is represented by Ω(n) notation, Worst case is represented by Ο(n) notation, the Average case is represented by Θ(n) notation.
Give some examples of greedy algorithms?
The below-given problems find their solution using the greedy algorithm approach
Travelling Salesman Problem, Prim’s Minimal Spanning Tree Algorithm, Kruskal’s Minimal Spanning Tree Algorithm, Dijkstra’s Minimal Spanning Tree Algorithm, Graph – Map Coloring, Graph – Vertex Cover, Knapsack Problem, Job Scheduling Problem.
In RDBMS, what is the efficient data structure used in the internal storage representation?
B+ tree. Because in B+ tree, all the data is stored only in leaf nodes, that makes searching easier. This corresponds to the records that shall be stored in leaf nodes.
What is the need for the header node?
The header of the linked list is the first element in the list and it stores the number of elements in the list. It points to the first data element of the list.
What is a leaf?
In a directed tree any node which has outdegree o is called a terminal node or a leaf.
Data Structure interview answers for fresher
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.
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 the frequency of occurrence for each data element.
What is a linked list?
The linked list is a data structure which stores the same kind of data elements but not in contiguous memory locations and size is not fixed. The linked lists are related logically.
How to find if the linked list has a loop?
It means we can use the two-pointer approach to solve this problem. If we maintain two pointers, and we increment one pointer after processing two nodes and other after processing every node, we are likely to find a situation where both the pointers will be pointing to the same node. This will only happen if the linked list has the loop.
What is a stack?
In data-structure, the stack is an Abstract Data Type (ADT) used to store and retrieve values in Last In First Out method.
Why do we use stacks?
Stacks follows LIFO method and addition and retrieval of a data item takes only Ο(n) time. Stacks are used where we need to access data in the reverse order or their arrival. Stacks are used commonly in recursive function calls, expression parsing, depth-first traversal of graphs, etc.
What is the different application of stack?
Some of the applications of the stack are as follows – Function calls, Reversal of a string, Checking the validity of an expression containing nested parentheses, Conversion of infix expression to postfix.
What is a spanning Tree?
A spanning tree is a tree associated with a network. All the nodes of the graph appear on the tree once. A minimum spanning tree is a spanning tree organized so that the total edge weight between nodes is minimized.
What is the queue?
A Queue is a sequential organization of data. A queue is a first in first out type of data structure. An element is inserted at the last position and an element is always taken out from the first position.
What are priority queues?
A priority queue is a collection of elements such that each element has been assigned a priority.