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.