姓名手機電子郵件
學校專業
答題說明:
1、每個題型有兩道備選題,可以自行選擇其中一道題進行回答;
2、請深入思考你選擇的問題,方法不會只有一種,請盡情發揮,充分展示你的才華;
3、解決問題是一門權衡的藝術,如果有可能,請說明你的考慮;
4、所有答案請寫在答題紙上;
一、程式設計題(1)
編寫乙個簡單的支援正規表示式的字串匹配函式。簡單的正規表示式如下:
字元含義
c 匹配字元c
. 匹配任意乙個字元
* 若乙個字元後緊跟*,則匹配0個或多個此字元
函式原型定義如下, 引數regexp是待匹配的正則字串,text是原始字串。如果text中包含該正則串,函式返回1,否則0。建議先寫明解題思路,再編碼。
int match(const char *regexp, const char *text);
例如:regexp:c* test:ccccc 返回1
regexp: a.*d text:abcd 返回1
regexp:a* text:abcd 返回1
regexp:a* text:bbcd 返回0
程式設計題( 2)
判斷字串b的所有字元是否都在字串a中出現過,a、b都是可能包含漢字的字串。b中重複出現的漢字,那麼a中也要至少重複相同的次數。
漢字使用gbk編碼(簡單的說,用兩個位元組表示乙個漢字,高位元組最高位為1的代表漢字,低位元組最高位可以不為1)。
int is_include(char *a, char *b);
返回0表示沒有都出現過,返回1表示都出現過。
請給出所給演算法的複雜度分析,尤其是在字串長度不同的情況下的複雜度分析。
二、演算法題(1)
序列seq = [a,b,…,z, aa,ab,…,az, ba,bb,…,bz, …, za,zb,…,zz, aaa,…] 類似與excel的字母序排列,任意給出乙個字串s = [a-z]+(由a-z字元組成的任意長度字串),請問s是序列seq的第幾個字串。
演算法題(2)
對數列的一次「塊移動」是指把一段數取出來插入到數列中的另乙個地方(說穿了就是一次選擇剪下貼上的操作)。
例如,數列1,4,5,6,2,3,7可以通過一次塊移動完成排序(把456挪到3後面)。
那麼,想要讓乙個1到n的逆序排列n, n-1, ..., 3, 2, 1變為順序排列,最少需要多少次塊移動?
給出你的演算法,並證明這個移動數目不能再少了。
三、系統設計題(1)
在乙個有1000萬使用者的系統中,設計乙個推送(feed)系統。以下是乙個預定義概念
1、使用者:在這個系統中,每個使用者用乙個遞增的unsigned int來表示user id(簡寫為uid);
則uid的範圍是從1到1000萬的正整數。
2、好友:使用者之間可以形成好友關係,好友是雙向的;比如說uid為3和uid為4的兩個
使用者可以互為好友。每個使用者好友的上限是500個;使用者之間的好友關係可以
被解除3、活動:每個使用者只能發文章;文章可以被作者刪除,其他人不能刪除非自己發表的文章; 每篇文章通過乙個blogid表示。
4、feed:我們希望,每個使用者可以看到他所有好友的活動列表,在這個簡化的系統中就是
所有好友的文章更新列表。
5、訪問量要求:所有feed訪問量每天在1億量級;所有的blogid增加量每天在百萬量級。
題目:請在以上限制條件下,設計乙個高效的feed訪問系統。
要求:1、能夠盡快的返回每個使用者的好友feed列表,每個使用者可以最多保留1000條feed; feed的展現按照時間倒排序,最新的在最前面
2、使用者刪除某片文章後,被推出去的feed需要及時消失。即每個使用者看到的好友
feed都是未被刪除的
3、盡可能高效。
系統設計題(2)
使用者在網路上進行search服務時,經常會無意中將漢字直接書寫成拼音,現在請你設計乙個系統,完成以下功能:
1)系統輸入是使用者輸入的查詢串;
2)系統返回是:如果有拼音則返回最有可能的漢字(詞語),否則返回原串;
四、興趣題(1)
某種藥方要求非常嚴格,你每天需要同時服用a、b兩種藥片各一顆,不能多也不能少。這種藥非常貴,你不希望有任何一點的浪費。一天,你開啟裝藥片a的藥瓶,倒出一粒藥片放在手心;然後開啟另乙個藥瓶,但不小心倒出了兩粒藥片。
現在,你手心上有一顆藥片a,兩顆藥片b,並且你無法區別哪個是a,哪個是b。你如何才能嚴格遵循藥方服用藥片,並且不能有任何的浪費?
興趣題(2)
100個囚犯從前往後坐成一列。坐在最後面的那個囚犯能夠看到其餘99個囚犯,坐在最前面的那個囚犯啥也看不見。看守給每個囚犯戴上一頂黑色的或者白色的帽子。
然後,看守會從後往前依次叫這些囚犯猜測自己頭頂上的帽子的顏色。如果哪個囚犯猜對了,他就自由了。坐在前面的每乙個囚犯都可以聽到後面的囚犯的猜測。
如果這100個囚犯事先可以商量好一種策略,那麼最理想的策略是什麼?
校園招聘面試題
中可集團校園招聘面試小組討論題目 a 背景 abc是一家國有企業的水泥廠。該廠最近與法國一家世界著名的水泥生產公司初步達成合資協議。合資後法方會提供工廠所缺乏的資金 技術和裝置,但法國方面要求將現有的500名職工裁減到120人,除了保留一些管理人員 青年的技術骨幹和熟練工人之外,大量四五十歲的老員工...
研發部技術工程師招聘要求
崗位職責 1.客戶聯絡 客戶回訪,進行公司產品技術層面日常服務工作,包括遠端或現場解決客戶在產品應用的疑惑和問題 2.客戶問題反饋及跟蹤,溝通客戶,跟蹤專案中產品的執行狀況,及時了解接收客戶反饋資訊,提供售後技術支援,定期提供報告 3.產品部署 公升級 安裝除錯 資料遷移 模擬使用者環境測試 4.使...
軟體研發面試題
2 從以上分析可以看出,把區域性變數改變為靜態變數後是改變了它的儲存方式即改變了它的生存期。把全域性變數改變為靜態變數後是改變了它的作用域,限制了它的使用範圍。3 static函式與普通函式作用域不同,僅在本檔案。只在當前原始檔中使用的函式應該說明為內部函式 static 內部函式應該在當前原始檔中...