- 浏览: 1203430 次
- 性别:
- 来自: 荆州
文章分类
- 全部博客 (396)
- Android 基础 (72)
- Java 基础 (42)
- Android(动画效果) (26)
- Android(自定义组件) (13)
- Android(手机服务) (38)
- Android(网络相关) (27)
- Android(多媒体) (12)
- Android(小技巧) (30)
- Android(用户界面) (39)
- 基础概念 (24)
- Android组件学习 (21)
- Android数据库相关 (11)
- 生活杂谈 (10)
- 调试技巧部分 (8)
- Sql Server相关 (1)
- Android(xml相关) (2)
- Android 开发 (12)
- 韩语学习 (4)
- Mac添加环境变量的三种方法 (1)
- iPhone开发 (1)
- Android Studio (1)
最新评论
-
ppfbsar:
下载网络文件到SD卡上 -
851228082:
好文!彻底理解单类型导入与按需导入的区别了。还有一点可以通过 ...
谈java的导入(import) -
麦田的设计者:
老乡啊
sqlite 数据库保存图片 -
sf_dream:
我要是读写list、map之类的集合呢
ObjectOutputStream和ObjectInputStream类的学习 -
xfyunyun:
博主,请问webview加载html字符串时怎么进行缓存处理呢 ...
WebView使用总结2(加载HTML内容形式的String)
转贴地址:url
[url] http://blog.csdn.net/caowenbin/archive/2011/03/02/6217976.aspx[/url]
无论是技术笔试还是面试,通常会要求写一点代码或详细描述程序思路,很多应试者都认为自己的回答还算过得去,但往往还是没有了下文。究其原因,既有对试题的轻视,也有平时没有养成良好的思维习惯。其实无论试题的难易程度如何,其背后都可以考核出很多知识点来,比如我们来看这样一道简单的笔试题:
写程序,能够计算组合数 。
这道题太简单了,当我们第一次学程序设计语言的时候可能都写过这个程序,我们一起来看一下这道题的思路过程。
首先想到的是写一个求阶乘的函数,然后再另一个函数中对其调用以计算该组合数。这个思路没有问题,但是能写好代码也不是件容易的事,而且我们应该意识到,招聘方的这道简单的问题很显然是需要我们尽量写得完整的,而不是象征性写出思路,因此,必要的健壮性是要体现出来的。很多人的程序如下:
在这段程序中,由于没有任何容错机制,所以肯定是得不到高分的。另外还有个别人在第二个函数中的语句写成了:
return factorial(all)/factorial(select)*factorial(all-select);
这样粗心的错误直接会被判0分,基本上就不会再进入下一轮了。
加入了容错检查的程序如下:
这样这个基本思路的代码就算差不多了,这道题的及格分也就够了。
但是,在众多及格分的成绩中要想获得机会,还是需要再继续改进的。也有的是面试官不断的提出新的需求,比如:如果保持程序中使用int类型不变,那么上述阶乘的计算函数只能算到大约12!,还能进一步提高这个数值吗?或者如果让你提高这段代码的运行效率,你要用什么思路优化?
类似这样问题的提出,就是考验应聘者的时候了,经过分析,优化的空间可以通过原表达式约分实现。在原表达式中,必然有一部分阶乘是重复计算的,而且n!决定了可计算的最大值,如果能把这些重复的计算去掉,把阶乘运算去掉,很显然不仅效率能提高,而且可计算的范围也将变大。
参考程序如下:
如果能第一次就写成这种思路,很显然,我们的机会会更多。
再来接受一下考验,如果面试官要求你再提供思路来优化运行效率,这时我们还要继续思考,比如把已经运算的结果缓冲起来,当再有相同的参数要求运算时直接从缓冲区返回算好的结果,将比重新运算要快。利用该思路,我们改造上边的函数,形成如下代码:
利用一个Map作为缓冲区以保存曾经计算好的结果,典型的空间换时间的思路,但已经能让面试官满意的了。
但是,面试官的问题是会一直延续下去的,他思路的过程也应该是我们写代码思路的过程,因此,新的问题可能是:用HashMap不一定能提高效率,反而会降低效率,能说说是什么原因吗?如果不用HashMap,那用什么容器做缓冲区能更高效?
其实,用HashMap,如果像上文程序那样使用String作为Key,则每次检索时的Hash运算都会耗掉很多时间,自然,如果不采用这种额外的寻址算法,才能达到预期的目的。常用的方式就是采用表格,将算好的结果以某种简单的方式存入到表格中,或者如果运算的数据范围在合适的范围内,也可以预先把表格定好,这样就减少了寻址带来的损失了。为了简单起见,下面的代码使用了数组代替前面的Map。
面试官的问题又来了:还能再优化吗?你可以与面试官讨论更多的细节以决定不同的优化方案,也可以如实告诉面试官你没有想到别的办法。我想,这时面试官期待的已经不是你能给他新的代码了,更多的是在考察你有没有独立解决难题这样代码之外的能力了。
对于前文的代码,最后通过对比发现,使用数组缓存的实现其运行效率最高,然后是改良算法2,接下来是阶乘的实现方案,但比combination2要慢上1-2倍,最后是使用HashMap的实现效率最低。
通过上述解析,可以看到,貌似简单的面试题,其实可以考察到很多内容,所以,求职时要认真准备,认真对待
[url] http://blog.csdn.net/caowenbin/archive/2011/03/02/6217976.aspx[/url]
无论是技术笔试还是面试,通常会要求写一点代码或详细描述程序思路,很多应试者都认为自己的回答还算过得去,但往往还是没有了下文。究其原因,既有对试题的轻视,也有平时没有养成良好的思维习惯。其实无论试题的难易程度如何,其背后都可以考核出很多知识点来,比如我们来看这样一道简单的笔试题:
写程序,能够计算组合数 。
这道题太简单了,当我们第一次学程序设计语言的时候可能都写过这个程序,我们一起来看一下这道题的思路过程。
首先想到的是写一个求阶乘的函数,然后再另一个函数中对其调用以计算该组合数。这个思路没有问题,但是能写好代码也不是件容易的事,而且我们应该意识到,招聘方的这道简单的问题很显然是需要我们尽量写得完整的,而不是象征性写出思路,因此,必要的健壮性是要体现出来的。很多人的程序如下:
private static int factorial(int n){ int ret=1; for(int i=2;i<=n;ret*=i++); return ret; } public static int combination1(int all,int select){ return factorial(all)/factorial(select)/factorial(all-select); }
在这段程序中,由于没有任何容错机制,所以肯定是得不到高分的。另外还有个别人在第二个函数中的语句写成了:
return factorial(all)/factorial(select)*factorial(all-select);
这样粗心的错误直接会被判0分,基本上就不会再进入下一轮了。
加入了容错检查的程序如下:
private static int factorial(int n){ if (n<0) throw new InvalidParameterException(); int ret=1; if (n==0 || n==1) return ret; else for(int i=2;i<=n;ret*=i++); return ret; } public static int combination1(int all,int select){ if (select>all || all<=0 || select<=0) throw new InvalidParameterException(); if (select==all) return 1; return factorial(all)/factorial(select)/factorial(all-select); }
这样这个基本思路的代码就算差不多了,这道题的及格分也就够了。
但是,在众多及格分的成绩中要想获得机会,还是需要再继续改进的。也有的是面试官不断的提出新的需求,比如:如果保持程序中使用int类型不变,那么上述阶乘的计算函数只能算到大约12!,还能进一步提高这个数值吗?或者如果让你提高这段代码的运行效率,你要用什么思路优化?
类似这样问题的提出,就是考验应聘者的时候了,经过分析,优化的空间可以通过原表达式约分实现。在原表达式中,必然有一部分阶乘是重复计算的,而且n!决定了可计算的最大值,如果能把这些重复的计算去掉,把阶乘运算去掉,很显然不仅效率能提高,而且可计算的范围也将变大。
参考程序如下:
public static int combination2(int all,int select){ if (select>all || all<=0 || select<=0) throw new InvalidParameterException(); int ret=1; int begin=0; if (all==select) return ret; //从1-begin之间的数被约分掉以简化计算 if (select<all-select) begin=all-select+1; else begin=select+1; for(int i=begin;i<=all;ret*=i++); //计算分子 for(int i=all-begin+1;i>1;ret/=i--); //被分母除 return ret; }
如果能第一次就写成这种思路,很显然,我们的机会会更多。
再来接受一下考验,如果面试官要求你再提供思路来优化运行效率,这时我们还要继续思考,比如把已经运算的结果缓冲起来,当再有相同的参数要求运算时直接从缓冲区返回算好的结果,将比重新运算要快。利用该思路,我们改造上边的函数,形成如下代码:
private static Map<String,Integer> mapTable=new HashMap<String,Integer>(); …… public static int combination3(int all,int select){ if (select>all || all<=0 || select<=0) throw new InvalidParameterException(); int ret=1; int begin=0; if (all==select){ return ret; } String tableKey=new String(all+","+select); Integer tableValue=mapTable.get(tableKey); if (tableValue!=null) return tableValue.intValue(); if (select<all-select){ begin=all-select+1; } else{ begin=select+1; } for(int i=begin;i<=all;ret*=i++); for(int i=all-begin+1;i>1;ret/=i--); mapTable.put(tableKey, Integer.valueOf(ret)); return ret; }
利用一个Map作为缓冲区以保存曾经计算好的结果,典型的空间换时间的思路,但已经能让面试官满意的了。
但是,面试官的问题是会一直延续下去的,他思路的过程也应该是我们写代码思路的过程,因此,新的问题可能是:用HashMap不一定能提高效率,反而会降低效率,能说说是什么原因吗?如果不用HashMap,那用什么容器做缓冲区能更高效?
其实,用HashMap,如果像上文程序那样使用String作为Key,则每次检索时的Hash运算都会耗掉很多时间,自然,如果不采用这种额外的寻址算法,才能达到预期的目的。常用的方式就是采用表格,将算好的结果以某种简单的方式存入到表格中,或者如果运算的数据范围在合适的范围内,也可以预先把表格定好,这样就减少了寻址带来的损失了。为了简单起见,下面的代码使用了数组代替前面的Map。
private static int[] intTable; …… public static int combination4(int all,int select){ if (select>all || all<=0 || select<=0) throw new InvalidParameterException(); int ret=1; int begin=0; if (all==select){ return ret; } if (intTable!=null && intTable[select]!=-1) return intTable[select]; if (select<all-select){ begin=all-select+1; } else{ begin=select+1; } for(int i=begin;i<=all;ret*=i++); for(int i=all-begin+1;i>1;ret/=i--); if (intTable==null){ intTable=new int[all+1]; for(int i=0;i<all+1;intTable[i++]=-1); } intTable[select]=ret; return ret; }
面试官的问题又来了:还能再优化吗?你可以与面试官讨论更多的细节以决定不同的优化方案,也可以如实告诉面试官你没有想到别的办法。我想,这时面试官期待的已经不是你能给他新的代码了,更多的是在考察你有没有独立解决难题这样代码之外的能力了。
对于前文的代码,最后通过对比发现,使用数组缓存的实现其运行效率最高,然后是改良算法2,接下来是阶乘的实现方案,但比combination2要慢上1-2倍,最后是使用HashMap的实现效率最低。
通过上述解析,可以看到,貌似简单的面试题,其实可以考察到很多内容,所以,求职时要认真准备,认真对待
发表评论
-
ArrayList添加add方法效率
2013-05-09 19:24 1527public static void main(Strin ... -
Java设计模式之组合模式(Composite)
2012-11-16 11:08 13802Composite模式定义: 将对象以树形结构 ... -
HashMap用法熟悉
2012-11-11 23:43 1363HashMap排列没有按一定规则示例代码: public ... -
谈java的导入(import)
2012-06-10 16:53 1665单类型导入(single-type-import),例如imp ... -
TCP和UDP协议理解
2011-12-04 21:32 1405我们学习过什么是 ... -
华为的一道面试题
2011-11-01 10:26 1593代码如下: package com.ex; publ ... -
Java中静态变量的初始化问题
2011-10-24 11:04 10734/** * java中的内存有一块地址叫"静态代 ... -
Java引用了解
2011-10-16 16:29 1147正常来说,传统的JAVA引用,如 public ... -
Java中的抽象类和接口的区别
2011-08-21 08:47 1119Java语言中, abstract class 和in ... -
谈谈final, finally, finalize的区别
2011-08-20 10:37 1221final—修饰符(关键字)如果一个类被声明为fi ... -
Java中重载和重写的区别
2011-08-20 10:17 1083这个问题已经研究了好多遍了,总是忘记,就整理下来加深印象: ... -
Hashtable和HashMap
2011-08-20 09:55 10792者概念: Hashtable继承自Dictionary类 ... -
Java中HashCode()理解
2011-08-20 09:42 1074先从一个java基础面试的问题开始引入吧: 问题: 两个对象值 ... -
java继承复习
2011-07-24 14:30 834package com.edison; public ... -
Java多态机制中的绑定规则
2011-07-23 10:25 1495package com.example; publi ... -
java接口进一步理解(二)
2011-07-23 09:54 1058抽象类与接口比较: 1.抽象类与接口都位于继承树的上层 相 ... -
java接口进一步理解(一)
2011-07-23 09:47 1258今天来整理篇关于java接口知识的文章: 首先我们知道 ... -
SimpleDateFormat的常用方法
2011-07-22 10:17 1082/** parse()可以 把String型的字符串转换成 ... -
内部类使用总结(参考白度文献上的文章)
2011-07-21 22:00 1098我是一个java基础不太好 ... -
线程和Runnable接口的理解
2011-06-21 11:59 1162通过卖票来进行解释: 1.ThreadTicket.java: ...
相关推荐
一道题目的算法优化过程 作者很详细的分析了算法的优化过程。
名企算法笔试题目
12-02-28网易笔试一道算法题,附件代码是我自己的解题
不骗人,整理的一套试卷的全部题目~2017年哒
华为OD、大厂笔试算法题; 一共87题,每一题附答案(java语言),笔试时频繁出现的原题,想进大厂的小伙伴,欢迎下载; eg: 1、5键键盘的输出 有一个特殊的5键键盘,上面有a,ctrl-c,ctrl-x,ctrl-v,ctrl-a五个键...
多种笔试面试的算法设计题,和经典笔试题目。
单链表是数据结构中最简单的一种数据结构,虽然在结构上最简单,但是使用好也是比较困难的,而在各大公司的面试中也是有单链表的各种算法的变种。下面我就列举出几种经常出现的几种题目,并通过简单分析,使用java...
20150402 阿里巴巴 算法工程师 笔试题目
算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题
常见C++笔试题目整理(含答案).docx
从米哈游的简介开始,逐步介绍了笔试题目的类型,包括编程题和数据结构与算法题。博客还提供了准备建议,如学习编程语言、掌握数据结构和算法、练习编程题和参加模拟笔试。此外,博客还涵盖了面试流程和注意事项,...
微创笔试题目(微创,微软在中国的合资公司) Intel笔试面试题目 IBM 社会招聘笔试题 宝洁公司(P&G)面试题目 飞利浦笔试试题 阿尔卡特(中国)的面试题目 Google 戴尔 意法半导体软件试题 Sony笔试题 华为笔试题 ...
各公司算法题目 各公司算法题目 各公司算法题目 各公司算法题目
邹博BAT笔试面试算法班PPT讲义(完整版)
秋招过程中遇到的笔试算法题 包括题目、答案和详细解题思路~
华为的两道算法笔试题及答案,自己已经用C语言调试通过
中兴最新笔试题目,最近几年刚考的。2015、2014、2013
C语言终极笔试 贪心算法解题
大疆求职算法笔试题 大疆求职算法笔试题大疆求职算法笔试题大疆求职算法笔试题大疆求职算法笔试题大疆求职算法笔试题大疆求职算法笔试题
C++面试题笔试题C++ 数据结构算法笔试题资料合集: 50个C、C++面试题.pdf C++ 数据结构、算法笔试题.docx C++基础面试题.docx C++开发工程师面试题库.docx C++技能测试试卷一及答案.docx C++技能测试试卷二及答案....