阿里的一道在線編程測試題
一道編碼解碼的題目
就是用
0xxxxxxx 表示0-127
10xxxxxx 10xxxxxx 表示128-65535
輸入一個string叫惊，然后讓你來解碼痪欲，明明簡單的很的一道編程題，硬是沒做出來…
感覺自己有點緊張，而且狀態(tài)很差子姜，不過沒關(guān)系原朝，慢慢來吧。
感覺之后有筆試什么的還是在宿舍自習室里做吧灶壶，狀態(tài)應該會好一些。
今天狀態(tài)實在是差杈曲，大腦暈乎乎的做什么測試題呢驰凛，唉，下次注意一點吧担扑。
有點尷尬的是求內(nèi)推的時候稱呼寫錯了恰响，是師妹結(jié)果以為是師兄，尷尬尷尬……
螞蟻金服公司電面
先吐槽一下你這沒什么項目經(jīng)歷啊涌献，挑一個可以的講講吧胚宦。
然后我挑了個本科畢業(yè)設計…確實沒什么可講的，現(xiàn)在想想應該挑資助中心項目的燕垃。然后感覺自己投了一個錯誤的崗位枢劝，或者說沒有根據(jù)這個崗位來寫我的簡歷…
數(shù)據(jù)庫都怎么用？都用了啥數(shù)據(jù)庫利术，了解其他數(shù)據(jù)庫嗎呈野？
HBase MongoDB MySQL Oracle Redis
關(guān)系型數(shù)據(jù)庫：關(guān)系模型指的就是二維表格模型，而一個關(guān)系型數(shù)據(jù)庫就是由二維表及其之間的聯(lián)系所組成的一個數(shù)據(jù)組織
非關(guān)系型數(shù)據(jù)庫：以鍵值對存儲印叁，且結(jié)構(gòu)不固定被冒，每一個元組可以有不一樣的字段，每個元組可以根據(jù)需要增加一些自己的鍵值對轮蜕，這 樣就不會局限于固定的結(jié)構(gòu)昨悼，可以減少一些時間和空間的開銷。
適合存儲一些較為簡單的數(shù)據(jù)
結(jié)構(gòu)化查詢語言（Structured Query Language）
- 關(guān)系型數(shù)據(jù)庫 V.S. 非關(guān)系型數(shù)據(jù)庫
關(guān)系型數(shù)據(jù)庫的最大特點就是事務的一致性：傳統(tǒng)的關(guān)系型數(shù)據(jù)庫讀寫操作都是事務的跃洛，具有ACID的特點率触，這個特性使得關(guān)系型數(shù)據(jù)庫可以用于幾乎所有對一致性有要求的系統(tǒng)中，如典型的銀行系統(tǒng)汇竭。
但是葱蝗，在網(wǎng)頁應用中穴张，尤其是SNS應用中，一致性卻不是顯得那么重要两曼，用戶A看到的內(nèi)容和用戶B看到同一用戶C內(nèi)容更新不一致是可以容忍的皂甘，或者 說，兩個人看到同一好友的數(shù)據(jù)更新的時間差那么幾秒是可以容忍的悼凑，因此偿枕，關(guān)系型數(shù)據(jù)庫的最大特點在這里已經(jīng)無用武之地，起碼不是那么重要了户辫。
相反地渐夸，關(guān)系型數(shù)據(jù)庫為了維護一致性所付出的巨大代價就是其讀寫性能比較差，而像微博渔欢、facebook這類SNS的應用墓塌，對并發(fā)讀寫能力要求極 高，關(guān)系型數(shù)據(jù)庫已經(jīng)無法應付(在讀方面奥额，傳統(tǒng)上為了克服關(guān)系型數(shù)據(jù)庫缺陷桃纯，提高性能，都是增加一級memcache來靜態(tài)化網(wǎng)頁披坏，而在SNS中，變化太 快盐数，memchache已經(jīng)無能為力了)棒拂，因此，必須用新的一種數(shù)據(jù)結(jié)構(gòu)存儲來代替關(guān)系數(shù)據(jù)庫玫氢。
關(guān)系數(shù)據(jù)庫的另一個特點就是其具有固定的表結(jié)構(gòu)帚屉，因此，其擴展性極差漾峡，而在SNS中攻旦，系統(tǒng)的升級，功能的增加生逸，往往意味著數(shù)據(jù)結(jié)構(gòu)巨大變動牢屋，這一點關(guān)系型數(shù)據(jù)庫也難以應付，需要新的結(jié)構(gòu)化數(shù)據(jù)存儲槽袄。
于是烙无，非關(guān)系型數(shù)據(jù)庫應運而生，由于不可能用一種數(shù)據(jù)結(jié)構(gòu)化存儲應付所有的新的需求遍尺，因此截酷，非關(guān)系型數(shù)據(jù)庫嚴格上不是一種數(shù)據(jù)庫，應該是一種數(shù)據(jù)結(jié)構(gòu)化存儲方法的集合乾戏。
必須強調(diào)的是迂苛，數(shù)據(jù)的持久存儲三热，尤其是海量數(shù)據(jù)的持久存儲，還是需要一種關(guān)系數(shù)據(jù)庫這員老將三幻。
問我申請內(nèi)存這些用的多不多…我說不多就漾。
問我分布式有啥經(jīng)歷沒…我說沒有。
問我多進程多線程的用的多不多…我說不多赌髓。
問我啥了我忘了…
問我進程和線程的區(qū)別…
然后問了兩道題
- 兩個數(shù)組从藤，一個有1000萬，一個有100萬锁蠕，求交集夷野。
我答了哈希，然后讓我再想想荣倾，也沒想出啥來悯搔。 - 一個數(shù)組，求有多少個不同的數(shù)及其數(shù)目舌仍。
我答了哈希妒貌，然后讓我再想想，我想了想說排序再遍歷铸豁。沒了…
我覺得自己弱爆了…
然后晚上和師兄聊了聊灌曙，發(fā)現(xiàn)自己還是得多學習！
3.13 小米公司
一個數(shù)节芥，如何求根號數(shù)在刺，不能調(diào)用系統(tǒng)函數(shù)，我說用二分头镊，先設一個初始值蚣驼，然后比較其平方和該數(shù)的大小，然后繼續(xù)搜索對比相艇。
注意先判斷數(shù)是大于1還是小于1颖杏。一個字符串，由一些單詞組成坛芽，間隔符是空格留储，然后將其反轉(zhuǎn)。
我想了想咙轩，leetcode做過欲鹏，只要先把整個反轉(zhuǎn)，然后再把里面的每個word反轉(zhuǎn)一下就可以了臭墨。一個系統(tǒng)赔嚎，有一大堆的定時任務。
每個任務包括開始時間、周期以及回調(diào)函數(shù)尤误。
然后問你怎么更有效率的執(zhí)行侠畔。
我說用哈希，直接存儲時間损晤，key是時間软棺，value是任務的id。然后結(jié)束之后把這個map銷毀掉尤勋，新建一個周期之后的map喘落。
問了下操作系統(tǒng)任務是怎么調(diào)度的，說隊列最冰，隊列是用什么數(shù)據(jù)結(jié)構(gòu)實現(xiàn)的瘦棋。一個100萬數(shù)字的數(shù)組，數(shù)字范圍0-999999暖哨。讓你找里面重疊的數(shù)字赌朋。
我說了哈希，說了排序篇裁，然后沒想到O(1)空間沛慢，O(n)時間來做的方法。
然后提示了說用位圖达布，沒聽說過…
然后后來想了想团甲，可以直接把數(shù)值i調(diào)換到i位置，假如i位置原值是i的話黍聂，那么i就是重復的伐庭。
看了下位圖，差不多就是這個意思分冈，就比如說{1,1,1,0,1,0,1,1}來表示{3,5,7,8,2,1}的排序結(jié)果
想想這一類的題目做的也不少了，就是說用原有空間來替代哈希所需要的空間０灾辍５癯痢！
網(wǎng)易游戲公司電面去件，在線視頻面試
首先問了之前在線筆試中沒有做出來的題目的想法和思路坡椒，NTES那道題目。
然后問哪種語言比較熟悉…我說C++尤溜，然后換了個哥們問我C++倔叼。
然后我就傻逼了，啥都不會啊臥槽宫莱。
- 問四種轉(zhuǎn)換操作符有什么區(qū)別
- static_cast
最常用的類型轉(zhuǎn)換符丈攒，在正常狀況下的類型轉(zhuǎn)換，如把int轉(zhuǎn)換為float，如：int i巡验；float f际插； f=（float）i；或者f=static_cast<float>(i);
- const_cast
用于取出const屬性显设，把const類型的指針變?yōu)榉莄onst類型的指針框弛，如：const int *fun(int x,int y){} int *ptr=const_cast<int *>(fun(2.3))
- dynamic_cast
該操作符用于運行時檢查該轉(zhuǎn)換是否類型安全，但只在多態(tài)類型時合法捕捂，即該類至少具有一個虛擬方法瑟枫。dynamic_cast與static_cast具有相同的基本語法，dynamic_cast主要用于類層次間的上行轉(zhuǎn)換和下行轉(zhuǎn)換指攒，還可以用于類之間的交叉轉(zhuǎn)換慷妙。在類層次間進行上行轉(zhuǎn)換時，dynamic_cast和static_cast的效果是一樣的幽七；在進行下行轉(zhuǎn)換時景殷，dynamic_cast具有類型檢查的功能，比static_cast更安全澡屡。如：
class C
{
//…C沒有虛擬函數(shù)
}猿挚；
class T : public C {
//…
}
int main()
{
dynamic_cast<T*> (new C);//錯誤
}
此時如改為以下則是合法的：
class C
{
public:
virtual void m() {};// C現(xiàn)在是 多態(tài)
}
- reinterpret_cast
interpret是解釋的意思，reinterpret即為重新解釋驶鹉，此標識符的意思即為數(shù)據(jù)的二進制形式重新解釋绩蜻，但是不改變其值。如：int i; char *ptr="hello freind!"; i=reinterpret_cast<int>(ptr);這個轉(zhuǎn)換方式很少使用室埋。 - 問多態(tài)的實現(xiàn)
我說用虛函數(shù)實現(xiàn)办绝，通過基類指針來調(diào)用派生類。 - 以對象管理資源的好處
我說了有利于資源的釋放姚淆。 - 讓寫string的構(gòu)造函數(shù)孕蝉，拷貝函數(shù)和賦值運算
完全不會…
class String
{
public:
String(const char *str = NULL);
String(const String &other);
~String(void);
String & operator = (const String &other);
private:
char *m_data;
};
String::String(const char *str) //構(gòu)造函數(shù)
{
if (str == NULL) {
m_data = new char[1];
*m_data = '\0';
}
else {
auto length = strlen(str);
m_data = new char[length + 1];
strcpy(m_data, str);
}
}
String::~String() {
delete [] m_data;
}
String & String::operator=(const String &other)
{
if (this == &other)
return *this;
delete [] m_data;
auto length = strlen(other.m_data);
m_data = new char[length+1];
strcpy(m_data, other.m_data);
return *this;
}
String::String(const String &other) //拷貝構(gòu)造函數(shù)
{
auto length = strlen(other.m_data);
m_data = new char[length + 1];
strcpy(m_data, other.m_data);
}
- 寫sqrt(n)
這個比較好寫。 - 是否了解一些比較前沿的技術(shù)腌逢。
我說了解一些降淮，比如新的非關(guān)系型數(shù)據(jù)庫啊，Hbase之類的搏讶，看看博客啊之類的… - 讓說一下項目中印象最深佳鳖，啟發(fā)最大的事情。
我說了懷教那個項目媒惕，和別人之間的溝通…完全在瞎扯淡… - 聊了下最后一個項目系吩。
這個聊了比較多。
最后還是慣例看有沒有什么問題問他妒蔚。
我就問了工作內(nèi)容工作職責啥的穿挨，沒有問太多東西月弛。
主要用python，會用一些C++絮蒿。
今日頭條公司當面面試
- const和static的區(qū)別以及基本用法尊搬。
static作用：“改變生命周期” 或者 “改變作用域”
- 作用于變量：
用static聲明局部變量，使其變?yōu)殪o態(tài)存儲方式(靜態(tài)數(shù)據(jù)區(qū))土涝，作用域不變矢否；用static聲明外部變量骇两，其本身就是靜態(tài)變量，這只會改變其連接方式，使其只在本文件內(nèi)部有效醉者，而其他文件不可連接或引用該變量麸锉。 - 作用于函數(shù)：
使用static用于函數(shù)定義時烂瘫，對函數(shù)的連接方式產(chǎn)生影響黔夭，使得函數(shù)只在本文件內(nèi)部有效，對其他文件是不可見的溯祸。這樣的函數(shù)又叫作靜態(tài)函數(shù)肢专。使用靜態(tài)函數(shù)的好處是，不用擔心與其他文件的同名函數(shù)產(chǎn)生干擾焦辅，另外也是對函數(shù)本身的一種保護機制博杖。
如果想要其他文件可以引用本地函數(shù)，則要在函數(shù)定義時使用關(guān)鍵字extern筷登，表示該函數(shù)是外部函數(shù)剃根，可供其他文件調(diào)用。另外在要引用別的文件中定義的外部函數(shù)的文件中前方，使用extern聲明要用的外部函數(shù)即可狈醉。
const作用: “只讀(readonly)”
- 定義常量
(1)const
修飾變量，以下兩種定義形式在本質(zhì)上是一樣的惠险。它的含義是：const修飾的類型為TYPE的變量value是不可變的,readonly苗傅。
TYPE const ValueName = value;
const TYPE ValueName = value;
(2)將const改為外部連接,作用于擴大至全局,編譯時會分配內(nèi)存,并且可以不進行初始化,僅僅作為聲明,編譯器認為在程序其他地方進行了定義.
extend const int ValueName = value; - 指針使用CONST
(1) 指針本身是常量不可變
char * const pContent;
const (char*) pContent; ???
(2) 指針所指向的內(nèi)容是常量不可變
const char *pContent;
char const *pContent;
(3) 兩者都不可變
const char* const pContent;
(4) 還有其中區(qū)別方法，沿著*號劃一條線：如果const位于*的左側(cè)班巩，則const就是用來修飾指針所指向的變量渣慕，即指針指向為常量；如果const位于*的右側(cè)趣竣，const就是修飾指針本身，即指針本身是常量旱物。sdfs - 函數(shù)中使用CONST
(1) const修飾函數(shù)參數(shù)
a. 傳遞過來的參數(shù)在函數(shù)內(nèi)不可以改變(無意義遥缕，因為Var本身就是形參)
void function(const int Var);
b. 參數(shù)指針所指內(nèi)容為常量不可變
void function(const char* Var);
c. 參數(shù)指針本身為常量不可變(也無意義，因為char* Var也是形參)
void function(char* const Var);
d. 參數(shù)為引用宵呛，為了增加效率同時防止修改单匣。修飾引用參數(shù)時：
void function(const Class& Var); //引用參數(shù)在函數(shù)內(nèi)不可以改變
void function(const TYPE& Var); //引用參數(shù)在函數(shù)內(nèi)為常量不可變
這樣的一個const引用傳遞和最普通的函數(shù)按值傳遞的效果是一模一樣的,他禁止對引用的對象的一切修改,唯一不同的是按值傳遞會先建立一個類對象的副本, 然后傳遞過去,而它直接傳遞地址,所以這種傳遞比按值傳遞更有效.另外只有引用的const傳遞可以傳遞一個臨時對象,因為臨時對象都是const屬性, 且是不可見的,他短時間存在一個局部域中,所以不能使用指針,只有引用的const傳遞能夠捕捉到這個家伙.
(2) const 修飾函數(shù)返回值
const修飾函數(shù)返回值其實用的并不是很多，它的含義和const修飾普通變量以及指針的含義基本相同。
a. const int fun1() //這個其實無意義户秤，因為參數(shù)返回本身就是賦值码秉。
b. const int * fun2() //調(diào)用時
const int *pValue = fun2(); //我們可以把fun2()看作成一個變量，即指針內(nèi)容不可變鸡号。
c. int* const fun3() //調(diào)用時
int * const pValue = fun2(); //我們可以把fun2()看作成一個變量转砖，即指針本身不可變。
內(nèi)存分配的使用場景
一個數(shù)組求重復數(shù)字的問題鲸伴，老問題府蔗。
給一個數(shù)組，求其前k大的元素汞窗。
可以用快速排序姓赤，找出前k大的，然后再對那一堆進行排序仲吏。給一堆字符串集合不铆，假如兩個集合有一樣的元素則把兩個合并。
基礎知識還是太弱裹唆，然后人不夠open誓斥！下次面試不要這么拘謹！好好準備一下自我介紹吧品腹！然后結(jié)束的時候記得問下面試官有什么建議岖食，然后討論下之前問的題目！
HULU公司面試
一面
先扯項目扯了會舞吭，然后問了倆題
1.一個篩子 怎么將40個人隨機分成4組泡垃，每組10人
2.一個長度為n字符串，只包含a和b羡鸥，問有多少種有循環(huán)節(jié)的情況
第二題寫代碼
二面
扯了會項目蔑穴，問一些設計方面的，比如一個非技術(shù)公司想讓你設計開發(fā)官網(wǎng)惧浴，怎么搞
扯了挺久怎么搞怎么搞…
讓寫了道題存和，
sqrt，精確到k位小數(shù)點
微軟面試
一面
問兩個有序數(shù)組衷旅，如何確定其中位數(shù)捐腿，拓展一下，如何求第k大柿顶。
用二分的方法來做茄袖。
二面
問了下給定n個數(shù)，如何隨機的取其中k個數(shù)嘁锯。
假如不知道一共有多少個數(shù)字宪祥，怎么隨機取聂薪。
然后問了下docker和虛擬機的區(qū)別，然后問了下海量圖數(shù)據(jù)的管理與挖掘課程都講了啥…
- Docker源自Linux核心的系統(tǒng)層功能蝗羊，如控制資源的控制群組機制cgroups藏澳、命名空間Namespaces，還有實現(xiàn)層級化功能的共通檔案系統(tǒng)AUFS等耀找。
Windows系統(tǒng)的docker翔悠，微軟為了docker特意實現(xiàn)了幾種系統(tǒng)層機制。
Namespace解決的問題主要是環(huán)境隔離的問題
Linux CGroup解決對計算機資源使用上的隔離 - 海量圖數(shù)據(jù)的管理與挖掘主要講了一些數(shù)據(jù)挖掘有關(guān)的算法涯呻，講了一些老的算法以及比較新的一些paper提出的算法凉驻，比如
- 頻繁模式挖掘，在一個數(shù)據(jù)集中頻繁出現(xiàn)的模式(一些項复罐、子序列涝登、子結(jié)構(gòu)等)
應用：銷售記錄里的啤酒與尿布，牛奶與面包效诅。Apriori算法胀滚，例子見這里。
1）支持度：表示某個item集合在數(shù)據(jù)表中出現(xiàn)的比例乱投。
2）K-項候選集：由K-1項頻繁集組合而成咽笼，支持度大于等于指定支持度的含有K個項的集合，供計算K項頻繁集使用戚炫。
3）K-項頻繁集：支持度大于等于指定支持度的含有k個項的集合剑刑，由K項候選集計算而得。 - 圖上的可達性問題研究
- 挖掘網(wǎng)絡上的最大影響力節(jié)點（比如說推廣手機的預算是100萬元双肤，預計每個新浪博主的宣傳費是1萬元施掏，如何利用這100萬元預算，使這款手機在新浪微博上的推廣效果最好?）
- 頻繁模式挖掘，在一個數(shù)據(jù)集中頻繁出現(xiàn)的模式(一些項复罐、子序列涝登、子結(jié)構(gòu)等)
三面
問了倆題茅糜，一道是求字符串中最長不重復子串七芭，然后擴展下，怎么求可以有一個字母重復兩次的蔑赘。
另一道是說一個矩陣狸驳，矩陣數(shù)值表示高度，問一個球從高處往低處最多能降低多少缩赛。
宜信大數(shù)據(jù)面試
被虐翻了…問了許多基礎知識各種不會
問如何刪除鏈表里的重復元素耙箍。
多態(tài)的實現(xiàn)
一般繼承及多重繼承看這里
菱形繼承看這里
哈希表是如何實現(xiàn)的
哈希表類項中必須存儲key，因為碰撞的存在酥馍，往往不能夠通過散列函數(shù)直接得到地址辩昆，還需要進一步的判斷，因此列表項中需要存儲key值物喷。
解決hash沖突的辦法
- 開放定址法（線性探測再散列卤材，二次探測再散列，偽隨機探測再散列）
- 再哈希法
- 鏈地址法
- 建立一個公共溢出區(qū)
面向?qū)ο笳Z言的特性
多態(tài)和繼承
問各種排序算法峦失，詳細的可以看看這里扇丛。
- 冒泡排序
它重復地走訪過要排序的數(shù)列，一次比較兩個元素尉辑，如果他們的順序錯誤就把他們交換過來帆精，直到?jīng)]有任何一對數(shù)字需要交換。 - 選擇排序
在未排序序列中找到最兴砥恰（大）元素卓练，存放到排序序列的起始位置。
再從剩余未排序元素中繼續(xù)尋找最泄鹤摹（大）元素襟企，然后放到已排序序列的末尾。
以此類推狮含，直到所有元素均排序完畢 - 插入排序
插入排序的工作原理是顽悼，對于每個未排序數(shù)據(jù)，在已排序序列中從后向前掃描几迄，找到相應位置并插入蔚龙。 - 希爾排序
希爾排序，也稱遞減增量排序算法映胁，實質(zhì)是分組插入排序木羹。 - 歸并排序
歸并排序的思想就是先遞歸分解數(shù)組，再合并數(shù)組解孙。 - 快速排序
“挖坑填數(shù)+分治法”坑填，
首先令i =L; j = R; 將a[i]挖出形成第一個坑，稱a[i]為基準數(shù)妆距。
然后j--由后向前找比基準數(shù)小的數(shù)穷遂，找到后挖出此數(shù)填入前一個坑a[i]中，再i++由前向后找比基準數(shù)大的數(shù)娱据，找到后也挖出此數(shù)填到前一個坑a[j]中蚪黑。
重復進行這種“挖坑填數(shù)”直到i==j。再將基準數(shù)填入a[i]中中剩，這樣i之前的數(shù)都比基準數(shù)小忌穿，i之后的數(shù)都比基準數(shù)大。
因此將數(shù)組分成二部分再分別重復上述步驟就完成了排序结啼。 - 堆排序
堆排序是采用二叉堆的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)的掠剑，雖然實質(zhì)上還是一維數(shù)組。二叉堆是一個近似完全二叉樹 郊愧。
智力題：一排犯人朴译，1井佑，2，3眠寿，4躬翁，5，前面的可以看到后面人身上穿的衣服盯拱，有紅黑兩種盒发，不能看到自己的。從1開始報自己身上衣服顏色狡逢，報對了活宁舰，報錯了槍斃。犯人們可以提前商量好奢浑，問如何報使得犯人死的最少蛮艰。
測試工具：apache ab
測試一般要考慮一下幾點：
Thoughput吞吐量，Latency響應時間雀彼，資源利用（CPU/MEM/IO/Bandwidth…）印荔，成功率，系統(tǒng)穩(wěn)定性
這次測試屬于局域網(wǎng)環(huán)境進行详羡，排除了外網(wǎng)的網(wǎng)速限制及不穩(wěn)定性
延遲在1s左右仍律，然后大概能夠支持的并發(fā)用戶數(shù)量大概是
反正都在扯淡…
滴滴新銳計劃面試
一共三面
感覺沒問什么c++基礎題，就主要問了問項目实柠，出了幾道簡單算法題讓你寫
一面：
扯項目水泉，讓寫個鏈表去重
二面：
扯項目，
給一堆元素窒盐，假如一個元素大于另一個元素的兩倍草则，則能組成一對，問最多能有多少對蟹漓。
想了想炕横，只能想到暴力方法…然后換了道簡單的。
一個三角形的數(shù)組葡粒，如下
[1]
[2, 3]
[3, 4, 5]
[6, 4, 6, 3]
問從最頂端到最底端數(shù)值和最小是多少份殿。每個元素只能和上下層的相鄰元素連接，比如說第三層的4可以和第二層的2嗽交，3連接卿嘲，第三層的3只可以和第二層的2連接。一道簡單的dp題夫壁。
三面：
又扯項目拾枣，感覺現(xiàn)在扯項目扯的很溜了。然后讓寫鏈表反轉(zhuǎn)…
然后就結(jié)束了。
