From Zero to Hero

本章海量数据的习题 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颗宝石，每一颗都一样大小和价值连城。他们决定这么分：...

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

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

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

网络协议 1 请简单阐述TCP连接的三次握手。

1.1 旋转字符串 题目描述 给定一个字符串，要求把字符串前面的若干个字符移动到字符串的尾部，如把字符串“abcdef”前面的 2 个字符’a’和’b’移动到字符串的尾部，使得原字符串变成字符串“cdefab”。请写一个函数完成此功能，要求对长度为 n 的字符串操作的时间复杂度为 O(n)，空间复杂度为 O(1)。 分析与解法 解法一：暴力移位法 初看此题，可能最先想到的方法是按照题目所要求的，把需要移动的字符一个一个地移动到字符串的尾部，如此我们可以实现一个函数LeftShiftOne(char* s, int n) ，以完成移动一个字符到字符串尾部的功能，代码如下所示： 123456789void LeftShiftOne(char* s, int n){ char t = s[0]; //保存第一个字符 for (int i = 1; i < n; i++) { s[i - 1] = s[i]; } s[n - 1] = t;} 因此，若要把字符串开头的 m...