Lintcode 538. Memcache

Implement a memcache which support the following features:

1. get(curtTime, key). Get the key's value, return 2147483647 if key does not exist.
2. 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.
3. delete(curtTime, key). Delete the key.
4. incr(curtTime, key, delta). Increase the key's value by delta return the new value. Return 2147483647 if key does not exist.
5. 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.

Have you met this question in a real interview?  

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

Example1

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



Code (Java)

class Value {
    int value;
    int ttl;
    public Value(int value, int ttl) {
        this.value = value;
        this.ttl = ttl;
    }
}

public class Memcache {
    Map<Integer, Value> map;
    public Memcache() {
        // do intialization if necessary
        map = new HashMap<>();
    }

    /*
     * @param curtTime: An integer
     * @param key: An integer
     * @return: An integer
     */
    public int get(int curtTime, int key) {
        // write your code here
        if (!map.containsKey(key) || curtTime > map.get(key).ttl) {
            return Integer.MAX_VALUE;
        }

        return map.get(key).value;
    }

    /*
     * @param curtTime: An integer
     * @param key: An integer
     * @param value: An integer
     * @param ttl: An integer
     * @return: nothing
     */
    public void set(int curtTime, int key, int value, int ttl) {
        // write your code here
        int validUntil = ttl == 0 ? Integer.MAX_VALUE : curtTime + ttl - 1;
        map.put(key, new Value(value, validUntil));
    }

    /*
     * @param curtTime: An integer
     * @param key: An integer
     * @return: nothing
     */
    public void delete(int curtTime, int key) {
        // write your code here
        if (!map.containsKey(key)) {
            return;
        }

        map.remove(key);
    }

    /*
     * @param curtTime: An integer
     * @param key: An integer
     * @param delta: An integer
     * @return: An integer
     */
    public int incr(int curtTime, int key, int delta) {
        // write your code here
        if (!map.containsKey(key) || curtTime > map.get(key).ttl) {
            return Integer.MAX_VALUE;
        }

        Value v = map.get(key);
        v.value = v.value + delta;
        map.put(key, v);
        
        return v.value;
    }

    /*
     * @param curtTime: An integer
     * @param key: An integer
     * @param delta: An integer
     * @return: An integer
     */
    public int decr(int curtTime, int key, int delta) {
        // write your code here
        if (!map.containsKey(key) || curtTime > map.get(key).ttl) {
            return Integer.MAX_VALUE;
        }

        Value v = map.get(key);
        v.value = v.value - delta;
        map.put(key, v);
        
        return v.value;
    }
}