面試 算法題編程 含答案算

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