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.
very good written article. It will be a good support to anyone who utilizes it including me. Keep doing what you are doing can’t wait to read more posts very nice article