面试题目搜集（5）

本博客的《面试题目搜集系列不错》

（1）面试题目搜集1

（2）面试题目搜集2

（3）面试题目搜集3

（4）面试题目搜集4

（5）面试题目搜集5

（6）面试题目搜集6

1.反着打印链表（递归实现）

#include<iostream>
#include <cstdio>
using namespace std;

typedef int Elem;

struct ListNode{
	Elem nData;
	ListNode *pNext;
	ListNode(int data,ListNode *next=NULL):nData(data),pNext(next){}
};

void PrintReverseList(ListNode *root)
{
	if(!root)
		return;
	PrintReverseList(root->pNext);
	cout<<root->nData<<" ";
};
int main()
{	
	ListNode *list3 = new ListNode(3,NULL);
	ListNode *list2 = new ListNode(2,list3);
	ListNode *list1 = new ListNode(1,list2);
    ListNode *pHead = new ListNode (0,list1);

	PrintReverseList(pHead);
	system("pause");
	return 0;
}

2.求最大连续字符串 （如“ ads3s1456789DF3456ld345AA ”，结果为“456789”）

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

typedef int StartIndex;
typedef int StrLenght;
typedef pair<StartIndex,StrLenght> Result;

Result FindContinuousSubStr(const string& str)
{
	int start = 0;
	int maxLen = 1;
	int length = 1;

	for(int i=1; i<str.size();++i){
		if(str[i] == str[i-1] + 1){
			++length;
		}
		else{
			if(length > maxLen){
				maxLen = length;
				start = i - length;
			}
			length = 1;
		}
	}

	return make_pair(start,maxLen);
}

int main()
{
	string str = "ads3s1456789DF3456ld345AA";
	Result ret = FindContinuousSubStr(str);

	for(int i=0; i<ret.second; ++i){
		cout<<str[ret.first+i];
	}

	system("pause");
	return 0;
}

3.编写CString类

class CString{
public:
	CString(const char *pStr = NULL){
		if(pStr == NULL){
			pData = new char;
			*pData = '\0';
		}
		else{
			pData = new char[strlen(pStr)+1];
			assert(pData != NULL);
			strcpy(pData,pStr);
		}
	}
	CString(const CString& other){
		pData = new char[strlen(other.pData)+1];
		assert(pData != NULL);
		strcpy(pData,other.pData);
	}
	CString& operator=(const CString& other){
		if(&other == this){
			CString strTemp(other);

			char *pTemp = strTemp.pData;
			strTemp.pData = pData;
			pData = pTemp;
		}
		return *this;
	}
	~CString(){
		if(!pData)
			delete[] pData;
	}
private:
	char *pData;
};

4.百度的一道笔试题目： 下面这段代码是把中英文混合字符串(汉字用两个字节表示，特点是第一个字节的最高位为1)中的大写字母转化为小写字母，请找出其中的bug，注意各种异常情况。 
for (char *piterator = szWord; *piterator != 0; piterator++) 
{ 
if (*piterator & 0x80 != 0) 
{ 
piterator++; 
} 
else if (*piterator >= 'A' && *piterator <= 'Z') 

piterator += 32; 

} 

上面有两个bug，答案更正如下：

#include <iostream>

using namespace std;

void Convert(char *szWord)
{
	for (char *piterator = szWord; *piterator != '\0'; piterator++) 
		if ((*piterator & 0x80) != 0) 
				piterator++;
		else if (*piterator >= 'A' && *piterator <= 'Z') 	
				*piterator += 32; 

	cout<<szWord<<endl;
}


int main()
{
	char str[] = "我是LSJ,请把我ZHUANHuan为小XIE";
	Convert(str);
	system("pause");
	return 0;
}

5.百度2012年实习得一道招聘题目。

        相信大家都使用过百度搜索框的suggestion功能(如下图所示)。百度搜索框中的suggestion提示功能如何实现的？请给出实现思路和主要的数据结构、算法。有什么优化思路可以使得时间和空间效率最高？
如下图所示：

答：统计搜索引擎查询日志，统计各个查询词出现的次数。然后统计查询串中可能出现的各个前缀子串，然后统计以各个前缀子串开头的查询串的频率。对各个子串，取以其作为前缀的前K个最高频查询串。再以各个子串为KEY，建立倒排索引(或trie树)。定期更新倒排索引(或trie树)，即可依据查询频率给出一个比较合理的提示内容。当用户输入时，去倒排索引(或trie树)中进行匹配，然后取其出现频率最高的前K个。

注：应用字典树来求前缀和TOP K对热词进行统计排序，求前缀用trie树（o（nle），le表示字符串的平均长度）

6.析构函数不能抛出异常

（1）构造函数可以抛出异常。

（2）c++标准指明析构函数不能、也不应该抛出异常。

more effective c++关于第2点提出两点理由：

1）如果析构函数抛出异常，则异常点之后的程序不会执行，如果析构函数在异常点之后执行了某些必要的动作比如释放某些资源，则这些动作不会执行，会造成诸如资源泄漏的问题。

2）通常异常发生时，c++的机制会调用已经构造对象的析构函数来释放资源，此时若析构函数本身也抛出异常，则前一个异常尚未处理，又有新的异常，会造成程序崩溃的问题。

解决办法：

1）永远不要在析构函数抛出异常。

2）通常第一点有时候不能保证。可以采取如下的方法：

~ClassName()

{

  try{

      do_something();

  }

  catch(){  //这里可以什么都不做，只是保证catch块的程序抛出的异常不会被扔出析构函数之外。

   }

}