2013華為校招機試與面試題整理
1
(1.) 字母大小寫反轉
這到題沒什麼可說的,只是我很久沒寫這樣要IO輸入輸出的代碼,當時看到華為的提示紙條上寫著“只能使用stdin方式輸入”,還愣了一會:一定是我打開方式不對,什麼時候有了一個stdin的輸入函數?難道我又學藝不精了……後面才反應過來,直接按英文字面意思理解為“只能使用標准輸入方式”就好了。好了,言歸正傳,回到這道題,至少可以用以下兩種方式:
C++ STL庫string中 有 isupper , islower , toupper ,tolower 函數
通過 +/- ('a'-'A'+0)
(2.) n個人圍成一圈,從第1個人開始報數,每報到第m個人,則其出局,求最後出局的人的初始序號。
第1種方法,我當時是用了個狀態表來記錄這人有沒有出局,沒出局則報數計數器加1並玩下走,碰到第m個報數號則更新狀態為已出局,碰到隊伍最末則重新移動到隊首。
#include <iostream>
#define N 4
#define M 3
using namespace std;
int *man = NULL;
int JosephusSol_statusTab(int n,int m)
{
int sn=0 , pos = 0 ,loop_pos=0;
do
{
if( man[pos] == 0 ){//此人未出局
loop_pos++;
if(loop_pos == m){//找到一輪報數的出局者
sn++;
man[pos] = sn ; // 標記出局序號
loop_pos = 0;
}
}
pos ++ ;
if(pos==n)
pos = 0;
}while(sn!=n);
return pos;
}
int main()
{
int sn=0 , pos = 0 ,loop_pos=0;
man = new int [N];
for(int i=0;i<N;i++)
man[i] = 0;
pos = JosephusSol_statusTab(N,M);
cout << pos <<endl ;
if(man != 0)
delete [] man;
return 0;
}
第2種方法是雙向鏈表,技術面面試的時候,面試官就考了我這一題,在紙上快速寫代碼的能力還是有所欠缺。
第3種方法是遞歸,
第0次報數(即初始排列狀態)如下:
1
2
……
n
第1次報數到m,剔除後的序列為:
m+1
m+2
…
n
1
2
…
m-1
重新編號的話為:
1
2
…
n-m
n-m+1
n-m+2
…
n-1
設f(n,m)為n個人的隊伍,剔除報數人m,最後留下的人的序號;f(n-1,m)為n-1個人的隊伍,剔除報數人m,最後留下的人的序號。則有:
考慮到第1次報數後的序列號n的情況,可得到統一的公式為:
這就是這個問題的一個遞歸公式,實現代碼如下:
#include < iostream >
using namespace std;
int JosephusSol_mathRecursion( int n, int m)
{
if (n == 1 )
return 1 ;
else
return (JosephusSol_mathRecursion(n - 1 ,m) + m - 1 ) % n + 1 ;
}
int main()
{
cout << JosephusSol_mathRecursion( 4 , 3 ) << endl ;
return 0 ;
}
3.兩段長度為1-5000變換的單詞word1,word2,設計一個字母權重分配方案:該方案中不區分大小寫字母;該方案A-Z的字母唯一對應一個1-26的數;該方案滿足word1的字母權重和與word2的字母權重和的差值最大 。
這個問題是實質是比較單詞,剔除相同的部分,看哪個剩余部分多,剩余多的單詞部分再進行一個字母頻率從大到小排列,頻率最高的給最大的權重——26,頻率低一些的依次給剩余的最大權重;剩余的單詞部分再進行一個字母頻率也是從大到小排列,只不過頻率最高的給最小的權重——1,頻率高一些的依次給剩余的最小權重。
至於實現,若是先直接比較單詞,再字母頻率統計,工作量有點大。可以考慮直接用 字母表A-Z為索引,將單詞裝換為字母表A-Z的編碼(更形象點,即將雜亂的單詞變成一個26進制數,當然這樣沒有包含單詞的全部信息——字母在單詞中的排序就不知道,所以可以裝換成26個節點,每個節點還含有一個排序數組,如單詞daddy,相對應的d節點下就含有一個size為3的數組,有sn['d'][3]={0,2,3}。當然本題只需要一個量就是size['d']=3。)
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main()
{
string str1("mother"),str2("father");
// string str1,str2;
// cin >> str1 >> str2;
size_t i = 0 ,j =0;
vector<int> status1(26,0);
vector<int> status2(26,0);
vector<int> diff(26,0);
vector<int> negative(26,0);
vector<int> positive(26,0);
int cntNeg = 0 , cntPos = 0;
for( i = 0; i< str1.size(); i++)
{
char c = str1[i];
if( 'a'<=c && c <= 'z' ){
status1[c -'a' + 0]++;
}
if( 'A'<=str1[i] && str1[i] <= 'Z' ){
status1[c-'A'+ 0]++;
}
}
for( i = 0; i< str2.size(); i++)
{
char c = str2[i];
if( 'a'<=str2[i] && str2[i] <= 'z' ){
status2[c -'a' + 0]++;
}
if( 'A'<=str2[i] && str2[i] <= 'Z' ){
status2[c -'A' + 0]++;
}
}
for( i = 0; i< 26; i++){
diff[i] = status2[i] - status1[i];
if(diff[i]<0)
{
negative[i] = -diff[i];
cntNeg += negative[i];
}
else
{
positive[i] = diff[i];
cntPos += positive[i];
}
}
for( i = 0; i< 26; i++)
cout << ' '<< status1[i] <<' '<< status2[i] <<' '<< diff[i] << endl;
int tmp= 0;
int a[26],b[26];
cout << ' '<< cntNeg <<' '<< cntPos;
for( i = 0 ; i < 26;i++ )
{
a[i] = 26-i;
b[i] = i+1;
}
for( i = 0 ; i < 26;i++ )
for(j = i+1 ;j <26;j++)
{
if( negative[i] < negative[j] ){
tmp = negative[i];
negative[i] = negative[j];
negative[j] = tmp;
}
}
for( i = 0 ; i < 26;i++ )
for(j = i+1 ;j <26;j++)
{
if( positive[i] < positive[j] ){
tmp = positive[i];
positive[i] = positive[j];
positive[j] = tmp;
}
}
int out=0 , large = 0, small =0 ;
for( i = 0 ; i < 26;i++ )
{
if( cntNeg >= cntPos ) {
large += a[i]*negative[i];
small += b[i]*positive[i];
}
else{
large += a[i]*positive[i];
small += b[i]*negative[i];
}
}
out = large - small;
cout << out ;
return 0;
}
2
華為2013年在長沙的一個機試題是判斷潤年。年份要求是四位數。
輸入樣例:
2012
2122
afdsfa
22.33
輸出樣例:
YES
NO
ERROR
我的答案是:
Java代碼
package cn.william;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JTextField;
/**
* 華為2013年機試題:求潤年
* @author william
*
*/
public class Test extends JFrame{
private JLabel lable;
private JTextField field;
public static void main(String[] args){
Test frame = new Test();
frame.init();
}
public void init(){
this.setSize(400, 250);
this.setLayout(null);
lable = new JLabel("請輸入年份:");
field = new JTextField();
lable.setBounds(140, 90, 120, 30);
field.setBounds(140, 120,120, 30);
this.add(field);
this.add(lable);
this.setVisible(true);
field.addActionListener(new ActionListener() {
@Override
public void actionPerformed(ActionEvent e) {
String year = field.getText().toString();
if(year.length() != 4){
System.out.println("ERROR");
return;
}
int y = 0;
try{
y = Integer.parseInt(year);
}catch(Exception ex){
System.out.println("ERROR");
return;
}
check(y);
}
});
}
private void check(int year){
if(year == 0){
System.out.println("ERROR");
return;
}
if(year % 100 == 0){
if(year % 400 == 0){
System.out.println("YES");
}else{
System.out.println("NO");
}
}else{
if(year % 4 == 0){
System.out.println("YES");
}else{
System.out.println("NO");
}
}
}
}
順便復習一下java異常的知識。
異常定義:能讓程序意外中斷運行的指令流。
java異常類的結構如下
Throwable包括了一切的異常。ERROR是JVM的異常,不可以用我們的代碼處理。Exception是我們程序中可能出現的異常,可以處理。
RuntimeException和Exception的關系:
RuntimeException繼承自Exception,RuntimeException和它的子類可以不用try catch進行處理。
Java代碼
ry{
y = Integer.parseInt(year);
}catch(Exception ex){
System.out.println("ERROR");
return;
}
其實這裡 Integer.parseInt(year) 可能會拋出NumberFormatException的,但是eclipse並沒有提示這句代碼需要處理異常,因為NumberFormatException是RuntimeException的子類。
當然因為RuntimeException是Exception的子類,所以,也可以用try catch來處理。
相關閱讀:Hulu 2013北京地區校招筆試題 http://www.linuxidc.com/Linux/2012-12/77130.htm