# Monthly Archives: August 2020

## lc1546 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.

## lc1563

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

## lc1558

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. ## lc1553

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;
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;
}```

## GoReplay traffic pattern change

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. 