CS面試問題(entry level)分享 - 面試

起始值
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了...
: ==
: 煩請版友幫忙我這新手解答疑惑...
: 感謝!!

--