Spaces:
Sleeping
Sleeping
File size: 2,893 Bytes
e266561 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 | """
Misconception Library — common wrong approaches per DSA topic.
Used by the hint node to generate targeted, awareness-raising hints.
"""
MISCONCEPTION_LIBRARY: dict[str, list[str]] = {
"two sum": [
"Using O(N²) nested loops instead of a hashmap giving O(N)",
"Sorting the array and using two pointers (works but misses the index requirement)",
],
"dynamic programming": [
"Recursive solution without memoization (exponential time)",
"Filling DP table in the wrong order (top-down vs bottom-up confusion)",
"Using 2D DP table when 1D rolling array suffices",
],
"graph bfs": [
"Not using a visited set — causes infinite loops in cyclic graphs",
"Using DFS instead of BFS for shortest-path problems",
],
"graph dfs": [
"Forgetting to backtrack state in recursive DFS",
"Not handling disconnected components",
],
"sliding window": [
"Shrinking the window incorrectly (off-by-one on left pointer)",
"Recomputing window sum from scratch instead of incrementally updating",
],
"binary search": [
"Using wrong boundary: `mid < right` vs `mid <= right`",
"Integer overflow: use `mid = left + (right - left) // 2`",
],
"linked list": [
"Losing the next pointer before reassignment",
"Not handling the head node as a special case",
],
"tree traversal": [
"Mixing up in-order, pre-order, and post-order for the required output",
"Forgetting base case for null nodes",
],
"heap / priority queue": [
"Using a max-heap when a min-heap is needed (or vice versa)",
"Not heapifying after updating an element",
],
"backtracking": [
"Not undoing state changes before returning (missing 'undo' step)",
"Pruning conditions placed after recursive call instead of before",
],
"trie": [
"Using a dict instead of a fixed-size array for children (slower but acceptable)",
"Forgetting to mark end-of-word node",
],
"union find": [
"Using naive union without path compression (too slow for large N)",
"Forgetting to check if two nodes share the same root before merging",
],
"default": [
"Incorrect time/space complexity analysis",
"Not considering edge cases (empty input, single element, negative numbers)",
],
}
def get_misconceptions(topic: str) -> list[str]:
"""Return known misconceptions for the given topic (case-insensitive)."""
key = topic.strip().lower()
# Try exact match first, then partial match
if key in MISCONCEPTION_LIBRARY:
return MISCONCEPTION_LIBRARY[key]
for lib_key, misconceptions in MISCONCEPTION_LIBRARY.items():
if lib_key in key or key in lib_key:
return misconceptions
return MISCONCEPTION_LIBRARY["default"]
|