After applying for any coding interview there is almost a surety that you will be asked data structures interview questions and there is a lot of computer graduate applying for big companies Google, Netflix, Yahoo, Microsoft, Adobe, IBM and service-based companies cognizant and Infosys.
In this article, we will discuss commonly asked data structures interview questions which will help any college graduate to land a job offer. However, it is not sure that interviewer will ask the same data structures interview questions as shared below but still you will get an idea about what type of questions can be asked. If you don’t have any basic knowledge about the data structure then I will recommend some books which can help
Introduction to Algorithms, by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
Data Structures and Algorithms Made Easy: Data Structures and Algorithmic Puzzles by Narasimha Karumanchi
Table of Contents
Data Structures Interview Questions and Answers
What is the data structure? Please explain briefly
As the term describes itself that it is a specific format in which the data is processed, organized, store and retrieve. There are many types by which data can be organized and related but the end goal is that data should be accessed appropriately and must serve the purpose.
Name some of the forms of data structure?
There are generally four forms of data structure
- Graphs
- Tree
- Hash
- Linear
Draw the data structure classification
What is the graph data structure?
In graph data structure there are nodes which are connected to each other. It can be undirected and directed, in directed the edges lines show the direction of the flow and in undirected, there is no arrow so the flow between the flow can be in either direction.
What is an algorithm?
It is a set of instructions or rules which are defined to solve problems or do calculations.
Why algorithm analysis is important?
After designing the algorithm, we analysis to calculate the complexity and the efficiency of it by measuring the cost, time, resources needed to execute it and the storage required. Also, it is very important from the software development phase and thus it answers why and what computer should do in the finite time.
What criteria must algorithm satisfy?
All the algorithm must satisfy the below criteria
- Input: Any algorithm must be provided zero or more values which are essential to run any algorithm.
- Output: Any algorithm must provide at minimum one output, which is considered the solution to the problem.
- Definiteness: Every step must be described and explained.
- Finiteness: There must be an end step which means the algorithm should have a stop condition when output is given in the finite time.
- Effectiveness: Every step in an algorithm is feasible for any system ton run and also practically possible in terms of time and resource utilized.
What is a tree in data structure?
It is a group of nodes and non-linear data structure, below is the image which describes as a tree in the data structure.
What is the linear data structure?
It’s a data structure where data elements are arranged in sequential order and they are connected adjacent to each other (next and previous).
Share any example of linear data structure?
There are four of them which are
- Array
- Linked List
- Queue
- Stack
What is a Stack? Share some examples?
As it is a linear structure so the data is organized in a particular order. For example LIFO – Last in First Out and FILO – First in Last Out. There is a simple example to when we go some shop where items are stacked on a rack thus the item which is stacked first comes out at the last from the rack.
Explain operations in the stack?
There are following operations in the stack
Push: To add item in a stack.
Pop: To take out the last item added.
Peek/ Top: returns the top item.
is Empty: to check the stack is empty or not.
What is Linked List? Share some examples?
The linked list is also a linear structure in which at every node contains a reference to the next node and another contains the data.
What is the Queue? Share some examples?
The queue is a linear data structure is organized in a particular order which is FIFO and the best example to explain is when we are in the shopping queue, so whosoever first go to billing counter will get items purchased.
What is an Array?
So, an array is a data structure which holds the group of elements or a variable which holds more the one fixed number of data value at a time.
Data structures interview questions on searching and sorting
What is the linear searching Algorithm?
Linear search is a very simple algorithm in this we make a sequential search to find the correct value. For example
We have 10, 20, 30, 40, 50, 60, 70, 80, 90. Thus if we want to search 70 in this then we have to traverse 10, 20, 30, 40, 50, 60 and the only we will find 70.
Input : arr[] = {10, 20, 80, 30, 60, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150}
y = 100;
Output : 10 element y is present at index 10
Now y = 55;
Output : -1
Element y is not present in arr[].
What is a binary search?
This is an algorithm which works on the principle divide and conquers, thus the algorithm to run efficiently the array needs to be sorted thus with that it divides the index of the array and if the mid position is the value then ok if not then all the before values and index will be discarded and then the cycle will run till the time value is not found.
For example
You have an array as 1, 7, 8, 9, 10, 2 3, 4, 5, 6
Then first it will be sorted to 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
We need to search value 5
After that the mid index is calculated ex- 0-9 is the index where middle = start + (end – start)/2 which is mid = 0+(9-0)/2= 4.5 and round about 4 thus on 4 index places is 5.
What is the Fibonacci series?
It is a series where the next term value is the addition of the previous two values.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 so how it works the first two terms are 0 and 1 then next term will be 0+1 = 1 it makes 0, 1, 1 then 1+1 = 2 it makes 0, 1, 1, 2 then 2+1 = 3 then it makes 0, 1, 1, 2, 3 and so on.
Name the sorting algorithms?
Some of them are
- Bubble Sort
- Recursive Bubble Sort
- Merge Sort for Linked Lists
- Merge Sort for Doubly Linked List
- 3-way Merge Sort
- Iterative Merge Sort
- Quick Sort
- Iterative Quick Sort
- Heap Sort
- Counting Sort
- Radix Sort
- Bucket Sort
- Odd-Even Sort / Brick Sort
- QuickSort on Singly Linked List
- QuickSort on Doubly Linked List
- ShellSort
- TimSort
- Comb Sort
- Pigeonhole Sort
- Cycle Sort
- Cocktail Sort
- Strand Sort
- Bitonic Sort
- Pancake sorting
- Binary Insertion Sort
- BogoSort or Permutation Sort
- Gnome Sort
- Sleep Sort
- Structure Sorting (By Multiple Rules) in C++
- Stooge Sort
- Tag Sort (To get both sorted and original)
- Insertion Sort
- Recursive Insertion Sort
- Merge Sort
- Tree Sort
- Cartesian Tree Sorting
- 3-Way QuickSort (Dutch National Flag)
- balloon sort
Which the fastest sorting algorithms
We cannot consider one as fastest, as it all depends on the data structure and data set.
If you have some other data structures interview questions and answer please comment below and let us know we will add more data structures interview questions and answer in the upcoming future.
What is big o notation?
It is the mathematical notion which helps to measure the complexity of the algorithm. It measure how much memory, time, resouces is required to resolve the problem with different inputs.
For more Big o Cheetsheet
Other Resources which may help to clear job interview
Things to Do Before During First Job Interview Tips & Checklist