Re: [北美] 徵求software engineer內推

看板Oversea_Job作者 (宇宙學型男)時間6年前 (2019/04/06 06:24), 6年前編輯推噓50(61推 11噓 147→)
留言219則, 57人參與, 6年前最新討論串2/4 (看更多)
各位前輩好 我想我跟原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的優勢又沒了 真的處在一個很尷尬的時間點 才會上來求助 如果版友們有覺得適合的軟體工作能夠內推的請讓我知道 (如果是華盛頓 加州 或是德州 那會更好!) 或是如果能只針對我的問題給予建議我也會很感激 最近覺得廢到笑所以如果知道我是誰的請不要認親 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 73.181.211.229 ※ 文章網址: https://www.ptt.cc/bbs/Oversea_Job/M.1554503074.A.F2D.html
推
04/06 06:49, 6年前 , 1F
加油 那你現在是用opt？
04/06 06:49, 1F
→
04/06 06:56, 6年前 , 2F
原po有身分吧
04/06 06:56, 2F
推
04/06 06:57, 6年前 , 3F
感覺目前你路也還沒走死
04/06 06:57, 3F
推
04/06 07:07, 6年前 , 4F
第一題，如果我是面試官，我會認為你沒有認真追求最佳解
04/06 07:07, 4F
→
04/06 07:08, 6年前 , 5F
他的follow up就是想問你當需求變的時候，可不可以避掉
04/06 07:08, 5F
→
04/06 07:10, 6年前 , 6F
一些不需要的effort。
04/06 07:10, 6F
推
04/06 07:14, 6年前 , 7F
已寄信
04/06 07:14, 7F
推
04/06 07:14, 6年前 , 8F
第一題就是 (i+1)*2-1 直到超出size 就是inorder第一
04/06 07:14, 8F
→
04/06 07:14, 6年前 , 9F
個 也許可以研究一下heap
04/06 07:14, 9F
回前幾樓 但我希望大家不要認為我硬凹還是只想聽我想聽的 我知道heap 可是真的有辦法從array直接找出inorder? 1, 2, 3, 4, 5, 6 -> 4, 2, 5, 1, 6, 3?
推
04/06 07:45, 6年前 , 10F
面試不是只是把題解了就好，面試官可能是未來同事
04/06 07:45, 10F
我100%同意 這就是我糾結的不是嗎? 我做了A 你喜歡B 那我們互相討論AB為什麼不好這樣不行嗎QQ? ※ 編輯: Cosmology (73.181.211.229), 04/06/2019 07:53:35
推
04/06 07:46, 6年前 , 11F
他還會看你的應對態度，太硬太難搞會直接打槍的
04/06 07:46, 11F
→
04/06 07:56, 6年前 , 12F
(3,3) (3,min) 可以用一些 check 簡單解決, 無論如何這
04/06 07:56, 12F
→
04/06 07:57, 6年前 , 13F
都比你 n log n 好... 我如果看到你這麼堅持也很阿雜
04/06 07:57, 13F
推
04/06 07:59, 6年前 , 14F
根據index算左右不都跟你說了 只是從root = nullptr
04/06 07:59, 14F
→
04/06 07:59, 6年前 , 15F
改成 i > size 停止的 recursive？ 坦白說 從文章跟
04/06 07:59, 15F
→
04/06 07:59, 6年前 , 16F
現在都感覺你難以溝通
04/06 07:59, 16F
→
04/06 07:59, 6年前 , 17F
看你文章敘述 你現在還是覺得你的方法比較好 我是面試官
04/06 07:59, 17F
→
04/06 07:59, 6年前 , 18F
可能也會怕怕的
04/06 07:59, 18F
→
04/06 08:01, 6年前 , 19F
尤其你建 map 不只慢還要花 n 空間複雜度
04/06 08:01, 19F
推
04/06 08:09, 6年前 , 20F
https://bit.ly/2YShpOR 很簡單自己看吧
04/06 08:09, 20F
推
04/06 08:11, 6年前 , 21F
你可以從array建出tree，就代表array index跟tree node有
04/06 08:11, 21F
→
04/06 08:12, 6年前 , 22F
直接關係，所以中間可以把直接建樹的cost省下來
04/06 08:12, 22F
→
04/06 08:13, 6年前 , 23F
i大已經講了
04/06 08:13, 23F
→
04/06 08:32, 6年前 , 24F
其實有同感 看完你的文我反而覺得工作上你可能不是太好溝
04/06 08:32, 24F
→
04/06 08:32, 6年前 , 25F
通 你的態度看起來就是不相信有更好的方法
04/06 08:32, 25F
推
04/06 08:36, 6年前 , 26F
好的工程師看到問題馬上就會反問 那[3,3]應該return什麼
04/06 08:36, 26F
→
04/06 08:36, 6年前 , 27F
而不是寫完看到有這個case不能處理 去找sub-optimal的
04/06 08:36, 27F
謝謝版友的建議 我並非一直覺得我的方法比較好 還是不相信有更好的解 我也有試著跟面試官討論我的方法優缺點 我想可能是我文章表達會有問題 如果有讓大家誤會請見諒
推
04/06 08:37, 6年前 , 28F
我也覺得看文章 不一定是程式的問題 有時候工作能力好解決
04/06 08:37, 28F
→
04/06 08:37, 6年前 , 29F
個性問題很難解 但我只是針對文章的感覺 如果你平常的個
04/06 08:37, 29F
→
04/06 08:37, 6年前 , 30F
性不是如此 那麼就要練習一下面試技巧 了解面試的目的
04/06 08:37, 30F
推
04/06 08:57, 6年前 , 31F
第一題 123456 -> 1 23 456 => 1 425 63 -> 425163
04/06 08:57, 31F
→
04/06 08:57, 6年前 , 32F
第二題 112233 => 1 => 12 => 23
04/06 08:57, 32F
※ 編輯: Cosmology (73.181.211.229), 04/06/2019 09:06:50
推
04/06 09:12, 6年前 , 33F
1. O(2N) 2. O(N) * O(2log2)
04/06 09:12, 33F
→
04/06 09:14, 6年前 , 34F
** 2. O(N) * O(log2)
04/06 09:14, 34F
→
04/06 09:23, 6年前 , 35F
我自己的感覺是 你試著討論優缺點 但你應該miss了一些很
04/06 09:23, 35F
還有 144 則推文
推
04/08 07:36, 6年前 , 180F
jennya 很佛心，不但告訴你怎麼解，還示範了遇到質疑該如何
04/08 07:36, 180F
→
04/08 07:36, 6年前 , 181F
處理。已經很多版友提出你該改進的地方了，原 PO 加油吧…
04/08 07:36, 181F
推
04/08 10:41, 6年前 , 182F
min heap constant factor 是2,time=O(2n)=O(n),space=O(n)
04/08 10:41, 182F
→
04/08 10:42, 6年前 , 183F
for掃一遍O(1n)=O(n),space=O(1),建heap到底好在哪裡?
04/08 10:42, 183F
→
04/08 11:03, 6年前 , 184F
印度面試官覺得heap非最佳解是對的,時間慢2倍空間多N倍
04/08 11:03, 184F
推
04/08 11:13, 6年前 , 185F
然後到底哪幾間大公司印度面試官問這題?我想去面,需要工作
04/08 11:13, 185F
推
04/08 11:40, 6年前 , 186F
我錯了,build heap證明https://tinyurl.com/yyoq8xmw
04/08 11:40, 186F
→
04/08 11:42, 6年前 , 187F
中間不斷利用big O特性省略常數項,所以常數並非2
04/08 11:42, 187F
推
04/08 12:19, 6年前 , 188F
用大小為2的heap不是 time:O(n log2) space:O(2) 嗎?
04/08 12:19, 188F
推
04/08 12:22, 6年前 , 189F
面試完就是move on 工作就是緣分而已
04/08 12:22, 189F
推
04/08 12:32, 6年前 , 190F
size2 heap跟for一遍加2個int時間一模一樣,空間是常數倍,因
04/08 12:32, 190F
→
04/08 12:33, 6年前 , 191F
為你把原本兩int換成兩個帶int的node,仍然非最佳解阿
04/08 12:33, 191F
推
04/08 12:53, 6年前 , 192F
再來,建heap為O(n)的關鍵是Heapify,以java來說,你必須直接
04/08 12:53, 192F
→
04/08 12:55, 6年前 , 193F
把collection傳進PriorityQueue建構子以保證linear time
04/08 12:55, 193F
→
04/08 12:56, 6年前 , 194F
如果你是建一個空的然後一個個插入那還是O(nlogn)
04/08 12:56, 194F
→
04/08 21:20, 6年前 , 195F
回 OckhamsRazor：我只是想強調建 heap 真的可以 O(n)，
04/08 21:20, 195F
→
04/08 21:20, 6年前 , 196F
複雜度上比 sort 好，我沒有覺得花 O(n) 的時間空間 建 h
04/08 21:20, 196F
→
04/08 21:20, 6年前 , 197F
eap 在這題是好方法… 只是「理論」上比 sort 好，實務
04/08 21:20, 197F
→
04/08 21:20, 6年前 , 198F
上我猜還因為 constant 太大比 sort 還爛 (library 的 so
04/08 21:20, 198F
→
04/08 21:20, 6年前 , 199F
rt 還往往 worst case n^2 勒…但用起來真的很接近 O(n)
04/08 21:20, 199F
→
04/08 21:20, 6年前 , 200F
了)
04/08 21:20, 200F
推
04/09 01:34, 6年前 , 201F
第二題你說的那個 case 只要額外用個變數紀錄陣列裡有沒
04/09 01:34, 201F
→
04/09 01:34, 6年前 , 202F
有出現 INT_MIN 就行啦。
04/09 01:34, 202F
→
04/09 01:41, 6年前 , 203F
這樣就還是 O(n) 而且你提出的 case 還是會給出正確答案
04/09 01:41, 203F
→
04/09 01:41, 6年前 , 204F
至於陣列裡只有一種數字，同樣可以檢查 top1 top2 是否一
04/09 01:41, 204F
→
04/09 01:42, 6年前 , 205F
樣來偵測出來。
04/09 01:42, 205F
→
04/09 01:43, 6年前 , 206F
總之加入各種錯誤偵測後就得到O(n)且任何case都正確的解
04/09 01:43, 206F
→
04/09 01:47, 6年前 , 207F
比如說 a= [INT_MIN,INT_MIN] 就會導致top1=top2=INT_MIN
04/09 01:47, 207F
→
04/09 01:49, 6年前 , 208F
a=[INT_MIN,3]就會top1=3 != top2=INT_MIN 然後就看另外
04/09 01:49, 208F
→
04/09 01:49, 6年前 , 209F
那個變數來檢查 INT_MIN 有沒有出現在 a 裡
04/09 01:49, 209F
推
04/09 18:57, 6年前 , 210F
高手在民間～
04/09 18:57, 210F
噓
04/10 04:17, 6年前 , 211F
你連第二題這種一看就送分題都做不好 再努力學習吧 別抱怨
04/10 04:17, 211F
推
04/11 05:58, 6年前 , 212F
x,y=-inf;for i in array {if (i>x) {y=x; x=i}}
04/11 05:58, 212F
→
04/11 05:59, 6年前 , 213F
if len(array)<2 raise error;if y==-inf raise error
04/11 05:59, 213F
→
04/11 06:00, 6年前 , 214F
return y 之類的吧
04/11 06:00, 214F
噓
04/11 23:45, 6年前 , 215F
技術不行溝通不行還搞性別歧視還怪東怪西，再多學習吧你
04/11 23:45, 215F
→
04/12 22:48, 6年前 , 216F
樓上da大 您的code在原po給的例子(3,-inf) 會給錯誤結
04/12 22:48, 216F
→
04/12 22:48, 6年前 , 217F
果 應回-inf 實回error
04/12 22:48, 217F
噓
04/13 01:53, 6年前 , 218F
都是別人的錯~
04/13 01:53, 218F
→
04/14 12:15, 6年前 , 219F
第二題用nlogn....我是面試官我也不接受啊
04/14 12:15, 219F
‣ 更多 Cosmology 的文章
文章代碼(AID): #1SfzMYyj (Oversea_Job)
‣ 更多 Cosmology 的文章
文章代碼(AID): #1SfzMYyj (Oversea_Job)