Data Structure Interview Questions and Answers

1. What is data structure?

Answer:

A data structure refers to the format for organizing and storing data. It makes data access more efficient. Data structure types include the array, the file, the record, the table, the tree, and so on.

2. When is a binary search best applied?

Answer:

Binary search is a type of algorithm. It is best applied to search in a list in which the elements are already in order or sorted.

The binary search algorithm starts searching the list from the middle. If the middle value is not the correct one, then it will go on to search the top or the bottom half in a similar manner. The idea behind binary search itself is to cut down your search space by half after each comparison. And this is only possible if the dataset is sorted.

3. What is a linked list?

Answer:

A linked list is a sequence of nodes in which each node is connected to the node following it. A linked list consists of nodes where each node contains a data field and a reference to the next node in the list. The elements in a linked list are linked using pointers.

4. What is a queue?

Answer:

A queue is an ordered collection of items. In a queue, the addition of new items happens at one end, called the "rear" and the removal of existing items occurs at the other end, commonly called the "front". As an element enters the queue, it starts at the rear and makes its way toward the front.

This makes queue as FIFO(First in First Out) data structure, which means that element inserted first will be removed first.

5. What are binary trees?

Answer:

A binary tree is one type of data structure that has two nodes, a left node, and a right node. It is made of nodes, where each node contains a "left" reference, a "right" reference, and a data element. The topmost node in the tree is called the root.

Binary trees are used to implement binary search trees and binary heaps.

6. What is a stack?

Answer:

A stack is a data structure in which data is inserted and removed according to the last-in first-out (LIFO) principle, leaving the most recently added data on top.  You can think of a stack of books; you can remove only the top book, also you can add a new book on the top.

7. Which data structures are applied when dealing with a recursive function?

Answer:

Recursion, is a function that calls itself based on a terminating condition, makes use of the stack. Using LIFO, a call to a recursive function saves the return address so that it knows how to return to the calling function after the call terminates.

8. What is merge sort?

Answer:

Merge sort is an efficient and very popular sorting algorithm. It basically follows the strategy that includes divide, conquer and combine. It divides the list recursively into two halves until it can no more be divided. And Merge the smaller lists into new list in sorted order.

9. What is the primary advantage of a linked list?

Answer:

Linked list is a dynamic data structure so it can grow and shrink at runtime by allocating and deallocating memory. So there is no need to give initial size of linked list. As size of linked list can increase or decrease at run time so there is no memory wastage.

Data structures such as stack and queues can be easily implemented using linked list.

10. What is the difference between a PUSH and a POP?

Answer:

PUSH basically is an operation to insert data into stack and POP is an operation to remove and read data from stack.

11. What is a linear search?

Answer:

In linear search method, each element in the list is checked and compared against the target key. The process is repeated until found or if the end of the file has been reached. Time taken to search elements keeps increasing as the number of elements is increased.

12. What is the advantage of the heap over a stack?

Answer:

The heap is more flexible than the stack. That is because memory space for the heap can be dynamically allocated and de-allocated as needed. However, the memory of the heap can at times be slower when compared to that stack.

13. What is recursive algorithm?

Answer:

Recursive algorithm targets a problem by dividing it into smaller, manageable sub-problems. The output of one recursion after processing one sub-problem becomes the input to the next recursive process.

14. What is binary search?

Answer:

A binary search works only on sorted lists or arrays. A binary search is a quick and efficient method of finding a specific target value from a set of ordered items.

It first checks the middle item and based on that comparison it discards the other half the records. The same procedure is then applied to the remaining half until a match is found or there are no more items left.

15. What is hashing?

Answer:

Hashing is a technique that is used to uniquely identify a specific object from a group of similar objects. 

For example, each student in a college is assigned a unique roll number that can be used to retrieve information about them.

Here, the students are hashed to a unique number.

Hashing is implemented in two steps:

An element is converted into an integer by using a hash function. This element can be used as an index to store the original element, which falls into the hash table.

The element is stored in the hash table where it can be quickly retrieved using hashed key.