1What is a hash table?
A data structure that maps keys to values using a hash function
2What is separate chaining in hashing?
A method of handling collisions by storing multiple elements in a bucket as a linked list
3What is open addressing in hashing?
A method of handling collisions by finding an alternative empty slot within the array
4What is quadratic probing?
A collision resolution technique using a quadratic function to find the next available slot
5What is double hashing?
A technique using a second hash function to resolve collisions
6What is the height complexity of a balanced BST?
O(log n)
7What is the primary balancing criterion in an AVL tree?
The height difference between left and right subtrees must be at most 1
8What are the possible rotations in an AVL tree?
Left, Right, Left-Right, Right-Left
9What is a red-black tree?
A self-balancing BST that enforces rules on node colors to maintain balance
10What is the difference between BFS and DFS?
BFS explores level by level, while DFS explores depth-first
11What is the time complexity of BFS and DFS?
O(V + E)
12What is the purpose of Dijkstra’s algorithm?
To find the shortest path from a single source
13What is Bellman-Ford’s algorithm used for?
Finding shortest paths, even with negative weight edges
14What is Floyd-Warshall’s algorithm used for?
Finding shortest paths between all pairs of nodes
15What is Kruskal’s algorithm used for?
Finding the minimum spanning tree by sorting edges
16What is Prim’s algorithm used for?
Building a minimum spanning tree by growing it from a single vertex
17What is the best sorting algorithm for nearly sorted data?
Insertion sort
18Which sorting algorithms guarantee O(n log n) complexity?
Merge sort, Heap sort, Quick sort (average case)
19What is the worst-case complexity of quicksort?
O(n^2)
20Why is merge sort considered stable?
It preserves the relative order of equal elements
21What is the space complexity of merge sort?
O(n)
22What data structure is typically used for priority queues?
Heap
23What is the time complexity of inserting into a heap?
O(log n)
24What is the time complexity of extracting min/max from a heap?
O(log n)
25What is the general form of the Master Theorem?
T(n) = aT(n) + O(n^d)
26What is the recurrence relation for binary search?
T(n) = T(n/2) + O(1)
27What is the recurrence relation for merge sort?
T(n) = 2T(n/2) + O(n)
28What is the space complexity of an adjacency list?
O(V + E)
29What is the space complexity of an adjacency matrix?
O(V^2)
30Which data structure is used in a Least Recently Used (LRU) cache?
Hash map with a doubly linked list
31What is a trie used for?
Efficient prefix-based searching
32What is amortized analysis?
A technique for analyzing the average time complexity of operations
33What is a strongly connected component in a graph?
A subgraph where every vertex is reachable from every other vertex
34What is topological sorting used for?
Ordering vertices in a Directed Acyclic Graph (DAG)
35Which algorithm is used to find strongly connected components?
Kosaraju’s or Tarjan’s algorithm
36What is the worst-case time complexity of inserting into an unbalanced BST?
O(n)
37What is the primary advantage of red-black trees over AVL trees?
Red-black trees provide faster insertion and deletion
38What is the primary advantage of AVL trees over red-black trees?
AVL trees provide more strictly balanced trees, resulting in faster lookups
39What is a suffix tree used for?
Efficient substring searching in linear time
40What is the difference between a min-heap and a max-heap?
A min-heap stores the smallest element at the root, a max-heap stores the largest
41What is a DAG?
A directed graph with no cycles
42What is a bipartite graph?
A graph whose vertices can be divided into two sets with no edges within the same set
43What is the main idea behind dynamic programming?
Breaking problems into smaller overlapping subproblems and storing solutions
44What is memoization?
A technique used in dynamic programming to store and reuse previously computed results