- 浏览: 913453 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (537)
- Java SE (114)
- Struts (18)
- Hibernate (25)
- Spring (3)
- Page_Tech (41)
- Others (87)
- Database (29)
- Server (24)
- OpenSource_Tools (15)
- IDE_Tool (22)
- Algorithm (28)
- Interview (22)
- Test (28)
- Hardware (1)
- Mainframe (25)
- Web application (4)
- Linux (3)
- PHP (17)
- Android (1)
- Perl (6)
- ubuntu (1)
- Java EE (9)
- Web Analysis (5)
- Node.js (2)
- javascript (2)
最新评论
-
一键注册:
request.getRequestURL()和request.getRequestURI() -
SuperCustomer:
...
SED的暂存空间和模式空间 -
juyo_ch:
讲得挺好理解的,学习了
java 死锁及解决 -
chinaalex:
最后一题答案正确,但是分析有误.按照如下过程,上一行为瓶,下一 ...
zz智力题 -
liaowuxukong:
多谢博主啦,弱弱的了解了一点。
C++/Java 实现多态的方法(C++)
一、给你1副扑克牌,你怎么发牌给4个人?
我:首先扑克牌可以排序,其次,可以每次产生1个随机数,然后把该随机数对应的牌发出去,每次发的牌轮流给第1个人、第2个人。。。 奥,不对,这样可能导致已经发出去的牌再次被发出去! (进入沉思~)
他: Smilence...
我:(随即就给出可行的低效解) 可以这样嘛,首先声明,不考虑效率的前提下,可以这样做:把每张牌维护成一个结点,串联成一个链表。每次还是产生随机数,对当前牌的张数取余得到N,从单链表的头结点开始next指针访问N次,最终指向结点p,把p结点从链表中删除,并将对应的牌发给第(i++)%4+1个人;这样循环下去直到链表为空。
他:你这样做的确是可以实现发牌,可是效率低了点,那还有没有更好的方法呢?
1分钟过去了。。。
他:或许你可以考虑这样的算法,还是每次产生随机数,把对应的牌发出去,然后将此数字标记,以后再随机到这个数字了就不发,继续随机
我:(马上指出)那你发到最后的时候,岂不是一直在那里随机,很少有机会能随机到你想要的剩下的没发出去的那几个数字?
他:那也是的,那你有更好的方法吗?
我:(好好思考一番后) 还可以这样做,把54张扑克牌维护成54个元素的char的数组,然后产生54个随机数,均对4取余,分别存入这个数组的54个单元中,然后遍历这个数组,对应数字为0的牌发给第1个人,对应数字为1的牌发给第2个人。。。 当然了,这样做,可能会有人多拿牌,有人少拿牌,强制从拿牌多的人那里抽取足量的牌。 哎,这样好像不大好办,还要算拿多少牌回来,容我再想想
他:没啊,我觉得这个算法挺好的啊
我:(想了半天,最终也没想出更好的)
他:你这方法还不错的,算法复杂度O(n)
我:那再最终总结下,
数组也不用了,维护一个计数值card_count,初试为1,表示第1张牌;
维护4个计数值count[1]、count[2]、count[3]、count[4],初始均为0,当相应的人被发到牌后就++,用来表示4个人各自当前的牌数;
然后产生一个随机数r%=4,若r为n,则将第count张牌发给第n+1个人,count [n+1]++;
检查count[1]、count[2]、count[3]、count[4],哪个数达到了54/4+1就不再对那个人发牌,然后只产生其余3个人对应的随机数;
继续以上发牌,直到card_count达到54为止;
他:满意地笑了笑
二、对于刚刚发牌的算法中用到的随机算法,你怎么定随机种子?
我:随机种子一般都是采用当前系统时间或者设备编号之类的,采用系统时间是为了种子的随机性,保证伪随机数产生得比较“随机”;用设备号的情况一般是多个设备跑同一个算法,都用到了随机数的时候,比如几台机器组网通信,要做到CSMA,需要随机退避,而因为随机数生成程序的随机是伪随机,如果这几台机器每次都随机到一样的数,那么当发生冲突的时候,他们再随机同样长度的时间来退避,结果还会是冲突,而因为这些机器的编号(比如IP地址)不一样,那么用来作为种子,就会各自采用不同组的伪随机数,就能达到随机退避的效果了!
他:恩,那你说的用系统时间作为种子,是怎么做到的呢?
我:系统调用啊,比如Windows编程,利用提供的
time()之类的API就可以得到当前系统时间了,因为每次运行的时间不同,所以产生的随机数也就比较“随机”了。
他:可以的,不过如果说这个发牌的程序需要运行很多很多次,而因为算法复杂度不高,所以每次都是很快就运行完了,第二次运行的时候,获得的系统时间基本上没变,那是不是每次产生的随机数都比较确定?不够“随机”?该怎么解决?
我:额。。。(好久以后)不清楚啊,既然时间没变的话,那当然没办法了,要不再结合其他可变的参数组合成为种子?
他:(自己都在那里偷笑了)哈哈哈,这还不简单,你每次发牌之间用一个延时函数隔开,保证系统时间有变化不久可以了?
我:- -b
三、给你十亿个数,如何找出其中最小的100个数?
我:(刚听完这个问题,我已经暗暗窃喜了,因为这个问题之前在其他地方已经看到过了) 于是镇定地回答,这个嘛,我知道,用堆排序就能迅速找出!
他:别告诉我堆排序,我要的是过程,整个过程,而不是一句提示。
我:好吧, 用这10亿个数中的前100个数先建立一个堆。(被打断)
他:别告诉我建一个堆,我要你建给我看,你怎么建!
我:。。。(只好拿出草稿纸,画了图比划给他看)建好了堆,而且是(大顶堆还是小顶堆?我思考了一下,马上说)大顶堆!,这样一来,堆顶就是这100个数中最大的那个了,是不是?
他:恩。
我:然后对于剩下的“10亿-100”个数,每个先和堆顶的元素比较大小,比堆顶大的数直接扔掉不要,比堆顶小的数把堆顶替换掉,然后进行一次堆的插入元素的算法,让新的100个数重新成为一个大顶堆,就这么继续下去,直到10亿-100个数都比较完,剩下还在堆里面的100个数就是10亿个数中最小的那100个了!
他:不错,那你觉得你的算法的复杂度咋样?
我:对于求n个数中的前m个最小的数而言,我先建堆,复杂度是O(m),而对于后面的(n-m)个数,最坏情况下每个数都要插入到堆中一次,堆中插入元素的算法时间复杂度最坏情况下是O(logm),所以最后是O(m)+(n-m)*O(logm)=O(m)+O((n-m)logm)=O((n-m)logm+m);
而如果是简单地先对10亿个数排序再取前100个的算法的话,即使用的是快排,那也是O(nlogn);
在n比m大这么多的前提下,显然算法复杂度不是一个数量级的~
四、有个10亿行*100列的二维字符数组,每行可以看成是一个字符串,怎么把这100亿个字符串按字典序排序?
我:&*¥(*palapala...
他:你理解错我的意思了,是这样的:¥……&&*)(
我:奥,这样啊,那可以这样做,因为10亿个字符串,内存肯定不够用,所以需要用到归并排序。
他:什么归并排序?
我:归并排序嘛,就是(*)&%%……
他:恩,然后呢?
我:反正有了归并排序后,只要先把每个分组各自排序,再归并就可以了,所以现在只讨论内存里可以放下的一个分组的排序,因为数量可能还是比较多,所以可以这样做:对于每一个字符串,维护其指针,根据每个字符串的第0列(也就是第一个元素)的大小对其指针进行排序,第0列相同的,就再比较第1列,第1列还是相同的,再比较第2列。。。
他:好吧。
面完了就差不多拿到了口头offer,我的处女面啊,虽然紧张了些,不过表现得还算可以了。
一个月后。。。
终于在一个不经意的时间才意识到了当初被面的各种问题的含义和用处!
首先是发牌问题,因为数据平台部门需要用到HTTP服务器,而这些HTTP服务器能够提供一种类似于反向代理的功能,所谓反向代理,和代理的功能刚相反。代理是将多个的,不同的用户的HTTP请求转交给WEB服务器,然后从WEB服务器端获得应答后,再把应答给用户;而反向代理则是将1个用户的HTTP请求分配给多个WEB服务器中的其中1个,也就是运行在WEB服务器集群前面的那个用于实现负载均衡和HTTP请求分配功能的那个。而这个反向代理的功能,就是类似于“发牌”,只不过它发的牌是用户的HTTP请求罢了!
其次是大数据量的排序、搜索信息等问题,这个是因为数据平台部门每天都要接触海量的数据,需要把大量日志等信息拉到数据仓库Hadoop上进行处理、数据挖掘等,这个数据传输、转存以及挖掘的过程就需要对大数据量运算的了解。
发表评论
-
IGT JAVA Test
2012-06-18 10:18 01. static synchronized vs synch ... -
zz IBM 面试问题
2012-05-30 14:31 9651.JAVA内存回收机制 2.抽象类与接口的区别 3. ... -
面试的准备与发挥
2012-04-26 10:00 870面试是一场智力的较 ... -
栈内存和堆内存
2010-10-21 11:55 790堆:顺序随意栈:先进 ... -
程序员面试题精选(18)-用两个栈实现队列
2010-10-18 22:45 1089题目:某队列的声明如下: C++代码 t ... -
程序员面试题精选(17)-把字符串转换成整数
2010-10-18 22:44 999题目:输入一个表示整 ... -
程序员面试题精选(16)-O(logn)求Fibonacci数列
2010-10-18 22:41 1825题目:定义Fibonacci数列如下: / ... -
程序员面试题精选(15)-含有指针成员的类的拷贝
2010-10-18 22:41 884题目:下面是一个数组类的声明与实现。请分析这个类有什么问题,并 ... -
程序员面试题精选(14)-圆圈中最后剩下的数字
2010-10-18 22:40 1449题目:n个数字(0,1,…,n-1)形成一个圆圈,从数字0开始 ... -
程序员面试题精选(13)-第一个只出现一次的字符
2010-10-18 22:38 906题目:在一个字符串中找到第一个只出现一次的字符。如输入abac ... -
程序员面试题精选(12)-从上往下遍历二元树
2010-10-18 22:37 965题目:输入一颗二元树,从上往下按层打印树的每个结点,同一层中按 ... -
程序员面试题精选(11)-求二元查找树的镜像
2010-10-18 22:36 1340题目:输入一颗二元查 ... -
程序员面试题精选(10)-在排序数组中查找和为给定值的两个数字
2010-10-18 22:33 1029题目:输入一个已经按升序排序过的数组和一个数字,在数组中查找两 ... -
程序员面试题精选(09)-查找链表中倒数第k个结点
2010-10-18 22:32 1144题目:输入一个单向链表,输出该链表中倒数第k个结点。链表的倒数 ... -
程序员面试题精选(08)-求1+2+...+n
2010-10-18 22:31 980题目:求1+2+…+n,要求不能使用乘除法、for、while ... -
程序员面试题精选(07)-翻转句子中单词的顺序
2010-10-18 22:30 1174题目:输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺 ... -
程序员面试题精选(06)-判断整数序列是不是二元查找树的后序遍历结果
2010-10-18 22:27 780题目:输入一个整数数 ... -
程序员面试题精选(05)-查找最小的k个元素
2010-10-18 22:24 1439题目:输入n个整数,输出其中最小的k个。 例如输入1,2,3, ... -
程序员面试题精选(04)-在二元树中找出和为某一值的所有路径
2010-10-18 22:22 850题目:输入一个整数和一棵二元树。从树的根结点开始往下访问一直到 ... -
程序员面试题精选(03)-求子数组的最大和
2010-10-18 22:20 850题目:输入一个整形数组,数组里有正数也有负数。数组中连续的一个 ...
相关推荐
**前端面试题**通常包括以下几个方面: 1. **HTML基础知识**:面试官可能会询问HTML5的新特性,如离线存储、表单控件、音频/视频处理、canvas与svg等。同时,也会考察对语义化标签的理解和使用,如、、、等。 2. *...
本次分享的淘宝面试题目主要面向C/C++工程师,涉及多个技术领域,包括基本的C/C++知识、数据结构与算法、操作系统原理以及软件工程实践等内容。下面将对这些题目进行详细解析。 #### 自我介绍与项目提问 面试官...
为了实现这样的DNS缓存系统,我们需要考虑以下几个关键要素: - **数据结构选择:** 首选的数据结构应当具备高效的插入和查找性能。常用的高效数据结构包括哈希表(HashMap)、跳表(Skip List)等。哈希表因其常数...
通过对提供的部分内容的分析,我们可以提炼出以下几个重要的知识点: 1. 用户获取与运营策略:在经营生鲜品类的淘宝店时,获取第一批用户是至关重要的。这涉及到市场调研、定位、营销策略以及用户关系管理。可能的...
这份笔试题集可能涵盖以下几个方面的知识点: 1. **数据结构与算法**:阿里巴巴重视程序员的基础功底,特别是对数据结构的理解。可能包含数组、链表、栈、队列、树、图等基础数据结构的运用,以及排序、查找、贪心...
PC端和移动端的区别主要可以从以下几个方面来进行详细阐述: 一、界面布局 PC端和移动端的界面布局存在较大差异,这主要是由于屏幕尺寸的不同导致的。PC端的屏幕尺寸较大,通常有更大的空间可以利用,布局也因此...
阿里巴巴的笔试题目通常涵盖以下几个方面: 1. **编程能力**:阿里巴巴作为一家技术驱动的公司,对编程基础有较高的要求。可能会涉及C++、Java、Python等主流编程语言的语法、数据结构(如链表、树、图)、算法...
这个压缩包文件"CodinGame.zip"包含了与该平台相关的几个文档和链接,帮助用户更好地理解和参与CodinGame。 首先,"使用说明.txt"很可能是平台的入门指南,其中可能包含了注册账户、浏览挑战、编写代码以及提交解决...