某公司笔试题目解答
一个偶然的机会，拿到了这份某互联网公司的笔试题目，抱着闲着也是闲着的态度做了一下答卷，发出来以供各位参考。
软件工程师笔试题目
1. XX网每个信息页面下方都有一个信息被浏览次数统计的计数器，如果让你用你熟悉的代码写一个这样一个支持8位ID统计的计数器，你的思路是怎样的？会怎样写？需要用code实现。
当帖子的并发量很高时,如果用传统的count或read会对数据库造成很大的读io,而在新用户浏览过该帖子后update阅读数量时则会产生大量的write lock,所以对于这个问题我使用memcache+php的解决方案.
count.php中已经回答了问题一.作为该问题的衍生,我设想了几个可能发生的问题并且给与大概的解决方案
1.如果网站访问量成倍增长,则memcache中的数据迟早会超出内存限制,此时该如何处理?
此时有三种解决方案,前两种不需要增加服务器,第三种是从硬件角度解决问题,需要增加服务器
第一种是增加内存,扩大memcache的允许运行空间,memcache在64bit系统下最大可以使用1t的内存空间.
第二种是开启memcahce的内容压缩功能,当该功能被开启后,cpu的负荷会略微上升,而内存占用由于压缩的关系则会降低,从而起到增加系统可用空间的目的.
第三种是对数据进行分片,分片方法可以使用余数法或者hash法,最简单的例子如下:
有三台服务器,分别位A,B,C,则id为1的数据的进A,2进B,3进C,4进A,如此循环.
2.如果memcache服务器产生运行异常,memcache中的统计数据该如何保存?
有两种办法,第一种实现起来较为简单,但是有可能损失一小部分数据,第二种不会损失数据,但是会增加硬件投入.
第一种,使用crontab每隔一段时间对数据做dump,将所有数据依次存入数据库中,待问题发生时,只要将数据从数据库导入memcache数据库即可.
第二种则是使用memcache的addserver方法,将同一键值存放在多个实例中,根据服务器是否正常运行来动态的选择从哪台服务器取得数据.
3.当memcache集群的服务器数量增多时,该如何对数据进行平均分片以保证每台服务器的负载都处在平均水平?
可以采用数据分片或者hash的方法,或者使用memcache代理软件:magent
2. XX网不允许一个人在一天之内发布过于重复或者接近重复信息，如果让你实现一个重复度检测算法判断，你的思路是怎样的？code上怎么写？需要用code实现。
我对于这个问题有几个不同的解决思路:
1.关键信息重复程度检测
对于不同的信息,它们最终地目是让浏览者产生兴趣并且联系发贴人,而在这个逻辑中,有几类信息是必不可少的,比如联系信息,包括联系人的电话(这是最重要的),email,qq号码,msn等联系方式,不管信息的结构如何变化,这个最重要的信息是不可能产生变化的,即使有变化也只是一些简单的替换,制造杂音等等,例如将手机号码加空格,换行,用中文代替阿拉伯数字等等.
而对于关键信息的提取这一问题,可能需要一个数据库来储存大量的产品基本信息,比如对于笔记本电脑分类,这个数据库可能牵涉的数据有:品牌,型号,制造年份,保修年数等等.将关键数据提取出来与现有数据做匹配,则可以判断该信息是否是重复信息.
具体代码见duplicateCheck.php内的checkDuplicateByKeyword方法.
所以判断关键信息是否重复可以用来作为判断此信息是否重复的解决方案之一.而由于单纯判断信息重复程度会带来一些问题,比如应该避免不同用户发送相同信息而被误判为重复信息的情况.所以需要第二个解决方案:判断用户是否重复.
2.信息发布来源重复程度检测
对于普通用户来说,可以通过判断IP,判断浏览器,植入cookie等方法判断这个用户在24小时内是否在网站上发送过信息.
3.信息正文重复程度检测
最后一个方法则是判断一段文字和一段文字的相似程度,相似程度是一个浮点数,从0到100,如果两端文字的相似程度达到了一个阀值(这个阀值可以通过大量的测试数据来得出,对于不同长度的文本可以采用不同的阀值,因为文字的长度越短,变动过的文字占全部文本的比例就越低),则可以判断为重复信息.
详见duplicateCheck.php内的checkDuplicateRateBySimilarText方法
附：源代码：
count.php
<?php
//define key
define("POST_ID", 12345);
define("KEY",'post_counter_'.POST_ID);
//create connection to memcache server
$memcache = new Memcache;
$memcache->pconnect('localhost', 11211) or die ("Could not connect");
/* ** IMPORTANT **
* If we create the key when user writes a new post,then we don't need check the key is exist or not,it will save time.
* ** IMPORTANT **/
$var = $memcache->get(KEY);
//If key is not exist,then create it.
if($var==false){
$memcache->set(KEY,1,false,88888);
$result=1;
//If key is exist,then increment it.
}else{
$result = $memcache->increment(KEY, 1);
}
//print result
echo 'counter of this post:'.$result;
duplicateCheck.php
<?php
//test data1
$text_1_1 = array(
'id'=>1,
'title' => '',
'category' => '',
'location' => '',
'price' => '',
'description' => "移动包月卡，每月3G流量7月启用卡剩余8个月即800元可10086查询\n
中兴网卡信号好速度快，因住地已装网线留着无用转给需要的人，价可小议\n
联系方式159 00491388 （直接联系拒绝短信）"
);
//test data 2
$text_1_2 = array(
'id'=>2,
'title' => '',
'category' => '',
'location' => '',
'price' => '',
'description' => "移动包年卡，每月3G流量7月启用卡剩余8个月即800元可10086查询\n
中兴网卡信号好速度快，因住地已装网线留着无用转给需要的人，价可小议\n
联系方式15900491388 （直接联系拒绝短信）"
);
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
function checkDuplicateByKeyword($text){
$database=array(
array(
'category'=>'移动',
'keywords'=>array(
'充值卡',
'包年卡'
)
)
);
//check category
foreach($database as $key => $value){
if(__IsKeywordExist($value['category'],$text['description'])){
echo "ID:".$text['id'].'的帖子 属于{'.$value['category'].'}分类'."\r\n";
foreach($value['keywords'] as $k2 => $v2){
//echo $v2;
if( __IsKeywordExist($v2,$text['description']) ){
echo "ID:".$text['id'].'的帖子 发现重复关键信息';
}
}
}else{
}
}
}
function __IsKeywordExist($keyword,$text){
if(strpos($text,$keyword)===false){
return false;
}else{
return true;
}
}
/*
* return:
*
* [scourgen@SMBP:~/BaiXing]$ php duplicateCheck.php
ID:1的帖子 属于{移动}分类
ID:2的帖子 属于{移动}分类
ID:2的帖子 发现重复关键信息
*/
checkDuplicateByKeyword($text_1_1);
checkDuplicateByKeyword($text_1_2);
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
function checkDuplicateByUser($text_1){
}
function checkDuplicateRateBySimilarText($text_1,$text_2){
similar_text($text_1, $text_2,$p);
return $p;
}
//return 98.5324947589
echo checkDuplicateRateBySimilarText($text_1_1['description'], $text_1_2['description']);