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
    ]
];

This seems longer than it should need to be:

function idx(array $array, $key, $default = null) {
  return (array_key_exists($key, $array) ? $array[$key] : $default);
}

function addKeysToOutput(array $output, array $keys, $value) {
  $key = array_shift($keys);
  $output[$key] = ($keys
    ? addKeysToOutput(idx($output, $key, array()), $keys, $value)
    : $value);
  return $output;
}

$output = array();
foreach ($input as $key => $value) {
  $output = addKeysToOutput($output, explode("_", $key), $value);
}

$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