concurrency

Goal To understand skiplist. Definition Skiplist is a dynamic search structure, as it is dynamic when it comes to insertion and deletion, which supports search). Other dynamic search structure: Treaps Red black tree B-Trees (2-3 trees etc) Operations on skiplist Search - O(log n) Insert - O(log n) Delete - O(log n) These operations are with high probability, 1/polynomial depending on polynomial number of operation. [Read More]

Problem Implement the LRU cache Solution Least Recently Used (LRU) Cache is to discard the least recently used items first How do you design and implement such a cache class? The design requirements are as follows: find the item as fast as we can Once a cache misses and a cache is full, we need to replace the least recently used item as fast as possible. We use two data structures to implement an LRU Cache : [Read More]