阿里巴巴秋招在线笔试经验

　　2015阿里秋招在线笔试附加题-数据研发工程师

　　20个选择，有好多行测题，老长一个，读都读晕了，

阿里巴巴秋招在线笔试经验

　　1.给出二叉树的先序遍历为ACDEFHGB，中序遍历DECAHFBG。求后序遍历。

　　答案：EDCHBGFA

　　2.甲，乙玩硬币游戏，分出胜负时停止，出现第一次为正面第二次为反面时甲胜，出现连续两次反面时乙胜，求甲胜的概率。

　　答：假设用A,B表示正反两面。前两次抛硬币可能为AA，AB，BA，BB。概率为1/4，为AB时甲胜，为BB时乙胜。出现AA或BA时继续第三次抛，第三次可能为A或B，概率都为1/2。此时前面两种情况第二次出现的都是A，概率为1/2，故第二次和第三次为AB时甲胜，为AA时继续抛硬币。。。此后甲胜概率都为1/2,以后乙都不可能胜，故乙只能是前两次出现BB的时候胜，概率为1/4，所以甲胜的概率为1-1/4=3/4。

　　3.两趟公家车10分钟一趟，第一辆分钟为2时发车，第二辆分钟为8时发车，求小命上第一辆车的概率。

　　4.鹰策略和鸽子策略

　　。。。。。。

　　附加题

　　第一题：这个就是求最长公共子串。

　　题目：给定一个query和一个text，均由小写字母组成。要求在text中找出以同样的顺序连续出现在query中的最长连续字母序列的长度。例如，query为"acbac"，text为"acaccbabb"，那么text中的"cba"为最长的联系出现在query中的字母序列，因此，返回结果应该为其长度3。请注意程序效率。

　　#include

　　#include

　　#include

　　using namespace std;

　　int LCS(const string &str1,const string &str2)

　　{

　　int xlen=str1.size(); //横向长度

　　vector tmp(xlen); //保存矩阵的上一行

　　vector arr(tmp); //当前行

　　int ylen=str2.size(); //纵向长度

　　int maxele=0; //矩阵元素中的最大值

　　int pos=0; //矩阵元素最大值出现在第几列

　　for(int i=0;i

　　string s=str2.substr(i,1);

　　arr.assign(xlen,0); //数组清0

　　for(int j=0;j

　　if(str1.compare(j,1,s)==0){

　　if(j==0)

　　arr[j]=1;

　　else

　　arr[j]=tmp[j-1]+1;

　　if(arr[j]>maxele){

　　maxele=arr[j];

　　pos=j;

　　}

　　}

　　}

　　tmp.assign(arr.begin(),arr.end());

　　}

　　return maxele;

　　}

　　int main()

　　{

　　strin

　　string text;

　　cin>>query>>text;

　　cout<

　　return 0;

　　}

　　第二题：这个题目我感觉有歧义，是求结点距离最大的`两结点的差值还是指求树中结点最大最小的差值呢?我提交的是最大最小的差值，

资料共享平台

　　题目：写一个函数，输入一个二叉树，树中每个节点存放了一个整数值，函数返回这棵二叉树中相差最大的两个节点间的差值绝对值。请注意程序效率。

　　struct TreeNode

　　{

　　int data;

　　TreeNode *pLeft;

　　TreeNode *pRight;

　　int nMaxLeft;

　　int nMaxRight;

　　};

　　int max=INT_MIN;

　　int min=INT_MAX;

　　int getMax(TreeNode *pRoot)

　　{

　　if (pRoot!=NULL)

　　{

　　if (pRoot->data>max)

　　{

　　max=pRoot->data;

　　}

　　if (pRoot->data

　　{

　　min=pRoot->data;

　　}

　　getMax(pRoot->pLeft);

　　getMax(pRoot->pRight);

　　}

　　return max-min;

　　}

　　第三题：我的想法是一个IP对应一个独立客户。因此首先找出这两个网站的IP，IP出现多次只留一个，然后再求出这两个网站共有的IP数就是所求答案。

　　题目：淘宝网(www.taobao.com)与阿里巴巴网(www.alibaba.com)是阿里巴巴集团下的两个独立网站，假设淘宝网每天的独立访客数载亿以上(以IP计)，阿里巴巴网每天的独立访客数在千万以上(以IP计);这两个网站有各自的浏览日志，记录了访客在本网站上的浏览记录，如IP、访问时间、访问页面的URL等(注：一个IP在某天可能访问多个页面);现有这两个网站某天的浏览日志文件各一份，要计算在该天既访问过淘宝网又访问过阿里巴巴网站的独立访客数大约是多少，请给出你能想到的方案(可多个)。