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.