From Zero to Hero

数据库 方法介绍 当遇到大数据量的增删改查时，一般把数据装进数据库中，从而利用数据的设计实现方法，对海量数据的增删改查进行处理。

倒排索引(Inverted index) 方法介绍 倒排索引是一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射，常被应用于搜索引擎和关键字查询的问题中。 以英文为例，下面是要被索引的文本： T0 = "it is what it is" T1 = "what is it" T2 = "it is a banana" 我们就能得到下面的反向文件索引： "a": {2} "banana": {2} "is": {0, 1, 2} "it": {0, 1, 2} "what": {0,...

本章海量数据的习题 1 有100W个关键字，长度小于等于50字节。用高效的算法找出top10的热词，并对内存的占用不超过1MB。 提示：老题，与caopengcs讨论后，得出具体思路为： 先把100W个关键字hash映射到小文件，根据题意，100W50B = 5010^6B = 50M，而内存只有1M，故干脆搞一个hash函数 % 50，分解成50个小文件； 针对对每个小文件依次运用hashmap(key，value)完成每个key的value次数统计，后用堆找出每个小文件中value次数最大的top 10； -最后依次对每两小文件的top 10归并，得到最终的top...

K近邻算法 1.1、什么是K近邻算法 何谓K近邻算法，即K-Nearest Neighbor...

语言基础 1、C++中虚拟函数的实现机制。 2、指针数组和数组指针的区别。 3、malloc-free和new-delete的区别。 4、sizeof和strlen的区别。 5、描述函数调用的整个过程。 6、C++ STL里面的vector的实现机制， 当调用push_back成员函数时，怎么实现？ 内存足则直接 placement new构造对象，否则扩充内存，转移对象，新对象placement new上去。 当调用clear成员函数时，做什么操作，如果要释放内存该怎么做。 调用析构函数，内存不释放。 clear没有释放内存，只是将数组中的元素置为空了，释放内存需要delete。

概率统计 1 已知有个rand7()的函数，返回1到7随机自然数，让利用这个rand7()构造rand10() 随机1~10。 分析：这题主要考的是对概率的理解。程序关键是要算出rand10，1到10，十个数字出现的考虑都为10%.根据排列组合，连续算两次rand7出现的组合数是7*7=49，这49种组合每一种出现考虑是相同的。怎么从49平均概率的转换为1到10呢？方法是： 1.rand7执行两次，出来的数为a1=rand7()-1，a2=rand7()-1. 2.如果a17+a2<40,b=(a17+a2)/4+1；如果a1*7+a2>=40,重复第一步。参考代码如下所示： 12345678910111213141516int rand7(){ return rand() % 7 + 1;}int rand10(){ int a71, a72, a10; do { a71 = rand7() - 1; a72 = rand7() - 1; a10 = a71 * 7 + a72; } while (a10...

智力逻辑 1 五个海盗抢到了100颗宝石，每一颗都一样大小和价值连城。他们决定这么分：...

支持向量机 ##第一层、了解SVM 支持向量机，因其英文名为support vector machine，故一般简称SVM，通俗来讲，它是一种二类分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，其学习策略便是间隔最大化，最终可转化为一个凸二次规划问题的求解。 ###1.1、线性分类 理解SVM，咱们必须先弄清楚一个概念：线性分类器。 ####1.1.1、分类标准 考虑一个二类的分类问题，数据点用x来表示，类别用y来表示，可以取1或者-1，分别代表两个不同的类，且是一个n...

系统设计 1、搜索关键词智能提示suggestion 百度搜索框中，输入“北京”，搜索框下面会以北京为前缀，展示“北京爱情故事”、“北京公交”、“北京医院”等等搜索词，输入“结构之”，会提示“结构之法”，“结构之法 算法之道”等搜索词。 请问，如何设计此系统，使得空间和时间复杂度尽量低。 提示：此题比较开放，简单直接的方法是：用trie树存储大量字符串，当前缀固定时，存储相对来说比较热的后缀。然后用hashmap+堆，统计出如10个近似的热词，也就是说，只存与关键词近似的比如10个热词，我们把这个统计热词的方法称为TOP...

操作系统 1 请问死锁的条件是什么？以及如何处理死锁问题？ 解答：互斥条件（Mutual exclusion）： 1、资源不能被共享，只能由一个进程使用。 2、请求与保持条件（Hold and wait）：已经得到资源的进程可以再次申请新的资源。 3、非剥夺条件（No pre-emption）：已经分配的资源不能从相应的进程中被强制地剥夺。 4、循环等待条件（Circular...