一道淘汰85%面试者的百度开发者面试题

首先对于标题我是根据题目原出处http://student.csdn.net/mcd/topic/235300/753730写的，所以如果大家觉得逼格有点高的话，请无视标题。

下面上题目：

大河轻松度，阴沟易翻船。无风无浪的地方，按理说是绝对不该翻船的。可是，就是在大家看似无比简单的问题上，栽倒无数人。

---

题目描述：

依序遍历0到100闭区间内所有的正整数，如果该数字能被3整除，则输出该数字及‘*’标记；如果该数字能被5整除，则输出该数字及‘#’标记；如果该数字既能被3整除又能被5整除，则输出该数字及‘*#’标记。

---

提示：

这道看似非常简单的题目，却潜藏着几个玄机。面试官通过这道题，考察学生在语法、语义、语用以及算法优化方面的能力。现实告诉我们，通过这一道题目，就可以淘汰85%的面试者。看似残酷的考察方式，却也体现出学生在基础知识、动手能力到思维能力上的差距。

需要注意的考察点：

- 语法：语法的正确书写，包括格式
- 语义：对循环、分支等语义的理解与掌握
- 语用：对变量命名、表达式及语句的组合使用
- 算法优化：如果要提高运行效率，可以在算法上寻找突破口，也可以采用空间换时间的通用原则。

对于这种问题，如果不是面试题的话，我想大家一般不会多想，大部分的思路就是一个循环加三个判断，打完收工。其实如果是0—100的话，确实也不需要过多考虑性能优化问题，因为对于今天的硬件来说这都不是事啊，下面上一般的常规写法：

for(int i=1;i<=100;i++){
			if(i%15 == 0){
				System.out.println(i+"*");
				System.out.println(i+"#");
				System.out.println(i+"*#");
			}else{
				if(i%3 == 0)
					System.out.println(i+"*");
				if(i%5 == 0)
					System.out.println(i+"#");
			}
		}

这种常规的写法，时间复杂度O(n)并没有得到优化，可以感觉到是一种不好的算法，通过分析可以看出，它的循环次数较多，因此可以通过减少循环次数来获得优化，下面就是我优化过的算法。

因为先前没注意看清题目输出要求，因此做了些小修改，多谢MarkSaas的提醒。

上代码：

		//商向下取整
		int threeIndex = (int) Math.floor(100/3);	
		int fiveIndex = (int) Math.floor(100/5);
		int bothIndex = (int) Math.floor(100/15);
		for(int i=1;i<=threeIndex;i++){
			if(i%5 != 0)
				System.out.println(3*i+"*");
			if(i<=fiveIndex && i%3 != 0)
				System.out.println(5*i+"#");
			if(i<=bothIndex)
				System.out.println(15*i+"*#");
		}

可以看出优化过的算法的时间复杂度为O(n/3)，通过计算它们的耗时，我用5000做了测试，发现后者优化过的算法耗时可以减少50%（此结果是我的计算机运行的结果，不同的计算机会有些许差异。）。我把这个结果已经回复到那个帖子里面去了，如果大家还有什么好的优化方案，可以留言交流讨论。
-----------转载请注明出处：http://blog.csdn.net/justmeing/article/details/24386071-------------