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.