Data-Structure Technical Interview Questions Answers
What is data structure?
The data structure is a way of defining, storing & retrieving data in a structural & systematic way. A data structure may contain different types of data items.
What are various data structures available?
Data structure availability may vary by programming language. Commonly available data structures are lists, arrays, stacks, queues, graphs, trees,s, etc.
What is an algorithm?
An algorithm is a step by step procedure, which defines a set of instructions to be executed in certain order to get the desired output.
Why we need to do algorithm analysis?
A problem can be solved in more than one way. So, many solution algorithms can be derived for a given problem. We analyze available algorithms to find and implement the best suitable algorithm.
What are the criteria of algorithm analysis?
An algorithm is generally analyzed on two factors − time and space. That is how much execution time and how much extra space is required by the algorithm.
What is an asymptotic analysis of an algorithm?
Asymptotic analysis of an algorithm refers to defining the mathematical foundation/framing of its run-time performance. Using asymptotic analysis, we can very well conclude the best case, average case, and worst-case scenario of an algorithm.
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. The worst case is represented by Ο(n) notation. The average case is represented by Θ(n) notation.
What is linear data structure?
A linear data structure has sequentially arranged data items. The next time can be located in the next memory address. It is stored and accessed in a sequential manner. Array and list are examples of linear data structures.
What are common operations that can be performed on a 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
Briefly explain the approaches to developing algorithms.
Greedy Approach − finding a solution by choosing the next best option
Divide and Conquer − diving the problem to a minimum possible sub-problem and solving them independently
Dynamic Programming − diving the problem to a minimum possible sub-problem and solving them combinedly
Give some examples greedy algorithms.
The below given problems find their solution using 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
What are some examples of divide and conquer algorithms?
The below given problems find their solution using divide and conquer algorithm approach − Merge Sort Quick Sort Binary Search Strassen's Matrix Multiplication Closest pair (points)
What are some examples of dynamic programming algorithms?
The below given problems find their solution using divide and conquer algorithm approach − Fibonacci number series Knapsack problem Tower of Hanoi All pair shortest path by Floyd-Warshall Shortest path by Dijkstra Project scheduling
What is a linked-list?
A linked-list is a list of data-items connected with links i.e. pointers or references. Most modern high-level programming language does not provide the feature of directly accessing memory location, therefore, linked-list are not supported in them or available in form of inbuilt functions.
What is stack?
In data-structure, 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 operations can be performed on stacks?
The below operations can be performed on a stack −
push() − adds an item to stack
peek() − gives value of top item without removing it
isempty() − checks if stack is empty
isfull() − checks if stack is full
What is a queue in data-structure?
Queue is an abstract data structure, somewhat similar to stack. In contrast to stack, queue is opened at both end. One end is always used to insert data (enqueue) and the other is used to remove data (dequeue). Queue follows First-In-First-Out methodology, i.e., the data item stored first will be accessed first.
Why do we use queues?
As queues follows FIFO method, they are used when we need to work on data-items in exact sequence of their arrival. Every operating system maintains queues of various processes. Priority queues and breadth first traversal of graphs are some examples of queues.
What operations can be performed on Queues?
enqueue() − adds an item to rear of the queue
dequeue() − removes the item from front of the queue
peek() − gives value of front item without removing it
isempty() − checks if stack is empty
isfull() − checks if stack is full
What is linear searching?
Linear search tries to find an item in a sequentially arranged data type. These sequentially arranged data items known as array or list, are accessible in incrementing memory location. Linear search compares expected data item with each of data items in list or array. The average case time complexity of linear search is Ο(n) and worst case complexity is Ο(n2). Data in target arrays/lists need not to be sorted.
What is binary search?
A binary search works only on sorted lists or arrays. This search selects the middle which splits the entire list into two parts. First the middle is compared. This search first compares the target value to the mid of the list. If it is not found, then it takes decision on whether.
What is bubble sort and how bubble sort works?
Bubble sort is comparison based algorithm in which each pair of adjacent elements is compared and elements are swapped if they are not in order. Because the time complexity is Ο(n2), it is not suitable for large set of data.
Tell me something about 'insertion sort'?
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 there. The output after insertion is a sorted sub-list. It iteratively works on all the elements of unsorted sub-list and inserts them to sorted sub-list in order.
What is selection sort?
Selection sort is in-place sorting technique. It divides the data set into two sub-lists: sorted and unsorted. Then it selects the minimum 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.
How insertion sort and selection sorts are different?
Both sorting techniques maintains two sub-lists, sorted and unsorted and both take one element at a time and places it into sorted sub-list. Insertion sort works on the current element in hand and places it in the sorted array at appropriate location maintaining the properties of insertion sort. Whereas, selection sort searches the minimum from the unsorted sub-list and replaces it with the current element in hand.
What is merge sort and how it works?
Merge sort is sorting algorithm based on divide and conquer programming approach. It keeps on dividing the list into smaller sub-list until all sub-list has only 1 element. And then it merges them in a sorted way until all sub-lists are consumed. It has run-time complexity of Ο(n log n) and it needs Ο(n) auxiliary space.
What is shell sort?
Shell sort can be said a variant of insertion sort. Shell sort divides the list into smaller sublist based on some gap variable and then each sub-list is sorted using insertion sort. In best cases, it can perform upto Ο(n log n).
How quick sort works?
Quick sort uses divide and conquer approach. It 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 quick sort.
What is a graph?
A graph is a pictorial representation of a set of objects where some pairs of objects are connected by links. The interconnected objects are represented by points termed as vertices, and the links that connect the vertices are called edges.
How depth first traversal works?
Depth First Search algorithm(DFS) traverses a graph in a depthward motion and uses a stack to remember to get the next vertex to start a search when a dead end occurs in any iteration.
How breadth first traversal works?
Breadth First Search algorithm(BFS) traverses a graph in a breadthwards motion and uses a queue to remember to get the next vertex to start a search when a dead end occurs in any iteration.
What is a tree?
A tree is a minimally connected graph having no loops and circuits.
What is a binary tree?
A binary tree has a special condition that each node can have two children at maximum.
What is a binary search tree?
A binary search tree is a binary tree with a special provision where a node's left child must have value less than its parent's value and node's right child must have value greater than it's parent value.
What is tree traversal?
Tree traversal is a process to visit all the nodes of a tree. Because, all 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
See the below image of a binary search tree, and traverse it using all available methods −
In-order traversal − 10 14 19 27 31 35 42 Pre-order traversal − 27 14 10 19 35 31 42 Post-order traversal − 10 19 14 31 42 35 27
What is an AVL Tree?
AVL trees are height balancing binary search tree. AVL tree checks the height of left and right sub-trees and assures that the difference is not more than 1. This difference is called Balance Factor. BalanceFactor = height(left-sutree) − height(right-sutree)
What is a spanning tree?
A spanning tree is a subset of Graph G, which has all the vertices covered with minimum possible number of edges. A spanning tree does not have cycles and it can not be disconnected.
How many spanning trees can a graph has?
It depends on how connected the graph is. A complete undirected graph can have a maximum nn-1 number of spanning trees, where n is number of nodes.
How Kruskal's algorithm works?
This algorithm treats the graph as a forest and every node it as an individual tree. A tree connects to another only and only if it has least cost among all available options and does not violate MST properties.
How Prim's algorithm finds spanning tree?
Prim's algorithm treats the nodes as a single tree and keeps on adding new nodes to the spanning tree from the given graph.
What is a minimum spanning tree (MST) ?
In a weighted graph, a minimum spanning tree is a spanning tree that has a minimum weight that all other spanning trees of the same graph.
What is a heap in data structure?
Heap is a special balanced binary tree data structure where the root-node key is compared with its children and arranged accordingly. In a min-heap, a parent node has a key value less than its child and a max-heap parent node has a value greater than its child.
What is a recursive function?
A recursive function calls itself, directly or calls a function that in turn calls it. Every recursive function follows the recursive properties −
base criteria where the function stops calling itself and
a progressive approach where the functions try to meet the base criteria in each iteration.
What ithe a tower of Hanoi?
Tower of Hanoi, is a mathematical puzzle that consists of three towers (pegs) and more than one ring. All rings are of different sizes and stacked upon each other where the large disk is always below the small disk. The aim is to move the tower of the disk from one peg to another, without breaking its properties.
What is the Fibonacci series?
Fibonacci Series generates subsequent numbers by adding two previous numbers. For example − 0 1 1 2 3 5 8 13.
What is hashing?
Hashing is a technique to convert 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 the data index can be found by providing its key values.
What is the interpolation search technique?
Interpolation search is an improved variant of binary search. This search algorithm works on the probing position of the required value.
What is the prefix and post fix notation of (a + b) * (c + d) ?
Prefix Notation − * + a b + c d Postfix Notation − a b + c d + *
The following formula will produce Fn = Fn-1 + Fn-2
Fibonacci Series generates subsequent numbers by adding two previous numbers.
The following formula is of left_subtree (keys) ≤ node (key) ≤ right_subtree (keys)
A binary search tree (BST) is a tree in which all nodes follow the below-mentioned properties − The left sub-tree of a node has a key less than or equal to its parent node's key. The right sub-tree of a node has a key greater than or equal to its parent node's key.
Match the following −
- (1) Bubble Sort-----------(A) Ο(n)
- (A) Ο(n)-------------------(B) Ο(n^2)
- (3) Selection Sort----------------------(C) Ο(n log n)
1 → B, 2 → C, 3 → A
node. next → node. next.next; will make.
node. next inaccessible After applying node.next → node.next.next; we will not have a n ode.next stored anywhere if not explicitly mentioned.
Differentiate between file and structure storage structure.
The key difference between both the data structure is the memory area that is being accessed. When dealing with the structure that resides in the main memory of the computer system, this is referred to as storage structure. When dealing with an auxiliary structure, we refer to it as file structures.
What is merge sort?
Merge sort, is a divide-and-conquer approach for sorting the data. In a sequence of data, adjacent ones are merged and sorted to create bigger sorted lists. These sorted lists are then merged again to form an even bigger sorted list, which continues until you have one single sorted list.
Differentiate NULL and VOID
Null is a value, whereas Void is a data type identifier. A variable that is given a Null value indicates an empty value. The void is used to identify pointers as having no initial size.
What is the difference between a PUSH and a POP?
Pushing and popping apply to the way data is stored and retrieved in a stack. A push denotes data being added to it, meaning data is being “pushed” into the stack. On the other hand, a pop denotes data retrieval, and in particular, refers to the topmost data being accessed.
Which sorting algorithm is considered the fastest?
There are many types of sorting algorithms: quick sort, bubble sort, balloon sort, radix sort, merge sort, etc. Not one can be considered the fastest because each algorithm is designed for a particular data structure and data set. It would depend on the data set that you would want to sort.
Differentiate STACK from ARRAY.
Stack follows a LIFO pattern. It means that data access follows a sequence wherein the last data is stored when the first one is extracted. Arrays, on the other hand, do not follow a particular order and instead can be accessed by referring to the indexed element within the array.
Differentiate linear from nonlinear data structure.
The linear data structure is a structure wherein data elements are adjacent to each other. Examples of linear data structures include arrays, linked lists, stacks, and queues. On the other hand, a non-linear data structure is a structure wherein each data element can connect to more than two adjacent data elements. Examples of nonlinear data structures include trees and graphs.
What are some of the applications of DS?
For representing a city region telephone network.
To implement back functionality in the internet web browser.
To store dynamically growing data which is accessed very frequently, based upon a key value.
To implement the undo function in a text editor.
To store information about the directories and files in a system
What are the advantages of a Linked list over an array?
Consider a scenario, where we need to store a large amount of data in an array. But, the memory to store that data is not available contiguously. In this case, we cannot use an array. Hence, we go for a linked list. Since each node is connected using the link, it is not necessary that memory has to be contiguous.
What are the applications of Graph DS?
Graphs are used in circuit networks where points of connection are drawn as vertices and component wires become the edges of the graph, in transport networks where stations are drawn as vertices and routes become the edges of the graph, and in maps that draw cities/states/regions as vertices and adjacency relations as edges, in program flow analysis where procedures or modules are treated as vertices and calls to these procedures are drawn as edges of the graph.
Explain how dynamic memory allocation will help you in managing data?
A dynamic memory allocation will help you effectively manage your data by allocating structured blocks to have composite structures which can be flexible, i.e. can expand and can contract based on the need. Also, they are capable of storing simple structured data types.
How does a linear data structure differ from a non-linear data structure?
If the elements of a data structure form a sequence or a linear list then it is called a linear data structure. On the other hand, non-linear data structures are those in which the traversal of nodes is done in a non-linear way.
Arrays, linked lists, stacks, and queues are examples of linear data structures, while graphs and trees are those of non-linear data structures.
Can you tell which data structures are used for the BFS and DFS of a graph?
BFS (Breadth First Search) of a graph uses a queue. Although the DFS (Depth First Search) of a graph makes use of a stack, it can also be implemented using recursion that uses a function called stack.
Please explain the stack and also mention some of its important applications.
Stack is a linear data structure that follows either LIFO (Last In First Out) or FILO (First In Last Out) approach for accessing elements. Push, pop, and peek are the basic operations of a stack.
Some notable applications of a stack are:
- Check for balanced parentheses in an expression
- Evaluation of a postfix expression
- Implement two stacks in an array
- Infix to postfix conversion
- Reverse a string
Do you know how memory is affected by signed and unsigned numbers?
For signed numbers, the first bit is reserved for indicating whether the number is positive or negative. Hence, it has one bit less for storing the value. Unlike signed numbers, unsigned numbers have all the bits available for storing the number.
The effect of the aforementioned can be seen in the value range available to signed and unsigned numbers. While an unsigned 8-bit number can have a range of 0 to 255, an 8-bit signed number has a range varying from -128 to 127.
What do you understand by an AVL tree?
An AVL tree is a type of BST (Binary Search Tree), which is always in a partially-balanced state. The measure of the balance is given by the difference in the heights of the subtrees from the root node of the AVL tree.
What do you understand by Infix, Prefix, and Postfix notations?
Infix Notation – Operators are written between the operands. This is the standard way of writing expressions. For example, A * (B + C) / D
Postfix Notation/Reverse Polish Notation – Operators are written after the operands, hence the name. For instance, A B C + * D /
Prefix Notation/Polish Notation – Operators are written before the operands. / * A + B C D is the prefix notation equivalent of the aforementioned postfix notation example
Please explain the Linked List and its various types.
In a linked list, each element is a distinct object. Like arrays, linked lists are a linear type of data structure. In addition to data, every element of a linked list comprises a reference to the next element. Various types of linked lists are:
Singly Linked List – Each node stores the address or reference of the next node in the linked list, leave for the last node that stores NULL
Doubly Linked List – Each node keeps two references. One points to the next node and the other points to the previous node
Circular Linked List – In this type of linked list, all nodes are connected to form a circle. Hence, there is no NULL at the end. A circular linked list can either be a singly circular linked list or a double circular linked list
Could you give a brief explanation of the various approaches for developing algorithms?
There are 3 main approaches to developing algorithms:
Divide and Conquer – Involves dividing the entire problem into several subproblems and then solving each of them independently
Dynamic Programming – Identical to the divide and conquer approach with the exception that all sub-problems are solved together
Greedy Approach – Finds a solution by choosing the next best option
How does insertion sort differ from selection sort?
Both insertion and selection approaches maintain two sub-lists, sorted and unsorted. Each takes one element from the unsorted sub-list and places it into the sorted sub-list. The distinction between the two sorting processes lies in the treatment of the current element.
Insertion sort takes the current element and places it in the sorted sublist at the appropriate location. Selection sort, on the other hand, searches for the minimum value in the unsorted sub-list and replaces the same with the present element.
Please explain a spanning tree. What is the maximum number of spanning trees a graph can have?
A spanning tree is a subset of a graph that has all the vertices but with the minimum possible number of edges. Neither a spanning tree can be disconnected and nor does it have cycles.
The maximum number of spanning trees that a graph can have depended on how connected the graph is. A complete undirected graph with n number of nodes can have a maximum of nn-1 number of spanning trees.
How does Kruskal’s Algorithm work?
Kruskal’s algorithm treats a graph as a forest and each node in it as an individual tree. A tree connects to another tree only if it: Has the least cost among all the available options and Does not violate the MST properties
Can you explain the Tower of Hanoi problem?
The Tower of Hanoi is a mathematical puzzle that comprises three towers (or pegs) and more than one ring. Each ring is of varying size and stacked upon one another such that the larger one is beneath the smaller one. The goal of the Tower of Hanoi problem is to move the tower of the disk from one peg to another without breaking the properties.
How do the BFS (Breadth-First Search) and DFS (Depth First Search) algorithms work?
The BFS algorithm traverses a graph in the bread towards motion. It uses a queue to remember the next vertex for starting a search when a dead end occurs in any iteration.
A DFS algorithm traverses a graph in the deathward motion. It uses a stack for remembering the next vertex to start a search when coming across a dead end in an iteration.
