user3642365 user3642365 - 4 months ago 9
PHP Question

Check if two arrays are "almost equal" (one can be transformed to the other)

I had an interview problem that I couldn't get and I thought this would be the right place to ask.

The premise of the problem is checking if two arrays are "just about equal".

Background:



You are given two arrays A and B, with
count(B) >= count(A)
. The elements in A and B are strings containing alphabetical characters and possibly ONE SET curly brackets.

Example:



A = {'Hello', 'World', 'This is {cool}'}
B = {'Hello', 'World', 'This is {cool}', '{This is cool}'}


Something like
'{This is {cool}}
would never show up since it has two sets of braces.

Arrays A and B are said to be "just about equal" if:


  • B contains every element in A

  • Every element in B that is not in A can be obtained by either applying curly brackets to an element in A (
    Hello => {Hello}
    ) or by moving the curly brackets within an element in A to the outside of the element (
    This is {cool} => {This is cool}
    )




Write a function to determine if two arrays A and B are "just about equal". Focus on efficiency.


My naive solution:



I wrote a function to remove an element from A, check to see if that element appeared in B, and if any "permutation" of that element appeared in B. If so, remove them from B. At the end I returned true if both A and B were empty. I was wondering if there was a more efficient solution.

Answer

B contains every element in A

This can be achieved using array_diff:

if (array_diff($a, $b) == array()) {
    // Check #1: pass
}

From the manual:

Compares array1 against one or more other arrays and returns the values in array1 that are not present in any of the other arrays.

Therefore, if there are values in $a that are not present in $b then the check above will return false


Every element in B that is not in A can be obtained by either applying curly brackets to an element in A (Hello => {Hello}) or by moving the curly brackets within an element in A to the outside of the element (This is {cool} => {This is cool})

I'd hoped this could be achieved by comparing the two arrays with the brackets removed entirely, but the rule or by moving the curly brackets within an element in A to the outside of the element suggests that if it were around one of the other words it should fail.

This isn't the case, but you can still remove the braces and put them back in at the edges of each string for comparison:

/**
 * Remove any braces in the value and put them back in at the edges of the string
 * @param  string $value
 * @return string
 */
function addOrMoveBraces($value)
{
    return sprintf('{%s}', str_replace(['{', '}'], '', $value));;
}

$aWithBraces = array_map('addOrMoveBraces', $a);
$bWithBraces = array_map('addOrMoveBraces', $b);

if (array_diff($bWithBraces, $aWithBraces) == array()) {
    // Check #2: pass
}

Put it together

You need a function, so you could do this:

/**
 * Remove any braces in the value and put them back in at the edges of the string
 * @param  string $value
 * @return string
 */
function addOrMoveBraces($value)
{
    return sprintf('{%s}', str_replace(['{', '}'], '', $value));;
}

function justAboutEqual($a, $b)
{
    // Check #1
    if (array_diff($a, $b) == array()) {
        return true;
    }

    // Check #2
    if (array_diff(array_map('addOrMoveBraces', $b), array_map('addOrMoveBraces', $a)) == array()) {
        return true;
    }

    return false;
}

Here's a couple of simple unit tests against these functions.