ParentAps Offline Tasks

balanced-string.php

<?php
function checkIfBalanced($string)
{
    $stack = [];
    $matches = ["(" => ")", "{" => "}", "[" => "]"];
    for ($i = 0; $i < strlen($string); $i++) {
        $currentChar = $string[$i];
        //balanced not start with a closure before start
        if (!count($stack) && in_array($currentChar, array_values($matches)))
            return false;
        //push start to stack
        if (in_array($currentChar, array_keys($matches)))
            array_push($stack, $currentChar);
    }
    for ($i = 0; $i < strlen($string); $i++) {
        $currentChar = $string[$i];
        if (in_array($currentChar, array_values($matches))) {
            if (!count($stack))
                return false;
            if ($currentChar !== $matches[array_pop($stack)])
                return false;

        }
    }
    if (count($stack))
        return false;

    return true;
}

$tests = [
    '[ 2( { hello } x ) u ]',
    '[ 2( { hello } x )) u ]',
    '[ 2( { hello } x ) u ]]',
    '[ (y { world ) } x ]',
    '[ (y { world ) } x2 ]]',

];

foreach ($tests as $test) {
    echo $test . ' => ' . (checkIfBalanced($test) ? 'Balanced' : 'Not balanced') . PHP_EOL.'</br>';
}

missing_number.php

<?php

/**
 * Find Missing Number Using Arithmetic Progression
 *
 * @param array $arr
 *
 * @return int
 *
 * get total using arithmetic progression formula
 * (0.5 * ( $n+1 )) * (2 * $a + n)
 * get actual sum using array_sum
 * return total - actual
 *
 */
function findMissingNumberUsingArithmeticProgression($arr)
{
    $firstElement = min($arr); //a
    $lastElement = max($arr);
    $elementCount = $lastElement - $firstElement; //n

    //Get The Total form start and count
    $arithmetic_sum = (0.5 * ($elementCount + 1)) * (2 * $firstElement + $elementCount);

    //Get the actual total from presented array
    $actual_sum = array_sum($arr);

    return $arithmetic_sum - $actual_sum;
}

/**
 * Find Missing number using a for loop and in_array
 *
 * @param $arr
 * @return bool|mixed
 */
function findMissingNumberUsingLoop($arr)
{
    $firstElement = min($arr); //a
    $lastElement = max($arr);

    for ($i = $firstElement; $i < $lastElement; $i++) {
        if (!in_array($i, $arr))
            return $i;
    }
    return false;
}

/**
 * Find Missing Number Using array_diff
 * @param $arr
 * @return mixed
 */
function findMissingNumberUsingArrayDiff($arr)
{
    $firstElement = min($arr); //a
    $lastElement = max($arr);

    $fullArray = range($firstElement, $lastElement);

    return array_values(array_diff($fullArray, $arr))[0];
}


function benchmark($solutions, $input)
{
    $results = [];
    $i = 0;
    foreach ($solutions as $name => $method) {
        $start = microtime(true);
        $result = $method($input);
        $execution_time = microtime(true) - $start;

        $results[$i]['execution_time'] = $execution_time;
        $results[$i]['name'] = $name;
        $results[$i]['result'] = $result;
        $i++;
    }
    return $results;
}


#Bootstrapping Task
$line_separator = (php_sapi_name() === 'cli') ? PHP_EOL : '<br>';
$arrayOfNumbers = range(300, 10000);
$randIndex = rand(300, 10000);
$knownMissing = $arrayOfNumbers[$randIndex];
unset($arrayOfNumbers[$randIndex]);
#End Bootstrapping


echo "known correct answer is " . $knownMissing . $line_separator;

$results = benchmark([
    'Arithmetic' => 'findMissingNumberUsingArithmeticProgression',
    'Loop Iteration' => 'findMissingNumberUsingLoop',
    'array_diff' => 'findMissingNumberUsingArrayDiff',

], $arrayOfNumbers);


foreach ($results as $result) {
    printf(
        '%s solution resulted %s and took %s microseconds' . $line_separator,
        $result['name'], $result['result'], number_format($result['execution_time'], 5)
    );
}

In missing number I build 3 implementations and the best on in performance is Arithmetic Progression
in this gist you find all 3 implementations and tiny benchmarking method for all of them