An Odyssey of Testing in Go
Why bother writing tests at all? It’s all about moving fast without breaking anything. This is a brief overview of the work we did on testing over the past half year in our team. With the help of CI, we significantly reduced the number of bugs and sped up the delivery of new features as we … Continue reading "An Odyssey of Testing in Go"
Read MoreParse thrift in Go: the Antlr Way
thrift2interface is a small project I developed for auto generating go interfaces from thrift by Antlr4. This could be easily done by following the steps in Parsing with ANTLR 4 and Go with some extra efforts: Grammar The struct definition from the canonical Thrift.g4 may cause exceptions when generating Golang runtimes, this can be fixed … Continue reading "Parse thrift in Go: the Antlr Way"
Read MoreTransactions in Microservices
Programming Paradigm
Polynomial Multiplication
Given two polynomials and of degree-bound : Multiply and , we get the product with coefficients: Here is also called the Convolution of and (denoted ). If we calculate by multiplying each term in by each term in and then combining terms with equal powers (exactly the old way we learnt in the junior high school), the time complexity would … Continue reading "Polynomial Multiplication"
Read More[Algorithm 101] Shortest Path Problem
In graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized. Dijkstra’s algorithm For a given vertex called the source in a weighted connected graph, Dijkstra’s Algorithm can find the shortest paths to all the graph’s other vertices. This algorithm is applicable to both undirected … Continue reading "[Algorithm 101] Shortest Path Problem"
Read MoreOperational Transformation
Back to I was in a startup company two years ago, we were going to develop an online video chatroom over WebRTC with a collaborative real-time editor to share codes or thoughts for online interviews. Starting to build the editor from scratch seemed quite challenging for us at that time, so we chose etherpad-lite, an … Continue reading "Operational Transformation"
Read MoreMatrix Multiplication: A Programmer’s Perspective
The problem find the nth fibonacci number(A000045) has an optimal solution: matrix multiplication. Similarly, the matrix representation of sequence An = An-1 + An-2 + An-3 (A000073) is: By using matrix multiplication, we can reduce the time complexity from O(n) to O(logn). In linear algebra textbooks, matrix multiplication is the composition of two linear functions. Suppose: Represent … Continue reading "Matrix Multiplication: A Programmer’s Perspective"
Read MoreOnline Judge from Scratch(3) – Sandbox
This article consists of two parts: the sandbox for GCC and the sandbox for the compiled binary. the sandbox for GCC Essentially, our sandbox for GCC is a wrapper of GCC with a watchdog, just like the sandbox we designed for the Java compiler. However, there are more situations need to be considered carefully for GCC. In … Continue reading "Online Judge from Scratch(3) – Sandbox"
Read MoreOnline Judge from Scratch(2) – Dispatcher
The dispatcher, as the name implies, fetches judge tasks from RabbitMQ, dispatches them to the sandbox workers and gets the results back synchronously. In Justice, the sandboxes are language-specific: If the submission is written in Java, we can sandbox it with Java Security Manager. If the submission is written in C/CPP, we need another sandbox … Continue reading "Online Judge from Scratch(2) – Dispatcher"
Read More