好好玩的面試

2008/04/15

跟門口的金髮姐姐登記過後,她叫我到旁邊的沙發等候。
IMG_0050.JPG
噢,原來這是面試的第一回合,Guitar Hero。雖然我沒有音樂感,但玩得較身旁的西人好,若干回合後,那位hr哥哥終於到來,胡謅了幾句,他帶我去搭車到另一棟建築物去。

第二回見試內容基本上都是那些可遇見的題目,例如你做過甚麼project、遇過其麼困難的事、為甚麼揀我地公司等等,然後是技術問題:implement一條唔知幾大,indexed by integer既list,好簡單,不過唔知點解我一開始諗起Pascal String,於是就整左一條好慢既linked list。面試官梗係覺得怪,又問我呢個algorithm有咩問題,於是我補飛,話整多個index咁可以做binary search⋯⋯冇穿冇爛又過左一關。

第三回係最好玩果個回合,果條友仔超過癮。其中一個技術問題係,佢比一個prototype我,同埋佢既black box,叫我估究竟個program做乜既。個prototype係:

int f(char* s1, char* s2);

我可以不斷咁比input佢,佢會比個答案我。最最最正路見到都好應該估佢係一個string comparison既function,但愛玩野既我又點會咁簡單,於是我比左下列既test case比佢:

f(0,0);
f(0,1);
char *s = new char[10];
f(s,s);
f(s,s+1);
char *ss = new char[5];
f(s,ss);

佢都知我玩野,佢話可以係一可以係零,因為c唔會initialize任何野,於是我又再黎:

memset(s, 1, sizeof(s));
memset(ss, 1, sizeof(ss));
f(s,ss);
s[1] = ss[1] = 0;
f(s,ss);
f(s,s+5);
....

最後我估呢個function係做strcmp,如果兩條null-terminated既string係一樣就return 1,否則就return 0。

佢話差唔多喇,佢話呢個係string matching既function,s2係個pattern,例如
f('hello', '*he*') = 1
f('hello', '*ll' ) = 0

佢又問我會點test,咁我又玩啦:
f('*','*');
佢話assume s1唔會有*
f('', 0);
佢話assume 0 係個invalid address:
f('', 1);
佢話好會出error
f('a','******************a');
我話一個蠢既implementation如果唔識做optimization會好慢,佢問我仲有冇其他case
f('hlhlhlhlhl', 'h*l*h*l*h*l*h*l');
我話有可能會好慢,佢話perl既regex慢就係呢個原因,去到呢個位,我兩眼發光,開始覺得好玩。
char s[12] = '*****hello';
f(s+5,s);

我解釋話因為有啲茂利會懶醒咁想慳memory而劃花人地啲野之後改番岩然後扮有事,如果兩條string係overlap就有機會奶野。佢滿意又問有冇其他。
f('abc','');
正常啲啦呢個。佢話正常黎講有三種testcase,叫我寫曬出黎。我肴左一肴,响邊道黎三種?讀書都冇教過既!亂寫條正常啲啦:
f('hello world', '*hello wo*l*');
佢就話得,我已經一次過demonstrate曬三種test case出黎。頂,原來咁淺。

然後戲肉到喇,佢叫我將f寫出黎。嘩!我O左一下嘴,一向好怕做呢類題目,有唔容易既case analysis,實會錯。咁梗係第一時間問可唔可以用perl/python啦,人地天生識得個regex,佢話sure, but you will need to do it in a hard way, you have to assume you don’t hv the regex component, so i guess you will prefer using C。都預左,之不過,人地話就算唔識做都起碼試下,咁我就話:I will use a DFA。佢笑,話想睇我點用dfa,佢話通常啲人都用recursion。其實去到果個位,我都唔係好知點寫,不過見步行步。

畫左個automata出黎之後,我先發覺,原來係個NFA黎,麻煩過dfa好多(我都知理論上佢地係相通,但係nfa可以exponential of the size of dfa喎!),如果呢個世界真係有parallel universe幾好。我擰轉身,同佢講,oh, it is a NFA, i will do it with a recursion,同時我心裏面大概已經有個點做recursion既概念。但佢話,no, keep it as a DFA, i want to see how you will do it。我諗左一點七秒之後發覺,超,整條queue咪得囉,recursion/stack/queue從來都係同一回事啫,十分鐘之後,就寫好左一個佢滿意既pseudocode。

之後同佢吹左好耐,佢指python同perl都係用recursion黎處理regex既,然後互相吹左好耐點解dfa/nfa好難做matching。超好玩,interview之餘仲有野執,呢一個鐘,過得超快。

其餘既,差唔多啦。愈見愈高級咁囉。尾二果個間房有三個mon三部電腦一部xbox,最尾果個間房得一個mon同一部laptop,仲有張梳化,好明顯最後呢個完全唔使寫code啦。

超級快有回音,番到酒店,上網,就已經收到email。

也算是吐了年多前的一口冤氣。

廣告

21 回應 to “好好玩的面試”

  1. Elizza Says:

    恭喜晒!! =)

  2. Lo哥 Says:

    所以話之前你唔掂我真係好嚇親 ( 我唔嚇得, *你地* 唔好嚇我.. 你知你地係邊個 ), 你既實力, 明既明既… =) 恭喜晒!

    幾時去屈機?

  3. fishskin Says:

    勁呀
    恭喜恭喜

  4. cr Says:

    恭喜恭喜。

    雖然我一啲都唔明嗰啲technical嘅術語。

    =)

  5. Derek Says:

    乜野公司﹖

  6. p* Says:

    nfa with a stack? it is a pushdown automata, right?

    you can go google and try! haha! congrat!

  7. Kris Says:

    好似d偵探小說入面既猜謎遊戲,考你技術,過完一關又一關。
    勁啊你!

  8. Max Says:

    wow congratulations !
    really really really really cool !!

  9. Learning_Forest Says:

    祝一切順利…
    恭喜!

  10. kd Says:

    Congratz! 睇完你個interview之後……自愧不如

  11. Patrick Says:

    Justin兄,強呀!!

    回Derek:Justin好像(無記錯的話)in整xbox個間公司呀

  12. 媽媽阿四 Says:

    Congrats!! :)  你會accept嗎?

    之後帶左你去邊度wet?果時我有個朋友喺度做緊,夾硬要chee埋嚟一齊去食埋一份,結果分薄晒個allowance。你知啦,窮學生,難得有得食餐勁,嬲到而家。

  13. 許港生 Says:

    面試通常都很浪費時間,難得遇著一個有趣的面試,做不做得到也上了一課。

    恭喜:-)

  14. 黑人 Says:

    過關斬將
    睇唔明都覺得爽喎

  15. Justin Says:

    Elizza, Fishskin, cr, kris, LF, Patrick, 許港生,黑人:多謝多謝!

    Lo: 果次唔掂其實都係自己問題。果次我apply PM,但我覺得自己既能力似係做dev多過個pm.

    Derek: xbox果間。

    P*: haha, thx! Only the non-deterministic property is problematic. Whenever we make a decision, there is no guarantee we will reach a solution, so that we need to provide a mechanism to restore the previous state. Either queue, stack, list….etc could do the task.

    Max: 係呀!係超超超超好玩。

    Kd: 唔同公司要求唔同skills set啫,好似你之前講咁,有時soft skills都好重要,但我覺得呢間公司冇咁重視soft skill。

    阿四:呢個真係要諗諗。。。
    我都係同我個frd出去食,實過佢個allowance啦,我唔知claim唔claim得番曬(HR話如果我有frd响裏面做,可以係我個frd host果個dinner)。

    話時話,我第一晚去到,即刻响酒店叫room service,呢世仔第一次!

  16. gordon Says:

    犀利,但其實你in緊咩…

  17. 米搞 Says:

    yeah yeah yeah~

  18. Alex Says:

    以我AL CS 為限既電腦知識,已經完全唔知你up乜…… congrats anyway!

  19. Justin Says:

    Gordon: software developer and test.

    米搞:yeah yeah yeah yeah!

    Alex: 嘿!其實上面好多都好無聊,只不過係遇著個咁geek既interviewer先會亂吹呢啲野。如果叫我响香港見銀行工,我一定唔敢咁玩。

    *******

    另,我發覺自己問漏左:
    f(‘陳奕迅’,’浮誇’);
    佢未必support unicode/big5.

  20. Lo哥 Says:

    >>Justin

    哈, 都係試啫, 家陣咪幾好. 出發啖氣喎! =)

  21. Justin Says:

    係呀。果次我真係懷疑自己既technical skills係唔係真係唔夠。呢下算係鬆一口氣。


發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s

%d 位部落客按了讚: