Design document-tag classes with concurrency safety
Overview
This question evaluates a candidate's ability to design in-memory class interfaces and indices for a document–tag manager, specify duplicate handling and normalization policies, and extend the design with concurrency control while reasoning about time and space complexity.
System Design: In‑Memory Document–Tag Manager (Single Node)
Context
You are designing an in-memory component that manages documents and tags. The component should expose a clear class interface, maintain efficient indices, and provide well-defined behavior regarding duplicates and normalization (e.g., case sensitivity). Later, extend the design to support safe concurrent reads and writes.
Assume documents and tags are small (e.g., IDs/strings and lightweight metadata), and the system runs on a single node process. Persistence, sharding, and distributed coordination are out of scope.
Requirements
-
Core operations
- Create/Delete document
- Create/Delete tag
- Add/Remove a tag on a document
- List all documents for a given tag
- List all tags for a given document
- Query documents by intersection of multiple tags (logical AND)
-
Deliverables
- Class interfaces (public API) and core internal data structures/indices
- Duplicate handling and normalization policy (e.g., case sensitivity for tags)
- Time and space complexity of key operations
-
Concurrency extension (same API, multi-threaded use)
- Concurrency control strategy (locking granularity, immutable/COW structures, or concurrent maps)
- Consistency guarantees for readers/writers
- Deadlock avoidance strategy
- Approaches to testing concurrency correctness
Solution
Login required