Archive for category 求职道路

近况汇报(201109-201111)

这三个月的主题就找工作,从9月初开始投简历,不断笔试面试,11月中旬签完三方,不得不说,找工作是件辛苦的事情。

简历没有海投,只挑了自己感兴趣的,规模还算不小的公司。9月底收到华为offer,面完烽火,百度二面结束。十一过后收到烽火offer,然后去了趟杭州,参加网易校招,顺便游览西湖,看望波波学长,受到波波学长热情款待。从杭州回来当天下午百度三面,两天后终面,两天后收到百度offer,职位是云计算工程师,不过很可能会调成安全工程师(原委就不详述了)。后面放弃了绿盟的面试,开始过年般的生活。

度过大学中第四个光棍节后终于和百度牵了手,签下三方,然后回家小住一周,前天回校。我已经跟hr说明了提前实习的希望,现在还在等安全组的消息,尚未确定去北京的时间,于是还可以多玩会儿:)

谢谢一直关心我工作的学长,晓刚,陈华哥,波波,杨老师,孔大姐,谢忱(信安大赛通达的队员),还有老大!

周五要给科协的同学搞个讲座(好比别扭的词汇),或许是大学里最后一次上讲台了。最后放两张今年年初在北京的留影。

2011年1月摄于百度大厦

2011年1月摄于谷歌中国

7 Comments

关于字符串“循环左移”算法的讨论

问题:有一个长度为n的字符串,对其循环左移i位,就像这样,有字符串“abcdefg”,对其循环左移3位得到“defgabc”。使用什么样的算法实现?

这个问题是腾讯C/C++研发实习生的一个面试题。

我要说明一下,在这里我只是关注算法。在实现中,不考虑错误检测或者异常处理,也不考虑特殊的情况,比如i<0就是循环右移啊,i>n需要取模啊等等;也不计算每种算法实现都需要步骤的时间开销,比如字符串的初始化,事实上,为了简化代码,我就直接使用了string类型而不是char[ ],再比如求字符串的长度,就直接调用了字符串处理函数等等。做这么多简化,为的就是能更侧重算法本身。下面来看几种实现算法。

一、使用一个字节的额外空间开销

这种算法要经历i趟,每一趟把str[0]赋值给临时变量char t,剩余的字符向左移动一位,即str[k]=str[k+1],移动完成后把临时变量t赋值给str[n-1]。

//code in C++
string rotateLeft_1(string str,int i)
{
	char t;
	int strlen;
	strlen = str.length();
	for (int j=0;j<i;j++)
	{
		t = str[0];
		for (int k=0;k<strlen;k++)
		{
			str[k] = str[k+1];
		}
		str[strlen-1] = t;
	}
	return str;
}

这个算法虽然空间开销小,但是时间开销可大了去了,两层的嵌套循环,效率太低。有没有效率高一点的算法呢——废话,当然有!

二、使用n个字节的额外空间开销

减小时间开销的一个基本思想是以空间换时间。这个算法使用一个新的长度为n的字符串(字符数组)保存原始字符串的副本,然后对原始字符串的每个元素重新赋值。

//code in C++
string rotateLeft_2(string str,int i)
{
	int strlen;
	strlen = str.length();
	string t = new char[strlen];
	for (int j=0;j<strlen;j++)
	{
		t[j] = str[j];
	}
	for (j=0;j<strlen;j++)
	{
		str[j] = t[(j+i)%strlen];
	}
	return str;
}

这种算法要比第一种时间开销小,但是似乎空间上的开销过大了。

三、使用i个字节的额外空间开销

显而易见,上面的算法远非最佳算法,所以算法有在时空上取得双赢的改进的可能。第三种算法将字符串的前i个元素复制到一个临时字符串(字符数组)中,将原始字符串余下的n-i个元素左移i个位置,最后将最初的i个元素从临时字符串(字符数组)中复制到余下的位置。

//code in C++
string rotateLeft_3(string str,int i)
{
	string t = new char[i];
	int strlen = str.length();
	for (int j=0;j<i;j++)
	{
		t[j] = str[j];
	}
	for (j=i;j<strlen;j++)
	{
		str[j-i] = str[j];
	}
	for (j=strlen-i;j<strlen;j++)
	{
		str[j] = t[j-strlen+i];
	}
	return str;
}

这种算法看上去和第二种没太大差别,但无论从时间开销还是空间开销上来讲,都要比第二种好。原因在于虽然原始字符串中的每个位置都要发生变化,但没有必要花费n个字节的内存开销保存原始字符串的副本,只需保存前i个位置的元素。不过总觉得这种算法还不够好-_-!

四、使用一个字节额外空间开销的“杂技”算法

同样是使用一个字节的额外空间开销,但这种“有点像精巧的杂技动作”的算法的时间开销比第一种要小很多。首先把str[0]存到一个临时变量char t中,然后移动str[i]到str[0],str[2i]到str[i],……,直到遇到str[0](str的下标对n取模),将t赋值给刚才移动的最后一个位置。str中的每个元素都要进行移动,如果没有移动完,就从str[1]开始再次移动,直到所有的元素都已经移动了。

//code in C++
string rotateLeft_4(string str,int i)
{
	int strlen = str.length();
	char t;
	int count = 0;    //统计移动次数
	int j,k = 0;      //k初始化为0,从str[0]开始
	while (1)
	{
		t = str[k];         //开始的元素保存到临时变量t中
		j = (k+i) % strlen;
		while(j != k)       //开始移动,直到遇到开始的元素
		{
			str[(j-i+strlen) % strlen] = str[j];
			count++;    //移动次数统计量+1
			j = (j+i) % strlen;
		}
		str[(k-i+strlen) % strlen] = t;    //临时变量t中保存的值赋值给刚才移动的最后一个位置
		count++;
		if (count<strlen)    //判断是否所有元素都已经移动
		{
			k++;         //没有移动所有元素,再次从str[k+1]开始
		}
		else
		{
			break;       //所有元素都已经移动,跳出循环
		}
	}
	return str;
}

这个算法看起来就比较复杂,难怪说是“有点像精巧的杂技动作”,实现起来也要格外小心。

五、“翻手”算法

来看一个有趣的实现字符串循环左移的算法。在具体讲这种算法之前,先来看看线性代数里的转置。(AB)T等于什么?等于BTAT。那么(ATBTT等于什么?等于(BTT(ATT,即BA。

啊哈!我们用三个步骤就可以完成这个字符串的循环左移了。对于字符串来讲,转置在这里就是逆置。把原始字符串分成ab两部分,a是前i个元素,b是后n-i个元素,首先对a求逆,得到a-1b,然后对b求逆得到a-1b-1,然后对整体求逆得到(a-1b-1-1=ba。

下面这张图形象地说明了这种算法,这里是将一个长度为10的字符串循环左移5位。

//code in C++
string reverse(string str,int m,int n)
{
	char temp;
	while(m<n)
	{
		temp = str[m];
		str[m] = str[n];
		str[n] = temp;
		m++;
		n--;
	}
	return str;
}
string rotateLeft_5(string str,int i)
{
	int strlen = str.length();
	str = reverse(str,0,i-1);
	str = reverse(str,i,strlen-1);
	str = reverse(str,0,strlen-1);
	return str;
}

我写的代码有些丑陋。“翻手”算法的时空效率是比较高的。

另外来看一下使用python实现的算法。用python来处理字符串非常方便,尤其是分片,简直就是神器啊。(这里就不讨论时空效率了)

#code in python
#! /usr/bin/python
str = raw_input("Please input the string and i\n")
i = input()
str = (str[i-1::-1]+str[:i-1:-1])[::-1]
print str

这里将分片操作的最后一个参数置为-1,用作置逆。但这是不是多此一举呢?既然都有分片操作了,直接分片连接就行了,这似乎就没有设计算法的味道了。

#code in python
#! /usr/bin/python
str = raw_input("Please input the string and i\n")
i = input()
str = str[i:]+str[:i]
print str

上面五个算法里我认为最漂亮的是第五个算法,算法思想简洁优美,实现起来也不复杂,并且效率高,空间开销也小。

,

4 Comments

淘宝2011春季实习生招聘研发类笔试题回顾

4月1日(坑爹的日子)晚上到南大参加了今年淘宝春季实习生的笔试,这是我求职路上的第一步——第一次投简历,第一次参加笔试。说个题外话,南大老校区很有味道。

虽然我投的是安全工程师的岗位,但和投研发类的同学做的是同一份试卷。发现考场里投安全工程师的还是很少的,大部分都是我同学了,恩,去了好多南邮人。笔试题总体上来讲比较基础,填空选择侧重基础的C语言语法,基本算法和数据结构,综合题比较考验思维和能力。现在把我还记得的部分题目记录一下,供大家参考,也欢迎讨论。

选择题:
在局域网的网关对访问请求进行过滤,哪种方案开销最小()
A:根据http请求的头信息包含的关键字进行过滤
B:对特定IP地址进行过滤,在握手阶段断开连接
C:拦截DNS请求,对请求返回随机的IP
D:检查访问请求的网址,对含有关键字的请求进行过滤

char val=‘A’,下面哪个选项正确()
A:free((char *)&val)
B:*((short*)&val)=65
C:*((unsigned char*)&val=’a’
D:delete ((char *)&val)

下面的cache替换的算法中,哪个平均命中率最高()
A:FILO   B:RAND     C:FIFO       D:LRU

剩下的选择题有排序算法、二叉树的中序遍历、进栈出栈顺序、二分搜索的题,比较基础,就不列了。

填空题:
前面两题是数组的元素插入问题和二分搜索非递归实现的程序填空,后面两题如下。

int c[4][5] , (*p)[5] ; p=c; 用p表示c[2][3]____________。(不能出现[])

下面程序运行结果是___________。

#include<stdio.h>
void main()
{
    int i;
    for(i=0;i<3;i++)
    {
        switch(i)
        {
            case 0:printf("%d",i);
            case 2:printf("%d",i);
            default:printf("%d",i);
        }
    }
}

综合题:
一间囚房里关押着两个犯人。每天监狱都会为这间囚房提供一罐汤,让这两个犯人自己来分。起初,这两个人经常会发生争执,因为他们总是有人认为对方的汤比自己的多。后来他们找到了一个两全其美的办法:一个人分汤,让另一个人先选。于是争端就这么解决了。可是后来,这间囚房里又加进来一个新犯人,现在是三个人来分汤。必须寻找一个新的方法来维持他们之间的和平。该怎么办呢?

给定一个整数数组a[0~n-1],试给出一个算法,找出一段连续的数组下标L,L+1,L+2……,M,使得a[L],a[L+1],a[L+2],……,a[M]的和最大,并给出该算法的计算复杂度。

淘宝网有2000台机器提供web访问服务,用户每次访问的信息都会被记录下来,包括用户名、IP、请求 url、响应时间等。现需要每天凌晨2点时要出一份报表,统计一天内平均响应时间最长的100个url,要求报表尽可能快地生成。如何设计这个报表系统?

9 Comments