PHP interview questions algorithm questions

Algorithm questions often appear in PHP interview questions. This article mainly shares with you the algorithm questions of PHP interview questions, hoping to help everyone.

Related recommendations: "2019 PHP Interview Questions Summary (Collection)"

Interview Questions - Algorithm Questions:

1. Insertion sort (one-dimensional array) Basic idea: Each time a data element to be sorted is inserted into the appropriate position in the previously sorted array, so that the array is still in order; until all the data elements to be sorted are until the insertion is complete. Example:

[Initial keyword] [49] 38 65 97 76 13 27 49
J=2(38) [38 49] 65 97 76 13 27 49
J=3(65 ) [38 49 65] 97 76 13 27 49
J=4(97) [38 49 65 97] 76 13 27 49
J=5(76) [38 49 65 76 97] 13 27 49
J=6(13) [13 38 49 65 76 97] 27 49
J=7(27) [13 27 38 49 65 76 97] 49
J=8(49) [13 27 38 49 49 65 76 97]

function insert_sort($arr){ $count = count($arr); for($i=1; $i<$count; $i++){ $tmp = $arr[$i]; $j = $i - 1; while($arr[$j] > $tmp){ $arr[$j+1] = $arr[$j]; $arr[$j] = $tmp; $j--; } } return $arr; }

2. Selection sort (one-dimensional array) Basic idea: Each pass selects the smallest (or largest) element from the data elements to be sorted, in order Place it at the end of the sorted array until all data elements to be sorted are exhausted. Example:

[Initial keyword] [49 38 65 97 76 13 27 49]
13 after the first sort [38 65 97 76 49 27 49]
13 after the second sort 27 [65 97 76 49 38 49]
After the third sorting 13 27 38 [97 76 49 65 49]
After the fourth sorting 13 27 38 49 [49 97 65 76]
Fifth After the sixth sorting pass 13 27 38 49 49 [97 97 76]
After the sixth sorting pass 13 27 38 49 49 76 [76 97]
After the seventh sorting pass 13 27 38 49 49 76 76 [ 97]
Final sorting result 13 27 38 49 49 76 76 97

function select_sort($arr){ $count = count($arr); for($i=0; $i<$count; $i++){ $k = $i; for($j=$i+1; $j<$count; $j++){ if ($arr[$k] > $arr[$j]) $k = $j; } if($k != $i){ $tmp = $arr[$i]; $arr[$i] = $arr[$k]; $arr[$k] = $tmp; } } return $arr; }

3. Bubble sorting (one-dimensional array) Basic idea: compare the sizes of the data elements to be sorted pairwise and find two data When the order of elements is reversed, swapping is performed until there are no more data elements in reverse order. Sorting process: Imagine that the sorted array R [1..N] is erected vertically, and each data element is regarded as a weighted bubble. According to the principle that light bubbles cannot be under heavy bubbles, the array R is scanned from bottom to top. Whenever light bubbles that violate this principle are scanned, they are made to "float" upward, and this process is repeated until the last two bubbles are the lighter one at the top and the heavier one at the bottom. Example:

49 13 13 13 13 13 13 13
38 49 27 27 27 27 27 27
65 38 49 38 38 38 38 38
97 65 38 49 49 49 49 49
76 97 65 49 49 49 49 49
13 76 97 65 65 65 65 65
27 27 76 97 76 76 76 76
49 49 49 76 97 97 97 97

function bubble_sort($array){ $count = count($array); if ($count <= 0) return false; for($i=0; $i<$count; $i++){ for($j=$count-1; $j>$i; $j--){ if ($array[$j]<$array[$j-1]){ $tmp = $array[$j]; $array[$j] = $array[$j-1]; $array[$j-1] = $tmp; } } } return $array; }

4. Quick sort (one-dimensional array) Basic idea: Take any data element in the current unordered area R[1..H] as the "baseline" for comparison (it may be recorded as The current disordered area is divided into two smaller disordered areas on the left and right: R[1..I-1] and R[I 1..H], and the data elements in the left disordered subarea are less than or equal to the reference elements. , the data elements in the unordered sub-area on the right are all greater than or equal to the reference element, and the reference X is located at the final sorting position, that is, R[1..I-1]≤X.Key≤RI 1..H, when R When both [1..I-1] and R[I 1..H] are non-empty, perform the above division process on them respectively until all data elements in the unordered sub-area have been sorted. Example:

Initial keyword [49 38 65 97 76 13 27 49]
After the first exchange [27 38 65 97 76 13 49 49]
After the second exchange [27 38 49 97 76 13 65 49]
J Scan to the left, the position remains unchanged, after the third exchange [27 38 13 97 76 49 65 49]
I Scan to the right, the position remains unchanged, the fourth exchange After [27 38 13 49 76 97 65 49]
J scan to the left [27 38 13 49 76 97 65 49]
(one division process)
Initial keyword [49 38 65 97 76 13 27 49]
After one sorting [27 38 13] 49 [76 97 65 49]
After two sortings [13] 27 [38] 49 [49 65] 76 [97]
After three sortings After that 13 27 38 49 49 [65] 76 97
The final sorting result 13 27 38 49 49 65 76 97
The status after each sorting

function quickSort(&$arr){ if(count($arr)>1){ $k=$arr[0]; $x=array(); $y=array(); $_size=count($arr); for($i=1;$i<$_size;$i++){ if($arr[$i]<=$k){ $x[]=$arr[$i]; }elseif($arr[$i]>$k){ $y[]=$arr[$i]; } } $x=quickSort($x); $y=quickSort($y); return array_merge($x,array($k),$y); }else{ return$arr; } }

5. Hill sorting (shell sort) — O(n log n)

functionshell_sort(&$arr){ if(!is_array($arr))return;$n=count($arr); for($gap=floor($n/2);$gap>0;$gap=floor($gap/=2)){ for($i=$gap;$i<$n;++$i){ for($j=$i-$gap;$j>=0&&$arr[$j+$gap]<$arr[$j];$j-=$gap){ $temp=$arr[$j]; $arr[$j]=$arr[$j+$gap]; $arr[$j+$gap]=$temp; } } } }

6. Binary search

/** * 二分算法查找 * @param array $array 要查找的数组 * @param int $min_key 数组的最小下标 * @param int $max_key 数组的最大下标 * @param mixed $value 要查找的值 * @return boolean */ function bin_search($array,$min_key,$max_key,$value){ if($min_key <= $max_key){ $key = intval(($min_key+$max_key)/2); if($array[$key] == $value){ return true; }elseif($value < $array[$key]){ return bin_search($array,$min_key,$key-1,$value); }else{ return bin_search($array,$key+1,$max_key,$value); } }else{ return false; } }

7. Deletion of linear table (implemented in array)

function delete_array_element($array, $i) { $len = count($array); for ($j=$i; $j<$len; $j++){ $array[$j] = $array[$j+1] } array_pop($array); return $array; }

8, String length

function strlen($str) { if ($str == '') return 0; $count = 0; while (1){ if ($str[$count] != NULL){ $count++; continue; }else{ break; } } return $count; }

9, String flip

function strrev($str) { if ($str == '') return 0; for ($i=(strlen($str)-1); $i>=0; $i--){ $rev_str .= $str[$i]; } return $rev_str; }

10, String comparison

function strcmp($s1, $s2) { if (strlen($s1) < strlen($s2)) return -1; if (strlen($s1) > strlen($s2)) return 1; for ($i=0; $i
      

      
11, Search string
      
function strstr($str, $substr) { $m = strlen($str); $n = strlen($substr); if ($m < $n) return false; for ($i=0; $i<=($m-$n+1); $i++){ $sub = substr($str, $i, $n); if (strcmp($sub, $substr) == 0) return $i; } return false; }
      

      
12, String replacement
      
function str_replace($substr, $newsubstr, $str) { $m = strlen($str); $n = strlen($substr); $x = strlen($newsubstr); if (strchr($str, $substr) == false) return false; for ($i=0; $i<=($m-$n+1); $i++){ $i = strchr($str, $substr); $str = str_delete($str, $i, $n); $str = str_insert($str, $i, $newstr); } return $str; }
      

      
13, Insert a string
      
function str_insert($str, $i, $substr) { for($j=0; $j<$i; $j++){ $startstr .= $str[$j]; } for ($j=$i; $j
      
14, Delete a string
      
function str_delete($str, $i, $j){ for ($c=0; $c<$i; $c++){ $startstr .= $str[$c]; } for ($c=($i+$j); $c
      

      
15, copy string
      
function strcpy($s1, $s2){ if (strlen($s1)==NULL || !isset($s2)) return; for ($i=0; $i
      

      
16, connect string
      
function strcat($s1, $s2){ if (!isset($s1) || !isset($s2)) return; $newstr = $s1; for($i=0; $i
      

      
17, simple encoding function (corresponding to php_decode function)
      
function php_encode($str) { if ($str=='' && strlen($str)>128) return false; for($i=0; $i
       
        31 && $c<107) $c += 20; if ($c>106 && $c<127) $c -= 75 ; $word = chr($c); $s .= $word; } return $s; }
       
      
18. Simple decoding function (corresponding to the php_encode function)
      
function php_decode($str) { if ($str=='' && strlen($str)>128) return false; for($i=0; $i106 && $c<127) $c = $c-20; if ($c>31 && $c<107) $c = $c+75; $word = chr($c); $s .= $word; } return $s; }
      

      
19. Simple encryption function (corresponding to the php_decrypt function)
      
function php_encrypt($str) { $encrypt_key = 'abcdefghijklmnopqrstuvwxyz1234567890'; $decrypt_key = 'ngzqtcobmuhelkpdawxfyivrsj2468021359'; if (strlen($str) == 0) return false; for ($i=0; $i
      

      
20. Simple decryption function (corresponding to the php_encrypt function)
      
function php_decrypt($str) { $encrypt_key = 'abcdefghijklmnopqrstuvwxyz1234567890'; $decrypt_key = 'ngzqtcobmuhelkpdawxfyivrsj2468021359'; if (strlen($str) == 0) return false; for ($i=0; $i
      
Related recommendations:
      
php’s classic algorithm questions Apple
      
A classic algorithm question caused by a commonly used Linux command in a project
      
A brief discussion on some basic algorithm questions on characters and arrays in js
      
The above is the detailed content of PHP interview questions algorithm questions. For more information, please follow other related articles on the PHP Chinese website!