Data Structure Interview Questions

1. What is a Data Structure?
A data structure is a way of organizing the data so that the data can be used efficiently. Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks. For example, B-trees are particularly well-suited for implementation of databases, while compiler implementations usually use hash tables to look up identifiers.

2. What are linear and non linear data Structures?

• Linear: A data structure is said to be linear if its elements form a sequence or a linear list. Examples: Array. Linked List, Stacks and Queues
• Non-Linear: A data structure is said to be non-linear if traversal of nodes is nonlinear in nature. Example: Graph and Trees. 

3. What are the various operations that can be performed on different Data Structures?

• Insertion ? Add a new data item in the given collection of data items.
• Deletion ? Delete an existing data item from the given collection of data items.
• Traversal ? Access each data item exactly once so that it can be processed.
• Searching ? Find out the location of the data item if it exists in the given collection of data items.
• Sorting ? Arranging the data items in some order i.e. in ascending or descending order in case of numerical data and in dictionary order in case of alphanumeric data.

4. How is an Array different from Linked List?

• The size of the arrays is fixed, Linked Lists are Dynamic in size.
• Inserting and deleting a new element in an array of elements is expensive, Whereas both insertion and deletion can easily be done in Linked Lists.
• Random access is not allowed in Linked Listed.
• Extra memory space for a pointer is required with each element of the Linked list.
• Arrays have better cache locality that can make a pretty big difference in performance.

5. What is Stack and where it can be used?
Stack is a linear data structure which the order LIFO(Last In First Out) or FILO(First In Last Out) for accessing elements. Basic operations of stack are : Push, Pop , Peek
Applications of Stack:

1. Infix to Postfix Conversion using Stack
2. Evaluation of Postfix Expression
3. Reverse a String using Stack
4. Implement two stacks in an array
5. Check for balanced parentheses in an expression

6. What is a Queue, how it is different from stack and how is it implemented? Queue is a linear structure which follows the order is First In First Out (FIFO) to access elements. Mainly the following are basic operations on queue: Enqueue, Dequeue, Front, Rear
The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added. Both Queues and Stacks can be implemented using Arrays and Linked Lists.

7. What is a Linked List and What are its types?
A linked list is a linear data structure (like arrays) where each element is a separate object. Each element (that is node) of a list is comprising of two items – the data and a reference to the next node.Types of Linked List :

1. Singly Linked List : In this type of linked list, every node stores address or reference of next node in list and the last node has next address or reference as NULL. For example 1->2->3->4->NULL
2. Doubly Linked List : Here, here are two references associated with each node, One of the reference points to the next node and one to the previous node. Eg. NULL<-1<->2<->3->NULL
3. Circular Linked List : Circular linked list is a linked list where all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can be a singly circular linked list or doubly circular linked list. Eg. 1->2->3->1 [The next pointer of last node is pointing to the first]

 8. Briefly explain the approaches to develop algorithms.

There are three commonly used approaches to develop algorithms −

• Greedy Approach − finding solution by choosing 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

 9. 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)

 10. 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 Ο(n²). Data in target arrays/lists need not to be sorted.

11. 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.

12. 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. 

13. 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.

14. What is a tree?
A tree is a minimally connected graph having no loops and circuits.

15. What is a binary tree?
A binary tree has a special condition that each node can have two children at maximum.

16. 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.

17. 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

18. 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 data index can be find by providing its key values.