2021年華為軟件工程師面試題

小編:管理員 424閱讀 2021.06.22

第1題:


寫一個程序, 要求功能:求出用1,2,5這三個數不同個數組合的和為100的組合個數。

如:100個1是一個組合,5個1加19個5是一個組合。。。。 請用C++語言寫。




最容易想到的算法是:

設x是1的個數,y是2的個數,z是5的個數,number是組合數

注意到0<=x<=100,0<=y<=50,0<=z=20,所以可以編程為: 

number=0;

for (x=0; x<=100; x++)

for (y=0; y<=50; y++)

for (z=0; z<=20; z++)

if ((x+2*y+5*z)==100)

number++;

cout<<number<<endl;

上面這個程序一共要循環100*50*20次,效率實在是太低了

事實上,這個題目是一道明顯的數學問題,而不是單純的編程問題。我的解法如下:

因為x+2y+5z=100

所以x+2y=100-5z,且z<=20 x<=100 y<=50

所以(x+2y)<=100,且(x+5z)是偶數

對z作循環,求x的可能值如下:

 

z=0, x=100, 98, 96, ... 0

z=1, x=95, 93, ..., 1

z=2, x=90, 88, ..., 0

z=3, x=85, 83, ..., 1

z=4, x=80, 78, ..., 0

......

z=19, x=5, 3, 1

z=20, x=0

 

因此,組合總數為100以內的偶數+95以內的奇數+90以內的偶數+...+5以內的奇數+1,

即為:

(51+48)+(46+43)+(41+38)+(36+33)+(31+28)+(26+23)+(21+18)+(16+13)+(11+8)+(6+3)+1

 

 

某個偶數m以內的偶數個數(包括0)可以表示為m/2+1=(m+2)/2

某個奇數m以內的奇數個數也可以表示為(m+2)/2

 

所以,求總的組合次數可以編程為:

number=0;

for (int m=0;m<=100;m+=5)

{

number+=(m+2)/2;

}

cout<<number<<endl;

這個程序,只需要循環21次, 兩個變量,就可以得到答案,比上面的那個程序高效了許多

倍----只是因為作了一些簡單的數學分析

 

這再一次證明了:計算機程序=數據結構+算法,而且算法是程序的靈魂,對任何工程問

題,當用軟件來實現時,必須選取滿足當前的資源限制,用戶需求限制,開發時間限制等種

種限制條件下的最優算法。而絕不能一拿到手,就立刻用最容易想到的算法編出一個程序了

事——這不是一個專業的研發人員的行為。

 

那么,那種最容易想到的算法就完全沒有用嗎?不,這種算法正好可以用來驗證新算法

的正確性,在調試階段,這非常有用。在很多大公司,例如微軟,都采用了這種方法:在調

試階段,對一些重要的需要好的算法來實現的程序,而這種好的算法又比較復雜時,同時用

容易想到的算法來驗證這段程序,如果兩種算法得出的結果不一致(而最容易想到的算法保

證是正確的),那么說明優化的算法出了問題,需要修改。

可以舉例表示為:

#ifdef DEBUG

int simple();

#end if

int optimize();

......

in a function:

{

result=optimize();

ASSERT(result==simple());

}

這樣,在調試階段,如果簡單算法和優化算法的結果不一致,就會打出斷言。同時,在程

序的發布版本,卻不會包含笨重的simple()函數!魏未笮凸こ誊浖夹枰A先設計良

好的調試手段,而這里提到的就是一種有用的方法。



第2題:


一個學生的信息是:姓名,學號,性別,年齡等信息,用一個鏈表,把這些學生信息連在一起,給出一個age, 在些鏈表中刪除學生年齡等于age的學生信息。




#include "stdio.h"

#include "conio.h"

 

struct stu{

char name[20];

char sex;

int no;

int age;

struct stu * next;

}*linklist;

struct stu *creatlist(int n)

{

int i;

//h為頭結點,p為前一結點,s為當前結點

struct stu *h,*p,*s;

h = (struct stu *)malloc(sizeof(struct stu));

h->next = NULL;

p=h;

for(i=0;i<n;i++)

s = (struct stu *)malloc(sizeof(struct stu));

p->next = s;

printf("Please input the information of the student: name sex no age \n");

scanf("%s %c %d %d",s->name,&s->sex,&s->no,&s->age);

s->next = NULL;

p = s;

}

printf("Create successful!");

return(h);

}

void deletelist(struct stu *s,int a)

{

struct stu *p;

while(s->age!=a)

{

p = s;

s = s->next;

}

if(s==NULL)

printf("The record is not exist.");

else

{

p->next = s->next;

printf("Delete successful!");

}

}

void display(struct stu *s)

{

s = s->next;

while(s!=NULL)

{

printf("%s %c %d %d\n",s->name,s->sex,s->no,s->age);

s = s->next;

}

}

int main()

{

struct stu *s;

int n,age;

printf("Please input the length of seqlist:\n");

scanf("%d",&n);

s = creatlist(n);

display(s);

printf("Please input the age:\n");

scanf("%d",&age);

deletelist(s,age);

display(s);

return 0;

}



第3題:


實現一個函數,把一個字符串中的字符從小寫轉為大寫。




#include "stdio.h"

#include "conio.h"

 

void uppers(char *s,char *us)

{

for(;*s!='\0';s++,us++)

{

if(*s>='a'&&*s<='z')

*us = *s-32;

else

*us = *s;

}

*us = '\0';

}

int main()

{

char *s,*us;

char ss[20];

printf("Please input a string:\n");

scanf("%s",ss);

s = ss;

uppers(s,us);

printf("The result is:\n%s\n",us);

getch();

}



第4題:


隨機輸入一個數,判斷它是不是對稱數(回文數)(如3,121,12321,45254)。不能用字符串庫函數




1.

函數名稱:Symmetry 

功能: 判斷一個數時候為回文數(121,35653) 

輸入: 長整型的數 

輸出: 若為回文數返回值為1 esle 0 

******************************************************************/

unsigned char Symmetry (long n)

{

long i,temp;

i=n; temp=0;

while(i) //不用出現長度問題,將數按高低位掉換

{

temp=temp*10+i%10;

i/=10;

}

return(temp==n);

方法一 

/* --------------------------------------------------------------------------- 

功能: 

判斷字符串是否為回文數字 

實現: 

先將字符串轉換為正整數,再將正整數逆序組合為新的正整數,兩數相同則為回文數字 

輸入: 

char *s:待判斷的字符串 

輸出: 

無 

返回: 

0:正確;1:待判斷的字符串為空;2:待判斷的字符串不為數字; 

3:字符串不為回文數字;4:待判斷的字符串溢出 

---------------------------------------------------------------------------- */ 

unsigned IsSymmetry(char *s) 

char *p = s; 

long nNumber = 0; 

long n = 0; 

long nTemp = 0; 

 

/*判斷輸入是否為空*/ 

if (*s == \'\\0\') 

return 1; 

 

/*將字符串轉換為正整數*/ 

while (*p != \'\\0\') 

/*判斷字符是否為數字*/ 

if (*p<\'0\' || *p>\'9\') 

return 2; 

 

/*判斷正整數是否溢出*/ 

if ((*p-\'0\') > (4294967295-(nNumber*10))) 

return 4; 

 

nNumber = (*p-\'0\') + (nNumber * 10); 

 

p++; 

 

/*將數字逆序組合,直接抄樓上高手的代碼,莫怪,呵呵*/ 

n = nNumber; 

while(n) 

/*判斷正整數是否溢出*/ 

if ((n%10) > (4294967295-(nTemp*10))) 

return 3; 

 

nTemp = nTemp*10 + n%10; 

n /= 10; 

 

/*比較逆序數和原序數是否相等*/ 

if (nNumber != nTemp) 

return 3; 

 

return 0; 

 

方法二 

/* --------------------------------------------------------------------------- 

功能: 

判斷字符串是否為回文數字 

實現: 

先得到字符串的長度,再依次比較字符串的對應位字符是否相同 

輸入: 

char *s:待判斷的字符串 

輸出: 

無 

返回: 

0:正確;1:待判斷的字符串為空;2:待判斷的字符串不為數字; 

3:字符串不為回文數字 

---------------------------------------------------------------------------- */ 

unsigned IsSymmetry_2(char *s) 

char *p = s; 

int nLen = 0; 

int i = 0; 

 

/*判斷輸入是否為空*/ 

if (*s == \'\\0\') 

return 1; 

 

/*得到字符串長度*/ 

while (*p != \'\\0\') 

/*判斷字符是否為數字*/ 

if (*p<\'0\' || *p>\'9\') 

return 2; 

 

nLen++; 

p++; 

 

/*長度不為奇數,不為回文數字*/ 

if (nLen%2 == 0) 

return 4; 

 

/*長度為1,即為回文數字*/ 

if (nLen == 1) 

return 0; 

 

/*依次比較對應字符是否相同*/ 

p = s; 

i = nLen/2 - 1; 

while (i) 

if (*(p+i) != *(p+nLen-i-1)) 

return 3; 

 

i--; 

 

return 0; 



第5題:


求2~2000的所有素數.有足夠的內存,要求盡量快




int findvalue[2000]={2};

static int find=1;

bool adjust(int value)

{

assert(value>=2);

if(value==2) return true;

for(int i=0;i<=find;i++)

{

if(value%findvalue[i]==0)

return false;

}

findvalue[find++];

return true;

}



第6題:


A,B,C,D四個進程,A向buf里面寫數據,B,C,D向buf里面讀數據,

當A寫完,且B,C,D都讀一次后,A才能再寫。用P,V操作實現。



第7題:


將單向鏈表reverse,如ABCD變成DCBA,只能搜索鏈表一次。



第8題:


將二叉樹的兩個孩子換位置,即左變右,右變左。不能用遞規(變態。



關聯標簽: