Monday, July 10, 2017

Mini Memcache



https://github.com/zxqiu/leetcode-lintcode/blob/master/system%20design/Memcache.java
Implement a memcache which support the following features:
get(curtTime, key). Get the key's value, return 2147483647 if key does not exist.
set(curtTime, key, value, ttl). Set the key-value pair in memcache with a time to live (ttl). The key will be valid from curtTime to curtTime + ttl - 1 and it will be expired after ttl seconds. if ttl is 0, the key lives forever until out of memory.
delete(curtTime, key). Delete the key.
incr(curtTime, key, delta). Increase the key's value by delta return the new value. Return 2147483647 if key does not exist.
decr(curtTime, key, delta). Decrease the key's value by delta return the new value. Return 2147483647 if key does not exist.
It's guaranteed that the input is given with increasingcurtTime.
Clarification
Actually, a real memcache server will evict keys if memory is not sufficient, and it also supports variety of value types like string and integer. In our case, let's make it simple, we can assume that we have enough memory and all of the values are integers.
Search "LRU" & "LFU" on google to get more information about how memcache evict data.
Try the following problem to learn LRU cache:
http://www.lintcode.com/problem/lru-cache
Example
get(1, 0)
>> 2147483647
set(2, 1, 1, 2)
get(3, 1)
>> 1
get(4, 1)
>> 2147483647
incr(5, 1, 1)
>> 2147483647
set(6, 1, 3, 0)
incr(7, 1, 1)
>> 4
decr(8, 1, 1)
>> 3
get(9, 1)
>> 3
delete(10, 1)
get(11, 1)
>> 2147483647
incr(12, 1, 1)
>> 2147483647
*/


public class Memcache {
    private class Data {
        int value;
        int ttl;
        int editTime;
       
        public Data(int value, int ttl, int editTime) {
            this.value = value;
            this.ttl = ttl;
            this.editTime = editTime;
        }
    }
   
    HashMap<Integer, Data> cache;

    public Memcache() {
        cache = new HashMap<Integer, Data>();
    }

    public int get(int curtTime, int key) {
        int value = 2147483647;
        if (!cache.containsKey(key)) {
            return value;
        }
       
        Data data = cache.get(key);
        if (data.ttl == 0 || data.ttl + data.editTime - 1 >= curtTime) {
            value = data.value;
        }
       
        return value;
    }

    public void set(int curtTime, int key, int value, int ttl) {
        Data data = new Data(value, ttl, curtTime);
        cache.put(key, data);
    }

    public void delete(int curtTime, int key) {
        if (cache.containsKey(key)) {
            cache.remove(key);
        }
    }
   
    public int incr(int curtTime, int key, int delta) {
        int value = 2147483647;
        if (!cache.containsKey(key)) {
            return value;
        }
       
        Data data = cache.get(key);
        if (data.ttl == 0 || data.ttl + data.editTime - 1 >= curtTime) {
            data.value += delta;
            value = data.value;
            cache.put(key, data);
        } else {
            cache.remove(key);
        }
       
        return value;
    }

    public int decr(int curtTime, int key, int delta) {
        int value = 2147483647;
        if (!cache.containsKey(key)) {
            return value;
        }
       
        Data data = cache.get(key);
        if (data.ttl == 0 || data.ttl + data.editTime - 1 >= curtTime) {
            data.value -= delta;
            value = data.value;
            cache.put(key, data);
        } else {
            cache.remove(key);
        }
       
        return value;
    }

Labels

Review (572) System Design (334) System Design - Review (198) Java (189) Coding (75) Interview-System Design (65) Interview (63) Book Notes (59) Coding - Review (59) to-do (45) Linux (43) Knowledge (39) Interview-Java (35) Knowledge - Review (32) Database (31) Design Patterns (31) Big Data (29) Product Architecture (28) MultiThread (27) Soft Skills (27) Concurrency (26) Cracking Code Interview (26) Miscs (25) Distributed (24) OOD Design (24) Google (23) Career (22) Interview - Review (21) Java - Code (21) Operating System (21) Interview Q&A (20) System Design - Practice (20) Tips (19) Algorithm (17) Company - Facebook (17) Security (17) How to Ace Interview (16) Brain Teaser (14) Linux - Shell (14) Redis (14) Testing (14) Tools (14) Code Quality (13) Search (13) Spark (13) Spring (13) Company - LinkedIn (12) How to (12) Interview-Database (12) Interview-Operating System (12) Solr (12) Architecture Principles (11) Resource (10) Amazon (9) Cache (9) Git (9) Interview - MultiThread (9) Scalability (9) Trouble Shooting (9) Web Dev (9) Architecture Model (8) Better Programmer (8) Cassandra (8) Company - Uber (8) Java67 (8) Math (8) OO Design principles (8) SOLID (8) Design (7) Interview Corner (7) JVM (7) Java Basics (7) Kafka (7) Mac (7) Machine Learning (7) NoSQL (7) C++ (6) Chrome (6) File System (6) Highscalability (6) How to Better (6) Network (6) Restful (6) CareerCup (5) Code Review (5) Hash (5) How to Interview (5) JDK Source Code (5) JavaScript (5) Leetcode (5) Must Known (5) Python (5)

Popular Posts