Implement a CRDT-Based Counter
Last updated: April 5, 2025
Quick Overview
Implement a conflict-free replicated counter (G-Counter and PN-Counter) that supports increment, decrement, and merge operations across distributed replicas.
Canva
April 5, 202511
8
1,678 solved
Implement a conflict-free replicated counter (G-Counter and PN-Counter) that supports increment, decrement, and merge operations across distributed replicas.
CRDTs are fundamental to Canva's collaborative editing infrastructure. This question tests your understanding of distributed data structures and conflict resolution, which directly relates to how Canva maintains consistency across concurrent editors.
What the Interviewer Expects
- Implement a G-Counter (grow-only counter) with per-replica state
- Extend to a PN-Counter that supports both increment and decrement
- Implement a merge function that resolves concurrent updates without coordination
- Demonstrate understanding of the mathematical properties (commutativity, associativity, idempotency)
Key Topics to Cover
How to Approach This
- Clarify input constraints and edge cases before writing code.
- Walk through your approach verbally and confirm with the interviewer before coding.
- Start with a brute force solution, then optimize. Mention time and space complexity.
- Test your solution with examples, including edge cases like empty input or duplicates.
- Consider common patterns: sliding window, two pointers, hash map, BFS/DFS, dynamic programming.
Possible Follow-up Questions
- How would you implement a CRDT set (G-Set, OR-Set)?
- What are the trade-offs between state-based and operation-based CRDTs?
- How would you garbage-collect tombstones in a CRDT?
Sharpen Your Skills on Codemia
Practice similar problems with our interactive workspace, get AI feedback, and track your progress.
Practice DSA ProblemsSample Answer
Problem Analysis
In this problem, we need to implement a G-Counter and a PN-Counter, which are types of CRDTs that allow for distributed counting without conflicts. The G-Counter is a grow-only counter that can only i...
Approach
- G-Counter Implementation:
- Use a list or dictionary to maintain a count for each replica identified by a unique identifier (replica ID).
- The increment operation for a specific replica ...
Submit Your Answer
