Viewed
Coding
Google
Gemini 2.5 Flash
VS
OpenAI
GPT-5.2
Implement a Lock-Free Concurrent Skip List with Range Queries
Design and implement a concurrent skip list data structure in a language of your choice (C++, Java, Rust, Go, or Python) that supports the following operations:
1. **insert(key, value)** – Insert a key-value pair. If the key already exists, update the value atomically. Returns true if a new key was inserted, false if updated.
2. **remove(key)** – Logically delete the key-value pair. Returns true if the key was found and removed, false otherwise.
3. **find(key)** – Return the value associated with the key, or indicate absence.
4. **range_query(low, high)** – Return all key-value pairs where low <= key <= high, as a list sorted by key. The result must be a consistent snapshot: it should not include keys that were never simultaneously present during the operation's execution.
5. **size()** – Return the approximate number of active (non-deleted) elements.
Requirements and constraints:
- The skip list must be safe for concurrent use by multiple threads performing any mix of the above operations simultaneously, without a single global lock. You may use fine-grained locking, lock-free techniques (CAS), or a combination.
- Lazy deletion is acceptable: nodes can be logically marked as deleted before physical removal.
- The probabilistic level generation should use a standard geometric distribution with p=0.5 and a maximum level of 32.
- Keys are 64-bit integers; values are strings.
- Include proper memory safety considerations. If using a language without garbage collection, explain or implement your reclamation strategy (e.g., epoch-based reclamation, hazard pointers).
Deliverables:
1. Complete, compilable/runnable source code with comments explaining your concurrency strategy.
2. A test or demonstration that launches multiple threads performing concurrent inserts, deletes, finds, and range queries, and validates correctness (e.g., no lost updates, no phantom reads in range queries, no crashes).
3. A brief analysis section (as comments or a docstring) discussing:
- The linearizability (or snapshot isolation) guarantees your implementation provides.
- The expected time complexity of each operation.
- Known limitations or potential ABA issues and how you address them.
Your solution will be evaluated on correctness under concurrency, code clarity, robustness of the concurrency strategy, quality of the range query snapshot mechanism, and thoroughness of the analysis.
