電腦科學 ^ IT人生 ^ 公益課程

#44 Coding 面試 - 列出公司組織人數

這一題是我以前面試時遇到的題目,不知道當初面試的老闆是在那找來的題目,總之我沒有看過類似題.先來說明題目,

你要寫一個程式,程式的 input 是一個字串,這字串包含了公司裡員工的名字,同時字串裡也包含了老闆與直屬員工的關係.以下是一個例子

A-B,C-B,B-D   這字串代表 A 的老闆是 B,C的老闆是 B, B 的老闆是 D,以此類推,中間會用逗號隔開每一組資料,然後一橫代表老闆和員工,左邊是員工,右邊是老闆.所以,這一個字串其實上就代表了整個公司的組織圖.你可以用手動的方式把每個資訊解析一下就可以把這組織圖的 tree 給畫了出來.

題目要求你要列出某一層次的老闆們下面一共有多少員工 ? 以上述的例子來說,D 是在 level 1, B 是在 level 2, A 和 C 是在 level 3,如果要求你列出 level 2 的老闆時,你的程式就要顯示 B 有兩個員工.

看到這裡,不知道你心裡有沒有想法要怎麼解決這一題.當初這個面試更特別的是,這位面試的老闆帶他自己的筆電過來,Visual Studio 已經開好了,題目的 function 和輸入字串也都打好了,直接要我寫 function 裡面需要的 code.就是上機考.這是我第一次面試遇到上機考,以前遇過的面試都是寫白板而己.寫白板的好處就是有一點小錯誤的話也沒關係,因為面試者主要是看你寫的邏輯對不對,所以不會在乎你是不是打錯 method name 或少了結尾分號之類的.但上機考就完全不一樣了,你一定要讓 compiler 很開心,不然既便有一個再小的錯誤,compile 會失敗的.

基本上,只有 30 分鐘可以這一題,我一開始想了一下,難道真的要建 tree 嗎 ?  寫了建立 tree 的功能之後,還要加上 tree traversal 的功能,這樣才能在 tree 上遊走找人數.當時我還很認真地思考要如何做 tree 和相關功能.後來想想不太對,因為這樣太麻煩了,我只剩 25 分鐘而己.後來就想了一招,雖然不是很好,但是用來解這個題目一定夠用.那就是改用 recursive 的觀念來做.做法如下

1. Parse 輸入字串來建立一個 hash table,key 是員工名,value 是老闆名
2. 用 recursive 的方式在這個 hash table 上找出某一個 level 的員工名稱
3. 根據步驟 2 的結果,把 hash table 上所有員工也是用 recursive 的方式來找看誰的上面老闆是在步驟 2 的結果內,同時把該老闆的下屬員工數做人數統計

因為老闆給的公司組織是真實的資料,所以我知道當我用 recursive 的方式來運作時並不會發生 call stack overflow 的現象.這個觀念在前面的文章中曾提過.

結果,最後我用了 40 分鐘才把整個程式做完,然後直接跑程式給面試老闆看,接下來就是討論我如何做,有沒有什麼改進之處等等.

很抱歉,當時的程式碼就在那面試老闆的電腦裡,沒機會貼在這裡供大家參考.但還是把我當時的做法寫出來供大家參考.

如果你看到在那邊有相似的題目,再麻煩你分享網址.^_^

Share:

0 意見:

張貼留言