華為面試題(8分鐘寫出代碼)

aero

原帖由 xmyth 于 2006-11-14 17:04 發(fā)表
當(dāng)前數(shù)組a和數(shù)組b的和之差為
A = sum(a) - sum(b)

a的第i個(gè)元素和b的第j個(gè)元素交換后，a和b的和之差為
A' = sum(a) - a + b[j] - （sum(b) - b[j] + a)
       = sum(a) - sum(b) - 2 (a - b[j]) ...

和我想得一樣。

zwylinux

原帖由 forrestgang 于 2006-11-13 00:56 發(fā)表
有兩個(gè)數(shù)組a,b，大小都為n,數(shù)組元素的值任意，無(wú)序；
要求：通過(guò)交換a,b中的元素，使數(shù)組a元素的和與數(shù)組b元素的和之間的差最小

我寫的一段，不知道對(duì)不對(duì)
#include<stdio.h>

int
sumb (int m[], int x)
{
  int i;
  int sum = 0;
  for (i = 0; i < x; i++)
    sum += m[ i ];
  return sum;
}

main ()
{
  int min;
  int tmp;
  int i;
  int j;
  int this;
  int
  a[3] =
  {
  1, 3, 3};
  int
  b[3] =
  {
  3, -1,9};

  for (i = 0; i < 3; i++)
    for (j = 0; j < 3; j++)
      {
        this = sumb (a,3) - sumb (b,3);
        if(i==0&&j==0)
        {
          if(this < 0)
            this = this * (-1);
          min=this;
        }
        if(this<0)this=this*(-1);
        if (this < min)
          min = this;
        else
          {
            tmp = a[ i ];
            a[ i ] = b[ j ];
            b[ j ] = tmp;
          }
      }
  printf ("Min=%d\n", min);
}

[ 本帖最后由 zwylinux 于 2006-11-15 00:46 編輯 ]

gnap

我的想法：
求整體的平均值V；

然后兩個(gè)數(shù)組連接，整體根據(jù)元素與平均值之差的絕對(duì)值排序；

然后從中間斷開；

如果新引入一個(gè)2n的指針數(shù)組，效率會(huì)比較高。

seaway

原帖由 chzht001 于 2006-11-14 14:19 發(fā)表


你做的很快，但計(jì)算機(jī)恐怕要累死了

這點(diǎn)計(jì)算量怎么可能吧計(jì)算機(jī)累死。你太小看現(xiàn)在的計(jì)算機(jī)計(jì)算能力了。
太過(guò)強(qiáng)調(diào)算法是中國(guó)程序員的毛病。

你可能花半個(gè)小時(shí)完成了一個(gè)相對(duì)比較好的程序，比我的程序快了一倍 （30秒）
一用用了30分30秒
我用了3分鐘
就是說(shuō)你讓客戶等待了30分30秒
而我讓客戶等待了3分鐘，從這個(gè)角度，我更有機(jī)會(huì)爭(zhēng)取到客戶。

一般應(yīng)用程序，都是將實(shí)現(xiàn)功能作為第一目的。當(dāng)需要處理效率問(wèn)題時(shí)候才去單獨(dú)分析優(yōu)化。前提是用戶選擇了你的程序之后。否則用戶都沒選擇你的程序，你程序再好有個(gè)屁用

seaway

原帖由 seaway 于 2006-11-14 12:48 發(fā)表
t1＝a1的和＋a2的和；
結(jié)果數(shù)組＝空數(shù)組;
循環(huán)開始（所有的數(shù)組組合情況）
{
  t2=絕對(duì)值（新數(shù)組a-新數(shù)組b）;
  if( t2< t1)
  {
       t1=t2;
       結(jié)果數(shù)組CLEAR（）；
       結(jié)果數(shù)組ADD（t2 ...

而且我的程序非常容易閱讀和理解。
容易閱讀也是好的程序的特點(diǎn)。他更容易維護(hù)，不容易出錯(cuò)。
至少可以用我的程序來(lái)檢驗(yàn)?zāi)隳侵挥袛?shù)學(xué)家才能看懂的代碼是不是可靠。

flw

原帖由 seaway 于 2006-11-15 08:58 發(fā)表

這點(diǎn)計(jì)算量怎么可能吧計(jì)算機(jī)累死。你太小看現(xiàn)在的計(jì)算機(jī)計(jì)算能力了。
太過(guò)強(qiáng)調(diào)算法是中國(guó)程序員的毛病。

你可能花半個(gè)小時(shí)完成了一個(gè)相對(duì)比較好的程序，比我的程序快了一倍 （30秒）
一用用了30分30秒
我 ...

你說(shuō)的一點(diǎn)兒也不錯(cuò)，我深有同感。
可是，我還是有兩點(diǎn)要說(shuō)：
1，本帖的前提應(yīng)聘的是華為，網(wǎng)絡(luò)設(shè)備對(duì)性能的要求大家都知道吧？
2，在你發(fā)貼之時(shí)，前面已經(jīng)有兩位網(wǎng)友表示過(guò)自己的高性能算法了——至少比你的性能高的不是一點(diǎn)半點(diǎn)，你為什么不參考一下他們的做法呢？埋頭苦干難道不是中國(guó)程序員的通病嗎？

seaway

原帖由 flw 于 2006-11-15 09:12 發(fā)表

你說(shuō)的一點(diǎn)兒也不錯(cuò)，我深有同感。
可是，我還是有兩點(diǎn)要說(shuō)：
1，本帖的前提應(yīng)聘的是華為，網(wǎng)絡(luò)設(shè)備對(duì)性能的要求大家都知道吧？
2，在你發(fā)貼之時(shí)，前面已經(jīng)有兩位網(wǎng)友表示過(guò)自己的高性能算法了——至少比你的 ...

首先我同意你的觀點(diǎn)，我并不認(rèn)為我的答案有多好。
如果考官在給我題目同時(shí)給了我前面幾位兄臺(tái)的答案我肯定是照抄不誤，并仔細(xì)學(xué)習(xí)其精妙的算法。
但是我起碼按要求完成了題目，起碼比把結(jié)果算錯(cuò)的朋友更有優(yōu)勢(shì)。

要保證8分鐘完成任務(wù)。你必須要考慮的的一個(gè)因素就是時(shí)間。怎么能在8分鐘內(nèi)完成任務(wù)。
我不是天才，所以我采用了最一般的思維方式在指定的時(shí)間內(nèi)完成了任務(wù)。

做事情首先明確目標(biāo)：

目標(biāo)1：完成題目
目標(biāo)2：確保結(jié)果正確
目標(biāo)3：全部時(shí)間8分鐘

我拿到題目后首先考慮如何實(shí)現(xiàn)，30秒后發(fā)現(xiàn)，以我的才智8分鐘不可能寫出精妙的算法。
所以，我拿出保守方案，就是以達(dá)到題目為目標(biāo)。
如果哪位可以在8分中吧上面三個(gè)目標(biāo)全部達(dá)成。這個(gè)工作機(jī)會(huì)我讓給他一點(diǎn)都不遺憾。

[ 本帖最后由 seaway 于 2006-11-15 10:40 編輯 ]

splitflag

原帖由 xmyth 于 2006-11-14 17:04 發(fā)表
當(dāng)前數(shù)組a和數(shù)組b的和之差為
A = sum(a) - sum(b)

a的第i個(gè)元素和b的第j個(gè)元素交換后，a和b的和之差為
A' = sum(a) - a + b[j] - （sum(b) - b[j] + a)
       = sum(a) - sum(b) - 2 (a - b[j]) ...

不錯(cuò)啊，有證明呢。

hawk2012

假設(shè)數(shù)組a中的所有元素用a1, a2, a3, ..., an表示， 數(shù)組b中的為b1,b2,b3,...,bn表示。
那么令result = (a1 + a2 + a3+ ... + an) - (b1 + b2 + b3 + ... + bn)
                   = (a1 + a2 + a3+ ... + an) +  (b1 + b2 + b3 + ... + bn) - 2(b1 + b2 + b3 + ... + bn)
      令Sum = (a1 + a2 +... + an) + (b1 + b2 + b3 + ... + bn) 這里Sum是個(gè)恒定的值
所以 result = Sum - 2(b1 + b2 + b3 + ... + bn)
要使 result 為最小，只需要(b1 + b2 + b3 + ... + bn)為最大。
所以 把數(shù)組a 和 b , 放到數(shù)組c中，進(jìn)行排序（可以使用快速排序方法），然后將c數(shù)組中的前n個(gè)元素放到a數(shù)組中，后n個(gè)元素放到b中。這樣的a,b數(shù)組就是符合題目要求的數(shù)組了

laowolf

樓上的......狂暈..........................