Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Some answers to some interview questions I've had
<?php
/** This may be one of the most useless files in the world, but it essentially encapsulates
* the answers to as many interview questions as I can remember over the years. Written in PHP
* because ... just because.
**/
/**
* Write me a program that can determine if something is a palindrome
* ex. A man, a plan, a canal - Panama! should count
**/
function palindrome($str) {
// clean string
$str=trim(strtolower(preg_replace( '/\W/', '', (string ) $str )));
$len=strlen($str);
for($i=0,$j=($len-1); $i<$len;$i++,$j--) {
if($str[$i] != $str[$j] ) return(false);
if($i > $j ) return(true);
}
} // executes in O(N)
/** Write me a program that flips a string in place, without using any extra memory.
* ex. "My String" becomes "gnirtS yM"
**/
function flipStringSimple($str) {
for($i=0,$j=(strlen($str)-1); $i<(floor(strlen($str)/2));$i++,$j--) {
if($str[$i] == $str[$j] ) continue;
// using XOR swap so we don't have to use a temp variable.
$str[$i] = $str[$i] ^ $str[$j];
$str[$j] = $str[$j] ^ $str[$i];
$str[$i] = $str[$i] ^ $str[$j];
}
return($str);
} // executes in O(N)
/** Write me a procedure that flips a string so that the words read forward but
* the sentence reads backwards
* ex. "My String" becomes "String My"
*/
function flipStringComplex($str) {
// piggy-backs off of flipStringSimple
$len=strlen($str);
$str = flipStringSimple($str);
$newstr='';
$buffer = ' ';
for($i=0;$i<$len;$i++) {
if( $str[$i] != ' ' ) {
$buffer .= $str[$i];
} else {
$newstr .= flipStringSimple($buffer);
$buffer=' ';
}
}
$newstr .= flipStringSimple($buffer);
return($newstr);
} // executes in O(N^2)
/**
* Write me a procedure that tells me if a number is prime
**/
function isPrime($int) {
$x = (int) $int;
// just to speed things along
if( $x < 1 ) return( false );
if( $x < 4 ) return( true );
for($i=2;$i<$x;$i++) {
if( ($x % $i) === 0 ) return(false);
}
return(true);
} //executes in O(N)
/**
* Write me a procedure that prints the Fibonnaci sequence up to n places
**/
function fibonacci($n) {
$a=$b=1;
echo "$a $b ";
for($i=0;$i<$n-2;$i++) {
$c=$a+$b;
$a=$b;
$b=$c;
echo $c . ' ';
}
} // executes in O(N)
/**
* Assume you have an array of sequential numbers of size n. We put them into an array at
* random and remove one of them. Find which number has been removed
i.e. in the array (1,2,3,5,6,7,8), the number 4 is missing.
**/
function missingInt($array) {
$n=count($array)+1; //because we know one is missing
$sum=0;
for($i=0;$i<count($array);$i++) {
$sum += (int) $array[$i];
}
return ( ( $n*($n+1) / 2 ) - $sum );
} // executes in O(N). thanks, Fermat!
/**
* Write me a procedure that finds the first two numbers that add up to n in an array
* ex. give [1,3,5,11,2,2,8], what are the first two integers that add up to 10?
**/
function addedPair($array,$total) {
$ints=array();
for($i=0; $i < count($array); $i++ ) {
$x= (int) $array[$i];
$y = $total-$x;
$ints[$x]=$y;
if($ints[$y]) {
echo "$x and $y add up to $total";
return;
}
}
echo "no results";
return;
} // executes in O(N)
/**
* Write me a procedure that gives me the first non-repeating letter in a string
**/
function noRepeat($str) {
$c=array();
for($i=0;$i<strlen($str);$i++) {
if(! $c[$str[$i]] ) {
$c[$str[$i]] = 1;
continue;
}
$c[$str[$i]] = 2;
}
foreach($c as $let=>$cnt ) {
if($cnt == 1) return( $let );
}
return(false);
}
// executes in O(N), since either a) no repeated letters, so immediate return or
// b) all repeated letters, so returns in strlen($str) / 2
?>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment