Daniel Satiro

Em julho de 2011, fiz uma entrevista em uma empresa na qual foi-me solicitado a resolução de um teste, para ser feito em casa e enviado via e-mail, resolvi em 3 dias, após meu horário de trabalho e usando a análise combinatória na solução, fui aprovado, porém infelizmente cancelaram a contratação.

Na época existia apenas uma solução pronta do teste na internet para exemplo e usando binários na sua resolução.

Achei o teste interessante e com um bom nível de complexidade, pois não basta saber apenas PHP, mas também um pouco de estatística e análise combinatória, por isso estou compartilhando a minha solução.

Enunciado do teste

Escrever um algoritmo, em PHP, que tenha como entrada uma string composta por palavras separadas por pipe (|) e  a saída seja uma sequência com todos os wildcards possíveis.

Exemplo 1:

Entrada: “sao-paulo”

Saída:       *

Exemplo 2:

Entrada: “sao-paulo|restaurante”

Saída:

sao-paulo|*

*|restaurante

Exemplo 3:

Entrada: “a|b|c”

Saída:

*|b|c

a|*|c

a|b|*

a|*|*

*|b|*

*|*|c

Solução

<?php
/**
 * @author Daniel Satiro da Rocha
 * Teste - 15/07/2011
 */

/**
 * retorna combinacoes sem repeticao
 * @param array $elementos
 * @param int $s
 * @return Ambigous <multitype:, string>
 */
function combinacoes($elementos = array(), $s) {
	$combinArr = array ();
	$combin = ( int ) sprintf ( "1%0{$s}d", 0 ) - 1;
	for($cur = 0; $cur <= $combin; $cur ++) {
		$number = sprintf ( "%0{$s}d", $cur );
		$equal_digits = array ();
		for($digit = 0; $digit < $s; $digit ++) {
			if (in_array ( $number {$digit}, $elementos ) && ! in_array ( $number {$digit}, $equal_digits )) {
				$equal_digits [] = $number {$digit};
			}
		}
		if (count ( $equal_digits ) == $s) {
			$numArr = array();
			for ($i = 0; $i < strlen($number); $i++) {
				$numArr[] = $number[$i];
			}
			sort($numArr);
			$combinArr [] = implode($numArr);
		}
	}
	$combinArr = array_unique($combinArr);
	$elemComb = array();
	foreach ($combinArr as $value) {
		$numArr = array();
		for ($i = 0; $i < strlen($value); $i++) {
			$numArr[] = $value[$i];
		}
		$elemComb[] = $numArr;
	}
		return $elemComb;
}

/**
 * calcula fatorial
 * @param int $valor
 * @return number|Ambigous <unknown, number>
 */
function fatorial($valor) {
	if ($valor == 0) {
		return 1;
	}
	$result = $valor;
	for ($index = $valor-1; $index > 1; $index--) {
		$result *= $index;
	}
	return $result;
}

/**
 * Calcula quantidade de combinacoes possiveis sem repeticao
 * Onde $n é o total de elementos e $s o número de elementos escolhidos.
 * @param int $n
 * @param int $s
 * @return number
 */
function combinatoria($n, $s){
	$c = fatorial($n)/(fatorial($s)*fatorial($n-$s));
	return $c;
}
/**
 * Calcula arranjo simples
 * Onde $n é o total de elementos e $s o número de elementos escolhidos.
 * @param int $n
 * @param int $s
 * @return number
 */
function arranjos($n, $s) {
	$a = fatorial($n)/fatorial($n-$s);
	return $a;
}
/**
 * Executa calculos conforme entrada e retorna as combinacoes
 * @param string $entrada
 * @return string|string
 */
function processaSaida($entrada) {
	$entArray = explode ( '|', $entrada );
	$n = count ( $entArray );
	if ($n == 1) {
		return '*';
	} else {

		$linhas = array ();
		$html = "";
		for($s = 1; $s < $n; $s ++) {
			$combin = combinatoria ( $n, $s );
			$combArr = combinacoes ( range ( 0, $n - 1 ), $s );
			for($c = 0; $c < $combin; $c ++) {
				$aux = array ();
				$d = 0;
				for($index = 0; $index < $n; $index ++) {
					if ($combArr [$c] [$d] == $index) {
						$aux [$index] = "*";
						$d ++;
					} else {
						$aux [$index] = $entArray [$index];
					}
				}
				$linhas [] = $aux;
			}
		}

		$html = "";
		foreach ( $linhas as $key => $value ) {
			$html .= implode ( '|', $value ) . "<br />";
		}
		return $html;
	}
}
$saida = "Nenhuma saida processada!";
if($_POST){
	$entrada = trim($_POST['entrada']);
	$saida = processaSaida($entrada);
}
?>
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<title>Teste Wildcard challenge</title>
</head>
<body>
<center>
<form action="<?php echo $_SERVER['PHP_SELF'];?>" method="post">
<table border="0">
	<tr valign="top">
		<td>Entrada:</td>
		<td><input type="text" name="entrada"
			value="<?php echo $_POST['entrada'];?>" /></td>
		<td><input type="submit" value="Enviar" /></td>
	</tr>
	<tr>
		<td>Saída:</td>
		<td colspan="2"><?php echo $saida;?></td>
	</tr>
</table>
</form>
</center>
</body>
</html>

É isso aí, não sei se a empresa ainda usa esse teste para avaliar seus candidatos, mas se ainda utilizar acho que ficará mais difícil para os próximos candidatos encontrar outra solução.