Monthly Archives: August 2020

For example, each pair is labeled as [l1, r1]. Because the pairs sequence is ordered by r. So, we can just iterate it. For current pair, if the l is overlapped with previous pair, then don’t consider it. This is a greedy strategy.

dp[i][j] is the result between stone i, and stone j.

If left is greater, then

dp[from][from+delta] = sum(i, from+delta) + dp[i][from+delta]

Else

right part

If both left and right are same, then choose the one which dp has larger value

There are actually 2 types of OPs. One is to make all digit multiplying by 2, this can be shared by all numbers together. Another is adding one. This can’t be shared. So result would be count how many one digit, plus the highest bit count.

Solution 1, just like frog jump.

public static int minDays(int n) {
    int[] dp = new int[n + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    for (int i = 0; i <= n; i++) {
        if (i * 2 <= n) {
            dp[i * 2] = Math.min(dp[i * 2], dp[i] + 1);
        }
        if (i * 3 <= n) {
            dp[i * 3] = Math.min(dp[i * 3], dp[i] + 1);
        }
        if (i + 1 <= n) {
            dp[i + 1] = Math.min(dp[i + 1], dp[i] + 1);
        }
    }
    return dp[n];
}

Solution 2, don’t consider 1 step away. Only consider n%2, and n%3. Greedy.

public static int minDays(int n) {
    Map<Integer, Integer> dp = new HashMap();
    return helper(n, dp);
}

private static int helper(int n, Map<Integer, Integer> dp) {
    if (n <= 2) {
        return n;
    }
    if (dp.containsKey(n)) {
        return dp.get(n);
    }
    int ans = 1 + Math.min(n % 2 + helper(n / 2, dp), n % 3 + helper(n / 3, dp));
    dp.put(n, ans);
    return ans;
}

After testing with GoReplay, it shows that GoReplay will change the traffic pattern. When setting a fix RPS rate traffic, GoReplay will just replay the traffic with fix RPS. For some caching use case, this may fail. Let’s say request 1, 2, 3, 4 are all same. We want to cache for request 1, then cache for 2, 3, 4 will hit. This cache hit will work on the replayed traffic, but not real traffic.