#### 1.使對象可以像數組一樣進行foreach循環，要求屬性必須是私有。(Iterator模式的PHP5實現，寫一類實現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實現一個雙向隊列（騰訊）
<?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.請使用冒泡排序法對以下一組數據進行排序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.寫出一種排序算法（要寫出代碼），并說出優化它的方法。（新浪）
<?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);
}
}
?>
該算法是通過分治遞歸來實現的，其效率很大程度上取決于參考元素的選擇，可以選擇數組的中間元素，也可以隨 機得到三個元素，然后選擇中間的那個元素（三數中值法）。
另外還有一點，就是當我們在分割時，如果分割出來的子序列的長度很小的話（小于5到20），通常遞歸的排序的效率就沒有諸如插入排序或希爾排序那么快了。因此可以會去判斷數組的長度，如果小于10的話，直接用插入排序，而不再遞歸調用這個快速排序。
#### 5.一群猴子排成一圈，按1，2，...，n依次編號。然后從第1只開始數，數到第m只,把它踢出圈，從它后面再開始數，再數到第m只，在把它踢出去...，如此不停的進行下去，直到最后只剩下一只猴子為止，那只猴子就叫做大王。要求編程模擬此過程，輸入m、n,輸出最后那個大王的編號。（新浪）（小米）
這是著名的約瑟夫環問題
<?php
// 方案一，使用php來模擬這個過程
function king($n,$m){
$mokey = range(1, $n);
$i = 0;
while (count($mokey) >1) {
$i += 1;
$head = array_shift($mokey);//一個個出列最前面的猴子
if ($i % $m !=0) {
#如果不是m的倍數，則把猴子返回尾部，否則就拋掉，也就是出列
array_push($mokey,$head);
}
// 剩下的最后一個就是大王了
return $mokey[0];
}
}
// 測試
echo king(10,7);
// 方案二，使用數學方法解決
function josephus($n,$m){
$r = 0;
for ($i=2; $i <= $m ; $i++) {
$r = ($r + $m) % $i;
}
return $r+1;
}
// 測試
print_r(josephus(10,7));
?>
#### 11.我們希望開發一款撲克游戲，請給出一套洗牌算法，公平的洗牌并將洗好的牌存儲在一個整形數組里。（鑫眾人云）
<?php
$card_num = 54;//牌數
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));
?>
