Home > 算法研究 > 常见的软件公司变态的面试编程题目的解决办法

常见的软件公司变态的面试编程题目的解决办法

今天上博客园转转,看到一篇介绍常见的软件公司变态的面试编程题目的日志遂决定提前解决调,早有准备,要是诸位网友曾经经历这些问题的话,欢迎留言感激!

1.任意给定一个整数n,请写出一个算法计算 1-2+3-4+5-6+7……n的结果

错答:这么答的话,多一个FOR循环,效率可是极低的,O(n),软件公司肯定不要你了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int n = this.TextBox1.Text.ToString();
//原文错误,C#语言,改为int n=Int.Prase(this.TextBox1.Text.ToString());
 int Sum = 0 ;
 for (int i = 0 ; i < n + 1 ; i++)
 {
  if((i%2) == 1)
  {
   Sum += i;
  }
  else
  {
   Sum = Sum - i;
  }
 }

正解:分析下算式的结构 可知道(1-2)=(3-4)=……=(2n-1)-(2n)= -1
那么用回溯法就可以推导 结果是 n/2 个-1 加上个 n 咯,再判断N的符号就可以
知道结果了本算法开销只有 O(1)

1
2
3
int n = input();
int result=(-1) * (n/2) + (n)*(n%2 ? -1:1);
printf("%d",result);

2.任意给定一个整数n,显示n的2008次方的末四位。

错答:一个数的2008方结果不溢出才怪,软件公司肯定要考虑是否要你了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void main()
{
 int Y,P;
 Y=n^2008;
 cout<<"n的2008次方是:"<
 
正解:总结分析分析一般1~52008次方结果一样的,5^2008一般不会
溢出吧,要是再精简,可以换成n^1004*n^1004,或者502*502*
502*502的形式,结果是一样的
<pre lang="CPP">long n=input();
long result=((n%6)^2008)%1000;//可以换1004*1004
cout&lt;
 
<strong>3.A、B两个整数,请写出一个算法不借助其他变量将两个数值对换。</strong>
 
正解:两个数交换比借用第三变量,单片开发中肯定会用到的,时间换空间
华为考过N次
<pre lang="CPP">void main()
{
cout&lt;&lt;"转换前A="&lt;
Categories: 算法研究 Tags:
  1. December 14th, 2008 at 09:31 | #1

    其实蛮简单的,仔细点,只要找到规律就行了

  2. December 14th, 2008 at 10:38 | #2

    感谢感谢~~
    我这就去链你。。。。
    http://wordpress.org.cn/thread-26189-1-1.html

  3. December 16th, 2008 at 17:58 | #3

    第一题最变态,一看就用for,我还用个flag记录符号,flag=!flag 。。。
    第三题受用了。。

  1. No trackbacks yet.