Idempotent Request Replay

Medium Hashing / Caching 3 parts 170 lines View on GitHub ↗

Question

Topic: Hashing / Caching · Difficulty: Medium

Requests arrive in order, each with an optional idempotency key and a value (the response it would produce). Return the response sent for every request.

Part 1: replay by key

No key → process it and return its own value.
First time a key is seen → process it and remember the response.
Key seen before → return the stored response (a replay), not the new value.

Part 2: keys expire

Each request also has a timestamp, and stored keys expire after ttl. A request after storedTime + ttl is processed fresh and replaces the stored response.

Part 3: conflicting retries

Within the TTL, a request with the same key but a different value is a client error: return -1. The same value is a normal retry.

Approach: HashMap<key, (response, expiresAt)>, checked on every request.

IdempotentReplayPart1.java 37 lines GitHub ↗

/**
 * Problem: Idempotent Request Replay
 * Difficulty: Medium
 * Topic: Hashing / Caching
 * Question: Replay stored responses for repeated idempotency keys, then with key expiry (TTL), then rejecting conflicting retries. Full statement in README.md.
 */
package dsa.question3;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class IdempotentReplayPart1 {

    static class Request {
        String key;
        int value;
        public Request(String key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    public static List<Integer> inputRequest(List<Request> input) {
        HashMap<String , Integer> requestedKey = new HashMap<>();
        List<Integer> output = new ArrayList<>();
        for(int i=0; i<input.size(); i++) {
            String key = input.get(i).key;
            int value = input.get(i).value;
            if(key == null || key.equals("")) {
                output.add(value);
            }else if(requestedKey.containsKey(key)) {
                output.add(requestedKey.get(key));
            }else{
                output.add(value);
                requestedKey.put(key, value);
            }
        }
        return output;
    }
}

IdempotentReplayPart2.java 48 lines GitHub ↗

package dsa.question3;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class IdempotentReplayPart2 {

    static class Request {
        String key;
        int value;
        long time;
        public Request(String key, int value, long time) {
            this.key = key;
            this.value = value;
            this.time = time;
        }
    }

    static class Pair{
        int value;
        long expireTime;
        public Pair(int value, long expireTime) {
            this.value = value;
            this.expireTime = expireTime;
        }
    }

    public static List<Integer> inputRequest(List<Request> processRequest, long ttl) {
        HashMap<String , Pair> store = new HashMap<>();
        List<Integer> output = new ArrayList<>();
        for(int i=0; i<processRequest.size(); i++) {

            String key = processRequest.get(i).key;
            int value = processRequest.get(i).value;
            long time = processRequest.get(i).time;

            if(key == null || key.isEmpty()){
                output.add(value);
            } else if(store.containsKey(key)) {
                Pair lastValue = store.get(key);
                if(time > lastValue.expireTime) {
                    output.add(value);
                    store.put(key , new Pair(value, time+ttl));
                }else{
                    output.add(lastValue.value);
                }

            }else {
                output.add(value);
                store.put(key , new Pair(value, time+ttl));
            }
        }
        return output;
    }
}

IdempotentReplayPart3.java 50 lines GitHub ↗

package dsa.question3;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class IdempotentReplayPart3 {
    static class Request {
        String key;
        int value;
        long time;
        public Request(String key, int value, long time) {
            this.key = key;
            this.value = value;
            this.time = time;
        }
    }

    static class Pair{
        int value;
        long expireTime;
        public Pair(int value, long expireTime) {
            this.value = value;
            this.expireTime = expireTime;
        }
    }

    public static List<Integer> inputRequest(List<Request> processRequest, long ttl) {
        HashMap<String , Pair> store = new HashMap<>();
        List<Integer> output = new ArrayList<>();
        for(int i=0; i<processRequest.size(); i++) {

            String key = processRequest.get(i).key;
            int value = processRequest.get(i).value;
            long time = processRequest.get(i).time;

            if(key == null || key.isEmpty()){
                output.add(value);
            } else if(store.containsKey(key)) {
                Pair lastValue = store.get(key);
                if(time > lastValue.expireTime) {
                    output.add(value);
                    store.put(key , new Pair(value, time+ttl));
                }else if(lastValue.value != value){
                    output.add(-1);
                } else{
                    output.add(value);
                }

            }else {
                output.add(value);
                store.put(key , new Pair(value, time+ttl));
            }
        }
        return output;
    }
}

Demo.java 35 lines GitHub ↗

package dsa.question3;

import java.util.ArrayList;
import java.util.List;

public class Demo {

    public static void main(String args[]) {
//        IdempotentReplayPart1.Request request1 = new IdempotentReplayPart1.Request("abc" , 200);
//        IdempotentReplayPart1.Request request2 = new IdempotentReplayPart1.Request("adc" , 200);
//        IdempotentReplayPart1.Request request3 = new IdempotentReplayPart1.Request("" , 500);
//        IdempotentReplayPart1.Request request4 = new IdempotentReplayPart1.Request("" , 800);
//        IdempotentReplayPart1.Request request5 = new IdempotentReplayPart1.Request("abc" , 800);
//
//        List<IdempotentReplayPart1.Request> input = new ArrayList<>();
//        input.add(request1);
//        input.add(request2);
//        input.add(request3);
//        input.add(request4);
//        input.add(request5);
//
//        List<Integer> output = IdempotentReplayPart1.inputRequest(input);
//        System.out.println(output);

        IdempotentReplayPart2.Request request1 = new IdempotentReplayPart2.Request("key_a" , 1000, 1000);
        IdempotentReplayPart2.Request request2 = new IdempotentReplayPart2.Request("key_a" , 2000, 2000);
        IdempotentReplayPart2.Request request3 = new IdempotentReplayPart2.Request("key_a" , 3000, 5000);
        IdempotentReplayPart2.Request request4 = new IdempotentReplayPart2.Request("key_a" , 4000, 6000);
        IdempotentReplayPart2.Request request5 = new IdempotentReplayPart2.Request("" , 8000, 4000);

        List<IdempotentReplayPart2.Request> input = new ArrayList<>();
        input.add(request1);
        input.add(request2);
        input.add(request3);
        input.add(request4);
        input.add(request5);

        List<Integer> output = IdempotentReplayPart2.inputRequest(input, 3600);
        System.out.println(output);

    }
}