Category Archives: algorithm
lc960. Delete Columns to Make Sorted III
https://leetcode.com/problems/delete-columns-to-make-sorted-iii/ 1. Naive way O(n^2) to calculate longest subsequence dp[i] is the longest subsequence ending with i position. if charAt(j) <= charAt(i), then dp[i] = max(dp[i], dp[j] + 1) 2. Only cares about column i, column j, where all chartAt(j) <= charAt(i), then we update dp[i] public static int minDeletionSize(String[] A) { int[] dp =… Read More »
@JsonIgnoreProperties
@JsonIgnoreProperties is used in jackson deserialization. When a json file is deserialized to a class, it is ok that field is missing. For example, we have class A: @Data @Builder @NoArgsConstructor @AllArgsConstructor public class A { @JsonProperty int a; @JsonProperty int b; } It is ok to deserialize {“a”:1}, which misses field b. But it… Read More »
lc 654 Maximum Binary Tree
We are given the root node of a maximum tree: a tree where every node has a value greater than any other value in its subtree. Just as in the previous problem, the given tree was constructed from an list A (root = Construct(A)) recursively with the following Construct(A) routine: If A is empty, return null. Otherwise, let A[i] be the largest element of A. Create a root node with value A[i]. The left… Read More »
Local/Instance/Class variable
Local variable, variable defined inside method, constructor or block. Instance variable, a variable inside class. It can be instantiated. Class variable, inside class, but outside method. Must be static. Only one copy per class. public class MyTest { static String str = “abcd”; // classs variable, only one copy private String a = “123”; //… Read More »
Vector Clock better than Lamport Clock
Lamport clock. Algorithms: ts = max(local stamp, msg timestamp) + 1. Problem, “So Lamport Clocks are great for making sure we know when there’s a causal dependency between records. But there is a problem. Because Lamport Clocks induce a total ordering over all records, they actually imply more dependencies than truly exist. If two records… Read More »
synchronized and synchronized static
Below are 2 code snippets. doSomething() in first one is synchronized. doSomething() in second one is synchronized static. For synchronized: When calling doSomething() within 2 different instances at the same time, it can be concurrent. When calling doSomething() within same instance at the same tim, it can’t be concurrent. For synchronized static: When calling doSomething()… Read More »
Performance Test
When talking about the performance of a web service, it is intended to think about 2 metrics. 1. TPS 2. Latency 3. TP50, TP90, TP99 etc. single thread test for base line. One thread tests for a period of time. This tests the ideal response latency. Find the peak TPS Test the web service TPS… Read More »
TLS, HTTPS
SSL/TLS are the protocols that aim to provide privacy and data integrity between two parties. HTTPS is HTTP protocols over SSL or TLS protocols. It requires the SSL/TLS establish first, then HTTP is exchanged over SSL/TLS protocols. In TLS, Certificate contains the public key that server sends out. Publish key will be used to encrypt… Read More »
Jump Game II
Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Your goal is to reach the last index in the minimum number of jumps. For example: Given array A = [2,3,1,1,4] The minimum number of… Read More »