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!
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