Data Structures Interview Questions and Answers

A data structure is a way of storing and organizing data in a computer so that it can be used efficiently. A data structure not only stores data, but also supports the operations for manipulating data in the structure. The choice of a data structure for a particular problem depends on the following factors:

• Frequency and ways in which data will be used.
• Time to retrieve an element.
• Volume of data involved
• Dynamic and static nature of the data.
• Amount of storage required by the data structure.
• Ease of programming.

An algorithm may be defined as a finite sequence of instructions each of which has a clear meaning and can be performed with a finite amount of effort in a finite length of time.

Data structures are broadly classified in two types.

Linear Data Structures:

• Array
• Stack
• Queue
• Linked List

Non-Linear Data Structures:

• Tree
• Graph

Algorithms are certainly proved approaches to the problem for a given set of data.

• Sorting
• Searching
• Traversal
• Delete
• Insert
• Clustering of data

Merge-sort is a sorting algorithm based on the divide-and-conquer paradigm. Many other sorts that sort data sets in a linear manner, Merge Sort breaks the data into small data sets.

• Spanning Tree and Minimum Spanning Tree
• Strongly Connected Components
• Adjacency Matrix
• Adjacency List

• Binary Tree
• Binary Search Tree
• AVL Tree
• B-Tree
• B+ Tree
• Red-Black Tree

Here are the lists of Commonly used Data Structures are:

Let’s first list the most commonly used data structures, and then we’ll cover them one by one:

• Arrays
• Stacks
• Queues
• Trees
• Linked lIsts
• Graphs
• Tries
• Hash Tables

Recursion is the process in which a function is called by itself again & again.

It is doubly-ended queue. In doubly-ended queue, insertion and deletion takes place at both ends.

• To implement applications that require a sorted list as input like various
• e-commerce websites.
• To implement multilevel indexing in database.
• To implement various efficient algorithms.
• To manage Virtual Memory Areas.
• To index various Networking & IP addresses.

AVL stands for Adelson, Velski, Landis. AVL trees are height balancing BST. It checks the height of left & right subtree and assures that difference is not more than 1, this difference is termed as balanced factor.

The compiler uses a stack to implement recursion. Recursion makes use of system stack for storing the return addresses of the function calls. Every recursive function has its equivalent function.

Array is a random-access data structure used to store large number of data values to reduce the complexity of the program. Stack is a linear data structure that can be thought as a basic data structure represented by a collection of items arranged in the form of a physical stack. It allows FIFO order or LIFO.

“Array has a fixed size. But, in stack has both fixed and dynamic size.

In Array, we can store elements of the same data type. But, in stack we can store elements of different data types.

In Dynamic data structure the size of the structure in not fixed and can be modified during the operations performed on it. Dynamic data structures are designed to facilitate change of data structures in the run time. In C Language, Dynamic memory management involves the use of pointers and four standard library functions, namely, malloc, calloc, realloc and free. Heap space is used in Dynamic Memory Allocation.

Two minimum Queues needed to implement the priority queue. One queue is used for actual storing of data and another for storing priorities.

Polish and Reverse Polish notations are used.

Backtracking Algorithm is used.

1014 – Formula for n nodes: – n

• Straight merging
• Natural merging
• Polyphase sort
• Distribution of Initial runs.

The data structure is a key component of Computer Science & Software Engineering. It is largely used in the areas of Artificial Intelligence, Complier design, Database design, operating systems, graphics, simulation etc

Array is a static type and Linked list is a dynamic type. In array, Insertion and Deletion operation takes more time, while in linked list operations takes less time. Linked list avoids memory wastage.

A gap buffer is a data structure that lets us perform efficient insertion and deletion operations clustered near the same location.

A hashed array tree is a data structure that maintains an array of separate memory-fragments or leaves that store data elements.

A rope is a tree data structure composed of smaller strings used to store and manipulate a long string. Rope, also known as the cord is effective for this purpose.

• Using Floyd’s cycle-finding Algorithm
• Using hashing
• Using the visited nodes method

Hach table also known as Hash map.  It is a data structure that you can use to store data in key-value format with direct access to its items in constant time.

Trie is also known as Prefix Trees. It is a tree-like data structure which proves to be quite efficient for solving problems related to strings. It provides fast retrieval, and is mostly used for searching words in a dictionary, providing auto suggestions in a search engine, and even for IP routing.

Beginner Level: Stack, Queue, Linked Lists, and Binary Search Tree.

Intermediate Level: Priority Queue, Heap, Tree Map, Huffman Tree, Union Find, Tries, and Hash Table

Proficient Level: Binary Indexed Tree, Suffix Array, Sparse Table, Segment Tree, Lowest Common Ancestor, and Range Tree.

Expert Level: Suffix, Treap, Aho-Corasick, K-d tree, Dynamic Suffix Array.Link-Cut Tree, Splay Tree, Palindromic Tree, Automaton, Suffix Tree, Heavy-Light Decomposition, Rope, Dancing Links, and Radix Tree.