一道c的面试题,大数相乘。

简介: 这是我亲身经历的一个面试题目,并且表现的是整个面试里面最为糟糕的环节,令我十分恼火。回来以后我在tc2.0上写它,发现依然花费了我相当多的时间用于改错和调试(从这一点来看,我面试里的表现也算正常了)。尽管这个问题看起来是如此的简单。

这是我亲身经历的一个面试题目,并且表现的是整个面试里面最为糟糕的环节,令我十分恼火。回来以后我在tc2.0上写它,发现依然花费了我相当多的时间用于改错和调试(从这一点来看,我面试里的表现也算正常了)。尽管这个问题看起来是如此的简单。当然,这里面有我对c 和c++的生疏和不熟练也有很大关系,此外是对算法的学习和研究还没有完成,还处于一个准备阶段。

题干:输入两个较大的数,输出相乘的结果。
意思也就是两个数很大,超出了int的存储范围。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N 100
void GetDigits(int *a,char *s);
void multiply(int *a,int *b,int *c);
main()
{
    char s1[N],s2[N];
    int i,j,a[N],b[N],c[N*2];

    printf("\n input number a: ");
    scanf("%s",s1);
    printf("\n input number b: ");
    scanf("%s" ,s2);


    //把输入的字符串,按位存放到数组 
    GetDigits(a,s1);
    GetDigits(b,s2);

    multiply(a,b,c);

    //找到最高位
    j=N*2-1;
    while(c[j]==0)
        j--;

    //打印计算结果
    printf("\n %s * %s=",s1,s2);
    for(i=j;i>=0;i--)
        printf("%d",c[i]);
}

/*把字符串形式的数字按位存放到数组*/
void GetDigits(int *a, char *s)
{
   int i;
   char digit;
   int len=strlen(s);
   for(i=0;i<N;i++)
    *(a+i)=0;
   for(i=0;i<len;i++)
   {
        digit=*(s+i);
        *(a+len-1-i) = digit - '0';
   }
}

/*把a*b的结果存储到数组c中,按位表示*/
void multiply(int *a,int *b,int *c)
{
     int i,j;
       //先把结果数组设置为0
     for(i=0;i<N*2;i++)
          *(c+i)=0;

     for(i=0;i<N;i++)
           for(j=0;j<N;j++)
                  *(c+i+j)+=*(a+i) * *(b+j);

     // 处理进位
     for(i=0;i<N*2-1;i++)
     {
           *(c+i+1)+=*(c+i)/10;       //进位累加到高位
           *(c+i)=*(c+i)%10;          //该位的最后结果
     }
}


当我贴出这些代码时,它们基本通过简单的测试。
大致的过程是,输入两个相乘的数字的字符串(没有对输入数字的合法性进行检查),然后按位存入较大的数组,然后循环按位相乘并累加。最后从低位到高位依次完成进位操作。这里面的问题是,一个是int数组每一个元素只存储0~9,一个byte就可以容纳2个数据位了,而现在是一位占用了4个byte,在空间上有巨大浪费。所以其实可以压缩。另外一点是相乘函数,实际上可以将两个因子的位数作为参数传递,以避免为0的那些高位的不必要的累加。

此外,我还答错了一个题目,冒泡排序的时间复杂度,实际上是从1累加到n,那么应该是n的平方才对。。。而我的回答居然是快速排序的复杂度,实际快速排序的时间n log n,它也是排序算法的极限。

我非常愤怒自己的低级表现,怎么批评也不为过。但是实际上也是一次经验累积,它非常类似应试,需要比较充分的准备以及比较深厚的理论功底。


  【补充的后记】

  这篇在我的博客中没有什么技术含量的文章,我发现阅读量竟然很大,应该是由于被搜索引擎带来的流量导致的。所以引发我又想写点补充。应该说这是我最失败和丢人的一次面试了,事到如今当然我不回避,也勇于承认自己当时是个超级菜鸟的事实。

 

  首先面试发生在我第一次没有和原公司续约而找工作的时期,当时我的主要兴趣和工作经历都在.net的C#和移动设备(PDA,当时还称为 Compact Framework)的开发方面。得到 XXX 这个面试纯属意外,这个面试是 C 语言方面的,而当时的我由于 C 语言仅停留在大一学习的水准,再加上工作时从事的是.net,所以失败的结果是必然的。在面试前晚上和师弟彻夜谈了很长时间,他也为了帮助我准备给我讲了很多linux下编译的一些东西,没有接触过的东西别人给你再怎么讲你也是无益的,在当时对我来说当然听得是不知所云,导致休息的不太好。他说面试我的时候还有一个 zju 的学妹。

 

  第二天的面试简直就是一个悲剧。更糟糕的是在我的嫡系土著学妹面前,别提多尴尬。面试有两个 GG 和一个 MM 即我的学妹,两个 GG 一个好像带着眼镜有点深藏不露的感觉,对我的回答往往不置可否,让我感觉比较的心理没谱和紧张。另一个 GG 稍胖一点的则比较友善一点,感觉挺好。一个人问我知道 valitile 这个关键字吗,我说不知道(汗,别说我当时那么菜,就算是今天我也还从没用过这个关键字,至今没接触到这个关键字的实际应用场景)。然后就是问我冒泡排序的复杂度是多少,虽然当时考出了软件设计师和系统分析师(突击复习的),但由于当时对算法也没有深入研究,所以我回答的是 (n log n),后来我知道这是基于比较排序的算法的时间复杂度的上限,也就是说不是基于比较的排序可能更快,例如我后来用C语言写了基本排序算法,通过试验我发现基尔排序是最快的,比快速排序还快,而冒泡排序是最慢的(n平方)。然后就是大数相乘的问题,同样没有遇到和做过类似问题,不会是正常的,如果我当时就说不会就对了,但我这个人是不轻易服输的,所以我在紧张条件下在他们在后面注视的条件下当然没办法写出来正确的代码,但我很固执,不想承认自己当时写不出来,而他们两个似乎也不打算打断我,ms是让我自己提出放弃,但我不会,在当时我是非常固执的,所以这个过程僵持了大概10多分钟,事后我想是不是我应该变通一下自己的原则。所以在之后的我再次遇到面试的时候,有时候我会让面试官重新描述下,然后我很快说出自己的真实想法和底细,如果不会我就不和他浪费时间了。总之,当时的窘迫的,面试出来也非常失落和受挫,以至于让自己有些伤心,尽管我并没有对这个意外而来的面试有什么期待。正是基于这次面试失败的打击,所以我当时就很快的同意了另一家公司的意愿。

 

  之后我在研究.net的过程中逐渐意识到了.net中的一些局限性,然后我逐渐开始思考真正“无所不能”和强大的语言是什么,当然这样的概念可能从技术上来讲容易引发口水,而我当时确实想要掌握的是最强大的语言,而不是由别人给我定一个舞台,我只能在这个舞台范围内发挥。然后我又去重新看了看C语言,重新掌握和学习 VC 和最传统的 Windows开发技术(即通常说的CS开发)。从这篇文章来说,但今天如果我重新经历那个面试结果自然又会略有不同(但linux方面我还是零分)。同时也印证了每个人都从菜鸟阶段经历过的这句话(这句话的意思并不是说我今天就不是菜鸟,这是一个相对的问题,例如横向说是和谁比,纵向是和自己的过去比),我想每个人的确都要经历一个成长阶段,尤其是技术是需要学习的,最重要的是做技术的态度,是不是严谨,是不是求是,这是最重要的。在这里有很多态度不好的人,他们或者抄袭,或者隐瞒自己对其他人技术成果的参考和引用。或者炫耀自己是一个高手而流露出洋洋自得的情绪,或者从不肯正面承认自己的错误,即使被人指出也要百般掩饰和拒绝承认。而这些都是普遍存在的现象。包括最近某些博客主对评论的态度等等,都是不当的。我从不在自己的博客上发表任何没有什么技术含量的口水文章或者感叹,但是我想,就是真正的高手,是什么样的?他们不是用自大的口气和语气吹嘘自己,而是用自己的成果和作品,这就足以了。我看到高手写文章的风格,都是用语关注和围绕要讲述的事物本身,而不会流于炫耀和自大,最多有一些调侃和诙谐用语而已。一旦一个人用语轻浮,则几乎可以肯定这个人的技术境界和程序员素质比较低,如果我发现这样的文章里的提到的成果是不那么容易获取的,我的反应就是最探查他是不是引用了其他人的成果(而被他有意识和无意识的进行隐瞒了,因为这样可以满足他的炫耀)。在一些论坛里,往往能见到一些很幼稚的意气之争,我不明白,这些人你为的目的是什么,为了成为所谓的“高手”?为了让别人说你是“高手”,这有何用?最重要的是你创造了什么,你又为别人提供了什么,你又对其他人带来了什么影响力,切勿陶醉在自己是“高手”的幻境中,一旦你觉得自己是高手了,别人真么都那么菜呢,哪么潜在的客观结论就是,你已经沦为了一只井底之蛙(因为真正的境界越高的高手通常是类似隐士,他们是不屑于提示一个肤浅的人他们的存在的)。

 

  —— hoodlum1980 补记于 2011年8月9日。

目录
相关文章
|
6月前
|
NoSQL Java Go
面试题30天打卡-day02
面试题30天打卡-day02
32 0
|
3月前
面试题 08.04:幂集
面试题 08.04:幂集
16 0
|
3月前
|
网络协议 NoSQL 数据库
C++面试题
C++面试题
|
8月前
|
前端开发 JavaScript 开发工具
【面试题2】2
【面试题2】
|
6月前
|
设计模式 负载均衡 Java
面试题30天打卡-day25
面试题30天打卡-day25
15 0
|
6月前
|
SQL Java 关系型数据库
面试题30天打卡-day09
面试题30天打卡-day09
28 0
|
6月前
|
存储 NoSQL Java
面试题30天打卡-day24
面试题30天打卡-day24
21 0
|
6月前
|
NoSQL 关系型数据库 应用服务中间件
面试题30天打卡-day15
面试题30天打卡-day15
23 0
|
6月前
|
缓存 Dubbo Java
面试题30天打卡-day16
面试题30天打卡-day16
24 0
|
存储 XML SQL
面试题
面试题
42 0