Tools / Data structures Interview questions
1. What is data structure?
Data structures refers to the way data is organized and manipulated. It helps to find ways to make data access more efficient. When dealing with data structure, we not only focus on one piece of data, but rather different set of data and how they can relate to one another in an organized manner.
2. Define linear data structure.
A linear data structure traverses the data elements sequentially, in which only one data element can directly be reached. For example Arrays, Linked Lists are linear data structure.
3. Define Non-Linear data structure.
The data items are not arranged in a sequential structure. Every data item is attached to several other data items in a way that is specific for reflecting relationships. Graph and Tree are examples of non linear data structure.
4. Mention different data structures.
Commonly used data structures are, list, arrays, stack, queues, graph, tree.
5. What are the operations that can be performed on a data-structure?
The following operations are commonly performed on any data-structure, Insertion : adding a data item. Deletion : removing a data item. Traversal : accessing and/or printing all data items. Searching : finding a particular data item. Sorting : arranging data items in a pre-defined sequence.
6. What is an Array?
Array is a data structure used to store homogeneous elements at contiguous locations. Size of an array must be provided before storing data.
7. Define Linked list.
A linked list is a linear data structure similar to arrays where each element is a separate object. Each element or node of a list comprises of two items: data and a reference to the next node.
8. What are the different types of linked list?
There are 3 types of linked list. Singly Linked List : Every node stores address or reference of next node in list and the last node has next address or reference as NULL. Doubly Linked List : There are two references associated with each node, one of the references points to the next node and ot...
9. How do I find middle element of linked list?
To find the middle element of linked list in one pass, you may maintain two-pointer, one increment at each node while other increment after two nodes at a time so that when first pointer reaches end, second pointer will point to middle element of linked list.
10. Define Stack in data structures.
A stack or LIFO (last in, first out) is an abstract data type that serves as a collection of elements, with two principal operations: push , which adds an element to the collection, and pop , which removes the last element that was added. In stack both the operations of push and pop takes place a...
11. Explain queue in data structure.
A queue or FIFO (first in, first out) is an abstract data type that serves as a collection of elements, with two principal operations: enqueue , the process of adding an element to the collection.(The element is added from the rear side) and dequeue , the process of removing the first element tha...
12. Why do we need stack data structure?
Stack implements LIFO method, addition and retrieval of a data item takes only Ο(1) time. Stack is used where we need to access data in the reverse order or its arrival order. Stacks are used commonly in recursive function calls, expression parsing, depth first traversal of graphs etc.
13. Minimum number of queues needed to implement the priority queue.
Two. One queue is used for actual storing of data and another for storing priorities.
14. Applications of tree data-structure.
The manipulation of Arithmetic expression, Symbol Table construction, and Syntax analysis.
15. What is priority queue?
A priority queue is a collection of elements such that each element has been assigned a priority.
16. What is the difference between Stack and Queue data structure?
Stack is LIFO (Last In First Out) data structure while Queue is a FIFO (First In First Out) data structure.
17. Difference between Singly Linked List and Doubly Linked List data structure.
The main difference between singly linked list and doubly linked list is the ability to traverse. In a single linked list, node only points towards next node, and there is no pointer to previous node, which means you can not traverse back on a singly linked list. On the other hand doubly linked l...
18. What is binary search tree?
Binary Search Tree has some special properties such as left nodes contains items whose value is less than root, right sub tree contains keys with higher node value than root, and there will not be any duplicates in the tree. Binary Search Tree is also known as ordered or sorted binary trees.
19. List out few areas in which data structures are applied extensively?
Compiler Design, Operating System, Database Management System, Statistical analysis package, Numerical Analysis, Graphics, Artificial Intelligence, and Simulation.
20. What is recursive data structure?
A data structure that is partially composed of smaller or simpler instances of the same data structure. For instance, a tree is composed of smaller trees (subtrees) and leaf nodes, and a list may have other lists as elements.
21. Give few examples of mathematical function that can be performed recursively?
Many mathematical functions can be defined recursively such as, Factorial, Fibonacci, Euclid's GCD (greatest common denominator), Fourier Transform.
22. Is sorting possible with delete operation in data structure?
Sorting is not possible in Deletion. Using insertion we can perform insertion sort, using selection we can perform selection sort, using exchange we can perform the bubble sort. But no sorting method can be done just using deletion.
23. List out few applications that make use of Multilinked Structures?
Sparse matrix, Index generation.
24. In RDBMS, what is the efficient data structure used in the internal storage representation?
B+ tree. 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.
25. 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. Its properties are as follows. The maximum number of nodes on any level i is 2i where i>=0. The maximum number of nodes possible in a binary tree of height h is 2h-1. The minimu...
26. What are multidimensional arrays?
Multidimensional arrays make use of multiple indexes to store data. It is useful when storing data that cannot be represented using a single dimensional indexing, such as data representation in a chess board game, tables with data stored in more than one column for example geo spatial data.
27. Are linked lists considered linear or non-linear data structure?
Based on storage, a linked list is considered non-linear. However on the basis of access strategies a linked list is considered linear.
28. What is dynamic data structure?
Dynamic data structure expands and shrinks in size as program runs. It provides a flexible means of manipulating data as it can adjust capacity according to the size of the data.
29. Differentiate Stack and Array.
Data that is stored in a stack follows a LIFO pattern. This means that data access follows a sequence wherein the last data to be stored will the first one to be extracted. Arrays, on the other hand, does not follow a particular order and instead can be accessed by referring to the indexed elemen...
30. What is a dequeue?
A dequeue is a double-ended queue in which elements can be inserted or removed from either end.
31. What is a graph?
A graph is a data structure that contains a set of ordered pairs. These ordered pairs are also referred as edges or arcs, and are used to connect nodes where data can be stored and retrieved.
32. What is an AVL tree?
An AVL tree is a type of binary search tree that is always in a state of partially balanced. The balance is measured as a difference between the heights of the subtrees from the root. This self-balancing tree was known to be the first data structure to be designed as such. AVL Tree is Named after...
33. What operations can be performed on stack data structure?
push : adds an item to stack. pop : removes the top stack item. peek : retrieves the value of top item without removing it.
34. What is linear search?
Linear search for an item in a sequentially arranged data type. These sequentially arranged data items known as array or list, are accessible in a incremental memory location. Linear search compares expected data item with each of data items in list or array. The average case time complexity of l...
35. Explain binary search.
A binary search works only on sorted lists or arrays. This search starts at the middle element which splits the entire list into two parts. This search first compares the target value to the mid of the list. If it is not found, then it takes decision on whether to search on first part or second p...
36. What is heterogeneous linked list?
Heterogeneous Linked List is a linked list data-structure that contains or is capable of storing data for different datatypes.
37. Which data structures are used with the following areas: RDBMS, Network data model and hierarchical data model?
RDBMS implements Array data structure. Network data model uses Graph. Hierarchal data model uses Trees.
38. What is a postfix expression?
An expression in which each operator follows its operand is known as postfix expression. The main benefit of this expression is that there is no need to group sub-expressions in parentheses or to consider operator precedence.
39. 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.
40. What does a linked list node consist of?
A singly list node consists of two fields:data field to store the element and link field to store the address of the next node.
41. What are the different types of binary tree?
A rooted binary tree has a root node and every node has at most two children. A full binary tree (proper or plane binary tree) is a tree in which every node in the tree has either 0 or 2 children. A Complete Binary Tree has all levels completely filled except possibly the last level and the last ...
42. What is tree traversal?
Tree traversal is the process to visit all the nodes of a tree. All the nodes are connected via edges (links), we always start from the root (head) node. There are three ways which we use to traverse a tree. In-order Traversal, Pre-order Traversal, Post-order Traversal,
43. What is a minimum spanning tree (MST) ?
In a weighted graph, a minimum spanning tree is a spanning tree that has minimum weight that all other spanning trees of the same graph.
44. What is hashing?
Hashing is a technique that converts a range of key values into a range of indexes of an array. By using hash tables, we can create an associative data storage where data index can be identified by providing its key values.
45. What is algorithm?
Algorithm is a step by step procedure, which defines a set of instructions to be executed in certain order to get the desired output.
46. What is the time complexity of Algorithm?
Time complexity of an algorithm indicates the total time required by the program to run to completion. It is usually expressed by using the big O notation.
47. Explain asymptotic analysis of an algorithm?
Asymptotic analysis of an algorithm refers to defining the mathematical boundation/framing of its run-time performance. Using asymptotic analysis, we can identify the best case, average case, and worst case scenario of an algorithm. Asymptotic analysis is input bound so that if there's no input t...
48. Mention the criteria for algorithmic analysis.
An algorithm are generally analyzed on 2 factors, time and space. How much execution time and how much extra space required by the algorithm forms basis for analysis.
49. Explain Quick Sort algorithm.
Quick sort algorithm uses divide and conquer approach. It divides the list into smaller 'partitions' using 'pivot'. The values which are smaller than the pivot are arranged in the left partition and greater values are arranged in the right partition. Each partition is recursively sorted using qui...
50. Explain bubble sort algorithm.
Bubble sort is a comparison based algorithm in which each pair of adjacent elements is compared and elements are swapped if they are not in order. Bubble sort has the time complexity of Ο(n2), it is the least used sorting strategy for large volume data.
51. How insertion sort algorithm works?
Insertion sort divides the list into two sub-list, sorted and unsorted. It takes one element at time and finds it appropriate location in sorted sub-list and insert it to the sorted sub-list. It iteratively works on all the elements of unsorted sub-list and inserts them to sorted sub-list in orde...
52. Explain selection sort algorithm.
List is divided into two parts, the sorted part at the left end and the unsorted part at the right end. It selects the smallest element from unsorted sub-list and places it into the sorted list. This iterates unless all the elements from unsorted sub-list are consumed into sorted sub-list. This a...
53. Explain merge sort algorithm.
Merge sort algorithm is based on divide and conquer programming approach. This algorithm divides the unsorted list into n sublists, each containing 1 element and repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining.
54. What is shell sort?
Shell sort is an unstable quadratic sorting algorithm and it is a generalization of insertion sort. This algorithm starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared.
55. How quick sort works?
Quick sort uses divide and conquer approach and this algorithm divides the list in smaller 'partitions' using 'pivot'. The values which are smaller than the pivot are arranged in the left partition and greater values are arranged in the right partition. Each partition is recursively sorted using ...
56. What is recursive function?
A recursive function is a function that makes a call to itself. To prevent infinite recursion a conditional statement is placed that prevent the further calls. For example Fibonacci series can be determined using recursive function.
57. What is Huffmans algorithm?
Huffmans algorithm is associated in creating extended binary trees that has minimum weighted path lengths from the given weights. It makes use of a table that contains frequency of occurrence for each data element.
58. Which algorithm used in solving the 8 Queens problem.
Backtracking.
59. Difference between a Tree and Graph in Data structure.
Tree. Graph. Tree is a special form of graph also called as minimally connected graph having only one path between any two vertices. A graph vertices can have more than one path, that is, a graph can have uni-directional or bi-directional paths (edges) between nodes. A tree has no loops , no circ...
60. Explain Heap data structure.
A heap is a specialized tree-based data structure that satisfies the heap property that If 'A' is a parent node of 'B', then the key (that is, value) of node A is ordered with respect to the key of node B with the same ordering strategy applyed across the heap. Heap data structure is always a Bin...
61. Explain max heap data structure.
The max heap is a type heap data structure where the value of the root node is greater than or equal to either of its child nodes.
62. Explain min heap data structure.
A min-heap is a type of heap data structure where the value of the root node is less than or equal to either of its child nodes.
63. Difference between Binary tree and Binary search tree.
A Binary tree is a type of tree data structure where each parent node can have at most two child nodes ( 0 to 2 nodes). Binary search tree is a binary tree where the left child contains only nodes with values less than the parent node, and where the right child only contains nodes with values gre...
64. Define a complete Graph.
A complete graph is a graph with N vertices and an edge between every two vertices. Given that N is positive integer, there are no loops and every two vertices share exactly one edge. The symbol K N denotes a complete graph with N vertices.
65. What is Adjacency matrix?
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
66. Difference between undirected and Directed graph.
An undirected graph is graph with a set of vertex or nodes that are connected together, where all the edges are bidirectional. An undirected graph is sometimes called an undirected network. In contrast, a graph where the edges point in a direction is called a directed graph.
67. What is a digraph in data structures?
A digraph pr directed graph is a Data Structure containing a vertex set V and an edge/arc set A, where each edge is an ordered pair of vertices. The arcs may be thought of as arrows, each one starting at one vertex and pointing at precisely one other.
68. Explain Adjacency list in data structures.
In graph theory and computer science, an adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a vertex in the graph.
69. What is Incidence matrix?
Incidence matrix is a two-dimensional Boolean matrix, in which the rows represent the vertices and columns represent the edges. The entries indicate whether the vertex at a row is incident to the edge at a column. Incidence matrix is one of the ways to represent a graph.
70. What is a dense graph?
A dense graph is a graph in which the number of edges is close to the maximal number of edges.
71. What is a sparse graph?
Sparse graph is a graph in which the number of edges is close to the minimal number of edges.
72. Preferred way of representing the graph.
Adjacency lists are generally preferred because they efficiently represent sparse graphs. An adjacency matrix is preferred if the graph is dense, that is the number of edges is close to the number of vertices squared.
73. What is a non-simple graph?
A graph which do contain loops are Non-Simple.
74. Explain Knapsack problem.
The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large a...
75. What is Dynamic programming?
Dynamic programming also known as dynamic optimization is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions using a memory-based data structure. The next time the same subpr...
76. Difference between memoization and dynamic programming.
Memoization is a term describing an optimization technique where you cache previously computed results, and return the cached result when the same computation is needed again. Dynamic programming is a technique for solving problems recursively and is applicable when the computations of the subpro...
77. How insertion sort is faster than bubble sort?
In bubble sort at i-th iteration you have n-i-1 inner iterations ((n^2)/2), but in insertion sort you have maximum i iterations on i-th step, but i/2 on average, as you can stop inner loop earlier, after you found correct position for the current element. So you have (sum from 0 to n) / 2 which i...
78. Explain trie data structure.
Trie is an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associa...
79. What is edge case in algorithm evaluation?
Edge cases are inputs that the specification for your function allows but that might be tricky to handle. An edge case is a problem or situation that occurs only at an extreme (maximum or minimum) operating parameter. For example, a stereo speaker might noticeably distort audio when played at its...
80. How to represent complexity when the best case, average case, and worst case are equal?
Use Theta to represent complexity when best/average/worst case are equal.
81. How do I delete an element from heap data structure?
Deletion always occurs at the root of the heap . The root element is removed and it is replaced by the last element in the heap. This satisfies the shape property, however, it violates the order property as the last element would be the smallest(in case of the max heap). The Reheapify operation n...
82. What is depth of node in a tree.
Depth is the node is equal to the number of edges to the node from root node. The depth of root node is 0. Also maximum number of children at level i is 2 to the power of I.
83. How to find the height of a node in a tree?
The height of the node is equal to the number of edges in the longest path to the leaf from the node. The depth of a leaf node is 0. Height of the tree is nothing but the height of the root node.
84. What is a strict or proper binary tree?
In a strict binary tree, each node can have either 0 or 2 children.
85. Define complete and perfect binary tree.
In complete binary tree, all level except the last are completely filled and all the node are on left as possible and no vacant space on left side. In perfect binary tree, all levels are completely filled.
86. Difference between Insertion Sort and Selection Sort.
Both insertion sort and selection sort have nested loops, one outer and inner loop. In selection sort, the inner loop is over the unsorted elements. Each pass selects one element and moves it to its final location which is at the current end of the sorted region. In insertion sort, each pass of t...
87. What is the complexity of Merge sort algorithm?
Merge sort takes O (n log n) in terms of worst case scenario.
88. What is inverted binary tree?
Inverted binary tree is the mirror image of the tree where the left of the nodes move to right and vice versa.
89. Explain jagged array.
A jagged array is an array whose elements are arrays. The elements of a jagged array can be of different dimensions and sizes. A jagged array is also called as array of arrays .
90. Mention a few use cases of a doubly linked list.
Any application where you want to traverse both sides from a specific point may leverage doubly-linked lists. Doubly linked list is used in constructing MRU/LRU (Most/Least Recently Used) cache. The browser cache that allows you to hit the BACK-FORWARD pages. Undo-Redo functionality. A music play...
91. What is a Binary Heap?
Binary Heap is a Binary tree that is complete. Except for the last level all its levels are strictly completely filled. A Binary Heap is either a Min Heap or a Max Heap and is suitable to be stored in an array. Binary Heap has many applications like implementations of the priority queue, Heap Sor...
92. What is an undirected graph?
An undirected graph is a graph in which edges have no orientation. The edge(u,v) is identical to the edge (v, u).
93. Difference between BFS vs DFS.
BFS (Breadth First Search) DFS (Depth First Search) BFS(Breadth First Search) uses Queue data structure for finding the shortest path. DFS(Depth First Search) uses Stack data structure. BFS considers all neighbors first and therefore not suitable for decision making trees used in games or puzzles...
