Top 61 Data Structures Interview Questions And Answers

Question 1

Define Linked List

Accepted Answer

A **linked list** is a linear data structure where each element is a separate object. Each element (we will call it a **node**) of a list is comprising of two items - the **data** and a **reference (pointer)** to the next node. The last node has a reference to **null**. The entry point into a linked list is called the **head** of the list. It should be noted that _head is not a separate node,_ but the reference to the first node. If the list is empty then the head is a null reference.

Question 2

Name some characteristics of Array Data Structure

Accepted Answer

Arrays are: 
* **Finite (fixed-size)** - An array is finite because it contains only limited number of elements.
* **Order** -All the elements are stored one by one , in contiguous  location of computer memory in a linear order and fashion
* **Homogenous** - All  the elements of an array are of  same  data types only  and hence  it is termed as collection of homogenous

Question 3

What is Heap?

Accepted Answer

A **Heap** is a special Tree-based data structure which is an almost complete tree that satisfies the heap property:

* in a **max heap**, for any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C. 
* In a **min heap**, the key of P is less than or equal to the key of C. The node at the "top" of the heap (with no parents) is called the root node.

A common implementation of a heap is the binary heap, in which the tree is a **binary tree.**

![](https://www.techiedelight.com/wp-content/uploads/2016/11/Min-Max-Heap.png)

Question 4

Define Tree Data Structure

Accepted Answer

**Trees** are well-known as a _non-linear_ data structure. They don’t store data in a linear way. They organize data _hierarchically_.

A **tree** is a collection of entities called **nodes**. Nodes are connected by **edges**. Each node contains a **value** or **data** or **key**, and it may or may not have a **child** node. The first node of the tree is called the **root**. **Leaves** are the last nodes on a tree. They are nodes without children.

![](https://miro.medium.com/max/975/1*PWJiwTxRdQy8A_Y0hAv5Eg.png)

Question 5

Define Stack

Accepted Answer

A **Stack** is a container of objects that are inserted and removed according to the last-in first-out (**LIFO**) principle. In the pushdown stacks only two operations are allowed: push the item into the stack, and pop the item out of the stack.

There are basically three operations that can be performed on stacks. They are:
 
1. inserting an item into a stack (**push**). 
2. deleting an item from the stack (**pop**). 
3. displaying the contents of the stack (**peek** or **top**).

A stack is a limited access data structure - elements can be added and removed from the stack only at the top. push adds an item to the top of the stack, pop removes the item from the top. A helpful analogy is to think of a stack of books; you can remove only the top book, also you can add a new book on the top.

![](https://user-images.githubusercontent.com/13550565/85218531-fea33d80-b3cd-11ea-8ba4-77c37d446d07.png)

Question 6

What is Priority Queue?

Accepted Answer

A **priority queue** is a data structure that stores **priorities** (comparable values) and perhaps associated information.  A **priority queue** is different from a "normal" queue, because instead of being a "first-in-first-out" data structure, values come out in order by **priority**. Think of a priority queue as a kind of bag that holds priorities. You can put one in, and you can take out the current highest priority.

![](https://cdn.programiz.com/sites/tutorial2program/files/Introduction.png)

Question 7

What is String in Data Structures?

Accepted Answer

A **string** is generally considered as a **data type** and is often implemented as an **array data structure** of bytes (or words) that stores a sequence of elements, typically characters, using some character encoding. String may also denote more general arrays or other sequence (or list) data types and structures.

Question 8

What is Hash Table?

Accepted Answer

A **hash table** (hash map) is a data structure that implements an **associative** array abstract data type, a **structure** that can **map keys to values**. Hash tables implement an associative array, which is indexed by arbitrary objects (keys). A hash table uses a **hash function** to compute an **index**, also called a **hash value**, into an **array of buckets** or slots, from which the desired **value** can be found.

![](https://i.stack.imgur.com/0yjYd.png)

Question 9

What is Queue?

Accepted Answer

A **queue** is a container of objects (a _linear_ collection) that are inserted and removed according to the first-in first-out (FIFO) principle. The process to add an element into queue is called **Enqueue** and the process of removal of an element from queue is called **Dequeue**.

![](https://user-images.githubusercontent.com/13550565/85218641-9d2f9e80-b3ce-11ea-8c1b-a9c058057a70.png)

Question 10

Explain why Stack is a recursive data structure

Accepted Answer

A **stack** is a **recursive** data structure, so it's:

* a stack is either empty or
* it consists of a top and the rest which is a stack by itself;

Top 61 Data Structures Interview Questions

What is a Graph?

Explain why Stack is a recursive data structure

What is Priority Queue?

Define Stack

Define Binary Tree

What is Heap?

What is String in Data Structures?

What is Hash Table?

What is Queue?

Define Tree Data Structure

What is Trie?

Define Linked List

Name some characteristics of Array Data Structure

What is Binary Heap?

What is the difference between Strings vs. Char arrays?

What is the space complexity of a Hash Table?

What's the difference between the data structure Tree and Graph?

Under what circumstances are Linked Lists useful?

What is Binary Search Tree?

What are some types of Linked List?

What are Dynamic Arrays?

Why and when should I use Stack or Queue data structures instead of Arrays/Lists?

What are some types of Queue?

Name some disadvantages of Linked Lists?

What is Complexity Analysis of Queue operations?

What is AVL Tree?

What is Balanced Tree and why is that important?

Name some application of Trie data structure

What does Sparse Array mean?

What is an Associative Array?

Compare Heaps vs Arrays to implement Priority Queue

What is complexity of Hash Table?

Name some common types and categories of Graphs

What is Red-Black tree?

What is Rope Data Structure is used for?

When is doubly linked list more efficient than singly linked list?

How To Choose Between a Hash Table and a Trie (Prefix Tree)?

What are some main advantages of Tries over Hash Tables

Explain what is B-Tree?

How would you traverse a Linked List in O(n1/2)?

What are Pascal Strings?

What is Bipartite Graph? How to detect one?

How are B-Trees used in practice?

Compare lookup operation in Trie vs Hash Table

Convert a Singly Linked List to Circular Linked List

How to implement a Tree data-structure? Provide some code.

Implement Pre-order Traversal of Binary Tree using Recursion

Return the N-th value of the Fibonacci sequence. Solve in O(n) time

Return the N-th value of the Fibonacci sequence Recursively

Find all the Permutations of a String

Can you do Iterative Pre-order Traversal of a Binary Tree without Recursion?

Convert a Binary Tree to a Doubly Linked List

Explain how Heap Sort works

LIS: Find length of the longest increasing subsequence (LIS) in the array. Solve using DP.

How to check if two Strings (words) are Anagrams?

How to merge two sorted Arrays into a Sorted Array?

Explain what is Fibonacci Search technique?

Find the length of a Linked List which contains Cycle (Loop)

Binet's formula: How to calculate Fibonacci numbers without Recursion or Iteration?

How to implement 3 Stacks with one Array?

Explain how QuickSort works

How would you traverse a Linked List in `O(n^1/2)`?

Return the N-th value of the Fibonacci sequence. Solve in `O(n)` time