各位前輩好 我想我跟原PO一樣也需要幫助
文長且有點抱怨文 請見諒
我可能運氣比較差 上個月因為家裡有事回台灣一趟
回來以後公司就叫我不用來上班了
明明放假前經理也批假了 唉 簡而言之我就是失業了
其實我自認coding應該是還可以
leetcode一直都有在寫 版上很多人強調的不要背題
多問問題我自認都有做到 都能夠用推理的去把一個新題解出
再看別人的解去改進 自己手寫都有做到
但我不知道是不是真的流年不利 總是在面試最後一關拿不到自己真的想要去的offer
目前面過的大廠:
VMWare / MagicLeap
有過但是當時因為家庭因素decline...
Google
on-site後沒過目前冷凍中
Amazon
失業後面的 面SDE後HR打來說原則上?過了但感覺JAVA經驗不夠
問我能不能轉system engineer
我答應後也是無聲卡
當然還有很多大小公司族繁不及備載
但昨天也剛面完一間on-site 我想是我主要發這篇的原因
面完HR告訴我一切都很好 但coding這關bar真的還差一點
叫我先練一下兩個月後再跟他連絡一次
題目確實不難 但我不知道是我跟面試官不對盤還是我自己問題比較大
因為如果不對盤那就算了 我覺得我也沒辦法改變什麼
但如果我自己問題大 我想上來真心尋求版友建議
以下強調我絕對沒有背題 但因為發文所以我盡可能簡化
第一題:
給定一個array 建造一個complete binary tree
ex: [1, 2, 3, 4, 5, 6]
1
/ \
2 3
/\ /
4 5 6
先清楚地把binary樹原理等等解釋清楚 有問條件等等
當然我用BFS可以解完了沒問題
面試官問那如果有給定一棵樹 輸出inorder的順序
我用遞迴也解出來也沒問題
但他這時候的問題變成是 如果給定原本的array怎麼直接output inorder
老實說我聽了問題楞了一下 我問他不就兩個functions在這裡了
我們為何不能直接叫這兩個function就好?
他覺得有其他辦法 想知道我會怎麼做
我就說我會有一個大function去包這兩個小的function這樣
(後來HR跟我說面試官覺得我用暴力解... 不願意去思考有沒有其他方法...)
其實我回來還有檢討一下 但真的有其他更好的辦法嗎?
第二題:
給定一個array 找出第二大的數字
我知道版友看到一定會笑掉大牙 這麼簡單也不會過...
但沒關係 我知道leetcode有類似的 但我們不能背題 對吧
我開始問主考官問題 確認到底要什麼
是否可以保證答案一定存在? 不保證 size可能小於2 要throw error
是否可以保證每個數字都是唯一的? 不保證 可能有重複的數字
數字是否有特定範圍? 不知道 這都隨機的
ex:
[1, 1, 2, 2, 3, 3] 答案2
一開始我先用hash map去把重複的數字過濾掉
先看數量夠不夠 夠的話用sort找出倒數第二個
結果面試官問複雜度(N log N) 他說他不喜歡這個
因為要用額外的memory 想問有沒有N的方法
我說可以記錄說最大跟大二大同時是什麼
我有先寫大概的想法跟code 但我提醒覺得這樣會有問題
面試官一直覺得沒問題 搞不清楚為什麼我說會有問題 叫我先寫出來
好的我們寫差不多跟這個幾乎一樣的
https://www.geeksforgeeks.org/find-second-largest-element-array/
他覺得ok 其實我當下閉嘴就好 但我可能自己假會 一直跟他說我覺得這樣會有問題
因為如果[3, 3] 跟 [3, INT32_MIN] 這個function會丟出一樣的結果
但是事實上第一個陣列沒有正確答案 第二個卻是有的
照他當初自己說的任何數字可能性都有 那他要求的這種方法不就死了...
我才告訴他這樣的方法會有問題 原本的優點在哪等等
但反正他可能不是很喜歡我原本的方法跟答案
但HR跟我說面試官覺得我在這邊卡住 而且他給了提示我卻沒辦法完成他的要求
我心裡才OS這樣明顯就有問題了...最後他自己才發現要至少兩個不一樣的元素才可以用
這樣的演算法吧...
自我檢討:
我自己很常糾結一些為什麼一定要照面試官的答案才是標準答案這樣的思維去跟他們討論
我自認應該很和善的去了解跟題出自己的想法
可能他們就會覺得我在硬凹還是沒有理解的透徹
加上我自己心態可能也有點崩了(以下開玩笑請不要太認真)
現在整天躺在床上
心裡都OS面試官都是智障嗎
例如第一題如果他有好的辦法 是不是可以提出來我們兩個討論
分析優缺點 這才是討論問題的本質不是嗎?
第二題我就給test case就打臉了 還一直叫我先寫出來
然後又說我卡住
就跟妹子一樣要什麼不講清楚 要別人去猜他到底要什麼
猜不到就說別人不合格 我是要應徵軟體工程師還是算命師?
還是我其實就閉嘴乖乖把戲演好就好 也不要自作聰明提出很多想法去質疑面試官?
反正把offer拿到才是最重要的?
之前有類似這樣做 這樣又會被說我們要可以互相討論的team player 不是單純解題機器
真的搞的心很累...
加上其實剛畢業一年又失業 當初能夠申請new grad的優勢又沒了
真的處在一個很尷尬的時間點 才會上來求助
如果版友們有覺得適合的軟體工作能夠內推的請讓我知道
(如果是華盛頓 加州 或是德州 那會更好!)
或是如果能只針對我的問題給予建議我也會很感激
最近覺得廢到笑所以如果知道我是誰的請不要認親
謝謝

加油 那你現在是用opt？

原po有身分吧

感覺目前你路也還沒走死

第一題，如果我是面試官，我會認為你沒有認真追求最佳解他的follow up就是想問你當需求變的時候，可不可以避掉一些不需要的effort。

已寄信

第一題就是 (i+1)*2-1 直到超出size 就是inorder第一個 也許可以研究一下heap

面試不是只是把題解了就好，面試官可能是未來同事他還會看你的應對態度，太硬太難搞會直接打槍的

(3,3) (3,min) 可以用一些 check 簡單解決, 無論如何這都比你 n log n 好... 我如果看到你這麼堅持也很阿雜

根據index算左右不都跟你說了 只是從root = nullptr改成 i > size 停止的 recursive？ 坦白說 從文章跟現在都感覺你難以溝通

看你文章敘述 你現在還是覺得你的方法比較好 我是面試官可能也會怕怕的尤其你建 map 不只慢還要花 n 空間複雜度

https://bit.ly/2YShpOR 很簡單自己看吧

你可以從array建出tree，就代表array index跟tree node有直接關係，所以中間可以把直接建樹的cost省下來i大已經講了

其實有同感 看完你的文我反而覺得工作上你可能不是太好溝通 你的態度看起來就是不相信有更好的方法好的工程師看到問題馬上就會反問 那[3,3]應該return什麼而不是寫完看到有這個case不能處理 去找sub-optimal的

我也覺得看文章 不一定是程式的問題 有時候工作能力好解決個性問題很難解 但我只是針對文章的感覺 如果你平常的個性不是如此 那麼就要練習一下面試技巧 了解面試的目的

第一題 123456 -> 1 23 456 => 1 425 63 -> 425163第二題 112233 => 1 => 12 => 231. O(2N) 2. O(N) * O(2log2)** 2. O(N) * O(log2)

我自己的感覺是 你試著討論優缺點 但你應該miss了一些很明顯的點 面試官很容易就發現你的depth不足 大部分時候我在這種地方都能刷掉很多人

有時候退一步，反而是進一步，能力反而不一定是最大原因

討論解法trade off的前提是多個效能相似的解法，而你的面試官的提示基本上都已經是在提醒說有個效能更好的做法，你沒抓到點而只想討論次佳解的話很難讓面試官幫你寫好的feedback

第二題 他想說的重點是 n log n 不大好吧，但你好像有點糾結在別人 O(n) 的 "bug" 然後說自己 n log n 比較好好像有沒看到問題本質的嫌疑我覺得你下次可以改成說，你原本想說你這個解法會有什麼樣的問題，如果這個不打緊的話，這樣的確不錯，然後看有沒有辦法繞過或解決那個 "bug"最後我覺得不斷精進是要的，但也不用糾結特定的一次面試沒過的原因千百種，把自己準備好從來只是增加機會再確認結果前沒有100%的事

面試是要找未來同事，你明顯表現出很難共事的特質

面試官對題目很熟 預設就是最佳解 這種時候要跟著演好

比你優秀的或同程度的一大堆。。。一般人寧願選程度差一點，但是好共處的

撇除這些互動先不談 很單純的來看 你這兩題也都沒有寫出最佳解 建議平常還是要多延伸思考 多質疑自己我這樣真的是對的嗎? 有沒有最佳解? 有沒有其他做法?要常常挑戰自己的答案 不要畫地自限 公司最怕的就是 newgrad 進來然後不聽其他人的建議...

小劇場有點多 就算題目有許多可質疑的點 也應該先趕快設定好假設 把解先寫出來 寫完再來講自己覺得有疑問的點 然後再改進 而不是馬上拿問題去打問題..拼命丟問題回去不是展現能力的好方法 反而會讓人覺得不好相處 毛很多

第二題O(N)的解法是有辦法分辨你舉的例子的 你再想想吧

難搞 不想當你同事 就這麼簡單講個笑話搞不好就上了

def inorder(arr, i):if i >= len(arr): return []return (inorder(arr,i*2) + [arr[i]] +inorder(arr, i*2+1))print(inorder([0,1,2,3,4,5,6], 1))我也在找，一起加油吧

LeetCode在招人 有工作經驗的話履歷可以發給我

很多人似乎搞錯了什麼，以為面試只要回答對全部問題就會過，忘記面試是在選同事而不是只考能力。 我自己也好幾次面試問題保證答對，但軟實力表現太差別人不要我的

話不投機半句多，磁場不合~

先不說個性問題，你這篇文提的所有被考的技術題都是「你想錯了、面試官的想法是對的」（等有心人把正確方法解釋給你聽），你竟然還覺得「面試官都智障」，真扯，是面試官們都覺得你是智障吧...上面竟然多數推文都只說你個性上有問題而已，可能大家沒有仔細看你的題目，你的技術上完全很不行......（然後說實在的，現在資源這麼多了，你怎麼不自己先去google解答、弄懂以後再來PO文？）其實我本來不會這麼凶的，不過看到你妹子那段真的覺得你面不上好爽，最討厭你這種性別歧視的男工程師。本來想要寫篇文回應你這篇被面試官問到的問題的正確解答，看到妹子那段就覺得你這種人還是一直找不到工作算了，爽。上面sssh5566大大說「很多人以為面試只要回答對全部問題就會過」，可是事實上這一篇原PO是錯的一蹋糊塗的程度，離「所以問題都回答對」還很遠。

樓上別氣 他第一輪是答對的呀 是沒理解什麼叫做follow up吧

是啦，真的不要覺得面試官白痴，題目我們自己都討論過了followup是刺探你對程式設計的理解程度，不是智障亂問如果你先入為主覺得面試官在亂問，那也無從followup

看到妹子那段同樣感到不爽

完全同意 jennya然後你舉的那幾題都不難 你沒接到面試官的提示只能說是你的問題

同意J大，自己跟面試官溝通不好固執己見，關女生什麼事

我覺得這個技術問題的根源其實是個性或思想問題，有時候技術問題並不是完全是一個人真的知識不足或邏輯非常差，而是沒去認真思考自己有錯或不夠好的可能性

第一題告訴你他是complete b-tree其實就等於你可以靠index來做traversel 了, l-child = i * 2 + 1,r-child = i * 2 + 2, parent = (i - 1) / 2寫個遞迴就解決

路過噓性別歧視

自己面試有問題牽拖女生是怎樣

面試考coding是基本，主要想看的還是個姓吧…

推J大，這兩題followup原po都錯得離譜，光從你敘述我都會給no-hire了，更不用說這還是你主觀的描述

1.陣列建二元樹：(X) 不必使用BFS，使用for迴圈將陣列跑一遍就可以做到，省下bfs queue的空間2.二元樹inorder：(O) 使用遞迴沒問題3.陣列inorder：(X) 一樣可寫成遞迴，只是遞迴裡面每當要呼叫子樹時，用index的方式。這是合理的需求，假設原本的資料格式就是陣列，現在唯一需求就是輸出inorder，難道你要每次都新建一個中繼用的二元樹、輸出完inorder以後就不用？因此你的想法「已經有兩個function為何不用」其實是不太好的反對理由，你並沒有理解到面試官題目的需求（不要新建中繼二元樹）、你想不到方法達成、你聽不進去面試官的引導提示4.給定陣列找第二大數字：(X) 先用簡單些的題目、假設數字不會重複好了，那你還是用nlogn的sort然後拿第二大嗎？你要是有在認真寫題目，應該會知道最佳解是O(n) one pass迴圈、使用變數和if else。而今換成數字會重複的版本也是一樣。面試官一直提示，她的方向是對的，O(n)沒有任何副作用且就是最佳解。然後你貼的網頁就已經說one pass是最佳解了為何你會沒有看進去，還會有自己的想法認為O(N)有問題= =有自己的想法不要緊，每個人也都有自己想做的時候，可是你看到那個網頁，應該要能夠「察覺」自己的想法不太對勁吧。關於你說的bad case，[3, 3]你應該要回傳錯誤值，你就算用sort也是得回傳錯誤值阿。

樓上第一題怎麼用for 建complete b-tree?我還真想不到而且還是在不用額外記憶體的情況下利用pre or inorder traversal建還是需要暫存parent不然要怎麼返回parent node?

這都是頗基本的題目，然後你四題卻只有一題有答對（還不論你寫出來的時間和變數命名等等），這是很慘烈的情況，應該要認知到自己的技術要增強；然後比起技術力，更為慘烈的是你毫無自覺...而且還想相反了...「整天躺在床上，覺得面試官都是智障嗎」......有懂那幾題在幹嘛的看到你這句話應該都感到震驚。

震驚，在智障眼中我是智障嗎？

同意樓上

@Ninja5566 你說的對。我原本的想法像是這樣：https://www.paste.org/97946但是仔細一想這的確和BFS差不多。這部分我的確是嗆原PO嗆錯了。謝謝~~

推 j大解說XD

都要建 tree 了 應該不可能不用額外記憶體吧..雖然說 tree 已經 implicit 的儲存在 array 中了..

找第二大數字 其實可以one pass 用一個heap去記錄 最後回傳heap的最大值就好了吧 小弟 遇過不只一次跟in 開頭國籍的面試官 還不是小小startup 跟我說我寫的 O(n) + O(n) 是O(n ^ 2) 他要更好的 我也是 笑笑 其實找工作有時軟實力比硬實力重要多了 一起共勉之

推文好熱烈XD

用heap那直接sort不就好了……

直接兩個變數存最大和第二大if else過去就好了吧

heap......

資遣有資遣費嗎？

謝謝分享 留言也都超有用 我猜原po應該也是轉行的 所以有點心態上還是解出來就好 再多磨練吧 加油

找第二大可以用min heap吧 一定要用heap的話啦...

回 jatj，用 heap 比較好唷 O(n) 時間可以建出 heap再拿出前2個 也是 + O(log n) 整體還是 O(n)

用個Size = 2的max heap更省空間吧 不過這樣就跟兩個變數if else過去差不多的意思

用heap的有考慮constant time嗎…都是O(n)不代表執行時間差不多啊…

請問用heap不是O(nlogn)嗎？全部放進去要O(n)，每次放跟拿都是O(logn)，這樣算O(n)建出heap嗎？

建只要 O(n) 最大在 root 且 次大一定在 root 的 child

jennya 很佛心，不但告訴你怎麼解，還示範了遇到質疑該如何處理。已經很多版友提出你該改進的地方了，原 PO 加油吧…

min heap constant factor 是2,time=O(2n)=O(n),space=O(n)for掃一遍O(1n)=O(n),space=O(1),建heap到底好在哪裡?印度面試官覺得heap非最佳解是對的,時間慢2倍空間多N倍然後到底哪幾間大公司印度面試官問這題?我想去面,需要工作我錯了,build heap證明https://tinyurl.com/yyoq8xmw中間不斷利用big O特性省略常數項,所以常數並非2

用大小為2的heap不是 time:O(n log2) space:O(2) 嗎?

面試完就是move on 工作就是緣分而已

size2 heap跟for一遍加2個int時間一模一樣,空間是常數倍,因為你把原本兩int換成兩個帶int的node,仍然非最佳解阿再來,建heap為O(n)的關鍵是Heapify,以java來說,你必須直接把collection傳進PriorityQueue建構子以保證linear time如果你是建一個空的然後一個個插入那還是O(nlogn)

回 OckhamsRazor：我只是想強調建 heap 真的可以 O(n)，複雜度上比 sort 好，我沒有覺得花 O(n) 的時間空間 建 heap 在這題是好方法… 只是「理論」上比 sort 好，實務上我猜還因為 constant 太大比 sort 還爛 (library 的 sort 還往往 worst case n^2 勒…但用起來真的很接近 O(n)了)

第二題你說的那個 case 只要額外用個變數紀錄陣列裡有沒有出現 INT_MIN 就行啦。這樣就還是 O(n) 而且你提出的 case 還是會給出正確答案至於陣列裡只有一種數字，同樣可以檢查 top1 top2 是否一樣來偵測出來。總之加入各種錯誤偵測後就得到O(n)且任何case都正確的解比如說 a= [INT_MIN,INT_MIN] 就會導致top1=top2=INT_MINa=[INT_MIN,3]就會top1=3 != top2=INT_MIN 然後就看另外那個變數來檢查 INT_MIN 有沒有出現在 a 裡

高手在民間～

你連第二題這種一看就送分題都做不好 再努力學習吧 別抱怨

x,y=-inf;for i in array {if (i>x) {y=x; x=i}}if len(array)<2 raise error;if y==-inf raise errorreturn y 之類的吧

技術不行溝通不行還搞性別歧視還怪東怪西，再多學習吧你

樓上da大 您的code在原po給的例子(3,-inf) 會給錯誤結果 應回-inf 實回error

都是別人的錯~

第二題用nlogn....我是面試官我也不接受啊