25.06.2023 15:07
alexanderskulikov 120 5200 Источник

Чему равно самое большое число, которое можно составить из следующих карточек?

Если бы числа на карточках были однозначные, то всё было бы совсем просто: мы бы просто упорядочили их по убыванию. Например, самое большое число, которое можно составить из карточек "2", "3", "9" — это 932.

Когда же на карточках числа могут быть произвольной длины, то решение придумать становится сложнее, но при этом есть такое же простое решение! (И соответствующий алгоритм можно реализовать в одну строчку!)

Как это часто бывает в алгоритмах, первым делом полезно придумать наивный алгоритм. В нашем случае — это просто перебор всех перестановок. Например, для чисел "6", "61", "69" он выдаст нам ответ 69661.

from itertools import permutations

xs = ['6', '61', '69']
print(max(''.join(p) for p in permutations(xs)))

Если чисел мало, то этот код отработает быстро. Но с ростом n, количества входных чисел, этот алгоритм быстро станет непрактичным, потому что количество перестановок есть n!, а n!растёт непозволительно быстро.

Например, если перебирать перестановки со скоростью 10^9штук в секунду, то на перебор всех перестановок двадцати объектов понадобится \frac{20!}{10^9 \times 60 \times 60 \times 24 \times 365} \approx 77 лет.

Можете вручную найти ответ для пяти карточек из шапки поста? И можете написать программу, которая за секунду обработает сто карточек?

Комментарии (120)


  1. alexanderskulikov Автор
    26.06.2023 08:50
    #0
    -3

    В комментариях есть много правильных и много неправильных решений. Вот здесь есть анимированное (и правильное =) ) решение.


  1. vesper-bot
    26.06.2023 08:50
    #25687156
    +7

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


    1. miksoft
      26.06.2023 08:50
      #25687200
      +7

      Или я не понял идею, или даст неверный результат для примера из статьи - "6", "61", "69".

      После деления получим 6, 6.1, 6.9. После сортировки 6.9, 6.1, 6. А нужно 6.9, 6, 6.1.


      1. Alexandroppolus
        26.06.2023 08:50
        #25687596
        +3

        Там же не 10^(n-1), а 10^n - 1, т.е. 99...9, где n девяток. Получается периодическая дробь, т.е. было, например, 456, стало 0.(456). Идея остроумная, но если у нас очень длинные числа, то дробь не влезет в double. Так что попарные сравнения конкатенаций A+B против B+A более надежны.


        1. MzMz
          26.06.2023 08:50
          #25687830

          но если у нас очень длинные числа, то дробь не влезет в double

          можно написать специальный класс `Rational(long dividend, long divisor)` и сравнивать с приведением к общему делителю. Тогда дробных чисел не будет, только целые.


          1. Alexandroppolus
            26.06.2023 08:50
            #25687978
            +1

            Можно просто сразу домножать на числа вида 111..1

            Например, для 345 и 34, сравниваем 345*11 против 34*111


            1. vesper-bot
              26.06.2023 08:50
              #25688516

              А как сравнить 889, 8898 и 89? На что их домножать?


              1. Alexandroppolus
                26.06.2023 08:50
                #25688766

                На 11..1 длины противоположного числа при сравнении. Например, 889*1111 сравниваем с 8898*111. Вместо единиц можно в принципе и девятки, кажется так удобнее.


    1. alexanderskulikov Автор
      26.06.2023 08:50
      #25687230

      Бинго! А почему это работает?


      1. Namynnuz
        26.06.2023 08:50
        #25687732

        Потому что таким образом происходит нормализация и сравнение идёт поциферно, начиная со старшего разряда, в отличии от оригинальной записи, в которой решает позиция.


      1. MzMz
        26.06.2023 08:50
        #25687888
        +2

        Если посмотреть что происходит при делении на 99..99 то виден хитрый маневр: число abc при делении на 999 будет равно 0.abcabcabc... т.е 0.(abc)

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

        case 1: 35 351 20 - 3#5 3#5#1 2#0

        case 2: 35 354 20 - 3#5#4 3#5 2#0


        Фактически нам нужно сравнить какое из чисел с одинаковым строковым префиксом идет первым, для этого мы можем сравнивать бесконечные строки состоящие из повторов тестируемых чисел:

        case 1:
        353535353535353535...
        351351351351351351...

        case 2:
        353535353535353535...
        354354354354354354...

        Тут можно и без всякого деления на 999..9 сделать если просто написать специальный компаратор строк с автоматическим расширением меньшей строки повторами.


        1. MzMz
          26.06.2023 08:50
          #25687910

              private static final Comparator<String> COMPARATOR = (s1, s2) -> {
        if (s1.length() < s2.length()) {
            // extend the shorter s1
            while (s1.length() < s2.length()) {
                s1 = s1 + s1;
            }
        } else if (s1.length() > s2.length()) {
            // extend the shorter s2
            while (s1.length() > s2.length()) {
                s2 = s2 + s2;
            }
        }

        return s1.compareTo(s2);
    };

    private String concat(String... values) {
        return Arrays.stream(values)
            .sorted(COMPARATOR.reversed())
            .reduce("", (a, b) -> a + b);
    }


          1. qw1
            26.06.2023 08:50
            #25687926
            +3

            Достаточно понимать, какая строка должна быть раньше, чтобы конкатенация была больше:


            COMPARATOR(a, b) { return (a+b).compareTo(b+a); }


            1. sshmakov
              26.06.2023 08:50
              #25689070
              +1

              def comparator(x: str, y: str) -> int:
    return 0 if x + y == y + x else 1 if x + y > y + x else -1


def srt(num_list):
    import functools
    m = map(str, num_list)
    return ''.join(sorted(m, key=functools.cmp_to_key(comparator), reverse=True))


if __name__ == "__main__":
    given = ['4', '42', '46', '427', '465']
    print(srt(given))

# 46546442742

              просто для иллюстрации, что идея работает


        1. Alexandroppolus
          26.06.2023 08:50
          #25688000
          +1

          специальный компаратор строк с автоматическим расширением меньшей строки повторами.

          Может понадобиться дополнительное расширение более длинной строки. Например, 212 против 21. Когда вторую расширим до 2121, то понадобится расширить первую, чтобы понять, что она тяжелее.


  1. pentela
    26.06.2023 08:50
    #25687184
    +1

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


    1. alexanderskulikov Автор
      26.06.2023 08:50
      #25687228
      +3

      Вот так?

      from itertools import permutations

xs = ['4', '42', '46', '427', '465']
print(max(''.join(p) for p in permutations(xs)))
print(''.join(sorted(xs, reverse=True)))
      46546442742
46546427424


  1. Fodin
    26.06.2023 08:50
    #25687196

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

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


    1. Fodin
      26.06.2023 08:50
      #25687258
      +1

      Number([6,61,69].map(String).sort().reverse().sort((a, b) => a + b < b + a ? 1 : -1).join``)


      1. Serge3leo
        26.06.2023 08:50
        #25687454

        Вроде как, одна сортировка - лишняя.


        1. Fodin
          26.06.2023 08:50
          #25687538

          Как и реверс. Останки размышлений.


  1. sl_bug
    26.06.2023 08:50
    #25687222
    +2

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


  1. Politura
    26.06.2023 08:50
    #25687232
    +2

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

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

    Упд:

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


    1. Politura
      26.06.2023 08:50
      #25687256

      Что-то типа такого:

      [6,61,69].map(String).sort((a,b) => a+b == b+a ? 0 : a+b > b+a ? -1 : 1).join('')

      только надо упростить, наверняка в жабаскрипт compare у строк нормальный есть, который выдаст -1, 0, 1


      1. Fodin
        26.06.2023 08:50
        #25687282

        Ну, как сказать "нормальный"... Вот такой:
        Number([6,61,69].map(String).sort().reverse().sort((a, b) => (b + a).localeCompare(a + b)).join``)


        1. Politura
          26.06.2023 08:50
          #25687314
          +1

          Ага, спасибо! У вас только с предыдущей итерации лишние .sort().reverse() остались.


  1. accurate_random
    26.06.2023 08:50
    #25687242
    +1

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


    1. vassabi
      26.06.2023 08:50
      #25687294
      +1

      да, можно сказать поразрядная сортировка (то что и алфавитная, только не надо преобразовывать в текст, чтобы потом сортировать)


    1. Politura
      26.06.2023 08:50
      #25687332
      +1

      Решается за один проход.

      В задачах на сортировку одного прохода не может быть, в лучшем случае radix sort которая O(n*k)


      1. accurate_random
        26.06.2023 08:50
        #25687446
        -2

        А Вы сортируйте с "родительского" разряда сразу все числа, и всё получится с одного прохода. У меня-же получилось с одного раза чисто визуально, никаких проходов я не делал. Просто сравнивал все числа сразу поразрядно, с "родительских" разрядов. Только я сделал это "вручную", без кода и в один проход.


  1. SerJook
    26.06.2023 08:50
    #25687386

    <?php

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

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

echo implode($arr);

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


  1. Leetc0deMonkey
    26.06.2023 08:50
    #25687444
    +6

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


  1. YAKOROLEVAZAMKA
    26.06.2023 08:50
    #25687486

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

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


  1. qw1
    26.06.2023 08:50
    #25687528
    +2

    У меня получилось такое решение:


    На каждом шаге выбираем максимальную стартовую цифру и рассматриваем только числа, начинающиеся с неё.


    В наших примерах такое уже выполнено.


    Дальше дополняем все рассматриваемые числе этой цифрой справа так, чтобы получить числа одинаковой длины.
    Например
    6 → 66
    61 → 61
    69 → 69


    4 → 444
    42 → 424
    46 → 464
    427 → 427
    465 → 465


    Сортируем, берём максимальное, повторяем шаги.
    Во втором примере после сортировки получаем: 465, 464, 444, 427, 424,
    что соответствует исходным числам
    465, 46, 4, 427, 42. Наше максимальное число: 46546442742


    1. IknowThatIknowNothing
      26.06.2023 08:50
      #25688768

      "+" за первую правильную идею, алгоритм реализации пропустим (например, слово "сортируем" мне не нравится)


      1. qw1
        26.06.2023 08:50
        #25688924

        А как без сортировки?
        Тут все предложенные решения так или иначе сделаны через сортировку.


  1. bad_imagination
    26.06.2023 08:50
    #25687568

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

    Давайте составлять ответ итеративно, пусть мы каким то образом получили ответ используя первые 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;
}


  1. samrus
    26.06.2023 08:50
    #25687692
    +5

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


    1. qw1
      26.06.2023 08:50
      #25687748

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


      1. masai
        26.06.2023 08:50
        #25688192

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


        1. Leetc0deMonkey
          26.06.2023 08:50
          #25688358
          +1

           И есть риск оттолкнуть кого-то, кто нам нужен.

          Это не риск, это свершившийся факт. Толковый спец и так работу найдёт по связям и знакомствам, и эта литкодрочерская херня ему нафиг не впёрлась. А с другой стороны, всякого рода карьеристы, пришедшие в айти за деньгами, без проблем прорешают что угодно чтобы пройти собес ради повышения. А работать? А зачем работать? Надо дальше проходить собесы с повышением.


          1. qw1
            26.06.2023 08:50
            #25689010

            Толковый спец и так работу найдёт
            А всякого рода карьеристы, пришедшие в айти за деньгами, без проблем прорешают

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


        1. qw1
          26.06.2023 08:50
          #25688966

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


          Как пример, присутствовал на собеседовании с человеком с 20 лет опыта. Ну я думаю, что там проверять, чел должен быть прошаренным, в резюме упоминаются именитые фреймворки. Сейчас спросим что-нибудь совсем простенькое, и хватит. Так он не рассказал, что такое псевдо-переменная this. Причём не то, что не дал точное корректное определение, а даже близко не знает, про что это.


          1. Alexandroppolus
            26.06.2023 08:50
            #25689012

            Возможно это уникальный чел, который все 20 лет обретался в заповедничках, где исповедуют "бесклассовое ООП по Дугласу Крокфорду" или что-то вроде того.


            1. qw1
              26.06.2023 08:50
              #25689738

              Тогда он нам не подходит — он не сможет поддерживать кодовую базу другой веры.


              1. Leetc0deMonkey
                26.06.2023 08:50
                #25690402

                Тогда он нам не подходит — он не сможет поддерживать кодовую базу другой веры.

                Вот и показали бы её. Пообщались. Зачем вокруг да около ходите?


          1. Leetc0deMonkey
            26.06.2023 08:50
            #25690394
            +1

            Для компании намного дороже выйдет ошибка взять некомпетентного,

            Так благодаря алгособесам она и возьмёт некомпетентного.

            Так он не рассказал, что такое псевдо-переменная this.

            Как правило это от неумения задавать вопросы. И от неумения слушать ответы. Ещё у спецов часто встречаются проблемы с вербализацией того чего они на самом-то деле отлично знают и применяют. Ну а если челик 20 лет пилил годные проекты и правда не знает, то, оказывается, знание этой this на самом-то деле и не нужно. Но, ваше право взять начитанного теоретика.


            1. wataru
              26.06.2023 08:50
              #25690416
              +2

              Так благодаря алгособесам она и возьмёт некомпетентного.

              Если человек способен решить алго задачку на интервью то:


              • он может писать код
              • он обучаем
              • обладает некоторым уровнем IQ и алгоритмического мышления
              • может объяснить свои идеи (ведь на интервью часто просят объяснить что там происходит, почему так)
              • понимает ваш язык и говорит на понятном вам языке

              В 99% случаев — это уже достаточная квалификация, потому что во всяких фаангах собственная кухня, свои фреймворки и системы. Никакой опыт в условном django фреймворке или мастерство владения jira там особо не релевантны.


              Если же нужен какой-то особенный специалист с уникальными знаниями, то вместо или в довесок к алго-интервью проводят domain knowledge интервью.


              1. alexanderskulikov Автор
                26.06.2023 08:50
                #25690434

                я тоже так вижу!


              1. Leetc0deMonkey
                26.06.2023 08:50
                #25690560

                Если человек способен решить алго задачку на интервью то:

                К сожалению это большое заблуждение. Термин "литкод-макака" не спроста гуляет. Они не умеют писать код. Они не обучаемые за пределами чётко изложенных инструкций. Они вообще не умеют работать. Просто не умеют, вот и всё. Они просто механически запоминают задачки и выпаливают их на собесах. Возможно лет 20 назад алгособесы в Гугл действительно выбирали самых из самых, но сейчас этот подход не работает и широко абьюзится совсем левыми людьми.


                1. wataru
                  26.06.2023 08:50
                  #25690590
                  +1

                  Ну в гугле, по крайней мере, утекшие на литкод задачи банят и особо часто не задают. Конечно, с некоторой задержкой, но шанс того, что из 4-5 задач вам не попадется ни одна невызубренная ничтожно мал. Потом, на интервью дают всякие дополнительные вопросы, изменяют задачу, дополняют ее. Этого на литкодах нет вообще. Поэтому эта "литкод макака" должна найти похожую задачу, понять, в чем там разница, изменить алгоритм, объяснить его и закодить. Это одной зубрежкой не сделать, так что все пункты выше все еще выполняются.


                  Про "не умеют работать": это как? И какими интервью это можно проверять вообще?


                  Ведь если можно зазубрить сотни задачек с реализацией и объяснениями, то гораздо проще зазубрить несколько историй о крутом проекте из прошлого, плюсы и минусы вот того фреймворка из текста вакансии и разъяснения, что вот этот вот код, сворованный и выложенный на гитхаб в качестве совего, делает.


                1. qw1
                  26.06.2023 08:50
                  #25691182

                  Термин "литкод-макака" не спроста гуляет. Они не умеют писать код. Они не обучаемые за пределами чётко изложенных инструкций

                  Обычных олимпиадников видел. Код в проде у них отличный.


                  А тех макак, о которых вы говорите, я даже теоретически не могу представить. У обычных людей, далёких от математики, глаз начинает дёргаться от терминов типа "выпуклая оболочка" или "разложение в ряд Тейлора". Не то, чтобы учить это будут.


                  Если бы тот феномен, о котором вы говорите, имел место, олимпиады по программированию брали бы студенты-зубрилы. А что? Выучил пару сотен алгоритмов, и шпаришь ими на контестах, так же?


                  1. masai
                    26.06.2023 08:50
                    #25691416

                    Я видел как олимпиадников с хорошим кодом, так и олимпиадников с катастрофически плохим (хоть и работающим). Всё же знать алгоритмы и уметь их быстро программировать маловато.


                  1. Leetc0deMonkey
                    26.06.2023 08:50
                    #25691486
                    +1

                    Обычных олимпиадников видел. Код в проде у них отличный.

                    Как повезёт. У олимпиадников код как правило ужасный. У них на уровне рефлексов сделать побыстрее, лишь бы работало. Интересы ограничены исключительно алгоритмами. Просто писать корпоративный код им скучно и неинтересно. Вцелом бесполезная в работе публика, если не бросать их непосредственно на алгоритмы. А в работе мне нужны инженеры. Понятно что встречаются и олимпиадники и инженеры в одном флаконе. Но зачем так урезать область доступных кадров, если вы не Гугл?

                    А тех макак, о которых вы говорите, я даже теоретически не могу представить.

                    Это явление ещё пока не пришло в Россию. В США гуляет вовсю.


                    1. qw1
                      26.06.2023 08:50
                      #25692074

                      Это явление ещё пока не пришло в Россию. В США гуляет вовсю.

                      И что делать? Если есть такой контингент, который всеми силами пытается "взломать собес", чтобы получить очередные 20% к з/п, они с удовольствием переключатся, как это отмечено выше, на симуляцию "опытного инженера" с большим опытом и богатым гитхабом. Это уж наверняка требует куда меньшего напряжения при подготовке.


                      1. Leetc0deMonkey
                        26.06.2023 08:50
                        #25693356

                        И что делать?

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

                        на симуляцию "опытного инженера"

                        Если вы сами опытный инженер, то не прокатит. Фальш и неестественность чувствуется сразу. Рыбак рыбака видит издалека.


                      1. qw1
                        26.06.2023 08:50
                        #25693414

                        Такое сейчас не приветствуется. Считается непрофессиональным отказать кандидату, только из-за ощущений, что он какой-то "неправильный рыбак".


                        Нужны объективные показатели:


                        Этот говорит, что имеет 30 лет опыта Vue. И тот говорит, что имеет 30 лет опыта Vue. Этот говорит, что сам написал с нуля CRM. А тот говорит, что сам написал с нуля RTB-модуль. Значит, самое время применять тяжёлую артиллерию. Этот решил задачу поиска цикла в списке без использования доп. памяти, а тот — не решил. Что-ж, у нас есть победитель.


                      1. Leetc0deMonkey
                        26.06.2023 08:50
                        #25693714

                        Такое сейчас не приветствуется. Считается непрофессиональным отказать кандидату, только из-за ощущений, что он какой-то "неправильный рыбак".

                        Ага, зато считается профессиональным отказать кандидату за то что он типа не софтскилловый.

                        Нужны объективные показатели:

                        Для забюрократизированной корпорации масштабов Гугла действительно нужны формальные метрики. И тут уж ничего не поделаешь. Это вне нашего контроля. Но вы ведь не Гугл, правда?

                        Этот говорит, что сам написал с нуля CRM.

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

                        Этот решил задачу поиска цикла в списке без использования доп. памяти, а тот — не решил.

                        Первый хорошо подготовился к собесу, а второй привык работать и решать проблемы бизнеса. Первый вам потом захерачит O(n^3) - "ачотакова?". В то время как второй, столкнувшись с проблемой, покумекав, решит её. Но решит её уже не у вас, а у ваших конкурентов.


                      1. wataru
                        26.06.2023 08:50
                        #25693822
                        +1

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

                        Но ведь, если макака может выучить решение сотен задач, объяснить, ответить на дополнительные вопросы, закодить без ошибок или исправить их, то рассказать про написанный CRM сможет и тем более. Это вызубрить невозможно что ли по каким-то причинам? Как раз про что-то большое и неформальное вроде проекта можно много и красиво наплести вообще не разбираясь в теме, только слова ключевые выучить надо.


                        Первый хорошо подготовился к собесу, а второй привык работать и решать проблемы бизнеса. Первый вам потом захерачит O(n^3)

                        При этом второй алгоритмы не знает, иначе бы ему это интервью было — как орешки. Но O(n^3) почему-то впендюривает тот, который знает 300 задачек наизусть и может, если что-то похожее попалось, подобрать аналогичную задачку и адаптировать решение, а не тот, который алгоритмы не знает? Почему? Типа, первому настолько насрать, что он принципиально не применяет свои умения, а вот второй горит желанием помочь бизнесу? Ну это вы, во-первых, никаким интервью не отловите, ибо на интервью человек приходит, чтобы его пройти, и там свое такое отношение показывать не будет. А во-вторых, это вообще перпендикулярная к алгоритмам и навыкам создания CRM с нуля тема. Точно так же чувак реально написавший с нуля отличный большой проект, похожий на ваш, может забить болт на все и впендюрить O(N^3), потому что ему пофиг.


                        Но вы ведь не Гугл, правда?

                        Вы согласны, что гуглу такие интервью подходят весьма неплохо?


                      1. vedenin1980
                        26.06.2023 08:50
                        #25693910

                        то рассказать про написанный CRM сможет и тем более. Это вызубрить невозможно что ли по каким-то причинам?

                        Дело в том, ИМХО, что основная ценность опытного старшего разработчика находится в двух экспертизах (кроме, собственно базовых навыков программирования)


                        1) умение доносить свою мысль (устно, с помощью кода, с помощью краткой, но понятной документации). Это особенно важно так как 90% кода пишется для людей, а не для машины, по сути языки программирование это средство общения,


                        2) техническая интуиция + понимание бизнес задач (если нас заказчит просят сделать так-то вероятно мы сталнемся со следующими подводными камнями, поэтому сделаем вот так), там же поиск золотой середины между качеством и скоростью разработки, сложностью и простой и т.п.,


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


                      1. Leetc0deMonkey
                        26.06.2023 08:50
                        #25694322
                        +1

                        Да, всё так и есть.


                      1. wataru
                        26.06.2023 08:50
                        #25694386

                        умение доносить свою мысль

                        Это и в алгоритмах проверяется. У нас там даже отдельная графа есть communication & comprehension skills. Если макака придет ко мне на интервью и нечленораздельно мыкая напишет идеальный код, все равно получит там жирный минус и скорее всего интервью не пройдет. Более того, я, как и многие другие интервьюверы, сначала требую от кандидата словесное описание решения и только потом говорю "приступайте к кодированию, пожалуйста".


                        если нас заказчит просят сделать так-то вероятно мы сталнемся со следующими подводными камнями, поэтому сделаем вот так

                        Вот что тут нельзя зазубрить?


                      1. vedenin1980
                        26.06.2023 08:50
                        #25694512

                        Это и в алгоритмах проверяется.

                        Этого слишком мало для оценки адекватности работы в команде и умение писать чистый и понятный код.


                        Вот что тут нельзя зазубрить?

                        Вы тим и тех лид, к вам приходит заказчик и говорит у меня несколько крупных животноводческих ферм и мне сказали, что ИТ может помочь увеличить прибыль — что вы мне предложите. Опишите как по вашему нужно работать с таким заказчикам, какие требования вы у него будете спрашивать, какие технологии вы будете использовать в проекте и почему, как вы будете набирать команду, если у вас будет такое право. Какие подводные камни вы видете в таком проекте и как вы их опишите вашим менеджерам.
                        Опишите из опыта где и когда у вас было что-то подобное и какие проблемы у вас возникали.


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


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


                      1. wataru
                        26.06.2023 08:50
                        #25694544

                        А теперь зазубрите все ответы на все вопросы выше

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


                      1. vedenin1980
                        26.06.2023 08:50
                        #25694562

                        Проблема не в том, что зазубрят или нет. А в том что эти несколько сот задачек имеют мало общего с 95% задач, которые решает программист.


                        А вот те вопросы, что я описывал — имеют. И если кто-то сумеет выучить вообще любые возможные вопросы и показать адекватное поведение в таких воображаемых ситуациях — то тут работает принцип Китайской комнаты — вероятно даже если он это зазубрил — он примет в будущем верное решение, а больше мне как его руководителю от него ничего не нужно.


                        P.S. Нет, разумеется, если вся задача программиста будет заключатся в придумывании с нуля новых алгоритмов без использование стандартных библиотек, гугла, github и stackoverflow — нужно проверять алгоритмы. Но сколько таких вакансий на свете?


                      1. qw1
                        26.06.2023 08:50
                        #25694976
                        +1

                        Вы тим и тех лид, к вам приходит заказчик и говорит у меня несколько крупных животноводческих ферм и мне сказали, что ИТ может помочь увеличить прибыль — что вы мне предложите. Опишите как по вашему нужно работать с таким заказчикам, какие требования вы у него будете спрашивать

                        Странные вопросы для программиста. Если бы я такое услышал, вряд ли бы принял оффер. Выяснять, что болит у коровозаводчиков и как это лечить — не то, чем бы мне хотелось заниматься на работе.


                        Как и наоборот — если вы ищете руководителя проекта или бизнес-аналитика, не нужно заставлять его литкодить.


                    1. wataru
                      26.06.2023 08:50
                      #25693456
                      +1

                      Как повезёт. У олимпиадников код как правило ужасный

                      В фаангах это нестрашно, потому что там код ревью везде. И эти олимпиадники за 2 недели страданий обучаются использовать нормальные имена и форматировать код.


        1. wataru
          26.06.2023 08:50
          #25689340
          +2

          У фаанга, откуда эти интервью пошли, опыт другой. Плюс им там действительно иногда алгоритмы понадобится могут. Я вот даже динамическое программирование в гугле в прод коммитил, да всякие максимумы в скользящих окнах писал. Другой вопрос, что когда всякие "рога и копыта" на должность админа начинают спрашивать алгоритмические задачки, потому что это модно — это глупость и карго-культ.


          1. masai
            26.06.2023 08:50
            #25690220

            У фаанга, откуда эти интервью пошли, опыт другой.

            Формально, компания, в которой я работаю, — это не буква фаанг, но и далеко не «Рога и копыта». Значительная часть наших инженеров в фаанге работала. Так что мой и их опыт всё же релевантен. Про задачи в гугле тоже в курсе, не так уж и часто там приходится хитрые алгоритмы писать руками. Либо вам очень повезло с задачами.


            1. wataru
              26.06.2023 08:50
              #25690252

              Завист от проекта, конечно. Если это условные фронт-енд или разработчики андроид приложений, то там такое реже встречается. Если это какие-нибудь разработчики Хрома, DeepMind или BigTable, то там такое встречается гораздо чаще.


              1. Leetc0deMonkey
                26.06.2023 08:50
                #25691496

                Если это условные фронт-енд или разработчики андроид приложений, то там такое реже встречается.

                Если фронтендеру вдруг понадобился хитрый алгоритм, это красный флажок что в архитектуре вашей системы что-то не так.


    1. Rupper
      26.06.2023 08:50
      #25688362
      +3

      Если такие задачки вызывают у вас сложности на собеседовании, то в науку вы пойти не можете. Кроме того, эта задачка проверка ваших мыслительных способностей, потому что если думать при разработке интернет магазина велосипедов не надо, то можно написать программу которая будет их делать. А чтобы написать такую программу надо думать. При этом, если для написания такой программы думать не надо то надеюсь вы догадались что дальше. Разработка по это про думать. И над какими задачами думать вообще говоря не важно.


  1. longclaps
    26.06.2023 08:50
    #25687930

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

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

    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. wataru
      26.06.2023 08:50
      #25689494

      Вы бы хоть расписали, что у вас за динамическое программирование тут считается-то.


      Насколько мои познания питона позволяют понять, у вас тут 1 параметр — сколько символов набрали. Храните там что? Максимальную строку такой длины, получаемую из каких-то карточек и оставшиеся карточки?


      Почему это правильное решение? Теоретически вы можете оказаться в ситуации, что вы получили такое же начало в заданной длине, но конец позволяет собрать нечто более мелкое, чем другой возможный вариант. Контр-тест пока придумать не могу.


      1. longclaps
        26.06.2023 08:50
        #25691068
        -3

        Насколько мои познания питона позволяют понять

        Вот вам два совета, на выбор:

        1. Если вы не уверены в вашем питоне – не лучше ли промолчать? В конце концов, это ваша проблема.

        2. Если же ваше желание высказаться неудержимо – возьмите другую интонацию.

        Как оппонент, вы мне не интересны. Балабол, который "контр-тест пока придумать не может", требует с меня отчета? Который предъявлял мне, что я не отвечаю за слова - и слился? Еще раз, настоятельно предлагаю покончить с этим. Не хочу тратить на вас коменты.

        ps @alexanderskulikov, подкиньте мне в карму, задолбала невозможность оперативно ответить.


        1. wataru
          26.06.2023 08:50
          #25694396

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


          А так да, посыпаю голову пеплом. Ваша сортировка за O(N^3) действительно работает. Только комментарии и именна переменных вообще ни к месту. Динамического программирования там нет.


      1. Alexandroppolus
        26.06.2023 08:50
        #25693004
        +1

        Теоретически вы можете оказаться в ситуации, что вы получили такое же начало в заданной длине, но конец позволяет собрать нечто более мелкое, чем другой возможный вариант

        Например, ['31', '3', '11', '111', '22222']

        dp[4] = ('3111', ['31', '11', '22222']), т.е. head составлен из '3' и '111', а из tail можно сделать 312222211. Если собрать head как '31' + '11', то из tail получается более лучшая 322222111.

        Но это не проблема, потому что на пути к результату dp[4] оказалась "тупиковым ответвлением". Результат в итоге прошел через dp[3], где head = '313'. Во всех подобных кейсах неудачный head (оптимальный для своей длины, но не оптимальный в целом), в итоге не используется.


        1. wataru
          26.06.2023 08:50
          #25693486

          Во всех подобных кейсах неудачный head (оптимальный для своей длины, но не оптимальный в целом), в итоге не используется.

          Эти и есть основной вопрос. Надо бы это доказать. Вручную кейс придумать сложно, вечером набросаю перебор. Если есть строка, которая разбивается на подстроки двумя способами, и все куски первого способа не хуже всех куско второго способа (и это не тривиальный случай, когда все строки равны по этому сравнению), то это будет контр пример. Надо к ним добавить еще одну строку между любыми двумя кусками меньшего разбиения — и все. Оптимальный ответ всегда имеет изначальную разбиваемую строку в начале. Поэтому любая ветка в итоге проходит через такой вот плохой индекс.


        1. wataru
          26.06.2023 08:50
          #25694392

          Можно доказать, что такого действительно не bбудет, используя жадность. Вообще, это "ложное динамическое программирование" работает только потому, что в задаче есть жадность. Но тогда это получается весьма странная реализация сортировки за O(N^3).


  1. nronnie
    26.06.2023 08:50
    #25687990
    -1

    дополняем все карточки нулями до длины самого длинного числа и сортируем по убыванию

    4 -> 400
    42 -> 420
    46 -> 460
    427 -> 427
    465 -> 465

    Результат: 465,46,427,42,4

    Я прав? (Если да, то мамой клянусь, что не подстматривал :))


    1. nronnie
      26.06.2023 08:50
      #25688026
      -1

      Нет, похоже я ошибся, но, кажись, направление верное , буду думать дальше :)


      1. Gromilo
        26.06.2023 08:50
        #25688538

        У меня похожие рассуждения, только одной сортировкой не обойтись, ибо нужно на каждом шаге выбирать лучшую карточку. Так же добиваем "нулями", только держим в уме, что нули - это числа из других карточек. Пытаемся найти комбинацию карточек, которые заменяют нули и будут больше кандидата. Если таких нет, то выбираем эту карточку. Сложность кубическая получается.


    1. vesper-bot
      26.06.2023 08:50
      #25688504

      Нет. Карточка "9" в этом случае окажется не в самом начале, где должна быть, так как её перемещение за "не-девятку" уменьшает число.


    1. mkokorev
      26.06.2023 08:50
      #25690484

      Последние две цифры поменяй местами и будет больше... а если 4 поставить перед 427 будет ещё лучше...


  1. fractalNo_name
    26.06.2023 08:50
    #25688536

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

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

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

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

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

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


  1. celen
    26.06.2023 08:50
    #25688612
    +2

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

    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. Luckee
    26.06.2023 08:50
    #25688778

    Раскладываем все карточки в бакеты по числу разрядов в них.
    Например, 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. sl_bug
      26.06.2023 08:50
      #25688874

      и ответ не верный


  1. ololo6e
    26.06.2023 08:50
    #25688930
    +1

    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 карточек


    1. ololo6e
      26.06.2023 08:50
      #25688960

      это верно, потому что последовательность может только возрастать при "проталкивании" числа вверх по разрядам, если не возрастает, то значит уже на месте(вправо не двигаем). В теории можно посчитать за NlogN если подключить двоичный поиск


    1. Fodin
      26.06.2023 08:50
      #25690836
      +1

      Пузырьковая сортировка.


  1. alexanderskulikov Автор
    26.06.2023 08:50
    #25689008
    -3

    В комментариях есть много правильных и много неправильных решений. Вот здесь есть анимированное (и правильное =) ) решение.


    1. wataru
      26.06.2023 08:50
      #25689510

      Жесть, конечно, на техническом ресурсе давать ссылки на шортсы. Этот тиктокоподобный формат подходит для видео про котиков и всякого треша, но не для обучающего контента. Кроме того там не доказывается, почему это является решением. Почему такое отношение является отношением порядка? Почему по нему можно сортировать? Даже ни слова о том, откуда оно взялось.


      1. alexanderskulikov Автор
        26.06.2023 08:50
        #25689580

        Ну да, я сам какое-то время привыкал к мысли, что и в формате шортсов что-то можно объяснять и понимать — и вот привык вполне =) Но да, есть такой вот формат микрообучения. Довольно популярный уже, со своими плюсами и минусами, как всегда. Вы считаете, что плюсов у него совсем нет?

        И да, за минуту тяжело всё подряд объяснить и доказать (а если видос длиннее минуты, то ютуб отказывается считать его шортсом). Но про то, почему сортировать можно, я там заикнулся всё-таки. А как бы Вы объяснили, откуда взялось решение?


        1. wataru
          26.06.2023 08:50
          #25689774
          +1

          Довольно популярный уже, со своими плюсами и минусами, как всегда. Вы считаете, что плюсов у него совсем нет?

          Плюс у него один. Автору. Если вдруг завирусится, то можно заработать на монетизации. Но этого не произойдет никогда, потому что весь этот формат сделан, чтобы привязывать пользователей с ментальностью "развлеки меня еще минутку". Научно-популярный контент тут не зайдет даже ботаникам вроде меня.


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


          По поводу объяснения, я бы делал так: В оптимальном ответе при помене местами любых двух соседних элементов ответ должен не улучшаться. Отсюда получается вот такое сравнение двух строк через конкатенации. Дальше, надо показать, что это действительно отношение порядка и по нему можно сортировать. Для этого, не вдаваясь во все детали, достаточно показать транзитивность. Что если ab <= ba и bc <= cb, то ac <= ca. Проще наверно доказать это, если сначала доказать, что ab <= ba тогда и только тогда, когда (a) <= (b) (постоянно повторяющиеся строки). Тут надо рассмотреть 2 случая. Если a и b не являются префиксами друг друга, то и ab c ba и (a) с (b) будут различаться где-то в первых строках. Теперь пусть a — префикс b. Т.e у нас строки a и ac. Дальше снова 2 случая, a=c и a != c.


          Может, есть более простой способ доказать это все.


          1. alexanderskulikov Автор
            26.06.2023 08:50
            #25689992

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

            Плюс у него один. Автору. Если вдруг завирусится, то можно заработать на монетизации. Но этого не произойдет никогда, потому что весь этот формат сделан, чтобы привязывать пользователей с ментальностью "развлеки меня еще минутку". Научно-популярный контент тут не зайдет даже ботаникам вроде меня.

            Вот много есть в мире людей, которые думают про этот формат и что-то в нём делает. И цель у них у всех — это монетизация. При этом очевидно, что это не сработает, потому что вирусятся видео про котов, а не про алгоритмы. И раз даже Вам не зайдёт, то никому не зайдёт. Правильно я расшифровал?

            Повторюсь, что мне формат всё же видится осмысленным. Так уж устроен сейчас мир, что люди информацию периодически вынуждены потреблять урывками. И если уж у них есть минута (когда они стоят в очереди за кофе), то почему бы и не узнать что-то новое? Ну и раз не зайдёт ботаникам типа Вас, то почему всем остальным-то не зайдёт?

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

            Можно и перемотать, и на паузу поставить. Когда поставите на паузу, можно подумать.

            Может, есть более простой способ доказать это все.

            Если пытаться в одну минуту запихать ещё и доказательства транзитивности (с разбором случаев ещё!), то будет менее поверхностно, но куда более скомкано =) С транзитивностью есть более простой способ (сказать, что сортируем по ключу — $\frac{A}{10^a-1}$), но и с ним скомкано получится.


            1. wataru
              26.06.2023 08:50
              #25690006

              Можно и перемотать, и на паузу поставить.

              Шортзы не перематываются. Ни веб версия, ни в приложении. По крайней мере я не нашел.


              Если пытаться в одну минуту запихать ещё и доказательства транзитивности (с разбором случаев ещё!), то будет менее поверхностно, но куда более скомкано =)

              Можно не запихивать все в одну минуту, а запихать, скажем, в три. Оставив доказательство в конце для особо любознательных. И перемотка работать будет.


              транзитивностью есть более простой способ (сказать, что сортируем по ключу — $\frac{A}{10^a-1}$), но и с ним скомкано получится.

              Это почти мое предложение, только я там со строчками периодическими пытался работать. Но вы правы, просо указав, что ab = 10^n*a+b и переписав неравенство, можно очень просто получить ключ $A/(10^a-1)$


              Это все в 2 минуты бы влезло вообще.


              1. alexanderskulikov Автор
                26.06.2023 08:50
                #25690102

                Шортзы не перематываются. Ни веб версия, ни в приложении. По крайней мере я не нашел.

                Прошу прощения, обманул Вас. Но тиктоки, и рилсы, вроде, перематываются. Подписывайтесь на меня в тиктоке!

                Можно не запихивать все в одну минуту, а запихать, скажем, в три. Оставив доказательство в конце для особо любознательных. И перемотка работать будет.

                Если видео будет длиннее минуты, то оно на ютубе перестанет считаться шортом и нельзя будет в два клика прикольную музычку наложить! А без музыки, как Вы понимаете, это не дело.


                1. wataru
                  26.06.2023 08:50
                  #25690106

                  Понятно, что на вкус и цвет фломастеры разные… но музыка — моя вторая претензия после отсутствия перемотки.


                  1. alexanderskulikov Автор
                    26.06.2023 08:50
                    #25690112

                    Тем не менее, хорошо, что уже обсуждаем, что разным людям разное заходит, а не что единственный плюс микрообучения — это призрачная монетизация.


                    1. wataru
                      26.06.2023 08:50
                      #25690244

                      уже обсуждаем, что разным людям разное заходит,

                      Хорошо. Еще запишем в плюсы легкость наложения "прикольной музычки".


                      Конечно, автор сам вправе решать, куда и как выкладывать материал. Но и пользователи вправе высказывать свое "фи", если им платформа или формат не нравятся. Пока все "плюсы" тут упомянутые, это со стороны автора. Хоть один плюс для усвояемости контента, удобства аудитории приведете?


                      1. alexanderskulikov Автор
                        26.06.2023 08:50
                        #25690362

                        Хоть один плюс для усвояемости контента, удобства аудитории приведете?

                        А Вам действительно интересно, какие есть удобства? Это я уже серьёзно спрашиваю, без сарказма. Потому что я писал выше, вроде бы, про то, что люди смотрят очень много коротких видео, но как-то Вы не заметили этого.


                      1. wataru
                        26.06.2023 08:50
                        #25690400

                        А Вам действительно интересно, какие есть удобства?

                        Уже интересно, да.


                        люди смотрят очень много коротких видео, но как-то Вы не заметили этого.

                        А еще, люди смотрят очень много порно. Но вы не будете же приводить это в качестве аргумента, что выкладывать ваш разбор на условном порнхабе имеет кучу плюсов?


                        Я про это еще в самом первом комментарии сказал. Люди смотрят в тиктоке и шортзах другие видео: пляшущие жопы, котки, смешные приколы. Вы претворяетесь сейчас, или реально не знаете, что за видео популярны в тиктоке? Чем тупее и бессмысленне видео, тем оно популярнее там. Потому что там почти все просмотры делают люди с ментальностью "развлеки меня еще 60 секунд". Мозг отключен: "О прикольно, еще допаминчик выделился. Давай еще". Какие-то разборы задачек не укладываются в этот тренд, потому что это не развлекательный контент.


                      1. alexanderskulikov Автор
                        26.06.2023 08:50
                        #25690454

                        А еще, люди смотрят очень много порно. Но вы не будете же приводить это в качестве аргумента, что выкладывать ваш разбор на условном порнхабе имеет кучу плюсов?

                        Какое тонкое сравнение! Но давайте попробую ещё раз мысль сформулировать. Люди смотрят очень много коротких видео. Даже если среди этого всего потока всего один процент образовательного видео, это всё равно дофига. То есть спрос явно есть.

                        Я про это еще в самом первом комментарии сказал. Люди смотрят в тиктоке и шортзах другие видео: пляшущие жопы, котки, смешные приколы.

                        Меня радует Ваша способность обобщать. Ну да, смотрят на котиков. Но не только на котиков смотрят.

                        Вы претворяетесь сейчас, или реально не знаете, что за видео популярны в тиктоке? Чем тупее и бессмысленне видео, тем оно популярнее там. Потому что там почти все просмотры делают люди с ментальностью "развлеки меня еще 60 секунд". Мозг отключен: "О прикольно, еще допаминчик выделился. Давай еще". Какие-то разборы задачек не укладываются в этот тренд, потому что это не развлекательный контент.

                        Но какая разница, какие там самые популярные видео? Конечно, образовательные видосы никогда не станут такими популярными, как образовательные. И что теперь? Вам это как-то мешает слушать непопулярную музыку, например?

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


                      1. wataru
                        26.06.2023 08:50
                        #25690516

                        Люди смотрят очень много коротких видео. Даже если среди этого всего потока всего один процент образовательного видео, это всё равно дофига. То есть спрос явно есть.

                        Нет, вы должны тогда привести статистику. Вот про то же самое порно — от того, что вы выложите ваш разбор на порнхаб, он не станет одинм процентом всех роликов там. Даже одной сто-миллиардной не станет. Потому что эта платформа заточена под другой контент. Люди ваш контент будут игнорировать и алгоритм его похоронит.


                        Но какая разница, какие там самые популярные видео?

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


                        Как раз с помощью образовательного контента можно людям помочь с какой-то пользой провести те две минуты, которые у них образовались

                        Т.е. это плюс этого формата, да? Вы просвещаете серые массы, которые просвящатся может и не хотели даже?


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


                        Вернемся к началу разговора. Плюсы вы сформулируете или нет?


                      1. alexanderskulikov Автор
                        26.06.2023 08:50
                        #25690792

                        Нет, вы должны тогда привести статистику.

                        Прямо должен я?

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

                        Перечитайте, пожалуйста, ещё раз мои комментарии и убедитесь, что я нигде там не утверждал, что моё видео будут много смотреть. Я даже и знаю, что конкретно мои видео много смотреть не будут.

                        Вернемся к началу разговора. Плюсы вы сформулируете или нет?

                        Чтобы Вы мне снова начали рассказывать про порно, про "серые массы", которые смотрят тикток, про людей с какой-то не той ментальностью? Как я и опасался, интересного диалога не случилось. Так что давайте свернём этот тред, пожалуйста.

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

                        Ох, мастер Вы передёргивать. Почему Вы за меня решили, какая у меня мечта? Да и разве я заставляю кого-то? Но не отвечайте, пожалуйста, на эти вопросы =) Всего хорошего!


            1. qw1
              26.06.2023 08:50
              #25690874

              Так уж устроен сейчас мир, что люди информацию периодически вынуждены потреблять урывками. И если уж у них есть минута (когда они стоят в очереди за кофе), то почему бы и не узнать что-то новое?

              И что остаётся от такого потребления? Отсюда я перешёл по ссылке, и хотя бы прочитал задачу и понимаю, о чём она. Если бы шортс мне попал случайно, вместе с котиками, я бы сказал "что это было и зачем?"


              В некоторых роликах вы вываливаете куски кода на питоне. Вы думаете, зритель будет жать паузу и читать его? Или даже перепечатывать?


              Особенно смешны вопросы "а как бы вы решили задачу?"
              Там некогда решать, через 10 секунд следующее видео.


              Призыв "пишите ваш ответ в комментариях" непонятный, потому что комментарии к шортсам не видны в интерфейсе ютюба, это надо очень постараться, чтобы на них выйти.


              Моё мнение: как интерактивная визуализация задачи — отличная штука, если такой ролик вставить в большую статью, когда зритель уже настроен на задачу и готов смотреть ролик по теме. Само по себе же — непонятно, для кого и зачем.


  1. Leetc0deMonkey
    26.06.2023 08:50
    #25691518
    -3

    А реализовывать типа "супербыстрые" алгоритмы на Питоне это вообще 5! Лишнее подтверждение что олимпиадник это не инженер, от слова совсем.
    Я O(n^3) выложу на GPU и он отработает там быстрее вашего O(logn) на CPU. Господа олимпиадники, мир реальной разработки ПО гораздо сложнее чем вам кажется в вашем уютненьком манямирке.


    1. qw1
      26.06.2023 08:50
      #25692092
      +2

      Из-за такого подхода я регулярно наблюдаю, как какой-нибудь отчёт строится 2-3 минуты, вместо того, чтобы выполниться за полсекунды. Пока пользователь не взбунтовался, "инженер", написавший это, считает, что всё порядке — код работает же!


      Это всё усугубляется тем, что в момент написания неоптимального алгоритма (N^3), на маленьких тестовых данных всё летает, а по мере наполнения базы медленно замедляется. Из-за того, что деградация медленная, пользователи думают, что так и должно быть, ведь всегда так было.


      1. Leetc0deMonkey
        26.06.2023 08:50
        #25693292

        Не имеет значения. Он либо одинаково хорошо работает и на больших данных, либо не применяется. Вы наняли не инженера, а очередного фанатика-сектанта. Свиделя мощей GPU в этот раз, видимо.


        1. qw1
          26.06.2023 08:50
          #25693422
          +1

          Причём здесь GPU. Люди просто кладут данные в список, а потом ищут линейным поиском, не задумываясь об O(.)


          1. Leetc0deMonkey
            26.06.2023 08:50
            #25693644

            При том что аппаратные особенности вдруг неожиданно из "хороших" алгоритмов делают "плохие", а из "плохих" - "хорошие". Впрочем, чую, рано тут ещё о таких материях рассуждать. А грамотный инженер, который понимает во что выльется O(n^3) на SISD, и без всяких алгособесов нанимается. Он просто понимает, а необходимый алгоритм по ходу разработки подберёт. Нет никакой необходимости их все знать наизусть.


      1. Leetc0deMonkey
        26.06.2023 08:50
        #25693786

        Это всё усугубляется тем, что в момент написания неоптимального алгоритма (N^3), на маленьких тестовых данных всё летает, а по мере наполнения базы медленно замедляется.

        Дополню. Не наблюдаете проблемы что тестовые данные были маленькие? Кто за это отвечает? Не стоит перекладывать с больной головы на здоровую.


        1. qw1
          26.06.2023 08:50
          #25694986

          Дорого выходит, если доказывать негодность говнокода тестами.
          Одно дело сказать, что это дрянь за N^2, выброси её и напиши нормально.
          Другое дело — готовить гигабайтные тесты горе-разработчику, только чтобы показать ему, что он не прав.


          1. Leetc0deMonkey
            26.06.2023 08:50
            #25695318

            Это не говнокод. O(n^3) это идеальный код для небольшого объёма данных: прост и лаконичен, легко отлаживать, минимальная вероятность хитрых багов.

            А то что вы не удосужились нагенерировать базу чтобы смоделировать "а как мы заживём когда вырастем" - это косяк ваш как архитектора/аналитика, и только ваш. И не надо свою некомпетентность сваливать на других. Инженер по-сути всё сделал правильно. Предложенные тесты работают.


            1. qw1
              26.06.2023 08:50
              #25695404

              Я думаю, оба подхода имеют право на жизнь.


              Тот, где литкодер напишет сложный алгоритм n*log(n), где сейчас даже оно и не нужно. И не надо будет бояться роста данных.


              И тот, где "инженер" применит минимум усилий, лишь бы работало сейчас. А рост данных — не его головная боль, а боль архитектора/аналитика/руководителя проекта, который должен за ним присматривать (читать его коммиты, анализировать сложность алгоритмов, предоставлять тесты): "мне тут Вася написал N^3, надо иметь ввиду и в нужный момент заменить алгоритм".


              Я не удивлен, что большинство руководителей хотят идти по пути №1 (если бюджет позволяет). Естественно, они не хотят себе лишней головной боли.


              1. Leetc0deMonkey
                26.06.2023 08:50
                #25696090
                +1

                Тот, где литкодер напишет сложный алгоритм n*log(n), где сейчас даже оно и не нужно.

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

                И тот, где "инженер" применит минимум усилий, лишь бы работало сейчас.

                Очень грамотный подход. Делаем здесь и сейчас, выдаём бизнесу результат чтобы бизнес начал зарабатывать деньги. Если высоконагруженные тесты начинают показывать проблемы, отдаём bottlenecks олимпиаднику для проработки. Он с превеликим удовольствием подберёт нужный алгоритм и вернёт обратно инженеру для имплементации в проекте. Каждый должен заниматься своим делом. Хотя, подозреваю, проблема может оказаться в архитектуре, а bottlenecks просто выскочили как прыщи-симптомы неправильной архитектуры. И невесть сколько ещё проблем выскочит, не только про производительность.


                1. qw1
                  26.06.2023 08:50
                  #25696444

                  Если высоконагруженные тесты начинают показывать проблемы, отдаём bottlenecks олимпиаднику

                  По моим наблюдениям, это "если" бывает очень не всегда. Команда разработки, работающая по принципу "и так сойдёт", не видит проблем, если страница загружается 3 секунды.
                  "Загружается же."
                  "А как вы хотели, данных-то много. Попробуйте сами вручную посчитать."
                  "Поставьте ещё 100500 серверов." (от адептов закидывания GPU и другим железом).


                  1. vedenin1980
                    26.06.2023 08:50
                    #25696738

                    не видит проблем, если страница загружается 3 секунды.

                    Если заказчик/менеджер от бизнеса не пришел c непечатной лексикой — а есть ли проблема?
                    Ну в смысле когда бизнесу реально важно — ставятся жесткие kpi по загрузке страниц, условно чтобы 99.9% страниц получило ответ от бека в течении 30-50 мс. (при сложнейшией логике рекомендательной системы). А если таких требований нет — может всем все равно? Какой-нибудь сложный отчет который делается раз в неделю вполне может грузиться секунд 30 и никого это особо может не напрягать.


                    "Поставьте ещё 100500 серверов." (от адептов закидывания GPU и другим железом).

                    Иногда это бывает выгодно бизнесу, если условно команда стоит в миллион долларов в месяц, а купить кучу новых серверов — в десять раз меньше, вместо того чтобы потратить пару месяцев на оптимизацию производтельности дешевле заплалить в 20 раз меньше и купить сервера. Просто тех.лид и бизнес должны разумно все посчитать.


                    Оптимизация ради оптимизации — плохая бизнес стратегия.


              1. Alexandroppolus
                26.06.2023 08:50
                #25696144
                +1

                сложный алгоритм n*log(n)

                Забавно, что именно в этой статье сложным оказалось как раз решение за N^3, а простым n*log(n). По всякому бывает, в общем.


  1. vasily_rozhkov
    26.06.2023 08:50
    #25692888
    +1

    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)))