很久以前打ACM的时候学过这个算法，但到用的时候还是忘了，起因是来源于这样一个问题:

给定任意一个矩阵 $nXn$, 选取其中 $n$ 个点，$s.t.$ 任意两个点 不在同一行，同一列，求这 $n$ 个点的和的最大值.

这个问题可以很简单的转化为 最大流，或者最大权匹配问题来求解。

可是难受的是这两个算法都忘了，不会敲，所以又重新拿起遗忘的知识， …

这是笔者学习 Stanford cs 168 课程的一些学习笔记 lecture 2, 主要讲一个基于 hash 和独立试验思想，设计的一种数据结构 count min sketch，想法非常类似于 bloom filter，都是以牺牲准确率换空间和时间。

heavy hitter problem

Find majority element

先来看 …

记得我人生第一次参加bytedance 的面试的时候，面试官问我的就是这样一个问题: 你有很多台服务器，每台服务器上都存放着很多数据，现在要加一台服务器，如何才能让数据搬迁尽可能的少，同时能让每台服务器经可能的负载均衡。现在才发现，这就是可一致性hash 问题，当时我答了个hashMap中的rehash操作，给糊弄过去了….

具体的内容可 …

这是 MIT 6.824 课程 lab1 的学习总结，记录我在学习过程中的收获和踩的坑。

我的实验环境是 windows 10，所以对lab的code 做了一些环境上的修改，如果你仅仅对code 感兴趣，请移步 : github/zouzhitao

mapreduce overview

先大致看一下 mapreduce 到底是什么

我个人的简 …

题目链接

A. Training

这题很简单，处理一下前缀和就完事儿，没什么好说的。当时就做出了这个题 :(

code

github

B. parcel

这题还是很有意思的，正式赛没做出来，其实第一问暴力很容易求，不过 作为一名 ACMer，有一种惯性会忽略掉这种方式…，下次一定要补上了。

题解可以参考官方题解

我这里就是将题解 …

本文主要总结Scala中关于generic variance(泛型变化， 我也不知道该怎么翻译，以下称 GV),(co-,contra-,in)variance in Scala 的相关知识，什么是 generic variance 呢？我的感觉是一种泛型类型的类型系统，应该和 type system 比较相关，(PL专家就不要嘲笑我了)。比如: …

这篇文章主要总结 PAC 学习框架以及样本复杂度相关的东西，大致来说就是:要保证以概率 $1-\delta$ 使得 generalized error 小于 $\epsilon$ 需要多大的样本复杂度，以及时间复杂度才是好的。

问题及约定

符号约定

两个 error 符号

就是我们常说的 train error 与 true …

纸上得来终觉浅，觉知此事要躬行。综上，我什莫都不懂.这仅仅是个人的学习防忘笔记

Adaboost

关于 Adaboost 的算法描述其实很简单，有趣的是的它的误差分析:

algorithm

其中

$$ \begin{align} \epsilon_t &= Pr_{i\sim D_t}[h_t(x_i)\ne y_i]\\ …

题目链接

google kickstart 2018 Scrambled Words

分析

分析在题目网站有，首先需要想到的就是不同串的长度只有 $O(\sqrt{\sum words_i})$ 种，那么枚举所有长度肯定是一种可行的方法，不过呢，即使枚举长度，对于每个枚举到的字串，我们仍然需要将他和所有具有此长度的串比较，太过浪费时间了，怎么做才能加速 …

本文来源于个人的凸优化学习笔记参考cs229 cvxoptnote,写成笔记的原因仅仅是想通过个人的笔记自己讲述与推导一下这些数学公式，内容可能会很简单，强力建议想得到一手资料的人好好学习文末参考资料

凸集合

定义就直接跳过了，这里简单写一些常见的凸集

• 凸集的交, 设 $C_i,i = 1,2,3,…,n$ 是凸集，那么我们 …