DSA Interview Questions and Answers

1. What is an array?

  • An array is a collection of elements identified by index or key.
  • It is a contiguous block of memory where each element is of the same data type. 
  • Arrays allow for quick access to elements, but resizing them is costly.

2. What is a linked list?

  • A linked list is a linear data structure where each element (node) contains a data part and a reference (link) to the next node in the sequence.
  • Linked lists can be singly linked, doubly linked, or circularly linked.

3. What is the difference between an array and a linked list?

  • Arrays have fixed size and allow O(1) access to elements, whereas linked lists have dynamic size and require O(n) time for element access.
  • Linked lists allow for efficient insertions and deletions compared to arrays.

4. What is a stack?

  • A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. Elements are added and removed from the top of the stack.
  • Common operations are push (add) and pop (remove).

5. What is a 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.
  • Common operations are enqueue (add) and dequeue (remove).

6. What is a binary tree?

  • 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 search trees and heaps.

7. What is a binary search tree (BST)?

  • A BST is a binary tree in which each node has a value greater than all values in its left subtree and less than all values in its right subtree.
  • BSTs support efficient searching, insertion, and deletion operations.

8. What is a heap?

  • A heap is a special tree-based data structure that satisfies the heap property.
  • In a max heap, for any given node, the value of the node is greater than or equal to the values of its children.
  • In a min heap, the value is less than or equal to its children. Heaps are commonly used to implement priority queues.

9. What is a graph?

  • A graph is a collection of nodes (vertices) and edges connecting pairs of nodes. Graphs can be directed or undirected, weighted or unweighted.
  • They are used to represent networks such as social networks, transportation systems, and more.

10. What is the difference between BFS and DFS?

  • BFS (Breadth-First Search) explores nodes level by level, using a queue, while DFS (Depth-First Search) explores as far as possible along each branch before backtracking, using a stack or recursion.
  • BFS is better for finding the shortest path, while DFS is easier to implement and can be used for topological sorting.

11. What is a hash table?

  • A hash table is a data structure that maps keys to values using a hash function to compute an index into an array of buckets.
  • Each key-value pair is stored in the bucket corresponding to its hash index.
  • Hash tables provide average-case O(1) time complexity for search, insert, and delete operations.

12. What is a trie?

  • A trie (prefix tree) is a tree-like data structure that stores a dynamic set of strings. Each node represents a common prefix of some strings.
  • Tries are used in applications like autocomplete and spell checker.

13. What is dynamic programming?

  • Dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems.
  • It involves solving each subproblem once and storing the solutions to avoid redundant computations.
  • Examples include the Fibonacci sequence and the knapsack problem.

14. What is the time complexity of binary search?

  • The time complexity of binary search is O(log n), where n is the number of elements in the sorted array.
  • Binary search repeatedly divides the search interval in half, making it highly efficient for large datasets.

15. What is a balanced binary tree?

  • A balanced binary tree is a binary tree where the height of the left and right subtrees of any node differ by no more than one.
  • Examples include AVL trees and Red-Black trees. Balanced trees ensure O(log n) time complexity for search, insertion, and deletion operations.

16. What is a sorting algorithm?

  • A sorting algorithm arranges elements in a certain order (ascending or descending).
  • Common sorting algorithms include:
    Bubble Sort: O(n^2)
    Selection Sort: O(n^2)
    Insertion Sort: O(n^2)
    Merge Sort: O(n log n)
    Quick Sort: O(n log n) on average
    Heap Sort: O(n log n)

17. What is the difference between Merge Sort and Quick Sort?

  • Merge Sort:
    • A stable, divide-and-conquer sorting algorithm with O(n log n) time complexity in all cases.
    • It requires additional space for merging.
  • Quick Sort:
    • A divide-and-conquer sorting algorithm with an average time complexity of O(n log n) but worst-case O(n^2).
    • It is typically faster in practice but not stable. It is an in-place sort.

18. What is a priority queue?

  • A priority queue is an abstract data type where each element has a priority assigned to it.
  • Elements are dequeued based on their priority (higher priority elements are dequeued first). Priority queues can be implemented using heaps.

19. Explain the concept of a “greedy algorithm”.

  • A greedy algorithm makes the locally optimal choice at each stage with the hope of finding the global optimum.
  • It is used in problems where local optimal choices lead to a global solution, such as the coin change problem and Kruskal’s algorithm for minimum spanning tree.

20. What is the difference between a min heap and a max heap?

  • Min Heap:
    • The value of each node is less than or equal to the values of its children.
    • The root node has the minimum value.
  • Max Heap:
    • The value of each node is greater than or equal to the values of its children.
    • The root node has the maximum value.

Related articles

Famous Interviews