Re: [北美] CS面試問題(entry level)分享

看板Oversea_Job作者Solti (請施捨我P幣)時間14年前 (2011/07/30 14:37)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串3/3 (看更多)

起始值 book array index: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10 value:-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2 counter = 0, input = 5, -->book array[10-5] = -2 -->之前沒有過5 -->先不print -->填入book array[5] = counter = 0 book array index: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10 value:-2,-2,-2,-2,-2, 0,-2,-2,-2,-2,-2 counter = 1, input = 5, -->book array[10-5] = 0 --> counter = 0的時候有過5 --> 要補print -->所以print 55, 55 -->填入book array[5] = -1 //-1代表已經有配對成功過 book array index: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10 value:-2,-2,-2,-2,-2,-1,-2,-2,-2,-2,-2 counter = 2, input = 7, -->book array[10-7] = -2 -->之前沒有過3 -->先不print -->填入book array[7] = counter = 2 book array index: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10 value:-2,-2,-2,-2,-2,-1,-2, 2,-2,-2,-2 counter = 3, input = 12, --> 12 > 10, 直接skip counter = 4, input = 3, -->book array[10-3] = 2 --> counter = 2的時候有過7 --> 要補print -->所以print 73, 37 -->填入 book array[7] = book array[3] = -1 //-1代表已經有配對成功過 book array index: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10 value:-2,-2,-2,-1,-2,-1,-2,-1,-2,-2,-2 counter = 5, input = 5, -->book array[10-5] = -1 -->之前有過且已經配對過 -->不用補print -->print 55 -->填入 book array[5] = -1 //雖然已經填過... book array index: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10 value:-2,-2,-2,-1,-2,-1,-2,-1,-2,-2,-2 依此類推.... 希望沒有bug... Time應該是O(N), memory應該是O(K), K是想要求的總合, 這裡是10, 不隨著N增加基本邏輯就是 -2代表從來沒有這數字過 -1代表之前有過這數字且配對成功過其他正值代表之前有過一次還沒有配對過.. (其實如果不在乎是在哪時出現過也可以都用0) 每次數字進來就去找他的真命天子出現過了沒沒出現過(-2)-->就住回自己的房子 (book array[input] = counter) 有出現過且沒配對過(正值)-->恭喜配對成功要補print, print 兩組 -->把雙方的房子都標示配對成功(-1) 有出現過但已經有對象(-1)-->單相思, print一組然後一值這樣下去..... ※ 引述《nukchichi (haha)》之銘言： : 大家好, : 今天phone interview某間大公司的小 entry level Software developer. : 考到一個問題...想分享出來且尋求答案. : == : 給數字 5, 5, 7, 12, 3, 5 : 如何找出並印出裡面是兩個和 sum = 10的數字組(pair) : 他給的printpair 的 output是 55 55 73 55 (但是我後來想應該有少給我37...) : == : 我一開始沒有想法但是時間壓力就直接先給他直觀的做法 : 兩個for loop 檢查, : 第一次迴圈用10-5 = 5 去找數組裡其他的5 找到就印出 : 2nd 10 - 5 = 5 去找其他的5 : 3nd 10 - 7 = 3 去找其他的3 : ... : 這樣他說可以, 但是希望能更好. 我想了想想不太出來請他能提示 : 他說: 想想為何我剛剛問你比較 link list, binary tree, 和hash table. : 我直覺是要用hashtable去找(他好像也認同我用hashtable) : 但是他要我把hashtable的樣子跟他講 exactly 一點~ : 我就答不出來了...然後就byebye了... : == : 煩請版友幫忙我這新手解答疑惑... : 感謝!! -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 99.116.21.150

推

nukchichi

07/31 00:34, , 1^F

07/31 00:34, 1^F

‣ 返回看板[ Oversea_Job ] 工作

‣ 更多 Solti 的文章

文章代碼(AID): #1ECwQQz6 (Oversea_Job)