hash表算法
hash表算法 ##第一部分：Top K 算法详解 ####问题描述 百度面试题： 搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。 假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。），请你统计最热门的10个查询串，要求使用的内存不能超过1G。 ####必备知识 什么是哈希表？ 哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。 哈希表hashtable(key，value)...
10.01.03
...
一致性哈希算法
一致性哈希算法 tencent2012笔试题附加题 问题描述： 例如手机朋友网有n个服务器，为了方便用户的访问会在服务器上缓存数据，因此用户每次访问的时候最好能保持同一台服务器。 已有的做法是根据ServerIPIndex[QQNUM%n]得到请求的服务器，这种方法很方便将用户分到不同的服务器上去。但是如果一台服务器死掉了，那么n就变为了n-1，那么ServerIPIndex[QQNUM%n]与ServerIPIndex[QQNUM%（n-1）]基本上都不一样了，所以大多数用户的请求都会转到其他服务器，这样会发生大量访问错误。 问： 如何改进或者换一种方法，使得： (1)...
傅里叶变换算法、上
从头到尾彻底理解傅里叶变换算法、上 I、本文中阐述离散傅里叶变换方法，是根据此书：The Scientist and Engineer’s Guide to Digital Signal Processing，By Steven W. Smith, Ph.D.而翻译而成的，此书地址：http://www.dspguide.com/pdfbook.htm。 II、同时，有相当一部分内容编辑整理自dznlong的博客，也贴出其博客地址，向原创的作者表示致敬：http://blog.csdn.net/dznlong 。这年头，真正静下心写来原创文章的人，很少了。 从头到尾彻底理解傅里叶变换算法、上 前言 第一章、傅立叶变换的由来 第二章、实数形式离散傅立叶变换（Real...
后缀树
后缀树 1.1、后缀树的定义 后缀树（Suffix tree）是一种数据结构，能快速解决很多关于字符串的问题。后缀树的概念最早由Weiner 于1973年提出，既而由McCreight 在1976年和Ukkonen在1992年和1995年加以改进完善。 后缀，顾名思义，就是后面尾巴的意思。比如说给定一长度为n的字符串S=S1S2…Si…Sn，和整数i，1 <= i <= n，子串SiSi+1…Sn便都是字符串S的后缀。 以字符串S=XMADAMYX为例，它的长度为8，所以S[1…8], S[2…8], … , S[8…8]都算S的后缀，我们一般还把空字串也算成后缀。这样，我们一共有如下后缀。对于后缀S[i…n]，我们说这项后缀起始于i。 S[1…8], XMADAMYX， 也就是字符串本身，起始位置为1 S[2…8], MADAMYX，起始位置为2 S[3…8], ADAMYX，起始位置为3 S[4…8], DAMYX，起始位置为4 S[5…8], AMYX，起始位置为5 S[6…8], MYX，起始位置为6 S[7…8], YX，起始位置为7 S[8…8],...
傅里叶变换算法、下
从头到尾彻底理解傅里叶变换算法、下 推荐阅读：The Scientist and Engineer’s Guide to Digital Signal Processing，By Steven W. Smith, Ph.D。此书地址：http://www.dspguide.com/pdfbook.htm。 前期回顾，在上一篇里，我们讲了傅立叶变换的由来、和实数形式离散傅立叶变换（Real...
奇偶调序
...
字符串问题
本章导读 字符串相关的问题在各大互联网公司笔试面试中出现的频率极高，比如微软经典的单词翻转题：输入“I am a student.”，则输出“student. a am I”。 本章重点介绍6个经典的字符串问题，分别是旋转字符串、字符串包含、字符串转换成整数、回文判断、最长回文子串、字符串的全排列，这6个问题要么从暴力解法入手，然后逐步优化，要么多种思路多种解法。 读完本章后会发现，好的思路都是在充分考虑到问题本身的特征的前提下，或巧用合适的数据结构，或选择合适的算法降低时间复杂度（避免不必要的操作），或选用效率更高的算法。