Interview question for PHP developers

interview.php

<?php
/*
  Objectives:
    - Create PHP script that will translate input data to expected output from example below.
    - Calculate time complexity of your script
    bonus: Implement solution that will not use pass-by-reference and will not use objects
*/

$input = [
    'A' => 1,
    'B_C' => 2,
    'B_D' => 3,
    'E_F_G' => 4,
    'E_H' => 5
];

$expectedOutput = [
    'A' => 1,
    'B' => [
        'C' => 2,
        'D' => 3
    ],
    'E' => [
        'F' => [
            'G' => 4
        ],
        'H' => 5
    ]
];

$tmp = [];
foreach ($input as $k => $v) {
    foreach (array_reverse(explode('_', $k)) as $k) {
        $v = [$k => $v];
    }
    $tmp[] = $v;
}
$output = call_user_func_array('array_merge_recursive', $tmp);

$output = [];

function parseEl($k, $v) {
    return [$k[0] => isset($k[2]) ? parseEl(substr($k, 2), $v) : $v];
}

foreach ($input as $k => $v) {
    $output = array_merge_recursive($output, parseEl($k, $v));
}

foreach($input as $k => $v)
    eval("\$output['".str_replace('_',"']['",$k)."']=$v;");

OK, didn't want to post it here initially, but for the record ;)

https://gist.github.com/foglcz/07ce7e1a1c29bcf28bf6