Re: [討論] 面試遇到的考題
我覺得有些人都陷入了一個盲點，
求最大整數值，該值不一定為0或正整數的，其實也有可能為負整數。
我的解法，基本概念很簡單，可以再優化，沒有針對陣列長度0以下除錯，
但是我懶…
語言用C#，時間複雜度O(n)或O(n-1)，根本沒差Orz
基本概念是
1. 一次迴圈跑完
2. 同時計算兩種相鄰的數字，然後再比較
目前可以優化的地方有
1. 針對陣列長度0以下除錯
2. 部分判斷流程可以再更好，加速計算時間
不考慮分割陣列與其他演算法是因為
1. 可讀性。如果程式接手，希望第一眼就知道在做什麼
2. 目前效率可接受。等哪天陣列長度是一百萬，應該就要換演算法了
private void button1_Click(object sender, EventArgs e)
{
int[] array1 = { 2, -7, 0, 2, 3, 8, -6, 5 };
int[] array2 = { -2, 0, 3, 5, -7 };
int max1 = this.CalculateMax(array1);
int max2 = this.CalculateMax(array2);
Console.WriteLine(max1); // 48
Console.WriteLine(max2); // 15
}
private int CalculateMax(int[] array)
{
if (array.Length == 1) // 陣列長度1，回傳該值
{
return array[0];
}
int max = array[0] * array[1]; // 初始max
for (int i = 0; i < array.Length - 1; i++)
{
// 計算相鄰兩個數字
int maxAdjacent2 = array[i] * array[i + 1];
// 計算相鄰三個數字，初始化
int maxAdjacent3 = maxAdjacent2 - 1;
if (i <= array.Length - 3)
{
maxAdjacent3 = array[i] * array[i + 1] * array[i + 2];
}
// 計算最大結果
if (maxAdjacent2 >= maxAdjacent3 && maxAdjacent2 > max)
{
max = maxAdjacent2;
}
else if (maxAdjacent3 >= maxAdjacent2 && maxAdjacent3 > max)
{
max = maxAdjacent3;
}
}
return max;
}
邏輯上應該沒什麼問題，
有錯誤麻煩請指出，謝謝。
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.249.117.38
※ 文章網址: http://www.ptt.cc/bbs/Soft_Job/M.1404444170.A.84E.html
※ 編輯: StupidGaGa (60.249.117.38), 07/04/2014 11:39:10
推
07/04 13:03, , 1F
07/04 13:03, 1F
原題的題意有很清楚的表達「相鄰」的概念，
是板上很多人不知道為什麼複雜化，
原題的陣列一是在說明，以某位置為中心，向左與向右的「相鄰」，
原題的陣列二是在說明，以某位置為中心，向左或向右的「相鄰」，
之前我在面試人的時候也是很多人題意都搞錯。
假設陣列為[1, 2, 3, 4]
頂多也只有這些排列，
左邊與右邊的相鄰：[1, 2, 3]、[2, 3, 4]
左邊或右邊的相鄰：[1, 2]、[2, 3]、[3, 4]
下面這種排列是沒有
四個以上：[1, 2, 3, 4]
因為不構成「相鄰」的概念
→
07/04 13:30, , 2F
07/04 13:30, 2F
其實這時候應該像面試官提出問題點，然後請面試官解釋題意，
或者寫出來後，
可以跟面試官說明為什麼這樣寫的想法，與自己所認解的題意為何。
這種面試通常都不會考太難，這一題30分鐘我覺得應該是希望面試者謹慎點，
要不然就是在試後當場key in紙上的程式碼看結果，但這太狠了…
推
07/04 13:32, , 3F
07/04 13:32, 3F
→
07/04 13:55, , 4F
07/04 13:55, 4F
→
07/04 13:55, , 5F
07/04 13:55, 5F
推
07/04 15:28, , 6F
07/04 15:28, 6F
→
07/04 16:10, , 7F
07/04 16:10, 7F
→
07/04 16:37, , 8F
07/04 16:37, 8F
其實因為原文底下有人說ACM 11059，
但實際上這題跟ACM 11059的題目差很多，
然後一推人的回答都是ACM 11059…
這是ACM 11059的題目 http://ppt.cc/nhYu
我貼一部分上來
The Problem
Given a sequence of integers S = {S1, S2, ..., Sn}, you should determine what
is the value of the maximum positive product involving consecutive terms of
S. If you cannot find a positive sequence, you should consider 0 as the value
of the maximum product.
簡單講就是
1. 給一串數列，要計算其中「連續」數列相乘的最大正數值
2. 如果沒有最大正數值，請回傳0
跟原PO的題意差蠻多的，然後回文多少人是根據ACM 11059再回的？
另外很有趣的一點，
如果連續四個數字算相鄰，那連續數字與相鄰數字的差別在？
難道打麻將，對家叫做相鄰？
難道過年排福袋，第一位與最後一位也叫做相鄰？
我只能說，哪間公司的考題！？面試官給我出來面對！！
※ 編輯: StupidGaGa (60.249.117.38), 07/04/2014 17:10:14
→
07/04 17:05, , 9F
07/04 17:05, 9F
→
07/04 17:09, , 10F
07/04 17:09, 10F
→
07/04 17:14, , 11F
07/04 17:14, 11F
推
07/04 18:04, , 12F
07/04 18:04, 12F
→
07/04 18:42, , 13F
07/04 18:42, 13F
推
07/04 21:09, , 14F
07/04 21:09, 14F
→
07/04 21:09, , 15F
07/04 21:09, 15F
→
07/04 23:37, , 16F
07/04 23:37, 16F
討論串 (同標題文章)