CODEWITHSUNDEEP
phpperformancealgorithmhashcompare
user2308097
user2308097

Reputation:

String Comparison Using Hash

So I just came out of an otherwise excellent interview where I happened to have dropped the ball towards the end. The test I was given involved solving a simple CS question.

You have two stings $a = 'abcd'; $b = 'cdfg';

Using the most efficient method possible I was asked to compare these two strings and return any matching characters. At the time, the most obvious (and least efficient) solution was as follows.

`

$matches = array();
$length = strlen($a);
for($i = 0; $i < $length; $i++) {
    if(strpos($b, $a[$i]) !== false) {
        $matches[] = $a[$i];
    }
}

return $matches;

I was informed that correct and most efficient solution required the use of hashes.
Could someone please elaborate?

edit:

The return value in this example should be "cd".

I was told that using PHP methods such as "array_intersect" would be considered cheating.

Upvotes: 0

Views: 205

Answers (1)

candu
candu

Reputation: 2883

Your solution is O(strlen($a) * strlen($b)), as strpos() may have to search all of $b in order to find a specific character. By "hashing", I assume they mean "storing the characters of $a in a hashtable":

$a_hash = array();
$length = strlen($a);
for ($i = 0; $i < $length; $i++) {
    $a_hash[$a[$i]] = true;
}
$matches = array();
$length = strlen($b);
for ($i = 0; $i < $length; $i++) {
   if (array_key_exists($a_hash, $b[$i])) {
       $matches[] = $b[$i];
   }
}
return $matches;

Assuming that the hashtable operations (using PHP's infamous array()) are constant-time, this is now O(strlen($a) + strlen($b)).

Upvotes: 1

Related Questions