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 <iostream>
#include <string>
#include <vector>
using namespace std;
int LCS(const string &str1,const string &str2)
{
int xlen=(); //橫向長度
vector
vector
int ylen=(); //縱向長度
int maxele=0; //矩陣元素中的最大值
int pos=0; //矩陣元素最大值出現在第幾列
for(int i=0;i<ylen;i++){
string s=tr(i,1);
gn(xlen,0); //陣列清0
for(int j=0;j<xlen;j++){
if(are(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;
}
}
}
gn(n(),());
}
return maxele;
}
int main()
{
string query;
string text;
cin>>query>>text;
cout<<LCS(query,text)<<endl;
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數就是所求答案。
題目：淘寶網()與阿里巴巴網()是阿里巴巴集團下的兩個獨立網站，假設淘寶網每天的獨立訪客數載億以上(以IP計)，阿里巴巴網每天的獨立訪客數在千萬以上(以IP計);這兩個網站有各自的瀏覽日誌，記錄了訪客在本網站上的瀏覽記錄，如IP、訪問時間、訪問頁面的URL等(注：一個IP在某天可能訪問多個頁面);現有這兩個網站某天的瀏覽日誌檔案各一份，要計算在該天既訪問過淘寶網又訪問過阿里巴巴網站的獨立訪客數大約是多少，請給出你能想到的方案(可多個)。