2021's Top 40 Interview-Quality Questions and Answers about Data Structures - Presented by IQCode

Data Structure Interview Questions

Here is a list of common interview questions related to Data Structures:

1. What is a linked list and how is it implemented in memory?<br>
2. Explain the difference between a stack and a queue.<br>
3. What is a binary search tree and how does it work?<br>
4. What is a hash table and how is collision resolved?<br>
5. Compare and Contrast Linear and Non-Linear Data Structures<br>
6. What is the difference between an array and a linked list?<br>
7. Describe Breadth First Search (BFS) and Depth First Search (DFS)<br>
8. How are trees represented in memory?<br>
9. What is the difference between a complete binary tree and a full binary tree?<br>
10. Can you explain Dijkstra's algorithm for shortest path finding?

What is a Data Structure?

Data structure is a critical concept in any programming language, playing a crucial role in algorithm design. It is utilized to organize and modify data efficiently. A data structure defines how data and relationships between different data are represented, which helps in the efficient application of various functions, operations, or algorithms.

// Example of a data structure

class LinkedList { 
     Node head;
     static class Node { 
         int data; 
         Node next; 
         Node(int d) { data = d;  next = null; } 
     } 
}

Here is an example of a data structure, in the form of a linked list class in Java.

Data Structures Types in Programming

In programming, data structures are broadly categorized into two categories:

• Linear data structure: If the elements in a data structure are arranged in a sequence or a linear list, then it is called a linear data structure. Examples of linear data structures include arrays, linked lists, stacks, queues and so on.
• Non-linear data structure: If the elements in a data structure are arranged in a way that traversal of nodes is not done in a sequential manner, then it is a non-linear data structure. Examples of non-linear data structures include trees, graphs and so on.

//sample code illustrating linear and non-linear data structures

// Linear Data Structures

int[] linear_arr = {1, 3, 5, 7, 9}; //array

LinkedList<String> linear_list = new LinkedList<String>(); //linked list

linear_list.add("Apple");
linear_list.add("Banana");
linear_list.add("Cherry");
linear_list.add("Durian"); 

// Non-Linear Data Structures

Map<String, Integer> non_linear_map = new HashMap<>(); //graph

non_linear_map.put("John", 25);
non_linear_map.put("Jane", 30);
non_linear_map.put("Bob", 35);
non_linear_map.put("Alice", 40);

Applications of Data Structures

Data structures are fundamental in software programming as the effectiveness of algorithms relies on the efficient structuring of data. Here are some areas where data structures are commonly used:

• Identifiers in compiler implementations use hash tables for lookup.
• B-trees are often used for database implementation.
• Artificial intelligence
• Compiler design
• Machine learning
• Database design and management
• Blockchain
• Numerical and statistical analysis
• Operating system development
• Image and speech processing
• Cryptography

Benefits of Learning Data Structures

Proper knowledge and understanding of data structures are essential to efficiently solve any given problem with constraints of time and space complexity. To achieve this, the problem needs to be represented in a well-structured format. Selecting the right data structure is a major step towards efficient problem-solving.

Data Structures in C and Java

Although the core concepts of data structures remain the same across all programming languages, the implementation differs according to the syntax or structure of the language used. In procedural languages like C, structures and pointers are used for implementation, while in object-oriented languages like Java, data structures are implemented using classes and objects.

Sound knowledge of data structures concepts is an essential part of any interview, as it helps in selecting the appropriate data structure for achieving efficient problem-solving.

Interview Questions

1. What is the difference between file structure and storage structure?

File structure represents data stored in secondary or auxiliary memory devices like a hard disk or pen drive, which remains intact until it is deleted manually. On the other hand, storage structure stores data in the main memory (RAM), which gets deleted once the function using that data gets executed completely.

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

Linear data structures result in a sequence or linear list of elements, whereas non-linear data structures have nodes traversed in non-linear fashion. Examples of linear data structures include stacks, queues, and lists, while graphs and trees are examples of non-linear data structures.

3. What is an array?

Arrays are collections of similar types of data stored in contiguous memory locations. They are the simplest data structures where the data element can be randomly accessed using its index number.

4. What is a multidimensional array?

Multi-dimensional arrays span across more than one dimension and allow the storage of data in more than one index on one or more dimensions. They are commonly used for representing matrices.

PRACTICE INTERVIEW QUESTIONS ON DATA STRUCTURES

1. Which data structure cannot store non-homogeneous data elements?

• Arrays
• Records
• Pointers
• Stacks

2. A directed graph is _______ if there is a path from each vertex to every other vertex in the graph.

• Weakly connected
• Strongly connected
• Tightly connected
• Linearly connected

3. In which traversal, we process all of a vertex's descendants before we move to an adjacent vertex?

• BFS
• DFS
• Level order
• Width first

4. In circular queue, the value of rear would be?

• REAR = REAR + 1
• REAR = (REAR + 1) % (QUEUE_SIZE+1)
• REAR = (REAR + 1) % (QUEUE_SIZE)
• REAR = (REAR - 1) % (QUEUE_SIZE-1)

5. Which of the following statement is true?

• i only
• ii only
• both i and ii
• none of the above

1. Using singly linked lists and circular list, it is not possible to traverse the list backwards
2. To find the predecessor, it is required to traverse the list from the first node in case of singly linked list.

6. The binary search method needs no more than ________ comparisons.

• (log2n) + 1
• logn
• (logn) + 1
• log2n

7. Which of the following are the properties of a binary tree?

• The first subset is called left subtree
• The second subtree is called right subtree
• The root cannot contain NULL
• The right subtree can be empty

8. Which of the following scenarios is true for the statement - "Arrays are best data structures"?

• For the size of the structure and the data in the structure are constantly changing
• For relatively permanent collections of data
• Both a and b
• None of the above

9. Which of the following code snippets is used to convert decimal to binary numbers?

public void convertBinary(int num){
    int bin[] = new int[50];
    int index = 0;
    while(num > 0){
        bin[index++] = num%2;
        num = num/2;
    }
    for(int i = index-1;i >= 0;i--){
        System.out.print(bin[i]);
    }
}

10. What will be the final elements on the stack if the following sequence of operations are executed?

Push(a,s);
Push(b,s);
Pop(s);
Push(c,s);

where a, b, c are the data elements and s is the stack.

• abc
• ac
• acb
• b

11. Dijkstra's algorithm cannot be applied on which of the following?

• Directed and weighted graphs
• Graphs having negative weight function
• Unweighted graphs
• Undirected and unweighted graphs