Собеседования по алгоритмам: максимальная конкатенация

Сопоставить каждой плашке число, равное написанному на нем, деленному на 10^n-1 где n - длина числа. Отсортировать по нему по убыванию. Профит

Посортировать в обратном алфавитном порядке как строки. Слишком много подсказок про строки и сортировку в одну строку.

Number([4, 42, 46, 427, 465].map(String).sort().reverse().join``)

Upd: Вижу, что не решение.

%w(4 42 46 427 465).sort { |a, b| (b + a) <=> (a + b) }.join

Нужна немного необычная сортировка. Функция сравнения двух чисел для сортировки: сравниваем символы по порядку, если у какого-то числа символы закончились - используем его первый символ.

Тогда пример с 6, 61 и 69 нормально сработает, т.к. для сортировки будут использованы числа 66, 61, 69

Упд:

Или даже еще понятнее. Для сравнения двух чисел конкатенуем их сначала в одном порядке, затем в другом и выбираем тот, где получится больший результат.

Все числа начинаются с 4, значит размещать надо с тех, которые имеют и дадут в весомых разрядах (в левых позициях числа) наибольшие цифры, то-есть так: 465 46 4 427 42 . Формул тут не надо, достаточно элементарного парсера. Вроде так. Решается за один проход. Минус не ставлю, так как задачка для новичков вполне годная. Минус поставил не я.

<?php

$arr = [4, 42, 46, 427, 465];

usort($arr, function($a, $b) { 
    return -($a .$b <=> $b.$a);
});

echo implode($arr);

С первого раза не получилось(

Всё это прекрасно, но причём тут собеседования? Оставьте спортивное программирование внутри рамок спорта, энтертэйнмента и прочего досуга "на любителя". К реальной работе всё это не имеет никакого отношения.

''.join(sorted(map(str, num_list), key=str, reverse=True))

если в списке будут числа ровно из одной цифры то работать не будет, печально

Про сортировку уже успели написать, предложу другой более наглядный, но медленный алгоритм.

Давайте составлять ответ итеративно, пусть мы каким то образом получили ответ используя первые i чисел, теперь хотим понять как изменится ответ если будем использовать i + 1 чисел. Для этого достаточно перебрать все возможные позиции вставки i + 1 числа и выбрать ту что дает максимум.

Вот мое решение для задачи https://leetcode.com/problems/largest-number/description/

string largestNumber(vector<int>& nums) {
    vector<string> order;
    for (int i = 0; i < nums.size(); ++i) {
        int insert_pos = 0;
        string pref, suf, mx;
        for (auto& str : order) {
            suf += str;
        }
        for (int j = 0; j <= order.size(); ++j) {
            string cur = pref + to_string(nums[i]) + suf;
            if (cur > mx) {
                insert_pos = j;
                mx = cur;
            }
            if (j < order.size()) {
                suf = suf.substr(order[j].size());
                pref += order[j];
            }
        }
        order.insert(order.begin() + insert_pos, to_string(nums[i]));
    }
    string ans;
    for (auto& str : order) {
        ans += str;
    }
    if (ans.front() == '0') {
        return "0";
    }
    return ans;
}

Почему никто не пишет о том, что сама идея проводить алгоритмическую секцию интервью в большинстве случаев идет в разрез тому на какую позицию собеседуют кандидата. Почему человек мечтающий делать веб-приложения для продажи велосипедов, аренды квартир и всякие чаты должен тратить свое время на то чтобы решать задачки на литкоде. Почему бы экзамен на тщательное знание английского или какой там язык использует компания тоже не устраивать? Почему бы не устроить экзамен по психологии? Пройтись по Фрейду и Юнгу. Ведь и язык и психология(знание о том как устроена психика и как вести себя с другими людьми) тоже критически необходимы для работы разработчиком. Наболело. В жизни итак мало времени, а компании хотят чтобы мы его еще тратили на решение задачек. Спасибо, я бы мог и в науку пойти за задачками, а не приложения разрабатывать.

можете написать программу, которая за секунду обработает сто карточек?

Да хоть двести

sz = sum(map(len, xs))  # длина сцепленного числа
dp = [('', xs)] * (sz + 1)  # буфер для динамического программирования
for i, (head, tail) in enumerate(dp):
    for s in tail:
        head_s, j = head + s, i + len(s)
        if j <= sz and dp[j][0] < head_s:
            new_tail = tail[:]
            new_tail.remove(s)
            dp[j] = (head_s, new_tail)
print(dp[sz][0])

Могу сделать немного побыстрее/поаккуратнее, сделал покороче.

1) находим сумму чисел поразрядно в исходных числах

2) находим среднее, деля найденную сумму чисел на количество разрядов

3) сортируем числа по величине среднего от большего к меньшему

4) сортируем числа поразрядно от большего к меньшему

5) конкатенируем все числа в одно

Понимаю, не очень оптимально...

Сортируем, используя функцию сортировки специального вида (прямо решающую эту задачу для случая двух чисел)

from functools import cmp_to_key

xs = ['4', '42', '46', '427', '465']
xs.sort(key=cmp_to_key(lambda a, b: int(b+a)-int(a+b)))
print(''.join(xs)) # 46546442742

Раскладываем все карточки в бакеты по числу разрядов в них.
Например, 1: [4], 2:[42, 46], 3:[427, 465]

Далее для выбора следующей карточки сравниваем два числа - последнее из старшего бакета и последнее из следуюшего за нима младшего бакета , с добавлением в конец лидирующей цифры, в данном случае 4.
На первой итерации это 465 и 464 --> 465. Использованное число выбывает из списка.
Далее 427 против 464 --> 46
427 против 424 --> 427,
42 против 44 --> 4.
И остается 42.

В итоге 465 46 427 4 42

1) Делаем число берём его за max = 4 42 46 427 465

2) Бежим в цикле слева направо и пытаемся каждое число сдвинуть на 1 позицию влево пока (newMax > max), если больше то сдвигаем, обновляем max = newMax и продолжаем работать с этим же числом

3) Повторяем для всех чисел


4 42 46 427 465

46 4 42 427 465

46 4 427 45 465

465 46 4 427 42

асимптотика примерно N^2, подойдёт и для 1000 карточек

from functools import reduce

def get_max(l:list) -> int:
return int(reduce(lambda x,y: x + y, sorted(list(map(str, l)), reverse=True)))

Stream.of("4", "42", "46", "427", "465")
      .sorted((o1, o2) -> new BigInteger(o2 + o1).compareTo(new BigInteger(o1 + o2)))
      .reduce((o1, o2) -> o1 + o2)
      .get();

Сортировка стрима по большей конкатенации, затем общая конкатенация. Мне кажется это самый простой вариант.