## Online Judge from Scratch(0) – Architecture

An online judge system(like codeforces, leetcode, etc) contains a problem set of algorithms to solve, while users can compile a piece of code and execute the generated binary with pre-constructed data to test if the code is correct. However details of algorithms won’t be discussed here, we mainly focus on how to build an online judge … Continue reading "Online Judge from Scratch(0) – Architecture"

Read More## Convex Hull

We start with the definition of a convex set: in convex geometry, a convex set is a subset of an affine space that is closed under convex combinations. More specifically, in Euclidean spaces, a convex region is a region where, for every pair of points within the region, every point on the straight line segment … Continue reading "Convex Hull"

Read More## Advanced Redis Use Cases

Active users of a web application Here we need to clarify what is an “active user” first: an active user is a logged-in user which has interactions with a web application recently. Web applications using http(s) protocal are stateless, so here “recently” has to be estimated and inaccurate: e.g., if we reckon a user is … Continue reading "Advanced Redis Use Cases"

Read More## Debug yii2 project with XDebug and PHPStorm

add Xdebug for PHP docs of adding Xdebug for PHP can be found here, and then add the following config section to php.ini: and make sure that Xdebug is enabled by checking phpinfo(): add local PHP interpreter setting add PHP server setting update Xdebug setting add PHPStorm Run/Debug configuration add … Continue reading "Debug yii2 project with XDebug and PHPStorm"

Read More## [Algorithm 101] Unbounded Knapsack Problem

We started this problem with Project Euler #31 Coin Sums: In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation: 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p). It is possible to make £2 in the following way: 1×£1 + 1×50p … Continue reading "[Algorithm 101] Unbounded Knapsack Problem"

Read More## [Algorithm 101] 0-1 Knapsack Problem

We start this problem with leetcode #494: Target Sum: You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol. Find out how many ways to assign … Continue reading "[Algorithm 101] 0-1 Knapsack Problem"

Read More## Higher-order functions in Javascript

In Javascript, functions are just like the other variables(AKA first-class citizen), and here are several interesting tricks implemented by treating functions as first-class citizen. currying Currying is for partial evaluation, a practical example is Function.prototype.bind() in Javascript: And we can implement bind()(under this circumstance only of course) by ourselves: trampolining Javascript(ES5) does not implement tail call optimization, … Continue reading "Higher-order functions in Javascript"

Read More## [Algorithm 101] Bit Manipulation: Count Bits of Integer (Hamming weight)

Function int bitCount(int n) returns how many “1”s does the number n have expressed in the binary form. For example, 0b101 is the binary form of number 5, so bitCount(5) returns 2. the naive way Check if each bit equals 1 and return the sum: the optimized naive way Consider the number 0b1. After the first right shift, 31 … Continue reading "[Algorithm 101] Bit Manipulation: Count Bits of Integer (Hamming weight)"

Read More## Solutions of Longest Palindromic Substring

suffix tree normal manacher’s algorithm DP Reference: leetcode articles (Mandarin Chinese) Manacher’s ALGORITHM: O(n)时间求字符串的最长回文子串

Read More## online judge sandbox 设计思路（2）

This article is deprecated, please see here for more details. seccomp() seccomp 是 Linux 内核提供的一种应用程序沙箱机制，seccomp 通过只允许应用程序调用 exit(), sigreturn(), read() 和 write() 四种系统调用来达到沙箱的效果。如果应用程序调用了除了这四种之外的系统调用， kernel 会向进程发送 SIGKILL 信号。 seccomp 很难在实际中得到推广，因为限制实在是太多了，Linus 本人也对它的应用持怀疑的态度，直到出现了 seccomp-bpf。seccomp-bpf 是 seccomp 的一个扩展，它可以通过配置来允许应用程序调用其他的系统调用。chrome 中第一个应用 seccomp-bpf 的场景是把 Flash 放到了沙箱里运行（实在是不放心），后续也把 render 的过程放到了沙箱里。 我们仍然先通过限制 unlink() 来看一下 seccomp 是如何工作的： 删除失败了。 下面，我们写一个程序 b.out，让 seccomp 允许调用 unlink() ，但是不允许调用 fork()： 编译运行下： 我们的目的达到了。 seccomp-nurse … Continue reading "online judge sandbox 设计思路（2）"

Read More