這道程序員面試題如何解答?
讀了三遍題,題目沒限制操作系統、語言。
Linux 下一行 sh 代碼可以搞定:
cut -d " " -f 1 input.txt | sort | uniq -c
既然是在職員工了,說明是個實際問題,不是故意出個大數據考驗你,不然還是可以往mapreduce方面考慮的。
能立刻聯想到的應該是用c++的map解決
然而這個時候,最好的裝逼技巧應該是手敲紅黑樹吧。作為前端的我,機智的用nodejs來強行作答
然後就被轉化成了數組去重方法的變種~~
答完題發現我畫蛇添足的還取了一個最大值,汗偶然看到,就來答了。也不知道優不優化,大神們快跟進先上圖: 再貼代碼:app.js
var fs = require("fs");
fs.readFile("./employees.dat", function (err, doc){
if(err) return console.error(err);
var data=doc.toString().split("
"),
count={},
max={
"familyName": "",
"nums": 1
};for(var i=0;i&
0 ? count[surname]++ : count[surname]=1;
count[surname]&>max.nums (max.nums++,max.familyName=surname);
}console.log("max: ",max);
employees.dat
console.log("count:",count);
});
溫 格
切 赫
厄 齊爾
溫 格
切 赫
張 三
李 四
溫 格
牛 頓
比爾 蓋茨
比爾 柯林頓
麥 迪
貝克 漢姆
莎士 比亞
威爾 史密斯
老年傳統程序員看到這道題下的答案有些懵...
自己的第一想法是開個map,key是姓,value作計數器累加用;
缺點是空間複雜度與姓的種類數正相關,優點是時間複雜度基本控制在O(n);考點1是姓需要使用hash做索引,否則時耗會增加到O(n^2)。(選擇其它的樹等索引方式也可以,能說出優缺點就行)
考點2是value的累加,如果是用Java的話,需要注意不要直接put數字,Java在這個場景下會分配新對象的,消耗很大,可以考慮實現一個計數器類包一下。
不過估計現在這個功能應該有不少現成的輪子了吧..不知道現在的Java版本對這個場景會不會做底層優化。此外應該就是看一下面試者的心態,常用語言,工具(比如熟悉office的可以直接Excel分列排序等),思路是否開闊(能否提出多個解決方案)等。
後來想了一下是否要答的高端一點,但是想了一下,內容是存在單個文本文件里的,瓶頸肯定是硬碟讀取,開多線程估計也沒什麼優化空間,就作罷了..
結果一上來就看到你們開管道和分散式計算什麼的..咱真的感覺自己老了呀(哭)
這題主要考察的數據結構的使用。需要知道hashset和hashmap能保證key的唯一。這個題既要保證唯一,又要計數,用HashMap分別存姓和出現的數量即可。這樣遍歷一遍文件的每一行就可以得到了。
gawk "{a[$1]++}END{for(x in a)print x,a[x]}" file
print "
".join([ "{}:{}".format(*i) for i in __import__("collections").Counter([line.split(" ")[0] for line in open("name.txt").readlines()]).viewitems()])
難道這是NOIP2016考題?!身為高一狗的我認為此題對於大學生不會很難吧,,,這比NOIP2015 day2的簡單多了吧。。。
用C#寫的,使用哈希表實現。還在學習中,請多指教。結果:
代碼:
大三。。想的一個好辦法,把姓氏人數排名前100的弄成個數組,然後先在這個數組查,絕大多數的人數應該都在這裡,其他按照下面的方法弄。。。定義一個類,有stringname和count。然後寫一個以這個類為節點的鏈表。每讀取一行就去遍歷這個鏈表,如果已有這個姓就count++,沒有則新增一個節點。
。。這個可能時間複雜度比較高。容我再想想。。。更新下。。。用平衡樹,把前面的類加個unicode碼做節點。這樣節省了一部分查找速度。
感覺是在考mapreduce,以姓為key,value為1,然後規約
同為大四狗,不懂各位大神的命令符。我就想到最基本的數據結構和演算法的知識。我的思路:用trie樹,漢字用unicode表示,每個Node的value初始為0,每命中一次就value++。
之前 @bhuztez 提到的 SQL 方法確實可以…Access 有把 CSV 轉化成資料庫的功能。。。打開 CSV 後選擇 Delimited
再選擇 Space
然後可以給欄位起一個好聽的名字
完成創建一個查詢
選擇 SQL 視圖
輸入以下代碼
SELECT FamilyName, COUNT(*) AS Count FROM thing GROUP BY FamilyName
然後切換到數據表視圖
我覺得如果這是一道 Office 題這樣回答不算錯吧…
Language- or Platform-agnostic solution:
1. Sort
(Time complexity θ(nlogn), ideally)2. Traverse through
(Time Complexity θ(n))
linux 命令行就可以。數據量小就 sort uniq -c 但是sort效率低,排序比較慢推薦直接用awk用數組做,有個回答的gawk就是這個。命令式語言天生比函數式快,所以沒必要折騰。
大一狗,完全無視這是面試題這個前提。。無腦遍歷,以空格和換行作為分隔遍曆數是單數代表這是一個姓創建一個二維數組,遍歷到底發現沒出現過,沒出現過的姓存儲在x[n+1][0]同時x[n+1][1]=1遍歷至n發現出現過,x[n][1]++不知道這樣可不可以。。看樣子演算法很啰嗦啊半個月前程序設計課的實驗題。。
pythonstrs=open(path,"r")
dic={}for string in strs: s=string.split(" ")[0] if dic.has_key(s): dic[s]+=1 else dic[s]=1最後dic就是姓的出現次數的表
推薦閱讀:
※socket 和多線程這兩部分選擇面試題, 哪些知識點比較能看出對方的水平?
※大學社團面試注意什麼?
※怎麼看待程序員普遍缺乏數據結構和演算法的知識?
※面試提問2的10次方是多少是否合適?
※一般在寫SQL時需要注意哪些問題,可以提高查詢的效率?