第四章 查找匹配
4.1有序数组的查找
题目描述
给定一个有序的数组，查找某个数是否在数组中，请编程实现。
分析与解法
一看到数组本身已经有序，我想你可能反应出了要用二分查找，毕竟二分查找的适用条件就是有序的。那什么是二分查找呢？
二分查找可以解决（预排序数组的查找）问题：只要数组中包含T（即要查找的值），那么通过不断缩小包含T的范围，最终就可以找到它。其算法流程如下：
?
?
? 一开始，范围覆盖整个数组。 将数组的中间项与T进行比较，如果T比数组的中间项要小，则到数组的前半部分继续查找，反之，则到数组的后半部分继续查找。 如此，每次查找可以排除一半元素，范围缩小一半。就这样反复比较，反复缩小范围，最终就会在数组中找到T，或者确定原以为T所在的范围实际为空。
对于包含N个元素的表，整个查找过程大约要经过log(2)N次比较。
此时，可能有不少读者心里嘀咕，不就二分查找么，太简单了。
然《编程珠玑》的作者Jon Bentley曾在贝尔实验室做过一个实验，即给一些专业的程序员几个小时的时间，用任何一种语言编写二分查找程序（写出高级伪代码也可以），结果参与编写的一百多人中：90%的程序员写的程序中有bug（我并不认为没有bug的代码就正确）。
…… …… 余下全文
1 算法面试题总结
1.把二元查找树转变成排序的双向链表
题目：
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点，只调整指针的指向。
10
/ \
6 14
/ \ / \
4 8 12 16
转换成双向链表
4=6=8=10=12=14=16。
解：首先我们定义的二元查找树 节点的数据结构如下：
typedef struct tree
{
int data; // value of node
struct tree *left; // left child of node
struct tree *right; // right child of node
}*ptree;
ptree f(ptree root,int sign)//sign==0返回链头，sign==1返回链尾
{ //main函数中调用f(root,0);
ptree p=root;
if(p->left) //如果左子树非空
{
p->left = f(p->left,1);//第4个参数为，表明f函数返回root左子树中根的链尾 p->left->right = p; //双链表中left记录前驱，right记录后继
…… …… 余下全文
程序员如何快速准备面试中的算法 备战面试中算法的五个步骤
对于立志进一线互联网公司，同时不满足于一辈子干纯业务应用开发，希望在后端做点事情的同学来说，备战面试中的算法，分为五个步骤，如下：
1、掌握一门编程语言
首先你得确保你已掌握好一门编程语言：
C的话，推荐Dennis M. Ritchie & Brian W. Kernighan合著的《C程序设计语言》，和《C和指针》；
C++ 则推荐《C++ Primer》，《深度探索C++对象模型》 、《Effective C++》 。 掌握一门语言并不容易，不是翻完一两本书即可了事，语言的细枝末节需要在平日不断的编程练习中加以熟练。
2、过一遍微软面试100题系列
我从20xx年起开始整理微软面试100题系列，见过的题目不可谓不多，但不管题目怎般变化，依然是那些常见的题型和考察点。当然，不考察任何知识点，纯粹考察编程能力的题目也屡见不鲜。故不管千变万化，始终不离两点：①看你基本知识点的掌握情况；②编程基本功。
而当你看了一遍微软面试100题之后(不要求做完)，你自会意识到：数据结构和算法在笔试面试中的重要性。
…… …… 余下全文
一.算法的基本概念
计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。
1.算法的基本特征：可行性，确定性，有穷性，拥有足够的情报。
2.算法的基本要素：算法中对数据的运算和操作、算法的控制结构。
3.算法设计的基本方法：列举法、归纳法、递推、递归、减半递推技术、回溯法。
4.算法设计的要求：正确性、可读性、健壮性、效率与低存储量需求
二.算法的复杂度
1.算法的时间复杂度：指执行算法所需要的计算工作量
2.算法的空间复杂度：执行这个算法所需要的内存空间
三.数据结构的定义
1.数据的逻辑结构：反映数据元素之间的关系的数据元素集合的表示。数据的逻辑结构包括集合、线形结构、树形结构和图形结构四种。
2.数据的存储结构：数据的逻辑结构在计算机存储空间种的存放形式称为数据的存储结构。常用的存储结构有顺序、链接、索引等存储结构。
四.数据结构的图形表示：
在数据结构中，没有前件的结点称为根结点；没有后件的结点成为终端结点。插入和删除是对数据结构的两种基本运算。还有查找、分类、合并、分解、复制和修改等。
五.线性结构和非线性结构
根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构和非线性结构。
…… …… 余下全文
第一轮：
（一）对你简历上列出的所有工作经验和开发过的项目。
（二）对商业和internet上IR与传统IR的区别的认识诸如此类。
（三）你对百度有多少了解，如果加入百度，你能给百度带来什么，又能从百度获得什么? 第二轮：
（一）上大学对哪些课感兴趣，学得比较好
（二）你认为自己的优点是什么，缺点是什么？喜欢什么运动？
（三）认为最大的成功是什么，最大的失败是什么。
（四）你希望三年后是什么样子?
第三轮：
介绍了他们公司的福利制度和待遇构成，主要有什么四险一金，商业保险，奖金，项目奖金，年底分红，员工期权，活动经费等等。
总的感觉，百度这样的小公司和IBM这样的大公司区别还是很大的，至少没有英语面试，让我感觉不错，而且他们的策略是选择最合适他们公司的人，面试的时候是几个经理齐上阵，轮流搞，一次结束战斗，也比IBM一次次筛选感觉要好一点。面试的时候谈话也比较深入，俺开始还说”如果我加入百度，会怎么怎么样“后来就变成”我在百度怎么怎么样“了，sigh，感觉被骗上了山了，今年形势这么差，搞不好就要卖给它了。
最后希望百度的人看到本文以后不要告诉他们老板，俺还指着offer哪。
…… …… 余下全文
1. 给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？
方案1：可以估计每个文件安的大小为50G×64=320G，远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。
s 遍历文件a，对每个url求取 ，然后根据所取得的值将url分别存储到1000个小文件（记为 ）中。这样每个小文件的大约为300M。
s 遍历文件b，采取和a相同的方式将url分别存储到1000各小文件（记为 ）。这样处理后，所有可能相同的url都在对应的小文件（ ）中，不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可。
s 求每对小文件中相同的url时，可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url，看其是否在刚才构建的hash_set中，如果是，那么就是共同的url，存到文件里面就可以了。
方案2：如果允许有一定的错误率，可以使用Bloom filter，4G内存大概可以表示340亿bit。将其中一个文件中的url使用Bloom filter映射为这340亿bit，然后挨个读取另外一个文件的url，检查是否与Bloom filter，如果是，那么该url应该是共同的url（注意会有一定的错误率）。
…… …… 余下全文
程序员面试、算法研究、编程艺术、红黑树4大系列集锦
与总结
作者：July--结构之法算法之道blog之博主。
时间：20xx年x月-20xx年x月。
出处：http://blog.csdn.net/v_JULY_v 。
声明：版权所有，侵犯必究。
前言
开博已过8个月，回首这8个月，发现自己在本blog上着实花费了巨大的时间与精力，写的东西可能也够几本书的内容了。希望我真真正正的为读者提供了实实在在的价值与帮助。 无私分享，造福天下
以下是本blog内的微软面试100题系列，经典算法研究系列，程序员编程艺术系列，红黑树系列4大经典原创系列作品与一些重要文章的集锦。有任何问题，欢迎不吝指正。
一、微软面试100题系列
横空出世，席卷Csdn--评微软等数据结构+算法面试100题 （在此文中，你能找到与微软100题所有一切相关的东西） 微软100题 （微软面试完整100题20xx版） 微软面试100题20xx年版全部答案集锦（含下载地址） 微软、谷歌、百度等公司经典面试100题[第1-60题] （微软100题第二版前60题） 微软、Google等公司非常好的面试题及解答[第61-70题]（微软 100题第二版第61-70题） 十道海量数据处理面试题与十个方法大总结 （十道海量数据处理面试题） 海量数据处理面试题集锦与Bit-map详解 （十七道海量数据处理面试题） 九月腾讯，创新工场，淘宝等公司最新面试十三题（20xx年度九月最新面试三十题） 十月百度，阿里巴巴，迅雷搜狗最新面试十一题（20xx年度十月最新面试七十题） 十月下旬腾讯，网易游戏，百度盛大迅雷校园招聘笔试题集锦（10.24）
…… …… 余下全文
C语言面试算法题
1.求组合数： 求n个数（1....n）中k个数的组合....
如：combination(5,3)
要求输出：543，542，541，532，531，521，432，431，421，321， 1. /*
2. 求组合数： 求n个数（1....n）中k个数的组合....
3. 如：combination(5,3)
4. 要求输出：543，542，541，532，531，521，432，431，421，321，
5. */
6. #include <stdio.h>
7. #include <error.h>
8. int pop(int *);
9. int push(int );
10. void combination(int ,int);
11.
12. int stack[3]={0};
13. int top = -1;
14.
15. int main()
16. {
17. int n,m;
18. n = 5;
19. m = 3;
20. combination(n,m);
…… …… 余下全文