An NLP-powered study companion that answers "which data structure and algorithm should I use?" for any DSA problem you type. It indexes 81 real DSA question-answer pairs into semantic vector space and returns the best match — plus alternatives — with a confidence score.
Built from scratch in pure Python on top of sentence-transformers, with no database, no web-service, and no hard-coded lookup table: the matching intelligence comes from vector embeddings + a hybrid scoring model.
| Core script | dsacheck_semantic.py (392 lines, std-lib parsers + sentence-transformers) |
| Knowledge base | bigpicture.md (27 deep-dive Q&A) + qabank.md (54 classic interview Q&A) = 81 pairs |
| Embedding model | all-MiniLM-L6-v2 — 384-dim vectors, ~90 MB, downloaded once |
| Scoring | 0.50·semantic + 0.25·domain + 0.25·lexical + 0.10·priority |
| Interfaces | Interactive prompt, q.txt file mode, library API |
| Runtime | Question matching in milliseconds; embeddings pre-computed once at startup |
- Why this project
- Features
- How it works — the embedding pipeline
- System architecture
- The hybrid scoring model
- The knowledge base
- Installation
- Usage
- Why "semantic" beats keyword search
- Evolution: three generations of the system
- Known quirks
- Repository tour
- Tech stack
- Possible extensions
Most DSA study tools are static lists. This one is interactive: you describe a problem in your own words — the way you would in an interview — and the system finds the closest known problem, then hands you the recommended data structure, the algorithm, and its time/space complexity.
It demonstrates end-to-end, production-shaped engineering:
- Natural language retrieval with real transformer embeddings (not regex keywords)
- Hybrid ranking that blends semantic, domain, and lexical signals
- Robust parsing of two very different Markdown documentation formats
- Interactive + scripted interfaces with graceful fallback guidance
- Semantic matching — understands paraphrases, not just keywords, via cosine similarity on 384-dim sentence embeddings
- 81-question knowledge base — real interview problems spanning arrays, linked lists, stacks, trees, heaps, hashing, graphs, DP, and advanced structures
- Domain-intelligence layer — 12 DSA concept groups (graph, heap, sliding-window, dynamic-programming, ...) that fire on domain vocabulary
- Top-3 ranking — the best match plus two alternatives, each with a confidence score and source id
- Priority handling — curated deep-dives (
bigpicture.md) are ranked ahead of the flat question bank - Confidence guard — below
0.30it falls back to generic DSA guidance instead of a wrong answer - Three interfaces — interactive REPL, file mode, and a clean library API (
DSAQuestionSystem)
- You type the problem in natural language: "Design an LRU cache with O(1) get and put operations."
- The model encodes it into a 384-dimension vector
qusingall-MiniLM-L6-v2. - The same vector space already holds the embeddings of all 81 stored questions (
a_1 … a_81), computed once at startup. - Cosine similarity
cos(q, a) = (q · a) / (‖q‖ · ‖a‖)measures the angle between your question and every stored question. - A hybrid score blends that semantic signal with domain keywords and lexical overlap (see below).
- The top-ranked pair — question, answer, data structure, algorithm, complexity — is rendered back to you with alternatives.
"Similar language ⇒ similar meaning" is exactly what transformer embeddings are good at, which is why typing "suggest the fastest way to cache pages I keep revisiting" can still land on the LRU Cache question even though the words match only loosely.
| # | Component | Code | What it does |
|---|---|---|---|
| 1 | Input | interactive_mode() / process_question_from_file() |
Accepts free text from the prompt or q.txt |
| 2 | Knowledge base | load_training_data() → parse_bigpicture() / parse_qabank() |
Regex-parses two Markdown formats into 81 (question, answer, data_structure, algorithm) records |
| 3 | Embeddings | compute_embeddings() |
Loads the transformer once and encodes all 81 questions into 384-dim vectors |
| 4 | Hybrid scorer | find_best_match() |
Combines semantic + domain + lexical scores with a priority boost |
| 5 | Ranker | find_best_match() (suggestions) |
Sorts descending, keeps top-3 |
| 6 | Response formatter | format_response() |
Renders the match, alternatives, confidence — or generic guidance below 0.30 |
typed question or q.txt
│
▼
┌─────────────────┐ ┌───────────────────────┐
│ parsers │ │ sentence-transformers │
│ bigpicture.md │────►│ all-MiniLM-L6-v2 │
│ qabank.md │ │ → q + 81×384-d vectors │
└─────────────────┘ └───────────┬───────────┘
▼
┌───────────────────────────┐
│ hybrid score per question │─► rank ─► top 3 ─► formatted answer
└───────────────────────────┘
For every stored question, the system computes three independent signals and adds a priority boost:
# dsacheck_semantic.py:220-223
semantic_sim = self.semantic_similarity(query, idx) # cosine similarity of embeddings
domain_sim = self.domain_similarity(query, qa['question']) # DSA-domain keyword overlap
text_sim = SequenceMatcher(None, query.lower(), qa['question'].lower()).ratio()
priority_boost = 0.1 if qa['source'] == 'bigpicture' else 0.0
combined_score = 0.5 * semantic_sim + 0.25 * domain_sim + 0.25 * text_sim + priority_boost| Signal | Weight | Why it matters |
|---|---|---|
| Semantic (embedding cosine) | 0.50 |
The core — captures paraphrase-level meaning |
| Domain (12 concept groups) | 0.25 |
Anchors DSA vocabulary: graph, heap, sliding, memoization… |
Lexical (difflib.SequenceMatcher) |
0.25 |
Bonus when the user copies or near-quotes a known question |
| Priority boost (deep-dives) | +0.10 |
Curated explanations (bigpicture.md) outrank flat bank entries when close |
Note: the boost means scores are semi-normalized and can exceed 1.0 — a perfect exact-quote match on a
bigpicturequestion scores1.0 + 0.10 = 1.10(in practice ≈1.09). The threshold guard atconfidence < 0.30triggers the generic fallback.
Two sources, two very different Markdown dialects, one unified record schema:
| Source | Format | Pairs loaded | IDs |
|---|---|---|---|
bigpicture.md |
## Q<n> blocks with ### Question / ### Answer from sniper.py / ### Data Structure Used / ### Algorithm Used |
27 | BP_Q1 … BP_Q27 |
qabank.md |
### Q<n> blocks with **Question:** / **Answer:** / **Data Structure:** / **Algorithm:** |
54 | QB_Q1 … QB_Q54 |
Each record stores question, answer, data_structure, algorithm, source, and id. The parsers (parse_bigpicture at :100, parse_qabank at :152) use re.split on section headers and regex capture groups — a real-world exercise in turning untrusted Markdown into structured data.
Requires Python 3.10+.
# 1. (optional but recommended) create a virtual environment
python -m venv .venv
.venv\Scripts\activate # Windows
source .venv/bin/activate # macOS / Linux
# 2. install dependencies
pip install sentence-transformers torchThe first launch downloads the all-MiniLM-L6-v2 model (~90 MB) into the Hugging Face cache; subsequent runs load it from disk.
Run from the dsaprac/ directory, which already contains bigpicture.md, qabank.md, and q.txt.
python dsacheck_semantic.pyIf a q.txt exists it is processed first; answer y at the prompt to open the interactive REPL:
Enter your DSA question: Design an LRU cache with O(1) get and put operations for a web browser.
============================================================
Advanced Semantic Match Found (Confidence: 0.83)
**Question**: Design LRU cache with get and put operations.
**Suggested Answer**:
Use hash map for O(1) access and doubly linked list for order.
**Recommended Data Structure**:
Hash Map + Doubly Linked List
**Algorithm to Use**:
Ordered hash map with O(1) operations.
**Source**: qabank (QB_Q34)
==================================================
**Alternative Semantic Suggestions**:
**Alternative 1** (Confidence: 0.83):
Question: Implement LRU cache with guaranteed O(1) get and put operations.
Data Structure: Custom Hash Map + Doubly Linked List
Algorithm: Ordered hash map with guaranteed O(1) complexity.
**Alternative 2** (Confidence: 0.69):
Question: A web browser needs to cache recently visited pages with limited memory.
Data Structure: Hash Map + Doubly Linked List
Algorithm: **LRU Eviction Policy** - Move accessed items to end, remove from front when capacity exceeded.
Type quit to exit, or file to load a question from q.txt mid-session.
Put any question in q.txt and run without interactive mode:
echo "Your backend has an API endpoint that returns a customer's history..." > q.txt
python dsacheck_semantic.pyHealth check output during startup:
Initializing Advanced Semantic DSA System...
Loaded 27 Q&A pairs from bigpicture.md
Loaded 54 Q&A pairs from qabank.md
Total Q&A pairs loaded: 81
Computing semantic embeddings...
Embeddings computed successfully!
Found q.txt, processing question with semantic analysis...
The stored question (q.txt — the classic "nested loops → customer report" problem) matches its own bigpicture deep-dive at confidence 1.09: Hash Map (Dictionary) with the Hash-based Grouping Algorithm, turning O(n²) into O(n).
Embed it into your own workflows:
from dsacheck_semantic import DSAQuestionSystem
system = DSAQuestionSystem() # loads data + computes embeddings
result = system.find_best_match(
"Find the shortest path from a source to all other nodes in a weighted graph."
)
match = result["match"] # the best Q&A record
print(match["question"]) # Find shortest path from source to all vertices...
print(match["data_structure"]) # Weighted Graph + Priority Queue
print(match["algorithm"]) # Dijkstra's algorithm with O((V+E) log V) time.
print(result["confidence"]) # 0.82
print([s["score"] for s in result["suggestions"]]) # top-3 scoresRephrasings land on the right question even when wording differs:
| Your question (paraphrased) | Best match | Confidence | Recommended structure / algorithm |
|---|---|---|---|
| Find the shortest path from a source to all other nodes in a weighted graph. | QB_Q40 |
0.82 | Weighted Graph + Priority Queue → Dijkstra O((V+E) log V) |
| Design an LRU cache with O(1) get and put operations for a web browser. | QB_Q34 |
0.83 | Hash Map + Doubly Linked List → Ordered hash map O(1) |
| Find two numbers in an array that add up to a given target sum. | QB_Q1 |
0.86 | Hash Map (Dictionary) → Single-pass complement lookup O(n) |
| Implement a spell checker that suggests words for a text editor. | BP_Q20 |
0.60 | Trie (Prefix Tree) → Prefix matching with DFS |
Plain keyword/TF-IDF matching (the earlier dsacheck.py) only fires when the same words appear in both texts. Semantic search instead compares meaning:
- "a page that keeps getting revisited" ≈ "recently visited pages" — same meaning, different words
- "shortest route between two cities on a map" ≈ "shortest path … weighted graph" — domain-aware
- Misspellings and word order are tolerated because the embedding is robust to surface variation
The hybrid formula deliberately keeps 0.25 of weight on cheap lexical overlap: when a user does quote a known question verbatim, the system should jump straight to it.
| Script | Matching engine | Signals | Highlights |
|---|---|---|---|
dsacheck.py |
TF-IDF + cosine (std-lib only) | semantic (TF-IDF), domain, lexical | Zero dependencies — a pure-math baseline |
dsacheck_semantic.py |
Transformer embeddings | semantic, domain, lexical, priority | The flagship — meaning-based search |
dsacheck_final.py |
Transformer embeddings everywhere | semantic + precomputed concept embeddings (>0.3 thresholds), cached queries | Fastest of the three, embedding-driven domain layer |
The semantic version is the recommended entry point: it captures the qualitative jump from term-matching to transformer embeddings without the extra precomputation complexity of final. The deprecated lineage is worth a look to understand the design progression.
Being honest about real-world edge cases:
- Scores can exceed 1.0 — the
+0.10priority boost makes the scale semi-normalized (documented above in the scoring section). - Legacy Windows consoles mangle Unicode — the source answers contain superscripts like
O(n²); on an oldcmdcodepage these can print asO(n�). Use Windows Terminal or setPYTHONIOENCODING=utf-8. - Leftover Markdown markers in some answers — the
bigpictureparser captures bullet text verbatim, so a few answers keep stray**bold markers (e.g.**Trie (Prefix Tree)** - …). Harmless cosmetically.
Everything lives under dsaprac/. Beyond the semantic advisor, the repo is a complete DSA study environment:
| Component | Purpose |
|---|---|
takeofftakeoff.py |
27 real-world DSA questions solved and optimized (Q1–Q27): O(n²)→O(n) reporting, AVL fraud detection, quadtree spatial index, Dijkstra, Kruskal, tries, backtracking… |
ready_to_use.py + example_data.py |
Pre-loaded demo object dsa with working functions and realistic datasets for every question |
sniper.py |
Q&A commentary + hand-written data structure implementations per question |
big_o_adviser.py, big_o_advisor_validator.py |
Heuristic Big-O advisor (ProblemSpec → recommended data structure/algorithm) with optional empirical big_o validation |
prospect.py, prospect_nocollections.py |
Additional implementations (one variant avoids the collections stdlib as an exercise) |
simple_test_runner.py, run_all_tests.py, test_data_generator.py |
Test harness with realistic generated data (customers, orders, trades, graphs, Sudoku boards…) |
dsacheck*.py |
The three generations of the semantic Q&A system |
bigpicture.md, qabank.md |
The 81-pair knowledge base (also the parser input) |
deprecated/README.md |
The previous README, archived |
- Python 3.10+ — dataclasses, typing, regex parsing
- sentence-transformers —
all-MiniLM-L6-v2embedding model - PyTorch — tensor backend for cosine similarity (
torchutil.cos_sim) - Standard library only elsewhere —
difflib,re,osfor parsing and lexical scoring
- Reranking & LLM synthesis — feed the top-3 into an LLM for a tailored explanation
- Interactive study loop — quiz mode that scores the user against the 81-question bank
- Confidence calibration — normalize scores to a clean 0–1 with better separation
- Caching — embed the query once per session (as
dsacheck_final.pyalready does) for even faster interactive typing
Part of the DSA learning repository — questions, implementations, Big-O analyses, and tests for 27 real-world problems plus a 54-question classic interview bank.