Quiz

// 10 questions. Pass: >= 7.

// ===== Q1 =====
// What is the average time complexity of a hash map lookup?
// A) O(1)
// B) O(log n)
// C) O(n)
// D) O(n log n)

// ===== Q2 =====
// Which sort algorithm is stable and runs in O(n log n) worst case?
// A) QuickSort
// B) HeapSort
// C) MergeSort
// D) Selection sort

// ===== Q3 =====
// BFS is the right algorithm for:
// A) Shortest path in an UNWEIGHTED graph
// B) Shortest path in a weighted graph
// C) Detecting recursion in a function call
// D) Sorting

// ===== Q4 =====
// Dynamic programming is most useful when:
// A) The problem has overlapping subproblems + optimal substructure
// B) The input is sorted
// C) The graph is acyclic
// D) The data is small

// ===== Q5 =====
// What is the space complexity of an in-place merge sort?
// A) O(1)
// B) O(log n)
// C) O(n)
// D) O(n log n)

// ===== Q6 =====
// Binary search requires:
// A) Sorted input
// B) Hash map
// C) Linked list
// D) Sorted + indexable (array)

// ===== Q7 =====
// Which data structure is best for top-K elements?
// A) Sorted array
// B) Min-heap of size K
// C) Hash set
// D) Linked list

// ===== Q8 =====
// 'O(n!) ' algorithm input size you can realistically handle:
// A) n = 1 million
// B) n = 100
// C) n = 12
// D) n = 1000

// ===== Q9 =====
// A trie is best for:
// A) Sorted numeric data
// B) Prefix search / autocomplete
// C) Shortest path
// D) Sorting

// ===== Q10 =====
// In a hash map, what is the worst-case lookup time?
// A) O(1) always
// B) O(log n)
// C) O(n) — when collisions degrade to a linked list scan
// D) O(n log n)

// ===== Answers =====
// 1. A — O(1) average; worst case is O(n)
// 2. C — MergeSort is stable + O(n log n)
// 3. A — BFS finds shortest unweighted path
// 4. A — DP wants overlapping subproblems + optimal substructure
// 5. C — MergeSort uses O(n) extra space (not in-place)
// 6. D — Sorted + random-access (array)
// 7. B — Min-heap of size K for top-K
// 8. C — O(n!) becomes impossibly slow past n ~ 12
// 9. B — tries for prefix search
// 10. C — O(n) worst case under collisions

// ===== Patterns to internalise =====
// - Hash map for lookup; sort + sweep beats pairwise
// - BFS for unweighted shortest paths; Dijkstra for weighted
// - DP when subproblems overlap
// - Heap for top-K and merge-K-sorted
// - Always state worst + average + best

// 3 questions per lesson.