二分查找,你真的会吗?

2012年10月6日 19 条评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

面试常让写二分查找或其扩展的程序,以前总觉得很简单,但是真动手写起来,细节很多,容易出错的地方也很多,真是秒杀眼高手低的利器,本节就二分查找以及相关扩展程序都实现一下,同时将可能出错的地方以及需要注意的细节也一并说明,水平有限,欢迎补充。

内容如下:

1)二分查找元素key的下标,如无 return -1

2)二分查找返回key(可能有重复)第一次出现的下标,如无return -1

3)二分查找返回key(可能有重复)最后一次出现的下标,如无return -1

4)二分查找返回刚好小于key的元素下标,如无return -1

5)二分查找返回刚好大于key的元素下标,如无return -1

注:以上所有问题可能出错的地方以及需要注意的细节说明在代码注释中。

直接上代码:

阅读全文...

2013百度校园招聘面经

2012年10月4日 9 条评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

百度校招在大连站比较早,也比较迅速,十一假期前已经发放offer,我投的研发职位,有幸拿到了offer,这里贴个面经。

笔试

笔试前面是考察知识型,后面算法设计和系统设计还是比较有意思,题目就不一一列举了,这里有童鞋都码出来了。简单说下算法设计和系统设计,欢迎讨论。

算法设计1,锦标赛排序,赢者树;

算法设计2,程序写起来简单,但是写完程序也不知结果,哈,如果要直接分析出答案,有一定难度,网上有分析很给力,在这里

算法设计3,多路归并,败者树

系统设计题

这个题目比较复杂,原因是需要检索出的结果可以是电话号码中的连续子串匹配结果,也可以是姓名拼音的匹配结果,我没有好的思路,只有个模糊粗糙的方案,列出来欢迎讨论。

数据结构:Trie树,树的节点结构大致包含Next指针数组与存储resultUser的Vector。

方案:对电话列表进行预处理,建立索引系统;索引即trie树,不过这里不是字符trie,而是数字trie,因为用户输入是数字号码串;考虑到电话号码的连续子串也进行匹配,我做如下处理(比较粗糙)。

阅读全文...

百度面试题:POJ 2192 - Zipper

2012年9月30日 8 条评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

百度二面的时候有一道题目没有答上来,回来一查,原来是POJ上的原题,是一个DP问题,当时有向这方面想,但始终没有找出重叠子问题,网上看到别人定义的子问题,感觉真心简单,关键看是否能找出子问题了,这个积累不是一时半日的,自己还是太菜。刚刚到POJ上AC了这道题,附题目链接:

POJ 2192: http://poj.org/problem?id=2192

题意:就是给定三个字符串A,B,C;判断C能否由AB中的字符组成,同时这个组合后的字符顺序必须是A,B中原来的顺序,不能逆序;例如:A:mnl,B:xyz;如果C为mnxylz,就符合题意;如果C为mxnzly,就不符合题意,原因是z与y顺序不是B中顺序。

DP求解:定义dp[i][j]表示A中前i个字符与B中前j个字符是否能组成C中的前 (i+j) 个字符,如果能标记true,如果不能标记false;

有了这个定义,我们就可以找出状态转移方程了,初始状态dp[0][0] = 1:

dp[i][j] = 1 如果 dp[i-1][j] == 1 && C[i+j-1] == A[i-1]
dp[i][j] = 1 如果 dp[i][j-1] == 1 && C[i+j-1] == B[j-1]

代码如下:

阅读全文...

TF-IDF来源及理论推导

2012年8月16日 7 条评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

了解文本挖掘的都知道TF-IDF这个概念,以前也做过一个文本分类的项目,用到TF-IDF,当时也就是照现成的公式用,也没想过它的公式为什么那么定义,只是有一个感观上的理解。

了解信息论的都知道“熵”这个概念,这是个了不得的成就,信息是个很抽象的概念,但信息熵的提出很好地解决了信息的量化问题。

信息熵的用处很多,一个典型的例子就是它在决策树算法中的应用了,我最初接触信息熵和决策树时整理了一点资料(入门看),在这里备份,方便以后查找。

  1. 20090701-Yx.Ac-信息熵
  2. 20090714-Yx.Ac-决策树ID3
  3. 20090714-ID3条件熵的选择推导证明

郁闷的是我现在才知道TF-IDF的定义原来是由信息熵推导而来的,信息熵真是不错,要知道TF-IDF的各种形式常被搜索引擎所应用,它已经深深影响并改变着人们的生活。TF-IDF用在向量空间模型中为文档向量进行权重赋值,那么使用TF-IDF计算的权重有何物理意义呢

阅读全文...

网络爬虫中的那些多线程设计模式

2012年8月12日 1 条评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

前天跟师兄讨论问题,提到多线程,这些天做简历,也在回顾项目,忽然想到曾经写过网络爬虫中所用到的多线程,当时就顾写了,没有好好总结,只记得细节很多,学到的东西不少,今天就爬虫中涉及到的多线程设计模式做个小整理,重点加深读写锁模式的理解。内容如下:

===问题细节说明

===网页抓取:生产者消费者模式(多v多)

===URL去重:读写锁模式

===网页写入文件:生产者消费者模式(多v一)

===关于多线程的几点注意

=========================================

问题细节说明

1)简述一下这里涉及到的三个过程:a)爬虫从待爬取URL队列中取得URL进行抓取,抓取来的网页进行解析提取新的链接加入到待爬取URL队列;b)爬取每个网页之前,程序会到已爬取URL表中查询该URL是否已经爬取过;c)网页爬取完,网页解析的内容要写入文件

上述三个过程都是在多线程的环境下进行处理,涉及到的共享资源有:URL任务队列、已爬取的URL表,存储网页内容的文件。这些共享资源的读与写都需要处理好线程的同步互斥,以保证线程安全。

2)注:爬虫中多线程的管理实际是需要维护一个线程池;URL去重也是使用MD5结合布隆过滤器进行实现的;上述所述三个过程在爬虫中并不是独立的,而是互相结合工作的,但是为了提取模式特点,我们将其分拆开,在讲述一个模式过程中如果涉及到其他模式,便略去不谈。所以,这里仅仅提取爬虫中的多线程设计模式,举例重在了解模式工作原理,不涉及爬虫具体实现的过多细节。

阅读全文...

基于Nutch的站内搜索引擎搭建(二)

2012年8月9日 没有评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

Windows下Nutch的安装配置,参见:基于Nutch的站内搜索引擎搭建(一)

本节在上回基础上,对Nutch添加中文分词插件,进行二次开发,同时辅助Nutch分析工具了解Nutch的工作机制,并对其进行一些简单的优化配置。内容如下:

===部件及安装===

===Nutch添加中文分词插件===

===重新爬取建立索引发布===

===参考资料===

===========================================

部件及安装

Javacc:一个Java语法分析器,可以读取上下文无关且有着特殊意义的语法并把它转换成可以识别且匹配该语法的JAVA程序,这里主要用于将Nutch添加中文分词后进行重新编译生成Nutch的分词程序。附上快盘下载链接:Javacc下载

安装Javacc,解压缩包后,将Javacc的bin路径添加到环境变量Path中,然后可cmd测试命令Javacc验证。

IK Analyzer:开源分词软件,下载地址:http://code.google.com/p/ik-analyzer/

Luke:访问Lucene索引的开发分析工具,可以显示并修改Lucene索引内容,下载地址:http://www.getopt.org/luke/

阅读全文...

基于Nutch的站内搜索引擎搭建

2012年8月8日 2 条评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

以前配置过一次Nutch,后来干脆忘干净了,最近又折腾一次,记录下来,方便以后查阅。现在Nutch的版本已经出到1.51了(截止到7月份),新版资料少,入门还是找经典的版本混个眼熟先,本文采用0.9版,在Windows下搭建一个简单的站内搜索引擎,内容如下:

===所需装备===

===基本部件安装(从简述)===

===Nutch的安装与配置===

===Nutch部署到Eclipse===

===爬取网页:Nutch和Eclipse进行站内抓取===

===实现站内搜索:Nutch部署到Tomcat===

===参考资料===

===========================================

===所需装备

JDK1.6 不多说,大多数人都装有

Eclipse 不多说

Tomcat 开源web应用服务器,下载地址:http://tomcat.apache.org/

Nutch 0.9 下载地址:http://nutch.apache.org/  我安装时,官方没找到这个版本,这里提供一个快盘下载链接:Nutch-0.9

Cygwin 用来模拟运行UNIX类环境的,因Nutch是在Linux下开发的,故Windows环境下需要用Cygwin协助。下载地址:http://www.cygwin.com/ (本文没有在Cygwin环境下,大部分命令是通过Eclipse完成)

阅读全文...

线段树

2012年7月16日 1 条评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

概述

线段树也叫区间树,顾名思义,线段树是一种基于区间的树,每个节点表示一个“线段”或“区间”。树的根节点表示是“整体”的区间,左右子树分别表示这个区间的左半边和右半边。

基本结构及性质

假设要构造一个表示N个区间大小的线段树,线段树的根节点表示区间[0,N-1],然后将区间分成两半,分别为左右子树表示,这样的线段树的节点只有2N-1个,是O(N)级别的,如图所示表示构造区间[1-5]的线段树。

1)存储:

线段树可以使用链状结构动态构造,这样的优点是节省空间,空间复杂度在2N,但是缺点就是编程复杂度大,执行效率低;

所以线段树一般是使用一维数组以完全二叉树的方式来存储,类似堆,这样的编程复杂度低,执行效率高,但是耗费空间,一般来讲,这样情况下都是申请4N的空间,关于这方面的分析请见参考资料。

2)实现细节:

使用一维数组存储,设父节点的下标为idx,则左儿子下标为(idx<<1)+1,右儿子下标为(idx<<1)+2。

一般来讲,线段树的节点必有的两个域为left和right,代表该节点表示区间[left,right],区间的中间节点为mid=(left+right)>>1,它左儿子表示的区间为[left,mid],右儿子表示的区间为[mid+1,right],有时候右儿子的区间为[mid,right],具体是什么取决于实际问题,主要是看解决的问题是针对于“点”还是针对于“区间”,具体可参见本节后面的应用举例部分。

阅读全文...

逆序对 | 逆序数

2012年7月16日 3 条评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

设A[1…n]是一个包含n个不同数的数组。如果在i<j的情况下,有A[i]>A[j],则(i,j)就称为A中的一个逆序对(inversion)【《算法导论》2-4】

现给出一个数列,求该数列中的逆序对数(逆序数)。本节给出三种方法:方法一是最直接的暴力方法;方法二是基于归并分治的思想;方法三是基于线段树的。

解法一

暴力方法最直接,也最容易想到,两层for循环就可以算出来逆序数:每遇到一个元素回头遍历寻找比其大的元素个数即可,当然向后寻找比其小的元素个数也可以,复杂度为O(n^2),代码:

	int sum = 0;
	for(int i = 0; i < size; ++i)
	{
		for(int j = i+1; j < size; ++j)
		{
			if(arr[i] > arr[j])
			{
				++sum;
			}
		}
	}
	return sum;

解法二

这种方法最初见于《算法导论》,这里先附上《算法导论》2-4关于逆序对的几点讨论:

阅读全文...