Showing posts with label algorithm. Show all posts
Showing posts with label algorithm. Show all posts

Wednesday, August 24, 2011

shift array elements to the right in PHP

Another algorithm related question for C/C++ devs. It is always interesting to see how to solve it in PHP.

The question is: implement a function to shift $k array elements to the right. Time complexity must <= O(n)
For example, we have an array $a = array('a', 'b', 'c', 'd', 'e'), a function rightShift($array, $k), and if we call rightShift($a, 2), the return result must be array('c', 'd', 'e', 'a', 'b'). 'a' and 'b' have been shifted to the right of the array.

It is quite simple in PHP, with PHP's array functions.

function rightShift($array, $k)
{
                for($i=0; $i<$k; $i++) {
                                $temp = array_shift($array);
                                array_push($array, $temp);
                }
                return $array;
}

Even without using PHP array function, it is still simple:

function rightShift($array, $k)
{
                for($i=0; $i<$k; $i++) {
                                $temp = $array[$i];
                                unset($array[$i]);
                                $array[] = $temp;
                }
                return $array;
}

The function works and the complexity is O(n), so it meets the requirement.

But there is a flaw with the rightShift function and that is always easy for people to neglect. We don't carefully consider the value of $k. If $k <= 0, that is fine, the array keeps same. But what if $k > count($array)? We tend to assume $k < count($array) so in the function we don't do anything about it. Actually, $k could be much bigger than count($array). The function still works when $k > count($array), but obviously, it is not efficient.

So let's consider when $k > count($array). In this example, if $k = 8, what the result should be? It should be array('d', 'e', 'a', 'b', 'c'). We can find that we don't really need to shift $k times, we only need to shift $k % count($array) times. So, let's change our code:

function rightShift($array, $k)
{
                $k = $k % count($array);
                for($i=0; $i<$k; $i++) {
                                $temp = $array[$i];
                                unset($array[$i]);
                                $array[] = $temp;
                }
                return $array;
}

This will actually introduce another issue: what if count($array) === 0? So, we need to check this:

function rightShift($array, $k)
{
                $total = count($array);
                if ($total === 0) {
                                return false;
      }
                $k = $k % $total;
                for($i=0; $i<$k; $i++) {
                                $temp = $array[$i];
                                unset($array[$i]);
                                $array[] = $temp;
                }
                return $array;
}

Tuesday, August 23, 2011

find the only duplicate number in an array

Another interesting algorithm question. The question is this: we have an array $numbers with 1001 numbers as elements, all these numbers are between [1, 1000], including 1 and 1000. Now we know there is only one number appears twice in this array, and we need to find out what this number is (We are not allowed to modify $numbers).

So the array is like $numbers = array(1,2,3...,1000); count($numbers) = 1001; find out the only number that appears twice. The code to generate this $numbers array is below:

<?php
$limit          = 1000;
$numbers        = array();
//randomly generate duplicate number
$duplicate      = mt_rand(1, $limit);
//randomly generate the position of the duplicate number
$randomPosition = mt_rand(0, $limit-1);

for($i = 0; $i < $limit; $i++) {
    $numbers[] = $i + 1;
    if ($i === $randomPosition) {
        $numbers[] = $duplicate;
    }
}

To see what $numbers array is like, we can change the $limit = 10 to make it easier.

I guess this is supposed to be an interview question for C/C++ devs. When it comes to PHP, well, we know PHP provides the most powerful array functions among all these programming languages.

So, first, see how can we do it quickly with help of PHP array functions.

$unique = array_unique($numbers);
$diff = array_diff_key($numbers, $unique);
echo $numbers[$diff];

If we don't consider what array_unique and array_diff_key really do in the background, simply from the standpoint of PHP, we need constant steps(3 steps) to get it done. So the time complexity looks like O(1), although this is really misleading.

What if we are not allowed to use any special PHP array functions?

1. Use a temporary storage

$temp = array();
for($i=0; $i<=$limit; $i++) {
                $value = $numbers[$i];
                if (isset($temp[$value])) {
                                //we find it!
                                echo $value;
                                break;
                }
                $temp[$value] = $value;
}

In this way, the worst case of time complexity is O(n). But the worst case of space complexity is O(n) as well. That means this algorithm may cost a lot of memories (we need another array as a temporary storage).

2. Another idea is, we can get the sum of 1 - 1000, say $s1; get the sum of numbers in $numbers array, say $s2; the duplicate number must be $s2 - $s1. Since 1 - 1000 is an arithmetic sequence (http://en.wikipedia.org/wiki/Arithmetic_series), we have a formula to get its sum easily.

$s1 = ($limit + 1) * $limit / 2;
$s2 = 0;
for($i=0; $i<=$limit; $i++) {
            $s2 += $numbers[$i];
}
echo $s2 - $s1;

For $s2, as i said, not allowed to use special PHP array functions, so array_sum() is not allowed here.
The time complexity is always O(n) in this way. So it is not as fast as the first one. However, the space complexity is O(1), actually, nearly to none. We don't need too much extra space to get the task done.

Sunday, July 3, 2011

how to check if a number is prime - a step by step way to problem analysis and solving

Suppose we don't know the most efficient algorithm to check if a number is prime or not and we are being asked with this question in an interview. How can we solve this problem? 

Based on the definition of prime number, we can simply do this(i ignore the special case when $n === 2 or $n === 1):

function isPrime($n)
{
    for($i=2; $i<$n; $i++) {
        if($n % $i === 0) {
            return false;
        }
    }
    return true;
}

Obviously, this is not efficient, but at least we can solve the problem and give the correct result. I think this is the first step to problem analysis and solving.

Now, we can try to optimize the function. Let's suppose $n is not a prime number, which means it can be divided by two numbers other than 1 and itself. So we have $n = $x * $y. We can find out we definitely should have $x >= 2, and we can have $n / 2 >= $y. So we can change our function:

function isPrime($n)
{
    $end = $n / 2;
    for($i=2; $i<=$end; $i++) {
        if($n % $i === 0) {
            return false;
        }
    }
    return true;
}

Cool, it is obviously more efficient than the first one. Now, let's see if we can improve a bit more. Think of $n = $x * $y again. We obviously can have $x >= $y(or $y >= $x, it doesn't matter). So we can have $n >= $y ^ 2. We can change our function again:

function isPrime($n)
{
    $end = sqrt($n);
    for($i=2; $i<=$end; $i++) {
        if($n % $i === 0) {
            return false;
        }
    }
    return true;
}

I think this answer could be enough for those who just want to see if you can analyze and solve a problem logically instead of testing your math knowledge.

Friday, May 13, 2011

generate combinations of elements from multiple arrays

Problem: we have multiple arrays, and we must find all combinations of the elements of these arrays. For example, if we have two array:

$option1 = array('apple', 'orange', 'pear');
$option2 = array('rice', 'noodle');

And we must find all combinations(there are 6 of them in this example) of these two array elements:

'apple', 'rice',
'apple', 'noodle',
'orange', 'rice',
'orange', 'noodle',
'pear', 'rice',
'pear', 'noodle'

First, let's see how to implement the algorithm in PHP:

//$allOptionsArray is an array containing all options array
//$final is a stdClass
function getCombinations($allOptionsArray, $final) {
    if(count($allOptionsArray)) {
        for($i=0; $i < count($allOptionsArray[0]); $i++) {
            $tmp = $allOptionsArray;
            $final->codes[$final->pos] = $allOptionsArray[0][$i];
            array_shift($tmp);
            $final->pos++;
            getCombinations($tmp, $final);
        }
    } else {
        $final->result[] = $final->codes;
    }
    $final->pos--;
}
//let's see how to use the function:
$option1 = array('apple', 'orange', 'pear');
$option2 = array('rice', 'noodle');
$allOptionsArray = array($option1, $option2);
$final = new stdClass();
$final->result = array();
$final->codes  = array();
$final->pos    = 0;
getCombinations($allOptionsArray, $final);
//$final->result is an array containing all possible combinations
var_dump($final->result);

We can easily implement same algorithm in javascript:

var getCombinations = function(allOptionsArray, combination) {
    if(allOptionsArray.length > 0) {
        for(var i=0; i < allOptionsArray[0].length; i++) {
            var tmp = allOptionsArray.slice(0);
            combination.codes[combination.counter] = allOptionsArray[0][i];
            tmp.shift();
            combination.counter++;
            getCombinations(tmp, combination);
        }
    } else {
        var combi = combination.codes.slice(0);
        combination.result.push(combi);
    }
    combination.counter--;
}

//use it:
var a = ["01", "02", "03", "04"];
var b = ["white", "green", "blue", "red"];
var c = ["one", "two", "three", "four"];
var d = ["a", "b", "c", "d"];

var allOptionsArray = [a, b, c, d];
var combination = {codes : [], result : [], counter : 0};

getCombinations(allOptionsArray, combination);

for(var i=0; i < combination.result.length; i++) {
    console.log(combination.result[i]);
}