腾讯2014实习生招聘笔试

tencentInternship2014.md

腾讯2014实习生笔试

1、有四个人，四顶帽子，两个黑色，两个白色，说出自己帽子颜色的释放，否则死亡，每个人只能看前方不能看后方,位置如下：

	>W	
<B	|	>B
|	|	|	>W
|	|	|	|
A	B	C	D

释放的是C，因为A看不到任何人，他不敢说，B不确定自己帽子的颜色，因为前两个一个黑色一个白色，C过了好久看到B不说，肯定是C和D不一样，那么C说出自己的是黑色

2、服务器返回码

HTTP协议状态码表示的意思主要分为五类 ,大体是 :  
~~~~~~~~~~~~~~~~~~~~~~~~~~~~  
1×× 　　保留   
2×× 　　表示请求成功地接收   
3×× 　　为完成请求客户需进一步细化请求   
4×× 　　客户错误   
5×× 　　服务器错误   

Redirection 
==================================
300 Multiple Choices
请求资源符合任何一个呈现方式。

301 Moved Permanently 
请求的资源已经被赋予一个新的URI。

302 Found 
通过不同的URI请求资源的临时文件。
303 See Other

304 Not Modified 
如果客服端已经完成一个有条件的请求并且请求是允许的，但是这个文档并没有改变，服务器应该返回304状态码。304
状态码一定不能包含信息主体，从而通常通过一个头字段后的第一个空行结束。

305 Use Proxy
请求的资源必须通过代理（由Location字段指定）来访问。Location资源给出了代理的URI。

3、利用概率法求π

随机生成位于[-1,1]的点，然后统计 x*x+y*y<1 的点的个数a，然后4*(a/4)

圆的面积是πr*r = π，4等于圆的外接正方形的面积，所以 a/4 =π/4，所以本题求π

4、根据给定的JSON描述double数的形式写出 bool ParseNumber(const char* s,double& value)函数

	bool ParseNumber(const char* s,double &value)
	{   int i,sign,exp;
	    double power;
		char* INVLID_TAG="0.0";
		if(strcmp(s,INVLID_TAG)==0)
		{
			value=0;
			return true;
		}
	    for(i=0;isspace(s[i]);++i)
		{
	        /*do nothing*/;
		}
		//sign
	    sign=(s[i]=='-')?-1:1;
	    if(s[i] == '+' || s[i] == '-')
		{
	        i++;
		}
		if(s[i] == '0' && s[i+1] != '.')
		{
			value=0.0;
			return false;
		}
	    for(value=0.0;isdigit(s[i]);++i)
		{
	        value=value*10.0+(s[i]-'0');
		}
	    if(s[i]=='.')
		{
	        i++;
		}
	    for(power=1.0;isdigit(s[i]);++i)
	    {   value=value*10.0+(s[i]-'0');
	        power*=10.0;
	    }
	    value=sign*value/power;
		//exp
	    if(s[i] == 'e'|| s[i] == 'E')
	    {   
			i++;
	        sign=(s[i]=='-')?-1:1;
	        if(s[i] == '+'||s[i] == '-')
			{
	            i++;
			}
	        for(exp=0;isdigit(s[i]);++i)
			{
	            exp=exp*10.0+(s[i]-'0');
			}
	        if(sign==-1)
			{
	            while(exp-->0)
				{
	                value/=10;
				}
			}else{
	            while(exp-->0)
				{
	                value*=10;
				}
			}
	    }
		if(value == 0)
		{
			return false;
		}else
		{
			return true;
		}
	}

5、最大连续矩形面积问题

宽度相等的矩形，求最大的连续矩形面积

|						-----
|----			-----	|	|
|	|---		|	|	|	|
|	|	|		|	|---|	|
|	|	|		|	|	|	|
|	|	|		|	|	|	|
---------------------------------------------

分析

先前的腾讯笔试附加题，答错了，再写一遍

R(i,j)表示从i到j之间的最大面积，那么，肯定有h(i)>h(i-1),h(j)>h(j+1)

为此维护一个left数组，left[i]表示第i个矩形向左最多能延伸到第left[i]个矩形 同理，维护right数组

如果h[left[i]-1]>=h[i],我们可以直接跳到left[left[i]-1]，而不用再去和h[left[left[i]-1]+1],h[left[left[i]-1]+2]...h[left[i]-1]去比较

因为，我们维护的这个数组中，始终满足h[left[i]]>=h[left[i]+1]>=h[left[i]+2]>=...h[i],

且h[left[left[i]-1]]>=...>=h[left[i]-1]>=h[left[i]>=...>=h[i]，这个中间的每个数都是单调非递增的

代码

	int maxArea(vector<int>& h){
		//placeholder
		h[0]=h[n+1]=-1;
		int ans=0; 
		//init
		for(i=1;i<=n;i++){
			Left[i]=i;
			while(h[Left[i]-1]>=h[i]){
				Left[i]=Left[Left[i]-1];
			}
		}
		for(i=n;i>=1;i--){
			Right[i]=i;
			while(h[Right[i]+1]>=h[i]){
				Right[i]=Right[Right[i]+1];
			}
		}
		for(i=1;i<=n;i++){
			ans=max(ans,h[i]*(Right[i]-Left[i]+1));
		}
		return ans;
	}