数据结构php面试题 高级php面试题及部分答案

数据结构与算法处理面试题

1、时针走一圈，时针分针重合几次

我们注重客户提出的每个要求，我们充分考虑每一个细节，我们积极的做好网站建设、成都网站设计服务，我们努力开拓更好的视野，通过不懈的努力，创新互联公司赢得了业内的良好声誉，这一切，也不断的激励着我们更好的服务客户。 主要业务：网站建设,网站制作,网站设计,小程序开发,网站开发,技术开发实力，DIV+CSS，PHP及ASP，ASP.Net，SQL数据库的技术开发工程师。

2、N*N的方格纸,里面有多少个正方形

3、2000万个整数，找出第五十大的数字？

4、百度POI中如何试下查找最近的商家功能(提示：坐标镜像+R树)。

5、一个文件中有100万个整数，由空格分开，在程序中判断用户输入的整数是否在此文件中。说出最优的方法

6、两个不重复的数组集合中，这两个集合都是海量数据，内存中放不下，怎么求共同的元素？

7、烧一根不均匀的绳，从头烧到尾总共需要1个小时。现在有若干条材质相同的绳子，问如何用烧绳的方法来计时一个小时十五分钟呢？

8、万亿级别的两个URL文件A和B，如何求出A和B的差集C(提示：Bit映射-hash分组-多文件读写效率-磁盘寻址以及应用层面对寻址的优化)

9、怎么在海量数据中找出重复次数最多的一个？

10、海量日志数据，提取出某日访问百度次数最多的那个IP。

11、在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这2.5亿个整数。

12、搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。

13、有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。

14、有10个文件，每个文件1G，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。要求你按照query的频度排序。

15、给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？

16、一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词，请给出思想，给出时间复杂度分析。

17、腾讯面试题：给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？

18、100w个数中找出最大的100个数。

PHP面试有什么技巧么？

PHP程序员在面试的时候一般应该抓住以下几个点。

一、应该介绍自己掌握的开发一种，主要介绍PHP语言的独特语法以及如何使用，比如PHP语言会比CGI更快的执行动态页面。

二、必须熟悉Oracle、Mysql等数据库，并能简单的介绍自己掌握的程度。由于php做出的动态页面比用其他语言做出来的页面在执行效率以及CGI方面高得多，所以你还需要在面试中说出自己的文档撰写能力很强。

三、PHP程序员应该具备独立分析和解决问题的能力，可以在自我介绍中讲讲自己曾经遇到过的问题是如何解决的。让面试官看到你的能力，这将会直接影响到你自我介绍的成功与否。

四、一个PHP程序员必须有良好的职业道德和工作态度，所以在面试中应该尽量讲自己在做项目时的认真态度以及今后的工作规划，表现出自己的进取心。

五、还有关于沟通能力和理解能力的体现，这个在与HR的交谈中就可以表现出来，所以需要做的工作就是从容的有条理的把自我介绍说完，回答每一个问题时都应该简洁明了，关于自我介绍可以提前做个草稿，背一下。

六、团队合作能力也是企业非常看重的，在培训中老师一般都会带领大家做项目，大的项目一般会分小组，每个人都有相对应的任务，这就模拟了公司中的团队合作，在自我介绍过程中要把做项目的具体流程以及相互协作的过程说出来，让HR看到自己具备团队合作的能力。

七、最后就是执行力，每当任务分配下来的时候该如何执行，还有自己讲过职业规划后该如何执行，还有在学习的过程中是如何人字形的，遇到困难又是如何执行的，这些都可以体现出php程序员的执行力，回答的时候抓住发现及时寻找原因，快速展开行动的这个主线即可。

八、最重要的是你的能力、技术以及自己的项目

php面试项目遇到的难点

php面试项目遇到的难点，

准备可能遇到的问题，

1.消息队列

答：消息队列：是在消息的传输过程中保存消息的容器。消息队列管理器在将消息从它的源中继到它的目标时充当中间人。队列的主要目的是提供路由并保证消息的传递；如果发送消息时接收者不可用，消息队列会保留消息，直到可以成功地传递它。

应用场景：异步处理，应用解耦，流量削锋和消息通讯四个场景；

2.全文索引

全文检索大体分两个过程，索引创建 (Indexing) 和搜索索引 (Search) 。

索引创建：将现实世界中所有的结构化和非结构化数据提取信息，创建索引的过程。

搜索索引：就是得到用户的查询请求，搜索创建的索引，然后返回结果的过程。

php面试题 memcache和redis的区别

Redis与Memcached的区别

传统MySQL+ Memcached架构遇到的问题

实际MySQL是适合进行海量数据存储的，通过Memcached将热点数据加载到cache，加速访问，很多公司都曾经使用过这样的架构，但随着业务数据量的不断增加，和访问量的持续增长，我们遇到了很多问题：

1.MySQL需要不断进行拆库拆表，Memcached也需不断跟着扩容，扩容和维护工作占据大量开发时间。

2.Memcached与MySQL数据库数据一致性问题。

3.Memcached数据命中率低或down机，大量访问直接穿透到DB，MySQL无法支撑。

4.跨机房cache同步问题。

众多NoSQL百花齐放，如何选择

最近几年，业界不断涌现出很多各种各样的NoSQL产品，那么如何才能正确地使用好这些产品，最大化地发挥其长处，是我们需要深入研究和思考的

问题，实际归根结底最重要的是了解这些产品的定位，并且了解到每款产品的tradeoffs，在实际应用中做到扬长避短，总体上这些NoSQL主要用于解

决以下几种问题

1.少量数据存储，高速读写访问。此类产品通过数据全部in-momery 的方式来保证高速访问，同时提供数据落地的功能，实际这正是Redis最主要的适用场景。

2.海量数据存储，分布式系统支持，数据一致性保证，方便的集群节点添加/删除。

3.这方面最具代表性的是dynamo和bigtable 2篇论文所阐述的思路。前者是一个完全无中心的设计，节点之间通过gossip方式传递集群信息，数据保证最终一致性，后者是一个中心化的方案设计，通过类似一个分布式锁服务来保证强一致性,数据写入先写内存和redo log，然后定期compat归并到磁盘上，将随机写优化为顺序写，提高写入性能。

4.Schema free，auto-sharding等。比如目前常见的一些文档数据库都是支持schema-free的，直接存储json格式数据，并且支持auto-sharding等功能，比如mongodb。

面对这些不同类型的NoSQL产品,我们需要根据我们的业务场景选择最合适的产品。

Redis适用场景，如何正确的使用

前面已经分析过，Redis最适合所有数据in-momory的场景，虽然Redis也提供持久化功能，但实际更多的是一个disk-

backed的功能，跟传统意义上的持久化有比较大的差别，那么可能大家就会有疑问，似乎Redis更像一个加强版的Memcached，那么何时使用

Memcached,何时使用Redis呢?

如果简单地比较Redis与Memcached的区别，大多数都会得到以下观点：

1 Redis不仅仅支持简单的k/v类型的数据，同时还提供list，set，zset，hash等数据结构的存储。

2 Redis支持数据的备份，即master-slave模式的数据备份。

3 Redis支持数据的持久化，可以将内存中的数据保持在磁盘中，重启的时候可以再次加载进行使用。

抛开这些，可以深入到Redis内部构造去观察更加本质的区别，理解Redis的设计。

在

Redis中，并不是所有的数据都一直存储在内存中的。这是和Memcached相比一个最大的区别。Redis只会缓存所有的

key的信息，如果Redis发现内存的使用量超过了某一个阀值，将触发swap的操作，Redis根据“swappability =

age*log(size_in_memory)”计

算出哪些key对应的value需要swap到磁盘。然后再将这些key对应的value持久化到磁盘中，同时在内存中清除。这种特性使得Redis可以

保持超过其机器本身内存大小的数据。当然，机器本身的内存必须要能够保持所有的key，毕竟这些数据是不会进行swap操作的。同时由于Redis将内存

中的数据swap到磁盘中的时候，提供服务的主线程和进行swap操作的子线程会共享这部分内存，所以如果更新需要swap的数据，Redis将阻塞这个

操作，直到子线程完成swap操作后才可以进行修改。

使用Redis特有内存模型前后的情况对比：

VM off: 300k keys, 4096 bytes values: 1.3G used

VM on: 300k keys, 4096 bytes values: 73M used

VM off: 1 million keys, 256 bytes values: 430.12M used

VM on: 1 million keys, 256 bytes values: 160.09M used

VM on: 1 million keys, values as large as you want, still: 160.09M used

当

从Redis中读取数据的时候，如果读取的key对应的value不在内存中，那么Redis就需要从swap文件中加载相应数据，然后再返回给请求方。

这里就存在一个I/O线程池的问题。在默认的情况下，Redis会出现阻塞，即完成所有的swap文件加载后才会相应。这种策略在客户端的数量较小，进行

批量操作的时候比较合适。但是如果将Redis应用在一个大型的网站应用程序中，这显然是无法满足大并发的情况的。所以Redis运行我们设置I/O线程

池的大小，对需要从swap文件中加载相应数据的读取请求进行并发操作，减少阻塞的时间。

如果希望在海量数据的环境中使用好Redis，我相信理解Redis的内存设计和阻塞的情况是不可缺少的。

补充的知识点：

memcached和redis的比较

1 网络IO模型

Memcached是多线程，非阻塞IO复用的网络模型，分为监听主线程和worker子线程，监听线程监听网络连接，接受请求后，将连接描述

字pipe 传递给worker线程，进行读写IO, 网络层使用libevent封装的事件库，多线程模型可以发挥多核作用，但是引入了cache

coherency和锁的问题，比如，Memcached最常用的stats

命令，实际Memcached所有操作都要对这个全局变量加锁，进行计数等工作，带来了性能损耗。

(Memcached网络IO模型)

Redis使用单线程的IO复用模型，自己封装了一个简单的AeEvent事件处理框架，主要实现了epoll、kqueue和select，

对于单纯只有IO操作来说，单线程可以将速度优势发挥到最大，但是Redis也提供了一些简单的计算功能，比如排序、聚合等，对于这些操作，单线程模型实

际会严重影响整体吞吐量，CPU计算过程中，整个IO调度都是被阻塞住的。

2.内存管理方面

Memcached使用预分配的内存池的方式，使用slab和大小不同的chunk来管理内存，Item根据大小选择合适的chunk存储，内

存池的方式可以省去申请/释放内存的开销，并且能减小内存碎片产生，但这种方式也会带来一定程度上的空间浪费，并且在内存仍然有很大空间时，新的数据也可

能会被剔除，原因可以参考Timyang的文章：

Redis使用现场申请内存的方式来存储数据，并且很少使用free-list等方式来优化内存分配，会在一定程度上存在内存碎片，Redis

跟据存储命令参数，会把带过期时间的数据单独存放在一起，并把它们称为临时数据，非临时数据是永远不会被剔除的，即便物理内存不够，导致swap也不会剔

除任何非临时数据(但会尝试剔除部分临时数据)，这点上Redis更适合作为存储而不是cache。

3.数据一致性问题

Memcached提供了cas命令，可以保证多个并发访问操作同一份数据的一致性问题。 Redis没有提供cas 命令，并不能保证这点，不过Redis提供了事务的功能，可以保证一串 命令的原子性，中间不会被任何操作打断。

4.存储方式及其它方面

Memcached基本只支持简单的key-value存储，不支持枚举，不支持持久化和复制等功能

Redis除key/value之外，还支持list,set,sorted set,hash等众多数据结构，提供了KEYS

进行枚举操作，但不能在线上使用，如果需要枚举线上数据，Redis提供了工具可以直接扫描其dump文件，枚举出所有数据，Redis还同时提供了持久化和复制等功能。

5.关于不同语言的客户端支持

在不同语言的客户端方面，Memcached和Redis都有丰富的第三方客户端可供选择，不过因为Memcached发展的时间更久一些，目

前看在客户端支持方面，Memcached的很多客户端更加成熟稳定，而Redis由于其协议本身就比Memcached复杂，加上作者不断增加新的功能

等，对应第三方客户端跟进速度可能会赶不上，有时可能需要自己在第三方客户端基础上做些修改才能更好的使用。

根据以上比较不难看出，当我们不希望数据被踢出，或者需要除key/value之外的更多数据类型时，或者需要落地功能时，使用Redis比使用Memcached更合适。

关于Redis的一些周边功能

Redis除了作为存储之外还提供了一些其它方面的功能，比如聚合计算、pubsub、scripting等，对于此类功能需要了解其实现原

理，清楚地了解到它的局限性后，才能正确的使用，比如pubsub功能，这个实际是没有任何持久化支持的，消费方连接闪断或重连之间过来的消息是会全部丢

失的，又比如聚合计算和scripting等功能受Redis单线程模型所限，是不可能达到很高的吞吐量的，需要谨慎使用。

总的来说Redis作者是一位非常勤奋的开发者，可以经常看到作者在尝试着各种不同的新鲜想法和思路，针对这些方面的功能就要求我们需要深入了解后再使用。

总结：

1.Redis使用最佳方式是全部数据in-memory。

2.Redis更多场景是作为Memcached的替代者来使用。

3.当需要除key/value之外的更多数据类型支持时，使用Redis更合适。

4.当存储的数据不能被剔除时，使用Redis更合适。

谈谈Memcached与Redis(一)

1. Memcached简介

Memcached是以LiveJurnal旗下Danga Interactive公司的Bard

Fitzpatric为首开发的高性能分布式内存缓存服务器。其本质上就是一个内存key-value数据库，但是不支持数据的持久化，服务器关闭之后数

据全部丢失。Memcached使用C语言开发，在大多数像Linux、BSD和Solaris等POSIX系统上，只要安装了libevent即可使

用。在Windows下，它也有一个可用的非官方版本()。Memcached

的客户端软件实现非常多，包括C/C++, PHP, Java, Python, Ruby, Perl, Erlang,

Lua等。当前Memcached使用广泛，除了LiveJournal以外还有Wikipedia、Flickr、Twitter、Youtube和

WordPress等。

在Window系统下，Memcached的安装非常方便，只需从以上给出的地址下载可执行软件然后运行memcached.exe –d

install即可完成安装。在Linux等系统下，我们首先需要安装libevent，然后从获取源码，make make

install即可。默认情况下，Memcached的服务器启动程序会安装到/usr/local/bin目录下。在启动Memcached时，我们可

以为其配置不同的启动参数。

1.1 Memcache配置

Memcached服务器在启动时需要对关键的参数进行配置，下面我们就看一看Memcached在启动时需要设定哪些关键参数以及这些参数的作用。

1）-p num Memcached的TCP监听端口，缺省配置为11211；

2）-U num Memcached的UDP监听端口，缺省配置为11211，为0时表示关闭UDP监听；

3）-s file Memcached监听的UNIX套接字路径；

4）-a mask 访问UNIX套接字的八进制掩码，缺省配置为0700；

5）-l addr 监听的服务器IP地址，默认为所有网卡；

6）-d 为Memcached服务器启动守护进程；

7）-r 最大core文件大小；

8）-u username 运行Memcached的用户，如果当前为root的话需要使用此参数指定用户；

9）-m num 分配给Memcached使用的内存数量，单位是MB；

10）-M 指示Memcached在内存用光的时候返回错误而不是使用LRU算法移除数据记录；

11）-c num 最大并发连数，缺省配置为1024；

12）-v –vv –vvv 设定服务器端打印的消息的详细程度，其中-v仅打印错误和警告信息，-vv在-v的基础上还会打印客户端的命令和相应，-vvv在-vv的基础上还会打印内存状态转换信息；

13）-f factor 用于设置chunk大小的递增因子；

14）-n bytes 最小的chunk大小，缺省配置为48个字节；

15）-t num Memcached服务器使用的线程数，缺省配置为4个；

16）-L 尝试使用大内存页；

17）-R 每个事件的最大请求数，缺省配置为20个；

18）-C 禁用CAS，CAS模式会带来8个字节的冗余；

2. Redis简介

Redis是一个开源的key-value存储系统。与Memcached类似，Redis将大部分数据存储在内存中，支持的数据类型包括：字

符串、哈希表、链表、集合、有序集合以及基于这些数据类型的相关操作。Redis使用C语言开发，在大多数像Linux、BSD和Solaris等

POSIX系统上无需任何外部依赖就可以使用。Redis支持的客户端语言也非常丰富，常用的计算机语言如C、C#、C++、Object-C、PHP、

Python、Java、Perl、Lua、Erlang等均有可用的客户端来访问Redis服务器。当前Redis的应用已经非常广泛，国内像新浪、淘

宝，国外像Flickr、Github等均在使用Redis的缓存服务。

Redis的安装非常方便，只需从获取源码，然后make make

install即可。默认情况下，Redis的服务器启动程序和客户端程序会安装到/usr/local/bin目录下。在启动Redis服务器时，我们

需要为其指定一个配置文件，缺省情况下配置文件在Redis的源码目录下，文件名为redis.conf。

PHP程序员上机面试题（并附答案，回答好的加分）

某大公司的PHP面试题

管理提醒: 本帖被 haowubai 执行取消置顶操作(2009-07-30)

1. 如何用php的环境变量得到一个网页地址的内容？ip地址又要怎样得到？

[php]

echo $_SERVER ['PHP_SELF'];

echo $_SERVER ['SERVER_ADDR'];

[/php]

2. 求两个日期的差数，例如2007-2-5 ~ 2007-3-6 的日期差数

[php]

$begin=strtotime('2007-2-5');

$end=strtotime('2007-3-6');

echo ($end-$begin)/(24*3600);

[/php]

3. 请写一个函数，实现以下功能：

字符串“open_door” 转换成 “OpenDoor”、”make_by_id” 转换成 ”MakeById”。

[php]

function changeStyle( $str) {

/*$str = str_replace ( "_", " ", $str );

$str = ucwords ( $str );

$str = str_replace ( " ", "", $str );

return $str;*/

$arrStr=explode('_',$str);

foreach($arrStr as $key=$value){

$arrStr[$key]=strtoupper(substr($value,0,1)).substr($value,1);

}

return implode('',$arrStr);

}

$s = "open_door";

echo changeStyle ( $s );

[/php]

4. 要求写一段程序，实现以下数组$arr1转换成数组$arr2：

[php]$arr1 = array (

'0' = array ('fid' = 1, 'tid' = 1, 'name' ='Name1' ),

'1' = array ('fid' = 1, 'tid' = 2 , 'name' ='Name2' ),

'2' = array ('fid' = 1, 'tid' = 5 , 'name' ='Name3' ),

'3' = array ('fid' = 1, 'tid' = 7 , 'name' ='Name4' ),

'4' = array ('fid' = 3, 'tid' = 9, 'name' ='Name5' )

);

$arr2 = array (

'0' = array (

'0' = array ( 'tid' = 1, 'name' = 'Name1'),

'1' = array ( 'tid' = 2, 'name' = 'Name2'),

'2' = array ( 'tid' = 5, 'name' = 'Name3'),

'3' = array ( 'tid' = 7, 'name' = 'Name4')

),

'1' = array (

'0' = array ( 'tid' = 9, 'name' = 'Name5' )

)

);

?php

$arr1 = array (

'0' = array ('fid' = 1, 'tid' = 1, 'name' ='Name1' ),

'1' = array ('fid' = 1, 'tid' = 2 , 'name' ='Name2' ),

'2' = array ('fid' = 1, 'tid' = 5 , 'name' ='Name3' ),

'3' = array ('fid' = 1, 'tid' = 7 , 'name' ='Name4' ),

'4' = array ('fid' = 3, 'tid' = 9, 'name' ='Name5' )

);

function changeArrayStyle($arr){

foreach($arr as $key=$value){

$result[$value['fid']][]=$value;

}

return array_values($result);

}

$arr2=changeArrayStyle($arr1);

echo "pre";

var_dump($arr2);

[/php]

5. 请简述数据库设计的范式及应用。

一般第3范式就足以，用于表结构的优化，这样做既可以避免应用程序过于复杂同时也避免了SQL语句过于庞大所造成系统效率低下。

ANSWER：

第一范式：若关系模式R的每一个属性是不可再分解的，再属于第一范式。

第二范式：若R属于第一范式，且所有的非码属性都完全函数依赖于码属性，则为第二范式。

第三范式：若R属于第二范式，且所有的非码属性没有一个是传递函数依赖于候选码，则属于第三范式。

6.一个表中的Id有多个记录，把所有这个id的记录查出来，并显示共有多少条记录数，用SQL语句及视图、存储过程分别实现。

存储过程：

[php]

DELIMITER //

create procedure proc_countNum(in columnId int,out rowsNo int)

begin

select count(*) into rowsNo from member where member_id=columnId;

end

call proc_countNum(1,@no);

select @no;

[/php]

视图：

create view v_countNum as select member_id,count(*) as countNum from member group by member_id

select countNum from v_countNum where member_id=1

7 表中有A B C三列,用SQL语句实现：当A列大于B列时选择A列否则选择B列，当B列大于C列时选择B列否则选择C列。

[php]select

case

when first_namemiddle_name then

case when first_namelast_name then first_name

else last_name end

else

case when middle_namelast_name then middle_name else last_name

end

end as name

from member

[/php]

8请简述项目中优化sql语句执行效率的方法,从哪些方面,sql语句性能如何分析?

ANSWER: sql优化有鸟用，不如直接加索引。

9 如果模板是用smarty模板。怎样用section语句来显示一个名为$data的数组。比如：

[php]$data = array(

[0] = array( [id]=8 [name]=’name1′)

[1] = array( [id]=10 [name]=’name2′)

[2] = array( [id]=15 [name]=’name3′)

……

)[/php]

写出在模板页的代码？ 若用foreach语句又要怎样显示呢？

占无答案.

10 写一个函数，能够遍历一个文件夹下的所有文件和子文件夹。（目录操作）

[php] ?php

$d = dir(dirname(__file__));

//echo "Handle: " . $d-handle . "\n";

//echo "Path: " . $d-path . "\n";

while ( false !== ($entry = $d-read ()) ) {

echo $entry . "br /";

}

$d-close ();

[/php]

11 两张表 city表和province表。分别为城市与省份的关系表。

city:

id City Provinceid

1 广州 1

2 深圳 1

3 惠州 1

4 长沙 2

5 武汉 3

………. 广州

province:

id Province

1 广东

2 湖南

3 湖北

……….

（1） 写一条sql语句关系两个表，实现：显示城市的基本信息。？

（2） 显示字段：城市id ，城市名， 所属省份 。

如：

Id（城市id） Cityname(城市名) Privence(所属省份)

。。。。。。。。。

。。。。。。。。。

（2）如果要统计每个省份有多少个城市，请用group by 查询出来。？

显示字段：省份id ，省份名，包含多少个城市。

ANSWER:

1.select A.id,A.Cityname,B.Province from city A,province B where A.provinceid=B.id

2.select B.id,B.Province,count(*) as num from city A,province B where A.provinceid=B.id group by B.id

12. 按照你的经验请简述软件工程进行软件开发的步骤。以下工具Rational Rose、PowerDesigner、Project、VSS或CVS、TestDirector使用过那种,有缺点是什么？

公司用dbdesigner及cvs,测试管理工具用的是Mantis

13. 请简述操作系统的线程与进程的区别。列举LINUX下面你使用过的软件？

14. 请使用伪语言结合数据结构冒泡排序法对以下一组数据进行排序 10 2 36 14 10 25 23 85 99 45。

[php]function bubble_sort( $arr){

$number=count($arr);

for($i=0;$i$number-1;$i++){

for($j=0;$j$number-1-$i;$j++){

if($arr[$j]$arr[$j+1]){

$tmp=$arr[$j];

$arr[$j]=$arr[$j+1];

$arr[$j+1]=$tmp;

}

}

}

}

$str="10 2 36 14 10 25 23 85 99 45";

$arr=explode(" ",$str);

bubble_sort($arr);

echo "pre";

var_dump($arr);

[/php]