top 10 DSA interview questions and answers

Here are the top 10 Data Structures and Algorithms (DSA) interview questions along with their answers:

1. What is a linked list? Explain its types.

Answer: A linked list is a linear data structure where elements, called nodes, are stored in a sequence. Each node contains data and a reference (or link) to the next node in the sequence.

Types of Linked Lists:

• Singly Linked List: Each node points to the next node, and the last node points to null.
• Doubly Linked List: Each node has two pointers, one to the next node and one to the previous node.
• Circular Linked List: The last node points back to the first node, forming a circle.

2. What is a binary tree?

Answer: A binary tree is a hierarchical data structure in which each node has at most two children, referred to as the left child and the right child. Binary trees are used in various applications, including searching and sorting.

3. Explain the difference between a stack and a queue.

Answer:

• Stack: A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. Elements are added and removed from the same end, called the top of the stack.
  • Operations: push (add), pop (remove), peek (view top element).
• Queue: A queue is a linear data structure that follows the First In, First Out (FIFO) principle. Elements are added at the rear and removed from the front.
  • Operations: enqueue (add), dequeue (remove), front (view front element).

4. What is a hash table, and how does it work?

Answer: A hash table is a data structure that maps keys to values for highly efficient lookup. It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

• Collision Handling: Common methods include chaining (where each bucket is a linked list) and open addressing (where collisions are resolved by probing).

5. Explain the time complexity of different operations in a binary search tree (BST).

Answer:

• Search: Average case O(log n), worst case O(n) if the tree becomes unbalanced.
• Insert: Average case O(log n), worst case O(n) if the tree becomes unbalanced.
• Delete: Average case O(log n), worst case O(n) if the tree becomes unbalanced.

Balancing techniques like AVL trees or Red-Black trees ensure the tree remains balanced, thus maintaining O(log n) time complexity for these operations.

6. What is dynamic programming?

Answer: Dynamic programming is an optimization technique used to solve problems by breaking them down into simpler subproblems and storing the results of these subproblems to avoid redundant computations. It is particularly useful for problems with overlapping subproblems and optimal substructure properties.

Example Problem: Fibonacci sequence.

def fibonacci(n):
    if n <= 1:
        return n
    fib = [0] * (n + 1)
    fib[1] = 1
    for i in range(2, n + 1):
        fib[i] = fib[i - 1] + fib[i - 2]
    return fib[n]

7. What is the difference between a depth-first search (DFS) and a breadth-first search (BFS)?

Answer:

• DFS: Explores as far as possible along each branch before backtracking. Uses a stack (recursively or explicitly).
  • Applications: Topological sorting, solving puzzles.
• BFS: Explores all neighbors of a node before moving to the next level. Uses a queue.
  • Applications: Shortest path in unweighted graphs, level-order traversal.

8. What is a heap data structure?

Answer: A heap is a special tree-based data structure that satisfies the heap property:

• Max-Heap: The key at the root is the largest among all keys in the heap, and the same property holds for all sub-trees.
• Min-Heap: The key at the root is the smallest among all keys in the heap, and the same property holds for all sub-trees.

Heaps are commonly used to implement priority queues.

9. How does quicksort work? Explain its average and worst-case time complexities.

Answer: Quicksort is a divide-and-conquer sorting algorithm that works as follows:

• Partitioning: Select a pivot element and partition the array into two halves, such that elements less than the pivot are on the left, and elements greater than the pivot are on the right.
• Recursion: Recursively apply the same process to the left and right halves.

Time Complexity:

• Average Case: O(n log n)
• Worst Case: O(n^2) (occurs when the smallest or largest element is always chosen as the pivot)

10. What is a graph, and how can you represent it?

Answer: A graph is a collection of nodes (or vertices) connected by edges. Graphs can be directed or undirected, weighted or unweighted.

Representation:

• Adjacency Matrix: A 2D array where the cell at (i, j) indicates the presence (and possibly the weight) of an edge between vertices i and j.
• Adjacency List: An array of lists. The index represents a vertex, and the list at that index contains the vertices that are adjacent to it.

Example:

# Adjacency list representation in Python
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}