9月29日百度面试, LBS搜搜部-搜索研发工程师.
当天进行了两轮面试, 第二轮结束后
面试官问: 到现在的公司才待了半年?
答: 目前暂无离职打算, 但是收到百度的面试邀约, 为了不错过机会, 就来试一试
面试官问: 那如果百度有机会考虑不?
答:考虑
面试官: 今天还不错, 如果通过国庆节后应该很快会收到下一步的通知.目前心里很忐忑啊, 不知道会不会有下文, 请各位兄弟姐妹给分析分析.下面分享记得的几个试题吧:
一面:
1. php的gc
回答的关键点:
1) 引用计数维护对象生命周期
2) unset等操作不保证GC运行, GC运行机制未知
3) PHP-5.3之前无法解决循环引用问题, 5.3新引入的GC算法可以解决该问题, 但具体算法实现不清楚
2. 用php实现单链表:
<?php
class Node {
public $data; /* 数据 */
public $next; /* 下一个节点 */
public function __construct($data, $next = NULL) {
$this->data = $data;
$this->next = $next;
}
}class Link {
public $head; public function __construct() {
$this->head = NULL;
} /**
* insert
* 插入节点
* @param mixed $value 要插入的值
*/
public function insert($value) {
$node = new Node($value);
$node->next = $this->head;
$this->head = $node;
} /**
* delete
* 删除节点
* @param mixed $value 要删除的值
*/
public function delete($value) {
$node = $this->head;
$prev = NULL;
while ( $node != NULL) {
if ( $node->data == $value ) {
if ( is_null($prev) )
$this->head = $this->head->next;
else
$prev->next = $node->next;
}
$prev = $node;
$node = $node->next;
}
}
}
二面:
1. php的数组内部实现
回答关键点:
1) HashTable, 具体结构直接说不出来
2) php变量都是struct zval;
3) zval中主要保存变量类型, 变量的引用计数, 变量的值
4) 变量的值是一个union
2. 用php实现字符串反转的函数:<?php
function str_reverse($str) {
return implode('', array_reverse(str_split($str)));
}3. 两个链表, 已知它们有交点, 写算法查找交点:
方案1:<?php
#伪代码
$a = link;
$b = link;
foreach ( $a as $ae ) {
foreach ( $b as $be ) {
if ( $ae === $be ) break 2;
}
}方案2:
1) 遍历链表1, 将每个节点的指针求哈希值, 保存到一个哈希表中
2) 遍历链表2, 对节点的指针求哈希值, 从哈希表中查找
4. 问题3中的两种算法时间复杂度分别是多少:
答: O(N*N), O(N)
我开始理解的N是两个链表的长度和, 经过和面试官交流, 第二种算法复杂度为O(N + M)
5. 大众点评中的商户点评页, 要求每个用户对每个商户只能一次评论, 用户可以在商户页查看评论, 删除评论, 修改评论, 用户也可以在自己的个人主页查看自己作出的评论, 商户页的评论需要按分数/时间排序, 设计数据库表.
答:
主要设计评论表, 表结构如下:
id 类型及长度由业务决定 自增主键
uid 类型及长度由业务决定 与bid联合主键
bid 类型及长度由业务决定
score small int 索引
ctime int 索引
content text
6. 第5题, 假设有上千万条评论信息, 该怎样优化
反问: 商户量多大
结果: 商户大概百万级, 平均每个商户10条评论左右
方案1: 按照bid分表
方案2: 将uid, bid, 评论id之间的关系用nosql管理
当天进行了两轮面试, 第二轮结束后
面试官问: 到现在的公司才待了半年?
答: 目前暂无离职打算, 但是收到百度的面试邀约, 为了不错过机会, 就来试一试
面试官问: 那如果百度有机会考虑不?
答:考虑
面试官: 今天还不错, 如果通过国庆节后应该很快会收到下一步的通知.目前心里很忐忑啊, 不知道会不会有下文, 请各位兄弟姐妹给分析分析.下面分享记得的几个试题吧:
一面:
1. php的gc
回答的关键点:
1) 引用计数维护对象生命周期
2) unset等操作不保证GC运行, GC运行机制未知
3) PHP-5.3之前无法解决循环引用问题, 5.3新引入的GC算法可以解决该问题, 但具体算法实现不清楚
2. 用php实现单链表:
<?php
class Node {
public $data; /* 数据 */
public $next; /* 下一个节点 */
public function __construct($data, $next = NULL) {
$this->data = $data;
$this->next = $next;
}
}class Link {
public $head; public function __construct() {
$this->head = NULL;
} /**
* insert
* 插入节点
* @param mixed $value 要插入的值
*/
public function insert($value) {
$node = new Node($value);
$node->next = $this->head;
$this->head = $node;
} /**
* delete
* 删除节点
* @param mixed $value 要删除的值
*/
public function delete($value) {
$node = $this->head;
$prev = NULL;
while ( $node != NULL) {
if ( $node->data == $value ) {
if ( is_null($prev) )
$this->head = $this->head->next;
else
$prev->next = $node->next;
}
$prev = $node;
$node = $node->next;
}
}
}
二面:
1. php的数组内部实现
回答关键点:
1) HashTable, 具体结构直接说不出来
2) php变量都是struct zval;
3) zval中主要保存变量类型, 变量的引用计数, 变量的值
4) 变量的值是一个union
2. 用php实现字符串反转的函数:<?php
function str_reverse($str) {
return implode('', array_reverse(str_split($str)));
}3. 两个链表, 已知它们有交点, 写算法查找交点:
方案1:<?php
#伪代码
$a = link;
$b = link;
foreach ( $a as $ae ) {
foreach ( $b as $be ) {
if ( $ae === $be ) break 2;
}
}方案2:
1) 遍历链表1, 将每个节点的指针求哈希值, 保存到一个哈希表中
2) 遍历链表2, 对节点的指针求哈希值, 从哈希表中查找
4. 问题3中的两种算法时间复杂度分别是多少:
答: O(N*N), O(N)
我开始理解的N是两个链表的长度和, 经过和面试官交流, 第二种算法复杂度为O(N + M)
5. 大众点评中的商户点评页, 要求每个用户对每个商户只能一次评论, 用户可以在商户页查看评论, 删除评论, 修改评论, 用户也可以在自己的个人主页查看自己作出的评论, 商户页的评论需要按分数/时间排序, 设计数据库表.
答:
主要设计评论表, 表结构如下:
id 类型及长度由业务决定 自增主键
uid 类型及长度由业务决定 与bid联合主键
bid 类型及长度由业务决定
score small int 索引
ctime int 索引
content text
6. 第5题, 假设有上千万条评论信息, 该怎样优化
反问: 商户量多大
结果: 商户大概百万级, 平均每个商户10条评论左右
方案1: 按照bid分表
方案2: 将uid, bid, 评论id之间的关系用nosql管理
解决方案 »
- SQL语句加引号的问题
- 在wap开发中,关于怎样用php得到访问者手机型号?
- 小妹急需解决菜鸟问题:用php把word打印出来的代码
- 报Warning: Invalid argument supplied for foreach() in D:\www\bbs\memcp.php on line 21
- 问几个简单的php疑问
- php与access数据库的联结问题
- php可以读取别个域下的cookie码?
- php建站模型：phpnuke6.5 所有源码公开
- 请问在APACHE里，怎样让PHP文件info.php正常显示出来啊？
- php输出excel乱码
- wamp 中的Apache服务于xampp中的Apache服务问题？
- php获取mysql中文后显示乱码，能帮修改一下吗
你写到
function str_reverse($str) {
return implode('', array_reverse(str_split($str)));
}
似乎不大切题，我以为这样好些
function strreverse($s) {
$len = strlen($s);
$r = '';
while($len--) $r .= $s{$len};
return $r;
}echo strreverse('abcdefg'); //gfedcba
$ary='';
for($i=0,$j=strlen($str);$i<$j;$i++){
$ary=$str[$i].$ary;
}
return $ary;
}
$sres=strrevv('abcdefg');
echo $sres;
方法2用哈希表, 哈希值是有可能碰撞的, 如果最坏情况算出来哈希值都一样.........
嗯, 这个问题就和一般的解决思路一样了, 当时没说...
HashTable + 链表, 先比较哈希, 再比较原始值嘛..
感觉LZ答的还是蛮不错的。相与楼主讨论下几个问题：
1. 关于php数组的内部实现，记得之前看手册是基于Map(有序映射)。
2. 涉及GC的，是否还应该有destruct,unset,session等清理过程？
3.作为单链表的基本操作，isempty(), getListLength()等操作应该加上吧？
4.链表求交点的另一个思路是否可以这样：
遍历连个单链表，将节点依次扔到两个不同栈中，扔完为止，弹出栈顶元素，直到两个栈的栈顶不相等为止，最后弹出的节点就是交点。
5.最后一题，考虑到用户数会动态增加，是否应该按照uid分表而不是按照bid分表欢迎讨论 提出异议。
应该是O(N+M)吧，N M分别为两个链表的长度。
不过一般都说O(N+M)你提到的几个问题完了抽时间细看
2. unset会将变量zval的引用计数减1, 当引用计数为0时, GC运行时释放; destruct应该是在GC运行释放对象内存时运行的方法; session清理应该不涉及在其中
3. 嗯, 当时就加了主要的两个操作, 面试官提到了一个重要接口是迭代接口(提供迭代执行外部行为的接口), isempty(), getListLength()我的想法是加一个长度属性实现
4. 这个问题我直观感觉你这个方案不可行, 因为交点不一定在哪里, 比如第一个链表长10, 第二个链表长20, 交点是第一个链表的首节点和第二个链表的尾节点.
5. 我对数据库其实不在行, 当时考虑是商户本身对数据有一个聚集, 按它分, 现在看你的方案, 其实也是一个道理, uid也是对评论的一个聚集...两者都存在一个问题, 就是以商户聚集时, 取用户评论费劲, 以用户聚集, 取商户评论费劲, 这个面试官也提到了...
所以沾点边就不能算错
关于第四个，如果第一个链表的尾部节点与第二个链表的头结点相交，那么第一个链表的尾部节点的next并不等于NULL。所以是不可能的吧。两个链表相交只能是一字形（不包括你说的那种情况）或者Y字形。
早晨没有理解ohmygirl的意思...
刚细想了下, 是可行的, 简单实现了下:<?php
function get_link_intersect($link1, $link2) {
$stack1 = array();
$stack2 = array();
foreach ( $link1 as $e )
array_push($stack1, $e);
foreach ( $link2 as $e )
array_push($stack2, $e);
for ( $e1 = array_pop($stack1), $e2 = array_pop($stack2), $prev = NULL;
$e1 === $e2;
$prev = $e1, $e1 = array_pop($stack1), $e2 = array_pop($stack2) )
;
return $prev;
}$l1 = array(0, 1, 2, 3, 4, 5, 6, 7);
$l2 = array(9, 8, 4, 5, 6, 7);
var_dump(get_link_intersect($l1, $l2));
三面进行了40分钟左右, 没有谈待遇, 说一周内通知结果, 是不是意味着挂了啊...下面是几个面试题:
1. 如何估算百度地图的日志量
这个开始没有理解面试官意思, 绕了一大圈才让他满意.
首先回答估算pv和单条日志大小...
面试官追问如何估算pv和单条日志大小....
回答根据一段时间的access_log和已有日志估算...
面试官继续引导...让我说下以前做的日志分析怎样估算单条....
才明白过来, 他想听到的是日志字段拆分, 根据每个字段大小进行估算2. 问答型网站, 如何避免广告贴...
经过面试官一路追问, 有以下答案:
1) 敏感词过滤
2) 管理员人工管理
3) 举报机制, 附加奖惩措施
4) 此类用户特征一般为新号, 可根据此特征进行一些限制
5) 开辟广告板块, 另分析了此方法效果不佳.3. 设计模式
答: 设计模式能说上名字的也就工厂, 单例, 策略, 命令, 设计模式对自己更多的是潜移默化的影响...
追问: 工厂用来解决什么问题?
答: 对象创建的封装4. 我自己提到做过一些程序层面上的优化, 就问怎样处理
答: 跟踪代码, 打印日志, 二分法查找问题点...更难找的问题用xhprof这样的工具跟踪查找...
追问: 查找到怎样优化解决
答: 比如某些可以用缓存的地方没有使用, 可以静态化的没有静态化等等..
追问: 用过缓存吗?
答: 是指memcached之类吗? (是) 用过, 缓存方面, 自己些过一个东西, 用来封装缓存操作过程...
追问: memcached的过期怎样实现?
答: 这个忘了, 但当时看过的...补充了一点: memcached使用标记删除, 而不真正清理内存5. 对目前项目组管理架构描述下, 并简述优缺点
答: (简述目前项目组架构), 然后生搬了一个优缺点: 讨论多, 对问题分析细致, 使得解决问题的思路更清晰; 同时由于度有些过, 使得对同事时间有些浪费..末了, 问: 我没有什么问题了, 你还有什么问题吗?
答: 您给我今天的面试打个分把?面试官: 先说优点: 真诚, 踏实, 上进之类...
追问: 那缺点呢?
面试官: 反应有点慢, 前面日志分析的问题之前你都做过类似的项目, 但用了较长时间; 问答社区的问题, 你经常混迹于问答社区, 却要我一路引导之类....面试官: 百度和以前其他公司的氛围会有些不一样, 更加自由,更需要主动承担去做事...
我答: 这一点其实更符合我自身条件, 我正是由于在之前的工作经历中主动工作, 主动学习, 所以才成长相对比别人快些.面试官: 还有其他问题吗?
问: 那我今天的面试能过吗?
面试官: 这个我还需要和前面两面的同事交流一下...over
这些牛人换地方都很勤。。张宴也是跳来跳去的
php实现链表其实不用class实现用数组也可以，只不过要自己做分隔符，空间占用要小一些，但计算复杂度要大一些。不过还是class更像struct。找两个链表交点你的方案2类似kmp算法，n为主串长度，m子串长度。由于主串不回溯。所以复杂度最坏应该为O(n)，也就是比较到主串结尾。反转字符串这题是个公司好像都出。我也用的是最基础的那种方法，也就是学c时用的那个。c里面字符串存储时是字符数组。那么就把数组的首尾两个两个对调就ok了。php里面$str = 'abc';a就是$str[0],b就是$str[1]...做个循环，把$str[2]和$str[0]交换。这是不用任何php内部函数的方法。设计模式那道题。工厂模式主要解决类与类之间耦合度的问题。举个例子，比如zendframework中的db模块。
首先有一个抽象类，它称之为：“适配器”。它就是一个工厂。在子集目录，有mysql、oracle、sqlserver...通过那个适配器工厂就来创建出那些这些不同的类。这些类都是松耦合的，互不干涉。同样，它的cache模块也是这样的。一个适配器下面先分了前端和后端两种cache，然后再具体分为memcache、sqlite、apc、xcache之类。我一直认为面试是非常不公平的，不过也知道除此之外也没有办法在短时间更好的了解一个人。其实这更考验一个人的交流能力而非技术能力。很多面试官自以为是的说着自己的问题，他认为他的表达很清楚，而你就应该很快能理解，事实上有些时候是他问题问的本身就不清楚。很多人面试时表现的并不优秀，但在做起事情时却远远好于面试优秀的人。
你举例的那个我感觉是适配器模式啊(http://baike.baidu.com/view/3371585.htm)
是不是它里面提供了工厂方法, 造成错觉啊?
(我没有看过zendframework哈)
$db = Zend_Db::factory($config['adapter'], $config['params']);//$config['adapter']和$config['params']是连接的db信息。包括什么类型的db，和连接参数之类。这是典型的通过Zend_Db这个工厂类去生产出不同类型的db对象。他下面会有一些什么class Zend_Db_Mysql,Zend_Db_Oracle之类的class。cache那个模块也类似这样。
适配器模式大概是这样：我这个类有个方法只接受两个array作为参数，而调用我这个方法的地方要传两个string参数。那么直接这样调用我的方法在处理参数时就会出错了。这时需要一个参数类型转换的方法在中间处理这个问题，它就是那个适配器。
实际中更多的用法应该是定义一个interface来适配调用方的需求。
问过联系我面试的那个hr了, 她说她只负责通知面试, 后续会有hr和我联系....郁闷中..