Data Structures

Question 1

What are the different types of data structures?

Answer 1

Linear data structure: If the elements of a data structure result in a sequence or a linear list then it is called a linear data structure. Example: Arrays, Linked List, Stacks, Queues etc.

Non-linear data structure: If the elements of data structure results in a way that traversal of nodes is not done in a sequential manner, then it is a non linear data structure. Example: Trees, Graphs etc.

Question 2

How do linear data structures differ from non-linear data structures?

Answer 2

If the elements of a data structure result in a sequence or a linear list then it is called a linear data structure. Whereas, traversal of nodes happens in a non-linear fashion in non-linear data structures.

Lists, stacks, and queues are examples of linear data structures whereas graphs and trees are the examples of non-linear data structures.

Question 3

What is an array?

Answer 3

Arrays are the collection of similar types of data stored at contiguous memory locations.

It is the simplest data structure where the data element can be accessed randomly just by using its index number.

Question 4

What is a multidimensional array?

Answer 4

Multi-dimensional arrays are those data structures that span across more than one dimension.

This indicates that there will be more than one index variable for every point of storage. This type of data structure is primarily used in cases where data cannot be represented or stored using only one dimension. Most commonly used multidimensional arrays are 2D arrays.

2D arrays emulates the tabular form structure which provides ease of holding the bulk of data that are accessed using row and column pointers.

Question 5

What is a linked list?

Answer 5

A linked list is a data structure that has sequence of nodes where every node is connected to the next node by means of a reference pointer. The elements are not stored in adjacent memory locations. They are linked using pointers to form a chain. This forms a chain-like link for data storage.

• Each node element has two parts:
  
  • a data field
  • a reference (or pointer) to the next node.
• The first node in a linked list is called the head and the last node in the list has the pointer to NULL. Null in the reference field indicates that the node is the last node. When the list is empty, the head is a null reference.

Question 6

Are linked lists of linear or non-linear type?

Answer 6

Linked lists can be considered both linear and non-linear data structures. This depends upon the application that they are used for.

When linked list is used for access strategies, it is considered as a linear data-structure. When they are used for data storage, it can be considered as a non-linear data structure.

Question 7

How are linked lists more efficient than arrays?

Answer 7

1. Insertion and Deletion
   
   • Insertion and deletion process is expensive in an array as the room has to be created for the new elements and existing
     elements must be shifted.
   • But in a linked list, the same operation is an easier process, as we only update the address present in the next pointer of a
     node.
2. Dynamic Data Structure
   
   • Linked list is a dynamic data structure that means there is no need to give an initial size at the time of creation as it can
     grow and shrink at runtime by allocating and deallocating memory.
   • Whereas, the size of an array is limited as the number of items is statically stored in the main memory.
3. No wastage of memory
   
   • As the size of a linked list can grow or shrink based on the needs of the program, there is no memory wasted because it is
     allocated in runtime.
   • In arrays, if we declare an array of size 10 and store only 3 elements in it, then the space for 3 elements is wasted. Hence,
     chances of memory wastage is more in arrays.

Question 8

Explain the scenarios where you can use linked lists and arrays.

Answer 8

• Following are the scenarios where we use linked list over array:
  
  • When we do not know the exact number of elements beforehand.
  • When we know that there would be large number of add or remove operations.
  • Less number of random access operations.
  • When we want to insert items anywhere in the middle of the list, such as when implementing a priority queue, linked list is
    more suitable.
• Below are the cases where we use arrays over the linked list:
  
  • When we need to index or randomly access elements more frequently.
  • When we know the number of elements in the array beforehand in order to allocate the right amount of memory.
  • When we need speed while iterating over the elements in the sequence.
• When memory is a concern:
  
  1. Due to the nature of arrays and linked list, it is safe to say that filled arrays use less memory than linked lists.
  2. Each element in the array indicates just the data whereas each linked list node represents the data as well as one or more
     pointers or references to the other elements in the linked list.
• To summarize, requirements of space, time, and ease of implementation are considered while deciding which data structure has to be used over what.

Question 9

What is a doubly-linked list (DLL)? What are its applications.

Answer 9

• This is a complex type of a linked list wherein a node has two references:
  
  • One that connects to the next node in the sequence
  • Another that connects to the previous node.
• This structure allows traversal of the data elements in both directions (left to right and vice versa).
• Applications of DLL are:
  
  • A music playlist with next song and previous song navigation options.
  • The browser cache with BACK-FORWARD visited pages
  • The undo and redo functionality on platforms such as word, paint etc, where you can reverse the node to get to the
    previous page.

Question 10

What is a stack? What are the applications of stack?

Answer 10

• Stack is a linear data structure that follows LIFO (Last In First Out) approach for accessing elements.
• Push, pop, and top (or peek) are the basic operations of a stack.
• Following are some of the applications of a stack:
  
  • Check for balanced parentheses in an expression
  • Evaluation of a postfix expression
  • Problem of Infix to postfix conversion
  • Reverse a string

Question 11

What is a queue? What are the applications of queue?

Answer 11

• A queue is a linear data structure that follows the FIFO (First In First Out) approach for accessing elements.
• Dequeue from the queue, enqueue element to the queue, get front element of queue, and get rear element of queue are
  basic operations that can be performed.
• Some of the applications of queue are:
  - CPU Task scheduling
  - BFS algorithm to find shortest distance between two nodes in a graph.
  - Website request processing
  - Used as buffers in applications like MP3 media player, CD player, etc.
  - Managing an Input stream

Question 12

How is a stack different from a queue?

Answer 12

In a stack, the item that is most recently added is removed first whereas in queue, the item least recently added is removed first.

Question 13

Explain the process behind storing a variable in memory.

Answer 13

• A variable is stored in memory based on the amount of memory that is needed. Following are the steps followed to store a variable:
  
  • The required amount of memory is assigned first.
  • Then, it is stored based on the data structure being used.
    
    • Using concepts like dynamic allocation ensures high efficiency and that the storage units can be accessed based on
      requirements in real time.

Question 14

What is hashmap?

Answer 14

Hashmap is a data structure that uses implementation of hash table data structure which allows access of data in constant time (O(1)) complexity if you have the key.

Question 15

What is the requirement for an object to be used as key or value in HashMap?

Answer 15

• The key or value object that gets used in hashmap must implement equals() and hashcode() method.
• The hash code is used when inserting the key object into the map and equals method is used when trying to retrieve a value from the map.

Question 16

How does HashMap handle collisions in Java?

Answer 16

• The java.util.HashMap class in Java uses the approach of chaining to handle collisions. In chaining, if the new values with same key are attempted to be pushed, then these values are stored in a linked list stored in bucket of the key as a chain along with the existing value.
• In the worst case scenario, it can happen that all key might have the same hashcode, which will result in the hash table turning into a linked list. In this case, searching a value will take O(n) complexity as opposed to O(1) time due to the nature of the linked list. Hence, care has to be taken while selecting hashing algorithm.

Question 17

What is the time complexity of basic operations get() and put() in HashMap class?

Answer 17

The time complexity is O(1) assuming that the hash function used in hash map distributes elements uniformly among the buckets.

Question 18

Which data structures are used for implementing LRU cache?

Answer 18

LRU cache or Least Recently Used cache allows quick identification of an element that hasn’t been put to use for the longest time by organizing items in order of use. In order to achieve this, two data structures are used:

• Queue – This is implemented using a doubly-linked list. The maximum size of the queue is determined by the cache size, i.e by the total number of available frames. The least recently used pages will be near the front end of the queue whereas the most recently used pages will be towards the rear end of the queue.
• Hashmap – Hashmap stores the page number as the key along with the address of the corresponding queue node as the value.

Question 19

What is a priority queue?

Answer 19

• A priority queue is an abstract data type that is like a normal queue but has priority assigned to elements.
• Elements with higher priority are processed before the elements with a lower priority.
• In order to implement this, a minimum of two queues are required - one for the data and the other to store the priority.

Question 20

Can we store a duplicate key in HashMap?

Answer 20

No, duplicate keys cannot be inserted in HashMap. If you try to insert any entry with an existing key, then the old value would be overridden with the new value. Doing this will not change the size of HashMap.
- This is why the keySet() method returns all keys as a SET in Java since it doesn’t allow duplicates.

Question 21

What is a tree data structure?

Answer 21

• Tree is a recursive, non-linear data structure consisting of the set of one or more data nodes where one node is designated as the root and the remaining nodes are called as the children of the root.
• Tree organizes data into hierarchical manner.
• The most commonly used tree data structure is a binary tree and its variants.
• Some of the applications of trees are:
  
  • Filesystems —files inside folders that are in-turn inside other folders.
  • Comments on social media — comments, replies to comments, replies to replies etc form a tree representation.
  • Family trees — parents, grandparents, children, and grandchildren etc that represents the family hierarchy.

Question 22

What are Binary trees?

Answer 22

A binary Tree is a special type of tree where each node can have at most two children. Binary tree is generally partitioned into three disjoint subsets, i.e. the root of the tree, left sub-tree and right sub-tree.

Question 23

What is the maximum number of nodes in a binary tree of height k?

Answer 23

The maximum nodes are : 2k+1-1 where k >= 1

Question 24

What are tree traversals?

Answer 24

Tree traversal is a process of visiting all the nodes of a tree. Since root (head) is the first node and all nodes are connected via edges (or links) we always start with that node. There are three ways which we use to traverse a tree −

- Inorder Traversal:
      - Algorithm:
            - Step 1. Traverse the left subtree, i.e., call Inorder(root.left)
            - Step 2. Visit the root.
            - Step 3. Traverse the right subtree, i.e., call Inorder(root.right)
- Preorder Traversal:
      - Algorithm:
            - Step 1. Visit the root.
            - Step 2. Traverse the left subtree, i.e., call Preorder(root.left)
            - Step 3. Traverse the right subtree, i.e., call Preorder(root.right)
- Postorder Traversal:
      - Algorithm:
            - Step 1. Traverse the left subtree, i.e., call Postorder(root.left)
            - Step 2. Traverse the right subtree, i.e., call Postorder(root.right)
            - Step 3. Visit the root.

Question 25

What is a Binary Search Tree?

Answer 25

• A binary search tree (BST) is a variant of binary tree data structure that stores data in a very efficient manner such that the values of the nodes in the left sub-tree are less than the value of the root node, and the values of the nodes on the right of the root node are correspondingly higher than the root.
• Also, individually the left and right sub-trees are their own binary search trees at all instances of time.

Question 26

What is an AVL Tree?

Answer 26

AVL trees are height balancing BST. AVL tree checks the height of left and right sub-trees and assures that the difference is not more than 1. This difference is called Balance Factor and is calculates as. BalanceFactor = height(left subtree) − height(right subtree)

Question 27

What is a graph data structure?

Answer 27

Graph is a type of non-linear data structure that consists of vertices or nodes connected by edges or links for storing data. Edges connecting the nodes may be directed or undirected.

Question 28

What are the applications of graph data structure?

Answer 28

Graphs are used in wide varieties of applications. Some of them are as follows:

- Social network graphs to determine the flow of information in social networking websites like facebook, linkedin etc.
- Neural networks graphs where nodes represent neurons and edge represent the synapses between them
- Transport grids where stations are the nodes and routes are the edges of the graph.
- Power or water utility graphs where vertices are connection points and edge the wires or pipes connecting them.
- Shortest distance between two end points algorithms.

Question 29

What is the difference between tree and graph data structure?

Answer 29

• Tree and graph are differentiated by the fact that a tree structure must be connected and can never have loops whereas in the graph there are no restrictions.
• Tree provides insights on relationship between nodes in a hierarchical manner and graph follows a network model.

Question 30

What is the difference between the Breadth First Search (BFS) and Depth First Search (DFS)?

Answer 30

• BFS and DFS both are the traversing methods for a graph. Graph traversal is nothing but the process of visiting all the nodes of the graph.
• The main difference between BFS and DFS is that BFS traverses level by level whereas DFS follows first a path from the starting to the end node, then another path from the start to end, and so on until all nodes are visited.
• Furthermore, BFS uses queue data structure for storing the nodes whereas DFS uses the stack for traversal of the nodes for implementation.
• DFS yields deeper solutions that are not optimal, but it works well when the solution is dense whereas the solutions of BFS are optimal.

Question 31

How do you know when to use DFS over BFS?

Answer 31

The usage of DFS heavily depends on the structure of the search tree/graph and the number and location of solutions needed. Following are the best cases where we can use DFS:
- If it is known that the solution is not far from the root of the tree, a breadth first search (BFS) might be better.
- If the tree is very deep and solutions are rare, depth first search (DFS) might take an extremely long time, but BFS could be
faster.
- If the tree is very wide, a BFS might need too much memory, so it might be completely impractical. We go for DFS in such
cases.
- If solutions are frequent but located deep in the tree we opt for DFS.

Question 32

What is a heap data structure?

Answer 32

Heap is a special tree-based non-linear data structure in which the tree is a complete binary tree. A binary tree is said to be complete if all levels are completely filled except possibly the last level and the last level has all elements towards as left as possible. Heaps are of two types:

1. Max-Heap:
    - In a Max-Heap the data element present at the root node must be greatest among all the data elements present in the 
      tree.
    - This property should be recursively true for all sub-trees of that binary tree.
2. Min-Heap:
    - In a Min-Heap the data element present at the root node must be the smallest (or minimum) among all the data elements 
      present in the tree.
    - This property should be recursively true for all sub-trees of that binary tree.