50 Data Structures Algorithms Interview Questions
What is Data structure?
Answer
The data structure is a way of defining, storing & retrieving of data in a structural & systematic way. A data structure may contain a different type of data items.
What are various data- structures available?
Answer
Data structure availability may vary by programming languages. Commonly available data structures are a list, arrays, stack, queues, graph, tree etc.
What is the algorithm?
Answer
The 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 do we need to do algorithm analysis?
Answer
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 are the criteria for algorithm analysis?
Answer
An algorithm is generally analyzed on two factors − time and space. That is, how much execution time and how much extra space required by the algorithm
What is an asymptotic analysis of an algorithm?
Answer
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 is the asymptotic of an algorithm?
Answer
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.
What is a linear data structure?
Answer
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 structure.
What are common operations that can be performed on a data-structure?
Answer
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
Briefly explain the approaches to develop algorithms.
Answer
There are three commonly used approaches to develop algorithms −
- Greedy Approach− finding 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 of greedy algorithms
Answer
The below-given problems find their solution using a 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?
Answer
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?
Answer
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?
Answer
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 the form of inbuilt functions.
What are stacks?
Answer
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?
Answer
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?
Answer
The below operations can be performed on a stack −
- push()− adds an item to stack
- pop()− removes the top stack item
- peek()− gives the value of a top item without removing it
- isempty()− checks if stack is empty
- isfull()− checks if the stack is full
.
What is a queue in data-structure?
Answer
The queue is an abstract data structure, somewhat similar to stack. In contrast to stack, the queue is opened at both ends. 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?
Answer
As queues follow FIFO method, they are used when we need to work on data-items in the 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?
Answer
The below operations can be performed on a stack −
- enqueue()− adds an item to rear of the queue
- dequeue()− removes the item from front of the queue
- peek()− gives value of a front item without removing it
- is empty()− checks if the stack is empty
- is full()− checks if the stack is full
What is linear searching?
Answer
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 the data items in list or array. The average case time complexity of the linear search is Ο(n) and the worst case complexity is Ο(n2). Data in target arrays/lists need not be sorted.
What is the binary search?
Answer
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 a decision on whether.
What is bubble sort and how bubble sort works?
Answer
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. Because the time complexity is Ο(n2), it is not suitable for a large set of data.
Tell me something about ‘insertion sort’?
Answer
Insertion sort divides the list into two sub-list, sorted and unsorted. It takes one element at a time and finds its 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?
Answer
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?
Answer
Both sorting techniques maintain 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?
Answer
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?
Answer
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 up to Ο(n log n).
How quick sort works?
Answer
Quicksort uses a divide and conquers 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 quicksort.
What is a graph?
Answer
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 does depth first traversal work?
Answer
Depth First Search algorithm(DFS) traverses a graph in a depth ward 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 does breadth first traversal work?
Answer
Breadth-First Search algorithm(BFS) traverses a graph in a breadth wards 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?
Answer
A tree is a minimally connected graph having no loops and circuits
What is a binary tree?
Answer
A tree is a minimally connected graph having no loops and circuits
What is a binary search tree?
Answer
A binary tree has a special condition that each node can have two children at maximum
What is a binary search tree?
Answer
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 a value greater than it’s parent value.
What is tree traversal?
Answer
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?
Answer
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 the Balance Factor.
BalanceFactor = height(left-sutree) − height(right-sutree)
What is a spanning tree?
Answer
A spanning tree is a subset of Graph G, which has all the vertices covered with the 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 have?
Answer
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 the number of nodes.
How does Kruskal’s algorithm work?
Answer
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 the least cost among all available options and does not violate MST properties.
How Prim’s algorithm finds a spanning tree?
Answer
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)?
Answer
In a weighted graph, a minimum spanning tree is a spanning tree that has the minimum weight that all other spanning trees of the same graph.
What is a heap in data structure?
Answer
Heap is a special balanced binary tree data structure where the root-node key is compared with its children and arranged accordingly. A min-heap, a parent node has key-value less than its children and a max-heap parent node has a value greater than its children.
What is a recursive function?
Answer
A recursive function is one which calls itself, directly or calls a function that in turn calls it. Every recursive function follows the recursive properties − base criteria where functions stop calling itself and progressive approach where the functions try to meet the base criteria in each iteration.
What is tower f Hanoi?
Answer
Tower of Hanoi, is a mathematical puzzle which consists of three towers (pegs) and more than one rings. All rings are of different size 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?
Answer
Fibonacci Series generates subsequent number by adding two previous numbers. For example − 0 1 1 2 3 5 8 13.
What is hashing?
Answer
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 data index can be find by providing its key values.
What is interpolation search technique?
Answer
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)?
Answer
Prefix Notation − * + a b + c d
Postfix Notation − a b + c d + *
