这篇博文简单总结一下局部敏感性hash(locality-sensetive-hash,LSH) 在找相似元素中的应用，这也是最近邻的另外一种解决方案

LSH 的直觉非常简单，设想一下我们判断一个集合 $set$ 中是否存在一个元素 $e$ 的方法，通常是将集合中的所有元素hash到一个一个的桶中，同时将 $e$ hash到桶中，如果存在， …

关于维度爆炸的问题，历来探讨的都很广泛。存在于很多真实的问题中，比如 nearest neighbor，最近邻问题，这里总结一种简单的技术，叫做随机投影(random projection)

最近邻问题的简单描述如下:

给定 $k$ 维空间 $R^k$ 中的 $n$ 个点 $x_1,x_2,\dots ,x_n$,找到每个点的最近邻居 $NN_i = …

这是cs276 information retrieval & web search的笔记2，这里总结关于IR 系统中，rank的一些概率模型，BIM，BM25

introduction

IR系统的核心就是ranking，也就是非常直观的任务，对于user的一个query $q$, IR系统希望给每个检索出来的文档一个分数 score，按 …

建立索引是 information retrieval 的一个核心问题，这一节简单记录关于index的相关笔记. 所有内容均来自 stanford cs276 information retrieval & web search

text preprocessing

一些术语

1. tokenization
   1. 将文本编程token流， …

简单总结一下SVM，以帮助ML相关面试

SVM 是一种上古时代(90s) 的东西，其实我也不清楚他在工业界的用处到底几何。只是感觉算法特别慢，还意义不太大。

intuition

首先SVM的动机其实很简单。我们都知道对于分类问题(这里以二分类为例)，就是要找一个超平面将正例和负例分开，而SVM找的这个超平面相对比较特殊，他希望找到一个超平面，s.t …

A. Cherries Mesh

easy

code : github

B. Code-Eat Switcher

这题结束后想通了，可以贪心，将 $(c_i,e_i)$ 按照 $c_i / e_i$ 排序，然后贪心.

codegithub

C. Street Checkers

这题还是很容易的，

首先翻译一下题意，对于一个数 $X$, 如果它 …

这要是对以下几种在c++里的 for-range-loop做一个总结

1. for(auto e : container)
2. for(auto &e : container)
3. for(const auto &e : container)
4. for(auto && e : container)

这里主要是参考 ref [1] …

整体来说这次的题不是很难，我都能自己想出来，并写完，但是这次马力有点大，C题写了2hrs…

A.X or What?

这题比较简单，重点在一个 xor的性质，与位的异或次序无关即两数$A,B$ 共 $K$ 位

$$ \bigwedge_i A_i \wedge B_i = (\bigwedge_i A_i)\wedge …

A. Wiggle Walk

难度 模拟，编码，hashtable

这个题比较简单，可以直接模拟，用一个 hashtable 维护 dp[x][y][dir] [注意这里不是开数组]， 因为只有 $N \le 5e4$ 个点所以用hashtable维护就好，复杂度 $O(n)$

code : github

B. Circuit Board …

A. Building Palindromes

easy

code : https://github.com/zouzhitao/competitive-programing/blob/master/kick-start/2019-B-A.cpp

B. Energy Stones

knapstack 变种.

题意

$n$ 块石头，每块石头有 3 …