1.使對象可以像數(shù)組一樣進(jìn)行foreach循環(huán)哑芹，要求屬性必須是私有钦铁。(Iterator模式的PHP5實(shí)現(xiàn)履恩，寫一類實(shí)現(xiàn)Iterator接口)（騰訊）
<?php
class Test implements Iterator{
private $item = array('id'=>1,'name'=>'php');
public function rewind(){ reset($this->item);
}
public function current(){
return current($this->item);
}
public function key(){
return key($this->item);
}
public function next(){
return next($this->item);
}
public function valid(){
return($this->current()!==false);
}
}
//測試
$t=new Test;
foreach($t as $k=>$v){
echo$k,'--->',$v,'<br/>';
}
?>
2.用PHP實(shí)現(xiàn)一個(gè)雙向隊(duì)列（騰訊）
<?php
class Deque{
private $queue=array();
public function addFirst($item){
return array_unshift($this->queue,$item);
}
public function addLast($item){
return array_push($this->queue,$item);
}
public function removeFirst(){
return array_shift($this->queue);
}
public function removeLast(){
return array_pop($this->queue);
}
} ?>
3.請使用冒泡排序法對以下一組數(shù)據(jù)進(jìn)行排序10 2 36 14 10 25 23 85 99 45识脆。
<?php
// 冒泡排序
function bubble_sort(&$arr){
for ($i=0,$len=count($arr); $i < $len; $i++) {
for ($j=1; $j < $len-$i; $j++) {
if ($arr[$j-1] > $arr[$j]) {
$temp = $arr[$j-1]; $arr[$j-1] = $arr[$j]; $arr[$j] = $temp;
}
}
}
}
// 測試
$arr = array(10,2,36,14,10,25,23,85,99,45);
bubble_sort($arr);
print_r($arr);
?>
4.寫出一種排序算法（要寫出代碼），并說出優(yōu)化它的方法缕碎。（新浪）
<?php
//快速排序
function partition(&$arr,$low,$high){
$pivotkey = $arr[$low];
while($low<$high){
while($low < $high && $arr[$high] >= $pivotkey){
$high--;
}
$temp = $arr[$low];
$arr[$low] = $arr[$high];
$arr[$high] = $temp;
while($low < $high && $arr[$low] <= $pivotkey){
$low++;
}
$temp=$arr[$low];
$arr[$low]=$arr[$high];
$arr[$high]=$temp;
}
return$low;
}
function quick_sort(&$arr,$low,$high){
if($low < $high){
$pivot = partition($arr,$low,$high);
quick_sort($arr,$low,$pivot-1);
quick_sort($arr,$pivot+1,$high);
}
}
?>
該算法是通過分治遞歸來實(shí)現(xiàn)的褥影，其效率很大程度上取決于參考元素的選擇，可以選擇數(shù)組的中間元素阎曹，也可以隨機(jī)得到三個(gè)元素伪阶，然后選擇中間的那個(gè)元素（三數(shù)中值法）。
另外還有一點(diǎn)处嫌，就是當(dāng)我們在分割時(shí)栅贴，如果分割出來的子序列的長度很小的話（小于5到20），通常遞歸的排序的效率就沒有諸如插入排序或希爾排序那么快了熏迹。因此可以會(huì)去判斷數(shù)組的長度檐薯，如果小于10的話，直接用插入排序注暗，而不再遞歸調(diào)用這個(gè)快速排序坛缕。
5.一群猴子排成一圈，按1捆昏，2赚楚，...，n依次編號骗卜。然后從第1只開始數(shù)宠页，數(shù)到第m只,把它踢出圈，從它后面再開始數(shù)寇仓，再數(shù)到第m只举户，在把它踢出去...，如此不停的進(jìn)行下去遍烦，直到最后只剩下一只猴子為止俭嘁，那只猴子就叫做大王。要求編程模擬此過程服猪，輸入m供填、n,輸出最后那個(gè)大王的編號。（新浪）（小米）
這是著名的約瑟夫環(huán)問題
<?php
// 方案一蔓姚，使用php來模擬這個(gè)過程
function king($n,$m){
$mokey = range(1, $n);
$i = 0;
while (count($mokey) >1) {
$i += 1;
$head = array_shift($mokey);
//一個(gè)個(gè)出列最前面的猴子
if ($i % $m !=0) {
#如果不是m的倍數(shù)捕虽，則把猴子返回尾部，否則就拋掉坡脐，也就是出列
array_push($mokey,$head);
}
}
// 剩下的最后一個(gè)就是大王了
return $mokey[0];
}
// 測試
echo king(10,7);
// 方案二泄私，使用數(shù)學(xué)方法解決
function josephus($n,$m){
$r = 0;
for ($i=2; $i <= $m ; $i++) {
$r = ($r + $m) % $i;
}
return $r+1;
}
// 測試
print_r(josephus(10,7));
?>
6.寫一個(gè)二維數(shù)組排序算法函數(shù)，能夠具有通用性备闲，可以調(diào)用php內(nèi)置函數(shù)晌端。
<?php //二維數(shù)組排序，$arr是數(shù)據(jù)恬砂，$keys是排序的健值咧纠，$order是排序規(guī)則，1是降序泻骤，0是升序
function array_sort($arr,$keys,$order=0){
if(!is_array($arr)){
return false;
}
$keysvalue=array();
foreach($arr as $key => $val){
$keysvalue[$key] = $val[$keys];
}
if($order == 0){
asort($keysvalue);
}else{
arsort($keysvalue);
}
reset($keysvalue);
foreach($keysvalue as $key => $vals){
$keysort[$key] = $key;
}
$new_array=array();
foreach($keysort as $key=> $val){
$new_array[$key]=$arr[$val];
}
return$new_array;
}
//測試
$person=array( array('id'=>2,'name'=>'zhangsan','age'=>23),
array('id'=>5,'name'=>'lisi','age'=>28),
array('id'=>3,'name'=>'apple','age'=>17)
);
$result = array_sort($person,'name',1);
print_r($result);
?>
7.用二分法查找一個(gè)長度為10的排好序的線性表漆羔，查找不成功時(shí)最多需要比較次數(shù)是（小米）
4
8.從0,1,2,3,4,5,6,7,8,9梧奢，這十個(gè)數(shù)字中任意選出三個(gè)不同的數(shù)字，“三個(gè)數(shù)字中不含0和5”的概率是（小米）
7/15
9.一個(gè)三角形三個(gè)頂點(diǎn)有3只老鼠演痒，一聲槍響亲轨，3只老鼠開始沿三角形的邊勻速運(yùn)動(dòng)，請問他們相遇的概率是（小米）
75%鸟顺，每只老鼠都有順時(shí)針惦蚊、逆時(shí)鐘兩種運(yùn)動(dòng)方向，3只老鼠共有8種運(yùn)動(dòng)情況讯嫂，只有當(dāng)3只老鼠都為順時(shí)針或者逆時(shí)鐘蹦锋，它們才不會(huì)相遇，剩余的6中情況都會(huì)相遇欧芽，故相遇的概率為6/8=75%莉掂。
10.描述順序查找和二分查找（也叫做折半查找）算法，順序查找必須考慮效率千扔，對象可以是一個(gè)有序數(shù)組（小米）
<?php
/**
* 順序查找
* @param array $arr 數(shù)組
* @param $k 要查找的元素
* @return mixed 成功返回?cái)?shù)組下標(biāo)巫湘，失敗返回-1
*/
function seq_sch($arr,$k){
????????for ($i=0,$n = count($arr); $i < $n; $i++) {
????????????????if ($arr[$i] == $k) {
????????????????????????break;
????????????????}
????????????}
????????if($i < $n){
????????????????return $i;
????????}else{
????????????return -1;
????????}
}
/** \* 二分查找，要求數(shù)組已經(jīng)排好順序 * @param array $array 數(shù)組 * @param int $low 數(shù)組起始元素下標(biāo) * @param int $high 數(shù)組末尾元素下標(biāo) * @param $k 要查找的元素 * @return mixed 成功時(shí)返回?cái)?shù)組下標(biāo)昏鹃，失敗返回-1 */
function bin_sch($array,$low,$high,$k){
????????if ($low <= $high) {
????????????????$mid = intval(($low + $high) / 2);
????????????????if ($array[$mid] == $k) {
????????????????????????return $mid; ????
????????????????} elseif ($k < $array[$mid]) {
????????????????????????return bin_sch($array,$low,$mid - 1,$k);
????????????????} else{
????????????????????????return bin_sch($array,$mid + 1,$high,$k);
????????????????}
????????}
????????return -1;
}
// 測試：順序查找
$arr1 = array(9,15,34,76,25,5,47,55);
echo seq_sch($arr1,47);//結(jié)果為6
echo "<br />";
// 測試：二分查找
$arr2 = array(5,9,15,25,34,47,55,76);
echo bin_sch($arr2,0,7,47);//結(jié)果為5
?>?
11.我們希望開發(fā)一款撲克游戲尚氛，請給出一套洗牌算法，公平的洗牌并將洗好的牌存儲在一個(gè)整形數(shù)組里洞渤。（鑫眾人云）
<?php
$card_num = 54;
//牌數(shù)
function wash_card($card_num){
$cards = $tmp = array();
for($i = 0;$i < $card_num;$i++){
$tmp[$i] = $i;
}
for($i = 0;$i < $card_num;$i++){
$index = rand(0,$card_num-$i-1);
$cards[$i] = $tmp[$index];
unset($tmp[$index]);
$tmp = array_values($tmp);
}
return $cards;
}
// 測試：
print_r(wash_card($card_num));
?>
12.寫出你所知道的排序方法（億郵）
冒泡排序阅嘶，快速排序，插入排序载迄，選擇排序
