参考博客

计组块忘光了呜呜呜。。。来复习一波。。

1. LRU

1.1. 原理

LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

I want to match those five numbers 3, 7, 8, 9, 87 through regular express.

  1Here is my thought:
  2
  3- match those four numbers `3 7 8 9` var `^[3|7|8|9]$`
  4- match number `87` var `^87$`
  5
  6Then combine them together, `(^[3|7|8|9]$|^87$)`. With some test, it seems correct. Is there any way to do that more …

转自：http://blog.csdn.net/v_july_v/article/details/6279498

第一部分、十道海量数据处理面试题

题意：定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数，要求时间复杂度为O(1)

思路：标题党去死一死好么。。。真是无趣。。。就是用两个栈封装成一个。。。一个栈s1正常搞。。。一个是辅助栈s2。。每次去存min(value,s2.top());

题意：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。

虽然说感觉这届学弟蛮厉害…不知道能不能拿到校内资格。。。

以及没有太多时间训练…

不过只要假期实习的地方。。。加班不是很多的话。。。

思路：

一个元素入队的时候直接插入到stack1中。。。

一个元素出队的时候。。。如果stack2不为空。。stack2顶的元素就是要出队的。。

如果stakc2为空。。。就将stack1清空，按照元素出栈的顺序依次入栈到stack2

思路：

分治搞之。

实际上两个vector就够了。。。4个会MLE(在leetcode上。。。

 1/**
 2 * Definition for binary tree
 3 * struct TreeNode {
 4 *     int val;
 5 *     TreeNode *left;
 6 *     TreeNode *right;
 7 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8 * };
 9 */
10class Solution {
11public:
12    TreeNode* res;
13    TreeNode* …

前言：

hash这种东西人人都会用的东西还有必要说？

起因是…本问了hash中的一个细节…然后…我知道怎么做… 结果描述的不够清楚？如果知道那个做法的名字也许就不用费劲描述了呢。。。所以来复习一下吧2333

前言：

其实有了前文simhash算法的基础，局部敏感hash算法已经不存在理解上的问题了吧。。。毕竟simhash算法应该是局部敏感哈希算法的一种。。所以我就直接转载几篇我认为比较好的文档结合一下好了。。。会把比较重要的概念或者定义标记重点。

先放原始论文。。。以此表达对这个算法的敬意orz

论文链接

问题引出：

那天百度一面，frog学姐问了我如何判断两篇新闻稿的相似度的问题….我满篇口胡…也只是回答了一些诸如从图片上考虑。。或者去掉stop word之后得到特征向量然后计算余弦值之类得到传统想法。。。

面京东被这个问题卡了QAQ，来补补这方面的课。

转自：链接

蓄水池抽样算法随机算法的一种，用来从 N 个样本中随机选择 K 个样本，其中 N 非常大（以至于 N 个样本不能同时放入内存）或者 N 是一个未知数。其时间复杂度为 O(N),包含下列步骤 (假设有一维数组 S, 长度未知，需要从中随机选择 k 个元素, 数组下标从 1 开始), 伪代码如下:

题目链接

题意：给一个二维数组。。。每一行每一列都分别递增。。问某个value是否出现过。。。

思路：单调。。显然二分。。。唯一的技巧是从右上角开始搜。

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2017年03月09日 星期四 19时03分07秒
 4File Name :74.cpp
 5************************************************ */
 6class Solution {
 7
 8public:
 9
10    bool …

一开始是晚上七点半，直接一个电话过来就开始面试》。。

窝说不方便，又约了周末下午或者晚上，然后周六上午来了电话….。。。。于是又约了周天下午。。。

回想起大一的时候打cf…那个时候对C++还不怎么熟悉。。。用sort不会自定义排序方式。。

于是手写快排。。。直接取中间元素没加随机化。。。跪了。。。

啊。。。虽然结果还没出来。。。不过回想发现有些细节已经有些记不清了。。。

所以打算先记录一下？ 就算过不了。。。也算是积累一些经验。

一面：

先是简单自我介绍。。。

起因是百度实习二面的时候被问了一道类似这样的题：

给我下面的代码，问有没有什么问题。

 1    /* ***********************************************
 2    Author :111qqz
 3    Created Time :2017年02月28日 星期二 14时49分37秒
 4    File Name :vector.cpp
 5    ************************************************ */
 6    #include <cstdio>
 7    #include <vector>
 8 …

题目链接

题意：求一棵二叉树中，所有一段连续路径之和等于给定值的路径数目。

思路：想了半天就只能想到暴力。。。复杂度大概O(n^2)。。。也不是不可以接受。。。但是感觉这也太暴力了。。就去看了题解。。。发现题解就还真是暴力orz。。。

题目链接

题意：判断一棵二叉树是否是自己的镜像。做法是做个copy，相当于两棵树做比较。注意逻辑不要漏掉就好

 1/**
 2 * Definition for a binary tree node.
 3 * struct TreeNode {
 4 *     int val;
 5 *     TreeNode *left;
 6 *     TreeNode *right;
 7 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8 * };
 9 */
10class Solution {
11public:

 1    bool leaf( …

题目链接

题意：判断一颗二叉树是否平衡….

思路：直接搞就好了。。。神TM又忘记dfs的时候忘记返回子调用的值。。。。我这是药丸啊。。。

 1 /**
 2 * Definition for a binary tree node.
 3 * struct TreeNode {
 4 *     int val;
 5 *     TreeNode *left;
 6 *     TreeNode *right;
 7 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8 * };
 9 */
10class Solution {  //错误原因：左右 …