Задача №1: сложение массивов

Мы хотим складывать очень большие числа, которые превышают емкость базовых типов, поэтому мы храним их в виде массива неотрицательных чисел.

Нужно написать функцию, которая примет на вход два таких массива, вычислит сумму чисел, представленных массивами, и вернет результат в виде такого же массива.

Пример

ввод

arr1 = [1, 2, 3] # число 123
arr2 = [4, 5, 6] # число 456

вывод

res = [5, 7, 9] # число 579 (допустим ответ с первым незначимым нулем [0, 5, 7, 9])

Решение

<?php

/**
 * Calc arrays sum
 * @param array $a
 * @param array $b
 * @return array
 */
function calcSum(array $a, array $b): array
{
    $res = [];
    $ost = 0;
    while (count($a) > 0 || count($b) > 0) {
        if (count($a)) {
            $digitA = array_pop($a);
        } else {
            $digitA = 0;
        }

        if (count($b)) {
            $digitB = array_pop($b);
        } else {
            $digitB = 0;
        }

        $sum = $digitA + $digitB + $ost;
        $digit = $sum % 10;
        $res[] = $digit;
        $ost = floor($sum / 10);
    }

    if ($ost > 0) {
        $res[] = $ost;
    }

    $res = array_reverse($res);     // 71 ==> 17

    return $res;
}

/////////////////////////////////////////

$a = [1];     # число 1
$b = [2];     # число 2
$res = calcSum($a, $b);
var_dump($res);     // [3] # число 3

echo "n";

$a = [1, 2, 3];     # число 123
$b = [4, 5, 6];     # число 456
$res = calcSum($a, $b);
var_dump($res);     // [5, 7, 9] # число 579 (допустим ответ с первым незначимым нулем [0, 5, 7, 9])

echo "n";

$a = [2, 9, 2, 3];     # число 2923
$b = [7, 5, 6];     # число 756
$res = calcSum($a, $b);
var_dump($res);     // [3, 6, 7, 9] # число 3679

Оценка сложности:

• алгоритм — О(n)

• по памяти О(n)

Задача №2: самые популярные элементы массива

Дан массив целых чисел nums и целое число k.

Нужно написать функцию на PHP, которая вынимает из массива k наиболее часто встречающихся элементов.

Пример

ввод

nums = [1,1,1,2,2,3]
k = 2

вывод (в любом порядке)

[1, 2]

Решение #1 (рабочее, но не оптимальное)

Вот функция на PHP для выбора k наиболее часто встречающихся элементов из массива:

<?php

/**
 * AvitoTech task #2: Frequent numbers
 * (not optimal solution, see optimal in freq_nums2.php)
 *
 * Дан массив целых чисел nums и целое число k.
 * Нужно написать функцию на PHP, которая вынимает из массива k наиболее часто встречающихся элементов.
 */

function topKFrequent222($nums, $k) {
    $freq = [];

    foreach ($nums as $num) {
        $freq[$num] = isset($freq[$num]) ? $freq[$num] + 1 : 1;
    }

    arsort($freq);

    $result = array_slice(array_keys($freq), 0, $k);

    return $result;
}

/**
 * Get frequent numbers
 * @param array $arr
 * @param int $limit
 * @return array
 */
function getMaxFreqNums(array $arr, int $limit): array
{
    $freqArr = [];

    foreach ($arr as $num) {
        if (isset($freqArr[$num])) {
            $freqArr[$num] += 1;
        } else {
            $freqArr[$num] = 1;
        }
    }

    arsort($freqArr);

    $res = array_slice(array_keys($freqArr), 0, $limit);

    return $res;
}

var_dump(getMaxFreqNums([1,1,1,2,2,3,3,3,3,3], 2));     // [3, 1]

Как это работает:

• Подсчитываем частоту каждого элемента в массиве

• Сортируем массив частот по убыванию

• Берем первые k ключи (элементы) из отсортированного массива

Это решение не оптимально, т.к. алг. сложность — O(Nlog(n)) из-за функции сортировки:

Функция arsort в PHP сортирует массив по значению в обратном порядке (от большего к меньшему). Алгоритмическая сложность функции arsort: O(N log N), где N — размер сортируемого массива.

Как решить задачу со временем O(N)? Смотрим решение №2.

Решение #2 (оптимизированное)

Здесь вместо сортировки строим хеш-массив вида:

[<частота> => <элементы>]

Т.о., пробегаясь по его элементам (от старшего элемента вниз), получим элементы исходного массива с максимальными частотами.

<?php

/**
 * AvitoTech task #2: Frequent numbers
 * (optimized solution)
 *
 * Дан массив целых чисел nums и целое число k.
 * Нужно написать функцию на PHP, которая вынимает из массива k наиболее часто встречающихся элементов.
 */

/**
 * Get frequent numbers
 * @param array $freqs
 * @param int $limit
 * @return array
 */
function getMaxFreqNums(array $freqs, int $limit): array
{
    $freqArr = [];

    if(!is_array($freqs) || !count($freqs)) {
        return [];
    }

    // [num => frequence]
    foreach ($freqs as $num) {
        if (isset($freqArr[$num])) {                // [1 => 3, 2 => 2, 3 => 4, 4 => 4, 1 => 5]
            $freqArr[$num] += 1;
        } else {
            $freqArr[$num] = 1;
        }
    }

    // [frequence => <nums_array>]
    $tmpArr = [];
    foreach ($freqArr as $num => $freq) {
        $tmpArr[$freq][] = $num;                    // [1 => [5], 2 => [2], 3 => [1], 4 => [3, 4]]
    }

    $freqArr = $tmpArr;

    // count result as slice of $maxArr
    $res = [];

    $freqArrKeys = array_keys($freqArr);
    $maxKey = max($freqArrKeys);

    for ($i = $maxKey; $i >= 0; $i--) {
        $freqs = (isset($freqArr[$i]) ? $freqArr[$i] : []);
        foreach ($freqs as $elem) {
            $res[] = $elem;
            if (count($res) >= $limit) {
                return $res;
            }
        }
    }

    return $res;
}

////////////////////////////////////

echo "n";
var_dump(getMaxFreqNums([], 2));     // []

echo "n";
var_dump(getMaxFreqNums([1], 1));     // [1]

echo "n";
var_dump(getMaxFreqNums([1,1,1,2,2,3,3,3,3,3,3,4,4,4,4,4,5], 2));     // [3, 4]