Some answers to some interview questions I've had

interview-questions.php

<?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 
?>