Category Archives: algorithm

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 »

First Missing Number

leetcode 41. Given an unsorted integer array, find the first missing positive integer. For example, Given [1,2,0] return 3, and [3,4,-1,1] return 2. Your algorithm should run in O(n) time and uses constant space. Solution. I learned the solution from here. The idea is try as much as possible to rearrange array like [1, 2,… Read More »

Sudoku

I came across the sudoku problem in leetcode 37. Here I wrote a page javascript version to solve this problem. Check my code on github.

Bulls and Cows

leetcode 299. You are playing the following Bulls and Cows game with your friend: You write down a number and ask your friend to guess what the number is. Each time your friend makes a guess, you provide a hint that indicates how many digits in said guess match your secret number exactly in both… Read More »

Metric for bloom filter

Assume totally has 1M record. We want test is 1% wrong rate. 7 hash functions. In this way, it totally need around 1.14MB bits for the bloom filter. Bloom filter block those which doesn’t exist. For those bloom filter think the value exist, there is 1% chance wrong. Refer bloom filter calculator. http://hur.st/bloomfilter?n=1000000&p=0.01