[問題] 程式考試時的拿捏
問題(Question)：
今天試著寫了一下 LeetCode 這個網站裡的題目
雖然是解得出來，但是也遇到一個疑問：
就是效能的拿捏，與程式合理性之間該如何平衡？
就拿這個例子來說：
https://leetcode.com/problems/two-sum/
題目意思是說輸入一個數字陣列 numbers，與一個目標數字 target，
如何在 numbers 中找到其中兩個數字之和，剛好等於 target。
舉例而言：
Input: numbers={2, 7, 11, 15}, target=9
則答案就是：
Output: index1=1, index2=2 (第1個數字(2) + 第2個數字(7) = 9)
題目有個前提假設：
輸入的陣列 numbers 裡面，必定有兩個數字之和等於 target，所以不需要考慮錯誤處理
所以我寫了下面第一版的程式：
int* twoSum(int* nums, int numsSize, int target) {
int i, j, *x;
for(i = 1; i < numsSize; i++) {
for(j = 0; j < i; j++) {
if(nums[j] + nums[i] == target) {
x = malloc(2 * sizeof(int));
x[0] = j+1; /* index1 */
x[1] = i+1; /* index2 */
return x;
}
}
}
}
這是一個用暴力法去尋找所有兩個數字的組合，所以 time complexity = O(N^2)
後來覺得太慢了，就寫了下面的第二版：
int* twoSum(int* nums, int numsSize, int target) {
int i, diff;
int x[200001] = {0}; /* 位置 0~200000 表示 -100000~100000 之間的數字 */
int *y;
for(i = 0; i < numsSize; i++)
x[nums[i] + 100000] = i + 1; /* 儲存位置，若為 0 表示不存在 */
for(i = 0; i < numsSize; i++) {
diff = target - nums[i];
if((x[diff + 100000] != 0) && (i + 1 != x[diff + 100000])) {
y = malloc(2 * sizeof(int));
y[0] = i + 1; /* index1 */
y[1] = x[diff + 100000]; /* index2 */
return y;
}
}
}
原理是利用類似 Hash 的方法，對於有出現的數字，先儲存其位置到一個陣列中。
當已知某一數字，又知道 target 時，就可以相減而得知缺哪個數字，
再去查詢該數字是否存在，以及其位置。
這種方法的 time complexity 就比剛剛的第一版小很多
but......
問題來了......
第二版的程式雖然效能快很多，但對於運算數字的大小有其限制。
至少我在上面的程式碼之中，是假設數字應該只會出現在 -100000~100000 的範圍之內
如果這樣的程式題目出現在應徵工作時，這樣寫是否恰當？
畢竟我覺得就工作而言，任何情況都有可能發生，
或者應該其實別想這麼多，只要程式能夠 work 就行？
(至少這個版本，我在 LeetCode 裡面是有通過驗證的)
想請教各位高手，對於這一點的看法...
謝謝！
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.161.161.233
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1436809890.A.F01.html
推
07/14 02:22, , 1F
07/14 02:22, 1F
→
07/14 02:23, , 2F
07/14 02:23, 2F
→
07/14 02:24, , 3F
07/14 02:24, 3F
→
07/14 02:25, , 4F
07/14 02:25, 4F
推
07/17 05:10, , 5F
07/17 05:10, 5F
推
07/17 23:40, , 6F
07/17 23:40, 6F
討論串 (同標題文章)