Programming Exercises
Most of the exerices here are open ended in that one can spend days implement an advanced and efficient versions. However, the idea is these can be used as quick exercises for fun where you come up with a simplistic toy implementation. The solution code for most problems can be found at https://github.com/sharvanath/generalcsproblems. However, note that the solution codes have been written by me quickly and not been tested thoroughly.
- [LRUCache] Implement an in-memory fixed size cache of objects with LRU replacement policy that supports.
- Put(int key, value)
- Get(int key)
- [Memtable] Implement a serializable memtable which supports:
- Put(int key, int value)
- Get(int key)
- Flush to disk
- Read from disk
- [ReaderWriterLock] Implement reader writer lock that avoids starvation.
- [ResourceAllocator] Implement a resource allocator that supports allocating contiguous resources from a fixed size pool (much like malloc):
- int AllocateResources(int amount). Return the index of the first resource.
- void FreeResources(int index, int amount).
- [VersionedVector] Implement a fixed sized vector that supports snapshotting.
- void Set(int index, int value)
- void Get(int index)
- int TakeSnapshot. Returns the snapshot id.
- int Get(int index, int snapshot_id)
generalcsproblems 