面試 算法題編程 含答案算

面試算法題編程含答案算1、在不借助第三個變量的情況下，把兩個int的變量X、Y的值互換，用任何自己熟悉的編程語言完成參考答案：思路如下X=X+Y;Y=X-Y;X=X-Y;具體編程語言完成情況由面試官檢查?？疾禳c：基本算法、語言基礎(chǔ)。2、文件查找優(yōu)化背景：百度每天都有大量搜索，如果有一個大文本文件（保存各種詞語），每次搜索都必須要檢查查詢詞是否在這個大文件中，請問有什么方式能夠提高查找效率要求：先講解所使用的算法，然后用自己最熟悉的編程語言，在3分鐘內(nèi)予以實現(xiàn)參考答案：基本方法：采用hash簽名，提高匹配效率；建立多叉樹保存文件數(shù)據(jù)，提高查找速度。如有列舉出更多簽名算法或更好數(shù)據(jù)結(jié)構(gòu)形式，可加分較優(yōu)方法：在上面基礎(chǔ)上，將文本文件轉(zhuǎn)化為key->value的二進(jìn)制文件，提高文件操作和查找速度更優(yōu)方法：在上面基礎(chǔ)上，開辟內(nèi)存做cache，保存高頻率查詢詞，提高整體查找效率。如能完整給出cache的更新機制，加分；考察點：基本數(shù)據(jù)結(jié)構(gòu)；靈活采取算法處理實際問題的能力；快速編程能力；在給出一定提示情況下，檢查學(xué)習(xí)能力和知識應(yīng)用能力。4、有一份成績單，只有兩個字段：姓名、成績；數(shù)據(jù)量在百萬級別。要求用最優(yōu)的數(shù)據(jù)存儲方式，能通過姓名快速查找出成績。（5分鐘）參考答案:存儲方式采用對姓名做hash?？疾禳c：數(shù)據(jù)結(jié)構(gòu)5、找出單向鏈表的中間節(jié)點參考答案：link*mid(link*head){link*p1,*p2;p1=p2=head;if(head==NULL||head->next==NULL)returnhead;do{p1=p1->next;p2=p2->next->next;}while(p2&&p2->next);returnp1;}考察點：算法基礎(chǔ)——鏈表6、給定43億個32位整數(shù)的順序文件，請問如何可以找到一個至少出現(xiàn)兩次的整數(shù)？考察：算法相關(guān)(10min)參考答案：用二分查找發(fā)。細(xì)節(jié)點：43億大于int的最大值，說明肯定有重復(fù)的數(shù)字7、如何判斷一個單鏈表是有環(huán)的（不能用標(biāo)志位，最多只能用兩個額外指針）（6分鐘）考察點：算法及數(shù)據(jù)結(jié)構(gòu)參考答案：可以只給出算法思路，一種O（n）的辦法就是（兩個指針，一個每次遞增一步，一個每次遞增兩步，如果有環(huán)的話兩者必然重合，反之亦然）structnode{charval;node*next;}boolcheck(constnode*head){}//returnfalse:無環(huán)；true:有環(huán)boolcheck(constnode*head){if(head==NULL)returnfalse;node*low=head,*fast=head->next;while(fast!=NULL&&fast->next!=NULL){low=low->next;fast=fast->next->next;if(low==fast)returntrue;}returnfalse;}8、有一個一維數(shù)組inta[100]，里面存儲的是1到100的這100個數(shù)，不過是亂序存儲；這時把其中某一位置的數(shù)值改成-1；請用最優(yōu)的空間復(fù)雜性和時間復(fù)雜性求出該位置和值（6分鐘）參考答案：遍歷一遍數(shù)組得到-1的位置并記錄