1

I did a training exercise (ranked as easy), and the question is here, and my answer in PHP below.

function solution($X, $A) {
    // write your code in PHP7.0

    $inplace = []; # positions in place to our goal, space O(X). Index by position number 0..$X

    foreach ($A as $k => $pos) {
        # time O(N) - array of N integers   

        if ($pos <= $X) { # we are only interested in positions within $X
            # count positions - but store the first $k key seconds which this position is reached. 
            # We are not interested in when the second leaf of this same position falls. 
            if (!isset($inplace[$pos]))  $inplace[$pos] = $k;
        }
    }

    $maxk = -1; # max key value which is the longest time for the needed leaf to fall
    for ($i=1; $i <= $X; $i++) {
        # go through every position   
        if (isset($inplace[$i])) {
            $tempk = $inplace[$i]; //k seconds for this leaf to fall
            $maxk = ($tempk > $maxk) ? $tempk : $maxk;
        }
        else return -1; # if this position is not set, the leaf does not fall, so we exit
    }

    return $maxk;
}

My questions:

1) Is there a better way you would write the code? I'm focusing on time complexity and simplicity of code, so any feedback is welcome.

2) In this training material - an example if given in Python for def counting(A, m) to count instances of an array. I used this concept in my solution, in PHP, where the index of the array was the value. In PHP, is there a way to instantiate an array as done in Python? I imagine in PHP, I'd use isset() in my code when processing the array count result, without actually instantiating a whole array of (m+1) elements, or is there actually a way to get the below line working in PHP?

count = [0] * (m + 1) # Python code for list (array) instantiation of (m+1) elements. 
# How do we do this in PHP?

Thanks very much!

rishijd
  • 1,294
  • 4
  • 15
  • 32

1 Answers1

1

1) A simpler and more efficent way to write this function would be using one for loop and a counter. Just loop over 1 - $X, and track the position of the items with array_search. 

function solution($X, $A){
    $p = 0;
    for($i=1; $i<=$X; $i++) {
        $k = array_search($i, $A);
        if($k === false) 
            return -1;
        if($k > $p) 
            $p = $k;
    }
    return $p;
}

Even though array_search is slower than isset this solution is much faster (with the given parameters) and it doesn't create an extra array for mapping the leaf positions.

2) Python has great tools for working with lists (concatenation, repetition, comprehensions, etc) which are not avaliable in PHP and other languages.
But you can achieve something similar with array_fill, ie: $count = array_fill(0, $m+1, 0);

The above function 'translated' to python would be: 

def solution(X, A):
    p = 0
    for i in range(1, X+1):
        if i not in A:
            return -1
        v = A.index(i)
        if v > p:
            p = v
    return p
t.m.adam
  • 15,106
  • 3
  • 32
  • 52
  • Thanks so much! Very useful and certainly much simpler. Question though on big-O time complexity for part 1. The function I wrote is believe O(2N) which is O(N). Given that your function has array_search within the for loop, and I believe array_search has O(N) complexity, what is the overall time complexity of the function? – rishijd Nov 20 '17 at 13:33
  • Well, it should be O(n²) right? However i run some tests (function a x 1000000 times, function b x 1000000 times). With `$a = array(1,3,1,4,2,3,5,4)` the resuults were 3 sec (my version) - 5 sec (original). With larger arrays the time for my solution remains about 3 sec, while the time for the original solution is ascending. – t.m.adam Nov 20 '17 at 13:49
  • I think the key here is `$X`. For values < 20 my solution is faster, but for values > 20 your solution is faster. I beleve it's about `array_search` vs `isset`, but i don't have enough knowledge on PHP internals to provide a proper explanation. – t.m.adam Nov 20 '17 at 15:17
  • Thanks very much for all the detail! Understood and much appreciated. Could you share what tool you used to get benchmarks? Or did you measure the time manually through the PHP script? – rishijd Nov 20 '17 at 17:59
  • FYI I found the Python solution online, https://www.martinkysel.com/codility-frogriverone-solution/ – rishijd Nov 20 '17 at 18:11
  • 1
    I just wrote a `function timer($f, $x, $a, $r=1000000)` using `microtime` and a loop, but for larger functions/scripts i would use a real tool (see [how-to-benchmark-efficiency-of-php-script](https://stackoverflow.com/questions/8291366/how-to-benchmark-efficiency-of-php-script)). – t.m.adam Nov 21 '17 at 02:27
  • In the link you provided the first python solution is a bit complicated and i think it should return -1 instead of raising an exception. The 2nd python solution looks better, but unfortunately is not accurate. I've updated my post with a python version of my php solution. – t.m.adam Nov 21 '17 at 03:24