- 浏览: 897070 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (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 9361.JAVA内存回收机制 2.抽象类与接口的区别 3. ... -
面试的准备与发挥
2012-04-26 10:00 846面试是一场智力的较 ... -
栈内存和堆内存
2010-10-21 11:55 753堆:顺序随意栈:先进 ... -
程序员面试题精选(18)-用两个栈实现队列
2010-10-18 22:45 1052题目:某队列的声明如下: C++代码 t ... -
程序员面试题精选(17)-把字符串转换成整数
2010-10-18 22:44 977题目:输入一个表示整 ... -
程序员面试题精选(16)-O(logn)求Fibonacci数列
2010-10-18 22:41 1789题目:定义Fibonacci数列如下: / ... -
程序员面试题精选(15)-含有指针成员的类的拷贝
2010-10-18 22:41 861题目:下面是一个数组类的声明与实现。请分析这个类有什么问题,并 ... -
程序员面试题精选(14)-圆圈中最后剩下的数字
2010-10-18 22:40 1425题目:n个数字(0,1,…,n-1)形成一个圆圈,从数字0开始 ... -
程序员面试题精选(13)-第一个只出现一次的字符
2010-10-18 22:38 869题目:在一个字符串中找到第一个只出现一次的字符。如输入abac ... -
程序员面试题精选(12)-从上往下遍历二元树
2010-10-18 22:37 949题目:输入一颗二元树,从上往下按层打印树的每个结点,同一层中按 ... -
程序员面试题精选(11)-求二元查找树的镜像
2010-10-18 22:36 1315题目:输入一颗二元查 ... -
程序员面试题精选(10)-在排序数组中查找和为给定值的两个数字
2010-10-18 22:33 1010题目:输入一个已经按升序排序过的数组和一个数字,在数组中查找两 ... -
程序员面试题精选(09)-查找链表中倒数第k个结点
2010-10-18 22:32 1123题目:输入一个单向链表,输出该链表中倒数第k个结点。链表的倒数 ... -
程序员面试题精选(08)-求1+2+...+n
2010-10-18 22:31 951题目:求1+2+…+n,要求不能使用乘除法、for、while ... -
程序员面试题精选(07)-翻转句子中单词的顺序
2010-10-18 22:30 1150题目:输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺 ... -
程序员面试题精选(06)-判断整数序列是不是二元查找树的后序遍历结果
2010-10-18 22:27 759题目:输入一个整数数 ... -
程序员面试题精选(05)-查找最小的k个元素
2010-10-18 22:24 1414题目:输入n个整数,输出其中最小的k个。 例如输入1,2,3, ... -
程序员面试题精选(04)-在二元树中找出和为某一值的所有路径
2010-10-18 22:22 823题目:输入一个整数和一棵二元树。从树的根结点开始往下访问一直到 ... -
程序员面试题精选(03)-求子数组的最大和
2010-10-18 22:20 830题目:输入一个整形数组,数组里有正数也有负数。数组中连续的一个 ...
相关推荐
面试算法题总结
面试经常遇到的,编程算法题。里面包括的都是面试官经常考你的算法设计问题,
经典面试算法题N道,经典面试算法题N道,经典面试算法题N道,经典面试算法题N道
JAVA经典算法面试39题及答案,算法是不得不看的
这是在面试中遇到的一些常见算法题,笔试面试经常遇到,所以总结了一下,方面以后查看,分享给大家。
最全的Java面试题整理,含算法题 从大学到现在,参加过很多面试,经常会被问到一些基本的算法题,而大部分算法的理论及思想,我们曾经都能倒背如流,并且也用语言实现过,可由于在项目开发中应用的比较少,久而久之...
程序员面试经典算法题.通过对经典的有一定难度的算法类题目的分析,培养程序员算法思维.
该资源为Android开发工程师面试算法题,为基础知识具备比较好的人提供。
招聘时常见的面试、笔试的算法数据结构、智力型问题。。。。。
求第30位数是多少, 用递归算法实现。 2 有一个3*4矩阵,输出最大元素的值,及其所在的行号和列号, int a[3][4]={{1,2,3,4},{9,8,7,6}, {-10,10,-5,2}}。 3 实现二分法查找,int a[8] = {3,12,24,36,55,68,75,...
java算法与编程面试题java算法与编程面试题java算法与编程面试题java算法与编程面试题java算法与编程面试题
用来记录我们刷LeetCode题目时候的心酸...编程语言使用Golang,代码风格上面并没有强制的采用什么编码规范,毕竟是算法解题,只需要代码清晰易懂就可以了。 鉴于个人精力时间有限,可能并不会完全最优解,请多多见谅。
50个C、C++面试题.pdf C++ 数据结构、算法笔试题.docx C++基础面试题.docx C++开发工程师面试题库.docx C++技能测试试卷一及答案.docx C++技能测试试卷二及答案.docx c++笔试面试宝典.docx C++笔试面试题带答案.docx...
微软等大公司算法面试题,程序员面试必备,算法一百题
Vue面试题,React面试题,JS面试题,HTTP面试题,工程化面试题,CSS面试题,算法面试题,大厂面试题,高频面试题
面试算法必刷题
面试高频算法习题精讲.rar
企业面试题 - 算法与编程 此文档包含了算法和算法详解
java的面试题和算法、以及算法的源码。
算法,数据结构,面试题,很经典的图