查看文章 |
创建时间 2007年4月20日 创建人 caoz 转载请携带以上标记，谢谢 题目1 现在有两个日志文件，格式为 211.137.1.1 125.65.2.3 202.36.71.33 .... 每条一个ip地址。每个日志文件各有100万左右条。文件中可能少部分ip是重复。 现在想知道文件1与文件2中，相同的ip有多少，请编写脚本实现。 小提示：第一，不要吧这个问题复杂化，这是这里最简单的问题。第二，注意程序效率。 答案，此题其实相当简单 将第一个文件遍历读取，存入数组，无须排序，存入即可。 $arr[$ip]=1; 然后遍历第二个文件，针对第二个文件中的每一个ip 查一下是否存在该数组下标 if (isset($arr[$nip])) $sum++; 然后输出$sum即可 其中无任何地方需要排序处理。
题目2 还是刚才那个日志文件，只有一个，100万条ip记录，少部分有重复 现在有一个ip地址库 格式为 ip地址1 - ip地址2 - 地区 这个库有15万条记录 现在请编写脚本，将这100万条记录的地区分布列出来。 小提示，这个题目的关键词是，效率。100万×15万，如果不用点窍门，是不可承受的系统开销，那么很多人都知道索引是提高效率的重要手段，但是基于区间的查询，是不能直接使用索引的，但是，想一下索引的实现原理和效率提升的原理，这个问题就会迎刃而解。很多时候，我们不仅仅要善于利用一些有效的工具，更要明白，这些工具背后的逻辑。 答案， 实际上是要点只有一条，将15万条地区库建立为有序的数组并格式化保存，这个数组会非常有用，做一次排序保存即可，在n多涉及地区查询的实际应用中都可以统一调用，无须每次重新排序。 之后就是最典型的二分查找法了，关键是编写一个二分查找的函数，可以通过不断的二分处理在15万条记录中快速找到该ip所对应的区间，理论每个ip的查找次数是log2(150000), 遍历100万条记录（这100万条记录无须做任何排序），对每个ip判断是否已进行过地区识别，如果没有，则调用二分查找，返回所属地区属性，然后 $sumarea[$return]++; 最后把sumarea排一下序输出即可。 这里唯一的排序是对15万条地区ip区段信息排序，而且只需要进行一次长期保存即可。考核的关键不是排序，而是二分查找，二分查找是最简单的快速索引算法，网上大量资料可查阅。
题目3 现在有2亿web服务的日志，假设就是apache日志或类似格式的日志，没说错，2亿条，格式大体为如下 ip地址,访问url,来路url,当前时间 假设就这些吧,这里可能涉及的是2万个不同的站点。 现在要求，做出每个站点的流量统计，包括这个站点的独立ip数，pv数，时间段分布，地区分布，来路分布，受访分布，Top进入url。 现在给你的电脑是一台双CPU，2G内存的服务器，请考虑实现方式。 小提示，这里的关键词除了效率，还有资源开销，如果我们不考虑数字，只考虑应用，这个题目并不复杂，只是罗嗦，但是当你考虑到要分析2亿个日志，而且对2万个站点每个站点都要做出统计，那么你程序时就可能会遇到一个天大的问题，按照一般的方式处理，内存肯定远远不够用。但是如果大量使用硬盘空间来替代内存，又存在巨大的i/o开销，如何寻找均衡的方式，这里考查的不是脚本编写，而是系统设计。 答案 这道题看上去很唬人，但是实际上只是一个日志切分的问题，不要把系统考虑太复杂 实际上组建一个二步处理的过程，第一步是遍历2亿的日志，然后将每条日志的站点主域取出来，作为文件名，处理到一定数量时批量储存为独立文件。 过程示例如下,处理函数略 $seed=0; while ($str=fgets($fd)) { $seed++; $arr=checklog($str); //将日志切分,将日志中的各个字段切分 $site=$arr["site"]; $vstr["$site"]=$vstr["$site"].$str; if ($seed>1000000) //假设以100万条日志为内存处理容量 { foreach($vstr as $key=>$value) { $fd=fopen("$path/$key","a"); fwrite($fd,$value); fclose($fd); } unset($vstr); $seed=0;
} } 这个程序执行后，2亿条日志就被分割为2万个文件，每个文件对应一个站点 然后再做一次针对站点的遍历，每个站点分析日志，就属于纯粹的罗嗦体力活了，过程略 该题目中不涉及任何排序操作及算法。这个模式只需要遍历日志两次，此外需要日至容量一倍的写操作，这些代价并不是不能承受的，至少系统设计上很简单。 题目4 小张是某大学的体育部主任助理，为了方便安排体育课程，他做了一个调查，发了1000份问卷，让所有人填写自己所期望的体育课程，这份调查是允许多选。 基本结果为，足球 500份，篮球350份，乒乓球200份，羽毛球200份，网球120份，棒球50份，.... 然后小张做了另一个统计，针对每个项目，查看与它共同选择最多的项目，看看冷门项目中，有没有多个项目合并的可能，结果发现，所有选择冷门项目的人，最多的共同选择项几乎都是足球和篮球。那么，是不是说所有项目都与足球，篮球高度相关呢？是不是所有冷门项目都可以并入足球篮球呢？这里的问题在哪里？ 如果你是小张，你是否能有更好的处理方法，如有可能，代码实现。 小提示，这是一个基本的关联模型和聚类模型的应用，关联模型中，考虑关联性的因素都包括哪些，共同选择的数字并非唯一的标尺。 答案： 关联模型中，我们不仅需要考虑支持度（共同推举数），也需要考虑置信度（相对比例），这里其实就是一种思维模式的考量，很多时候，我们设计关联模型时，针对不同应用，需要有不同的考量及评估模式，实际应用会比这个题目复杂。
总结 以上都是工作中遇到的实际问题，并非算法考试，和百度程序之星，google程序大赛的模式是不同的，这次招聘面向的目标是非技术部门的数据分析工作，因此并不十分特别强调高效算法，但是强调有解决实际问题的能力，所谓解决实际问题，核心的要求就是简洁高效，从收获的一些答案看，大部分应届生喜欢把问题复杂化，也许是题目描述的问题，不过希望年轻朋友们一定要记住，工作和做学术答辩不一样，一般学生做毕业论文的时候，喜欢化简为繁，简单的问题复杂化，显示卓越的学识和技能，但是工作要求的是化繁为简，用最短时间解决最多的问题，最短的时间不仅仅是程序执行的时间，也包括设计和编码的时间。 |
