作者etwas (i'm only dust)
看板Soft_Job
標題Re: [閒聊] 關於面試時問的問題
時間Tue Aug 2 23:40:14 2011
看到這個題目
我也只會用
1. hash做DP(像原PO, 以及之前回覆的人)
或是
2. sorting看中間element
前者time comp O(n), space comp O(n)
後者time O(nlogn),
space comp, 以題目看起來不能in-place, 應該還是O(n),
time comp貌似躲不過O(n)了
可是像這種考慮N極大的問題 space 用到O(n) 應該都不被接受
所以我google
stackoverflow上有兩個答案都很漂亮, space都是O(1)
我自認給我三天都想不出來
一個就是原PO的朋友用到的Moore's voting algorithm,
另一個是counting every bit, the most common bits will be the dominator,
再找它的index
http://goo.gl/pNkXI
看到這裡
我也有疑問:
半小時想出這樣的演算法?
當然我想不到不代表別人想不到(原PO的朋友想到了!)
只是這樣的人應該很少
畢竟
Moore的網頁上把這個voting演算法
跟他廣為人知的BM string searching演算法歸類於"My Best Ideas"
難道公司除了這麼聰明的人
其他都不要...
我也準備要找工作
假如面試到這個題目
因為我看過
可能有進一步的機會
但這並不代表我比沒看過的人強
難道公司要這樣的人?
看過很多演算法? 那天下演算法何其多...
不曉得各位先進對於用這種puzzle面試的想法是什麼
※ 引述《pandaforme (建 建)》之銘言:
: PO這篇文章的本意是想討論 公司出了靈活的面試題目來測試面試者
: 但是面試方法竟然如此的封閉 身為被面試者應該如何應對
: 假設某一家公司拿指考的數學題目來考面試者
: 面試者分別有
: 1. 普通的一般人 (大學以上的學歷)
: 2. 準備要參加指考的應屆考生
: 3. 對數學非常有天分的神人
: 考試時間為一小時 考完後 單純依據分數來判定有沒有入取
: 一般人在有限時間且缺乏練習的情況下 考得贏第2和第3類的人嗎?
: 之前遇到幾個公司面試就是這樣的做法...
: 考完就考券收一收 也沒有問你怎麼解 請等待回應
: 就算有問 面試官心中都有一定的成見
: 真的是自己能力不足 被問到釘在白板上也認了...
: 可是能這樣的機會也沒有
: 公司的面試方式似乎卻在走回頭路 只看你的筆試成績
: 卻一點都不在意你對問題的解決方式和想法
: 既然有版友想看題目 那我就PO出來吧
: http://tinyurl.com/3srmqfc 並且請考慮當N很大的時候
: 請在半小時內想出解法並且使用你拿手的程式語言實作它
: 我是第一次看到這個題目
: 當下判斷我不可能在半小時內想出最佳解且要考慮當N很大的時候
: 所以就採用硬幹法一一去算每個元素出現的次數
: 想好並且寫完CODE半小時也差不多過了
: 面試官就收回考券 說:等我們的技術長看過後再決定是否有第二次面試
: 想當然結果就是謝謝 再連絡...
: 嗯
: 這樣的陣亡方式 感覺有點死的不明不白
: 似乎這樣的面試方式 在浪費彼此的時間...
: 換個角度想 只能有緣再見面了~
--
'TIS better to be vile than vile esteem'd
~William Shakespeare
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 188.74.78.60
推 pandaforme:我想討論的就是你最後的觀點 但是大家都模糊焦點... 08/03 09:44
推 extravagate:運氣(緣份)本來就是實力的一部分 08/03 14:05
推 prag222:遇過拿半日工作量的題目來面試人的還說..我看你答案的架構 08/03 21:58
→ prag222:寫法之類 08/03 21:59