## Online Judge from Scratch(1) – Frontend

The frontend of Justice contains two sites: the web UI for users and the admin panel for administrators, the main reason to choose Yii2 is the Advanced Application Template provides both succinct project structure and great convenience to share the same logic between the two sites: Besides, we improved Yii2’s MVC pattern by adding an … Continue reading "Online Judge from Scratch(1) – Frontend"

## 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"

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"

## [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"

## [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"

## 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"

## [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)"

## Solutions of Longest Palindromic Substring

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

## 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）"

## online judge sandbox 设计思路（1）

This article is deprecated, please see here for more details. 实现 OJ 的 sandbox 主要有两种思路：ptrace 和 seccomp，下面我们分别讨论。 ptrace() ptrace 是类 Unix 系统上一个可以观察、控制其他进程内部状态的工具。它的用途有很多，例如程序调试（gdb、dbx等）、代码覆盖率检测、甚至可以用来做运行时补丁（想没想起来IDA和OllyDbg ）。今天我们讨论的是如何通过对系统调用的限制来达到在沙箱(sandbox)中运行程序的效果。 我们先写一个程序，用来删除 /etc/hosts 文件： a.out 完成了它的使命，成功的删除了 hosts 文件。 现在，我们需要设计一个程序：通过 ptrace() 来限制 unlink() 删除文件系统中的文件。 首先，我们来看下手册上是怎么介绍 ptrace() 的： 其中，request 参数决定了 ptrace() 的行为，我们选几个用得到的选项介绍： PTRACE_TRACEME: 表明子进程(tracee)正在被父进程(tracer)所控制。注意：只有本选项适用于子进程（tracee）； PTRACE_PEEKUSER: 可以从子进程中获取通用寄存器中的值，寄存器(orig_rax /orig_eax，取决于平台 )中保存的是最近一次的syscall number； PTRACE_SYSCALL: 可以将子进程从停止的状态唤醒并继续； 这样，我们就有思路了：每次程序调用系统调用，我们都去看看本次系统调用是不是 unlink()，如果是，杀掉子进程并退出即可： 当系统调用发生时，内核会把当前的 %eax/%rax … Continue reading "online judge sandbox 设计思路（1）"