存档

文章标签 ‘面试题’

矩阵转置 O(1)空间

2013年7月12日 8 条评论

---

题目:用O(1)的空间实现矩阵的转置

为了方便,使用一维数组来分析。所谓矩阵转置,行变列,列变行。在转置的过程中,有的元素位置是不变的;对于变化位置的元素,要求O(1)空间完成,那么这些位置的变化一定是有着规律的。

举例,2×5的矩阵,A={0,1,2,3,4,5,6,7,8,9};转置后为AT={0,5,1,6,2,7,3,8,4,9},探索下标变化:

0->0

1->2->4->8->7->5->1

3->6->3

9->9

这些下标的变化是一些环,如果我们能找到这个环,对环做移动处理,就可以O(1)完成了。

现在的问题是,我们如何知道一个环是已经处理过的,仔细观察,如果一个环被处理过,那么总能找到一个它的后继是小于它的。例如,处理了前三个环的时候,当尝试找下标4打头的环时,一直找4的后继下标,会发现后继1是小于4的,我们就知道4是存在于一条已经处理过的环,跳过。

接下来的问题是如何找到当前元素下标的前驱和后继。先求下标i转置前的下标,即i的前驱,对于m×n的矩阵,转置后为n×m,则一维数组的第i个元素表示的行列为(i/m, i%m),根据转置原理,那么这个元素在转置前的m×n矩阵中所表示的行列为(i%m, i/m),那么i在转置前一维数组中的位置为j=(i%m)×n+(i/m)。同理,下标i转置后的位置j=(i%n)×m+(i/n)。

这样,前驱后继都可以求得,找到环就移动环的元素,如果已处理过则跳过,代码如下

阅读全文...

兄弟单词 — 两种算法实现

2013年2月28日 2 条评论

---

兄弟单词这个题目最初见于《编程珠玑》,但是里面给出的方法是最笨的,一般不提倡采用吧;这个题目在之前的百度面试中也遇到过,本文实现两种方法的代码,方法如下:

方案一:使用数据结构 map<key,list>。兄弟单词共用一个签名key,key为单词内部排序后的词条,list存储同一key的单词集合;相对于编程珠玑中的方法,该方法在空间上节省了每个单词一个key的空间;在时间上,不再需要二分查找,O(1)的查找;但是这种方法还可以优化,见方案二

方案二:使用trie树。trie树又称字典树,在面试题中关于“字符串”与“数字串”类型的问题中高频出现,非常实用。对于兄弟单词,兄弟单词公用一个key自不必说,只是trie的节点结构应该多出一个域list,用来存储key对应的兄弟单词;具体节点结构应该为


bool isStr, Node* next[26], vector<const char*> brothers

该方案查询的复杂度为O(L),L为key的平均长度;空间上则有很大的优化,例如单词的key有“abc”、“abcd”、“abcde”之类的形式,则这些key也能达到空间公用,不过数据量大还好,数据量小,trie树开辟的空间还是有些浪费的,不多言,上代码:

【测试用例】


input:

cba acb bc cb b

output:

cba acb

bc cb

b

【方案一:使用哈希map实现兄弟单词】

#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;

#define MAXLEN 100  /* 单词最大长度 */

/* qsort比较函数 */
int charcmp(const void *p, const void *q)
{
	return *(char *)p - *(char *)q;
}

/* 打印输出 & 释放内存 */
void output(map<string,vector<char*>> dic)
{
	for(map<string,vector<char*>>::iterator it = dic.begin(); it != dic.end(); ++it)
	{
		for(vector<char *>::iterator itv = it->second.begin(); itv != it->second.end(); ++itv)
		{
			printf("%s ",*itv);
			free(*itv);
		}
		printf("\n");
	}
}

void main()
{
	map<string,vector<char*>> dic;  /* 存储<key,兄弟单词集> */
	char word[MAXLEN];
	int len = 0;

	while(scanf("%s",word) != EOF) /* ctrl+z结束输入 */
	{
		len = strlen(word);
		if(len > 0)
		{
			char * ptr = (char *) malloc(len+1);
			strcpy(ptr,word);
			qsort(word,len,sizeof(char),charcmp);
			string key(word);
			dic[key].push_back(ptr);
		}
	}
	output(dic);
}

【方案二:使用trie树实现兄弟单词】

阅读全文...

定长线段最多覆盖点的个数

2013年1月5日 2 条评论

---

来自之前百度一面的题目:给定一系列x轴的点坐标,例如 1,3,7,8,9,11这些坐标升序放在数组中,现在给一根绳子,长度为4,问绳子最多能覆盖的点数有多少,例如绳子放前面只能覆盖两个点,1,3,如果放后面能覆盖4个点。

题目不难,但也不是太容易想出来,两个指针前后跑的思路:两个指针往前走,前面的负责加,后面的负责减,前面的每次都移动,如果点间隔长度大于绳子长度,后面指针移动。

阅读全文...

2013百度校园招聘面经

2012年10月4日 9 条评论

---

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

笔试

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

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

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

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

系统设计题

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

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

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

阅读全文...

海量数据处理之归并、堆排、前K方法的应用:一道面试题

2011年9月8日 6 条评论

 

最初关注海量处理方面是因为好久以前在西安交大BBS算法版上看到一个牛人总结的帖子,收集了起来,后来发现网上铺天盖地地转载过,那个帖子提供了一些解决问题很好的思路,所以就零碎地整理过海量数据处理方面的一些方法,但终归没有深入并做一个稍微细致的思考,从这篇博文开始,希望能坚持整理出来。

下面一道面试题是以前大雄考过我的,据说是那时一些公司常问的类型题目,这里回顾并总结一下,欢迎大家讨论并提出问题。

题目:一个10G的关键词的log,找出词频最高的前K个词,设可用内存为2G左右

分析:

本题的难点主要有两处,一是如何在有限内存下对大文件进行词频统计;二是如何在有限内存的下找出词频的前K大个词

  1. 词频统计

词频统计,我们很自然的会想到使用hash。但是直接hash内存是放不下的啊…怎么办?其实对于有限内存下的大文件处理,都可总结为归并的思想,不过要注意归并时的分段亦是有学问的。请比较归并a与归并b方法

  • 归并a:将数据分为5段,分别对每段在内存中hash统计并将统计结果写入文件,然后合并分段的hash。

问题:表面看来不错的主意,实则有很大问题,稍微想一下,a方法存在一个主要的困难就是,hash合并的时候相当于同时在5个文件中判断是否有相同的词,要这样做会非常繁琐。

怎么解决呢?我当时是受编程珠玑中第一题(排序一千万个32位整数)启发的,它在归并分段的时候,不是直接的简单分段,而是每段取一个范围比如第一段取0~249000之间的数,这样有什么好处?将来的各段数彼此间是没有交集(重复)的。所以我们的思想就是要让这10G的关键词分段后各小段没有交集,这样hash合并就没有问题了。请看归并b

  • 归并b:将数据分为5段,分段时对每个词hashhash值在一个范围中的词语分到一个段中,然后对于每个分段统计的hash结果直接都写入一个文件即可。

分析:使用hash分段,保证各小段没有重复的词。我当时想的方法是将词语的首字拼音打头一样的分在一段中,例如“五谷丰登”、“万箭齐发”分到一起,都是w打头的拼音,其实这仅仅只是hash的一种,至于具体的hash函数,就不讨论了,哈哈

阅读全文...

关于反转字符串(Reverse Words)的思考及三种解法

2011年9月4日 1 条评论

 

早些时候在水木上看到一道面试题,于是就思考着如何去解,也就有了上篇博客的整理以及这篇文章的思考。

题:反转一个字符串句子中的单词,例如“Do or do not, there is no try.”反转后为“try. no is there not, do or Do”假设所有的单词间都是以空格分离的,将标点符号视为单词的一部分。

基于上篇文章本文提供三种方法解决该问题,第一种是Houdy博客中提到的方法,后两种方法是我在思考这个问题时想到的。其中,前两种方法都是基于Divide-and-Conquer (分治)的思想,该思想非常强大,是解决问题的一个重要的方法;第三种方法是基于非分治的思想,比分治能优化一些,较为直接,欢迎讨论。

注:以下方法在实现中所用到的函数都是源自与上一篇博文:交换两段连续(不连续)内存

方法一(分治A):

上篇文章我们提到了反转内存以及如何交换两段连续和非连续的内存,这里的分析也要基于此。个人感觉Houdy的分析很到位,循序渐进,由浅入深,他的核心思想我就直接转载了,呵呵。

从整体考虑这个问题,我们要处理的是由多个单词(单词间用空格分隔)构成的字符串,这个字符串中基本的元素就是单词和空格。首先拿几个特例来分析一下,看看有没有什么收获。

  1. 字符串中没有空格。这时候相当于字符串中只有一个单词,我们不需要进行任何操作。
  2. 字符串中有一个空格(暂且认为空格在中间)。这是反转两个单词的操作,等价于反转两块不连续的内存块的操作,这个操作上篇文章我们已经实现了
  3. 字符串中有两个空格。例如 ”Tom Jerry Mike”,我们应该怎么处理这种情况呢?结合前面两个特例的分析,我们可以马上想到一种常见的解决问题思路,即分治,也就是Houdy说的 “Divide-and-Conquer”。总体来说,我们可以将包含多于一个空格的字符串划分成三个部分:   |位于空格左边的字符串|空格|位于空格右边的字符串|

这样,我们就完成下面的处理就可以了:

  1. 对空格左边的字符串进行“反转字符串”处理
  2. 对空格右边的字符串进行“反转字符串”处理
  3. 将字符串看成一个整体,对左边的串和右边的串进行“交换两块不连续内存”处理

如果左右字符串中还包含多于一个空格,我们可以分别对他们再进行“分割”+“反转”的操作,直到字符串中的空格数量不大于1,空格数等于1时,做“交换两块不连续内存”的操作。所以,我们需要计算空格数目并记录空格的索引。

阅读全文...