Wildcard challenge (Desafio wildcard)

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.

Publicado por

Daniel Satiro

Tecnólogo em Sistemas para Internet pela Faculdade Sumaré, Bacharel em Sistemas de Informação pela Universidade São Judas Tadeu e Pós-graduado e Gestão de Tecnologia da Informação pela Faculdade de Informática e Administração Paulista. Atuo como analista e desenvolvedor de sistemas web desde 2007.

Deixe uma resposta

Esse site utiliza o Akismet para reduzir spam. Aprenda como seus dados de comentários são processados.