PTT職涯區 / Soft_Job (軟體人)

Re: [討論] 面試遇到的考題

看板Soft_Job (軟體人)作者 (のヮの)時間11年前 (2014/07/04 21:01), 11年前編輯推噓23(23推 0噓 43→)
留言66則, 20人參與, 最新討論串22/27 (看更多)
※ 引述《sleeper0121 (sleeper)》之銘言： : 今天去面試，裡面有題題目是這樣: : 寫個函式，傳個整數陣列進去，陣列裡面的整數可以是正數、負數或 0 : 請回傳一個陣列裡面相鄰互乘的最大整數值 : 例如: [2 , -7 , 0 , 2 , 3 , 8 , -6 , 5] : 就是 2 * 3 * 8 = 48 : 再一個例子: [-2 , 0 , 3 , 5 , -7] : 就是 3 * 5 = 15 : 請問這題思考邏輯大概是怎樣呢? : 當下沒解出來，害我回家後還一直再想 XD 今天在 facebook 釣出高手，我想應該是最正確的演算法了 先從左邊乘過去，再從右邊乘回來，遇 0 重算，取最大值 以 { 2, -7, 0, 2, 3, 8, -6, 5 } 來說 左邊乘過去會得到 2, -14, 0, 2, 6, 48, -288, -1440 右邊乘回來會得到 5, -30, -240, -720, -1440, 0, -7, -14 幾個值，得到最大值 48 我的實作 http://ideone.com/dmOEEO 沒判斷子陣列只有一個元素的情況，不過題目也沒定義所以就算了 :p -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.231.23.220 ※ 文章網址: http://www.ptt.cc/bbs/Soft_Job/M.1404478881.A.E1B.html
→
07/04 21:28, , 1F
-2, 10, 10, -2 呢？
07/04 21:28, 1F
→
07/04 21:30, , 2F
400 呀
07/04 21:30, 2F
推
07/04 21:36, , 3F
有趣
07/04 21:36, 3F
→
07/04 21:38, , 4F
好妙
07/04 21:38, 4F
推
07/04 21:45, , 5F
讚
07/04 21:45, 5F
※ 編輯: holydc (36.231.23.220), 07/04/2014 21:55:17
推
07/04 22:29, , 6F
(y)
07/04 22:29, 6F
推
07/04 23:17, , 7F
推 再加點判斷還可以只要單向算過去就好
07/04 23:17, 7F
推
07/04 23:19, , 8F
這作法還不錯 要看單向版本可以看我那篇
07/04 23:19, 8F
推
07/05 02:21, , 9F
推
07/05 02:21, 9F
推
07/05 10:17, , 10F
好方法!
07/05 10:17, 10F
→
07/05 10:33, , 11F
Good
07/05 10:33, 11F
推
07/05 13:14, , 12F
好厲害！！！
07/05 13:14, 12F
推
07/05 14:09, , 13F
引用一樓-2 10 10 -2 -3 呢?(-2 -20 -200 400 -1200) max600
07/05 14:09, 13F
→
07/05 14:11, , 14F
忘了還有右邊乘回來的
07/05 14:11, 14F
推
07/05 15:13, , 15F
Push
07/05 15:13, 15F
→
07/05 15:28, , 16F
我那篇有右邊乘回來同時把last value做動態變動的
07/05 15:28, 16F
推
07/05 15:41, , 17F
樓上 你那篇跑[-2, 2, -2]好像不會算出8?
07/05 15:41, 17F
→
07/05 15:53, , 18F
真的也 那篇只有回原Po的解決方式 看來要加判斷式
07/05 15:53, 18F
→
07/05 15:53, , 19F
應該還是能在O(n)內解決
07/05 15:53, 19F
→
07/05 15:54, , 20F
http://jsfiddle.net/ERKxh/3/ 這是有多一些設定的
07/05 15:54, 20F
→
07/05 15:54, , 21F
但是還是不能解決全部算完是正的 晚點來看
07/05 15:54, 21F
推
07/05 15:55, , 22F
0 999 999 999 999 999 999 999 999 999 999 999 999 999 0
07/05 15:55, 22F
→
07/05 18:37, , 23F
要解過大的數字 那只能建質數表 因式分解 最終才用大數
07/05 18:37, 23F
→
07/06 06:50, , 24F
...不是這樣吧 ... 這個例子0的位置讓他歪打正著
07/06 06:50, 24F
推
07/06 19:46, , 25F
[-0.5, 2, 2, -0.5] 就會算錯喔
07/06 19:46, 25F
推
07/06 19:54, , 26F
喔喔我搞錯如果題目只有整數就是對的
07/06 19:54, 26F
推
07/07 18:38, , 27F
-1,-2,-3,-4,-5,-6,-7
07/07 18:38, 27F
推
07/08 00:39, , 28F
bruceX: 遇到零就重算
07/08 00:39, 28F
→
07/08 00:39, , 29F
SansWord, 計算過程中取大的值, 所以反方向算回來就可以
07/08 00:39, 29F
→
07/08 00:40, , 30F
holydc: 這...這...這好像是我在你facebook的解法!!!
07/08 00:40, 30F
推
07/08 00:42, , 31F
pika0923: 你的是單向沒錯
07/08 00:42, 31F
→
07/08 00:42, , 32F
可是你有考慮過你每次都要做很多次乘積和三數取大/小
07/08 00:42, 32F
→
07/08 00:43, , 33F
雖然大家都是O(n), 可是我這邊實際跑出數字應該是不會
07/08 00:43, 33F
→
07/08 00:43, , 34F
比較慢?!
07/08 00:43, 34F
樓上就是被釣出來的高手 <(_ _)> 又釣到一次!! XD ※ 編輯: holydc (36.231.119.219), 07/08/2014 09:56:24
推
07/08 13:54, , 35F
這個方法改一下就可以單向了
07/08 13:54, 35F
→
07/08 13:54, , 36F
乘出負數時若之前沒有就記下來
07/08 13:54, 36F
→
07/08 13:55, , 37F
若之前有就除掉之前記下的數, 這樣就不必反向算回來
07/08 13:55, 37F
→
07/08 13:57, , 38F
實際速度會不會比較快就...要測看看 @@
07/08 13:57, 38F
→
07/08 15:07, , 39F
更進一步, 只有零的前一個是負數時需要去除, 中間不必
07/08 15:07, 39F
→
07/08 15:08, , 40F
這樣應該就確定會比較快
07/08 15:08, 40F
推
07/08 17:03, , 41F
剛剛看了一下lovdkkkk, 理論上你的做法應該會快些
07/08 17:03, 41F
→
07/08 17:03, , 42F
而且也才是真的one parse
07/08 17:03, 42F
→
07/08 17:04, , 43F
(1 parse比2 parse複雜的情況其實就當他不是好了...)
07/08 17:04, 43F
推
07/09 00:54, , 44F
perfact!
07/09 00:54, 44F
推
07/10 00:44, , 45F
現在才看到yp回的 嚴格說起來用ruby作已經比c慢20倍了XD
07/10 00:44, 45F
→
07/10 00:45, , 46F
而最大最小值其實算是為了閱讀方便
07/10 00:45, 46F
→
07/10 00:45, , 47F
如果玩過這類演算法競賽就會知道 在同一個語言的實作下
07/10 00:45, 47F
→
07/10 00:46, , 48F
其實答案對量級對之後實作差異非常小
07/10 00:46, 48F
→
07/10 00:46, , 49F
甚至有時候把一堆判斷式省掉還會比較快
07/10 00:46, 49F
→
07/10 00:47, , 50F
加一堆判斷式有時候是省小錢花大錢的作法
07/10 00:47, 50F
→
07/10 00:48, , 51F
我還蠻喜歡你這篇的作法就是因為概念簡單正確XD
07/10 00:48, 51F
推
07/10 03:09, , 52F
以 C 來說的話, 判斷相對於乘/除法是可以忽略的
07/10 03:09, 52F
→
07/10 03:10, , 53F
(除非判斷的對象本身需要其它運算)
07/10 03:10, 53F
→
07/10 03:17, , 54F
真的想再省的話, 只要多記一組數 (3 個 int)
07/10 03:17, 54F
→
07/10 03:18, , 55F
就可以把處理和原本判斷遇 0 重算的部份寫在一起
07/10 03:18, 55F
→
07/10 03:19, , 56F
以及在廻圈結束後再處理最後一個數
07/10 03:19, 56F
→
07/10 03:19, , 57F
更正, 多記一個 int 應該就夠了
07/10 03:19, 57F
→
07/10 03:39, , 58F
想成把處理前一個負數包成 function
07/10 03:39, 58F
→
07/10 03:40, , 59F
遇零及廻圈結束後再 call 一下就好, 只要多記前一個算的
07/10 03:40, 59F
→
07/10 03:40, , 60F
值, 位置則可以直接用推的
07/10 03:40, 60F
→
07/10 08:01, , 61F
再更正, 應該也不用多記, 在算下一個之前先處理就好
07/10 08:01, 61F
推
07/15 08:59, , 62F
pika0923: XD 因為我只想得出奇怪的解法XD
07/15 08:59, 62F
→
07/15 09:00, , 63F
不過是說 這其實有個複雜的證明在後面...
07/15 09:00, 63F
→
07/15 09:00, , 64F
理論上可以用數學歸納法證明...只要證明1~3個數字的數列
07/15 09:00, 64F
→
07/15 09:00, , 65F
然後最後在推廣他應該就可以
07/15 09:00, 65F
→
07/15 09:01, , 66F
lovdkkkk: 我自己實際上去看應該是多記一個負數就可
07/15 09:01, 66F
‣ 更多 holydc 的文章
文章代碼(AID): #1JjgMXuR (Soft_Job)
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 22 之 27 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共27篇)
Soft_Job 近期熱門文章
更多 近期熱門文章 >>
PTT職涯區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 holydc 的文章
文章代碼(AID): #1JjgMXuR (Soft_Job)