华为面试题(8分钟写出代码)

aero

原帖由 xmyth 于 2006-11-14 17:04 发表
当前数组a和数组b的和之差为
A = sum(a) - sum(b)

a的第i个元素和b的第j个元素交换后，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 发表
有两个数组a,b，大小都为n,数组元素的值任意，无序；
要求：通过交换a,b中的元素，使数组a元素的和与数组b元素的和之间的差最小

我写的一段，不知道对不对
#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；

然后两个数组连接，整体根据元素与平均值之差的绝对值排序；

然后从中间断开；

如果新引入一个2n的指针数组，效率会比较高。

seaway

原帖由 chzht001 于 2006-11-14 14:19 发表


你做的很快，但计算机恐怕要累死了

这点计算量怎么可能吧计算机累死。你太小看现在的计算机计算能力了。
太过强调算法是中国程序员的毛病。

你可能花半个小时完成了一个相对比较好的程序，比我的程序快了一倍 （30秒）
一用用了30分30秒
我用了3分钟
就是说你让客户等待了30分30秒
而我让客户等待了3分钟，从这个角度，我更有机会争取到客户。

一般应用程序，都是将实现功能作为第一目的。当需要处理效率问题时候才去单独分析优化。前提是用户选择了你的程序之后。否则用户都没选择你的程序，你程序再好有个屁用

seaway

原帖由 seaway 于 2006-11-14 12:48 发表
t1＝a1的和＋a2的和；
结果数组＝空数组;
循环开始（所有的数组组合情况）
{
  t2=绝对值（新数组a-新数组b）;
  if( t2< t1)
  {
       t1=t2;
       结果数组CLEAR（）；
       结果数组ADD（t2 ...

而且我的程序非常容易阅读和理解。
容易阅读也是好的程序的特点。他更容易维护，不容易出错。
至少可以用我的程序来检验你那只有数学家才能看懂的代码是不是可靠。

flw

原帖由 seaway 于 2006-11-15 08:58 发表

这点计算量怎么可能吧计算机累死。你太小看现在的计算机计算能力了。
太过强调算法是中国程序员的毛病。

你可能花半个小时完成了一个相对比较好的程序，比我的程序快了一倍 （30秒）
一用用了30分30秒
我 ...

你说的一点儿也不错，我深有同感。
可是，我还是有两点要说：
1，本帖的前提应聘的是华为，网络设备对性能的要求大家都知道吧？
2，在你发贴之时，前面已经有两位网友表示过自己的高性能算法了——至少比你的性能高的不是一点半点，你为什么不参考一下他们的做法呢？埋头苦干难道不是中国程序员的通病吗？

seaway

原帖由 flw 于 2006-11-15 09:12 发表

你说的一点儿也不错，我深有同感。
可是，我还是有两点要说：
1，本帖的前提应聘的是华为，网络设备对性能的要求大家都知道吧？
2，在你发贴之时，前面已经有两位网友表示过自己的高性能算法了——至少比你的 ...

首先我同意你的观点，我并不认为我的答案有多好。
如果考官在给我题目同时给了我前面几位兄台的答案我肯定是照抄不误，并仔细学习其精妙的算法。
但是我起码按要求完成了题目，起码比把结果算错的朋友更有优势。

要保证8分钟完成任务。你必须要考虑的的一个因素就是时间。怎么能在8分钟内完成任务。
我不是天才，所以我采用了最一般的思维方式在指定的时间内完成了任务。

做事情首先明确目标：

目标1：完成题目
目标2：确保结果正确
目标3：全部时间8分钟

我拿到题目后首先考虑如何实现，30秒后发现，以我的才智8分钟不可能写出精妙的算法。
所以，我拿出保守方案，就是以达到题目为目标。
如果哪位可以在8分中吧上面三个目标全部达成。这个工作机会我让给他一点都不遗憾。

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

splitflag

原帖由 xmyth 于 2006-11-14 17:04 发表
当前数组a和数组b的和之差为
A = sum(a) - sum(b)

a的第i个元素和b的第j个元素交换后，a和b的和之差为
A' = sum(a) - a + b[j] - （sum(b) - b[j] + a)
       = sum(a) - sum(b) - 2 (a - b[j]) ...

不错啊，有证明呢。

hawk2012

假设数组a中的所有元素用a1, a2, a3, ..., an表示， 数组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是个恒定的值
所以 result = Sum - 2(b1 + b2 + b3 + ... + bn)
要使 result 为最小，只需要(b1 + b2 + b3 + ... + bn)为最大。
所以 把数组a 和 b , 放到数组c中，进行排序（可以使用快速排序方法），然后将c数组中的前n个元素放到a数组中，后n个元素放到b中。这样的a,b数组就是符合题目要求的数组了

laowolf

楼上的......狂晕..........................