Как проходят алгоритмические секции на собеседованиях в Яндекс

А меньшинство туда пишет.

Самые страшные яды

Метиловая от изопропиловой отличается за секунду по запаху.
Метиловая от любой другой отличается с расстояния метров 5 по цене.

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

Все все знают. Не надо заниматься казуистикой.

Самые страшные яды

Метанол продается на всех обочинах страны. Оптом.

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

Честное резюме программиста

Работать в почте/мессенджерах/переговорках. Вместо IDE.

Честное резюме программиста

А лучше — идти из программирования в менеджеры.

Заниматься нелюбимой работой чтобы получать меньше денег?
Вы это серьезно?

Мы включили TLS 1.3. Почему вам стоит сделать то же самое

Бинарники без исходников? Это все что делается для включения в RFC?
Вы полностью заслужили не включения в tls1.3

Работать надо, а не изображать бурную деятельность и переживания.

Мы включили TLS 1.3. Почему вам стоит сделать то же самое

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

Таблица Менделеева на школьной информатике

А где водятся студенту первокурсники способные массово (ну хотя бы каждый второй в группе) решать такие задачки?

С виду уровень для массовых первокурсников просто неподъемный.

Алгоритм сортировки строк

Вы все это серьезно пишите? Я привел и написал самый оптимальный алгоритм попарного слияния массивов разного размера. Алгоритмически ничего лучше сделать нельзя. Computer science точная наука.

Ссылки на структуры копируются, а иногда создаются или уничтожаются. Так компьютеры работают. А языки эти действия описывают словами add, remove итд. Так человеку понятнее и удобнее.

Как под руку попадется выгоды не даст. Работа с кучей это logn от размера кучи. Потери на неправильном слиянии это n в степени сколько массивов осталось слить. Где n это разница в количестве элементов в слитом массиве оптимального размера и не оптимального. Цена ошибки слишком велика. Честно выбирать массивы для слияния выгоднее и результат будет стабильнее.

Выбирать массивы для слияния не по количеству элементов в них, а по занимаемому объему? Вы это серьезно? Если в вашу сортировку запихнуть объекты картинки (которые имеют размер от 10кб до 10мб) и отсортировать их по имени (корректный компаратор прилагается) ваш алгоритм слияния массивов выдаст полную чушь.

Видимо дискуссию пора заканчивать. Мы вам написали 2 реализации. Независимые, на разных языках. Они оказались хуже всех типовых алгоритмов. Вы свою реализацию не даете. Похоже она еще хуже чем мы написали. О чем дальше говорить непонятно.

Алгоритм сортировки строк

Все ровно по описанию. Когда пассивных воронок больше чем указанное ограничение сливаем 3/4 из них. Я тестировал на 1000.

Слияние самое быстрое из возможных.
1. Достать и удалить из кучи минимальный по количеству элементов массив.
2. Снова достать и удалить из кучи минимальный по количеству элементов массив.
3. Сливаем эти два массива.
4. Результат слияния добавляем в кучу.

Для попарного слияния разноразмерных массивов это лучший алгоритм из всех возможных в теории.

Код понятнее. Вы без кода уже написали страниц 10 текста. А могли бы вместо этого выложить ~100 строк кода.

Алгоритм сортировки строк

Мне было проще написать сразу для любого размера воронки. Хотите один? Передайте в параметрах 1 и будет один.

А какая разница что именно сортируем? Передаем компаратор и сравниваем элементы им. Пусть вызывающий код побеспокоиться как сравнивать элементы которые ему надо отсортировать.

Цикл по элементам выше, в кусок не включил. Вы просили кусок кода как элемент попадает в воронку. Ну я и привел кусок кода для одного элемента. Этот код выполняется для каждого элемента.

addFirst, addLast — добавление элемента в начало или конец очереди. O(1).
new — создание новой воронки.
remove — просто перекидывание коллекции из активных воронок в пассивные.

Я не знаю куда уж проще, чем я написал.

Алгоритм сортировки строк

Я все исходники выложил сразу. Там всего 80 строк сама сортировка. Неужели так сложно посмотреть было?

Добавление в воронки

public List<Integer> sort(List<Integer> arr, int runCrater, int passiveCrater, StrangeComparator strangeComparator) {
//skip init
            for (int i = 0; i < curLists.size(); ++i) { //перебор всех воронок
                if (strangeComparator.compare(num, curLists.get(i).getFirst()) <= 0) { //добавляем в начало

                    curLists.get(i).addFirst(num);

                    added = true;
                    break;
                } else {
                    if (curLists.get(i).size() == 1 || strangeComparator.compare(num, curLists.get(i).getLast()) >=0) {//добавляем в конец

                        curLists.get(i).addLast(num);

                        added = true;
                        break;
                    }
                }
            }
            if (!added) { //никуда добавить не смогли. Создаем новую воронку, если надо убираем старую воронку и сливаем пассивные воронки
                if (curLists.size() > runCrater) {
                    Deque<Integer> tmp = curLists.remove(curLists.size() - 1);
                    finalLists.add(tmp);
                }

                if (finalLists.size() > passiveCrater) {
                    merge(finalLists, false);
                }

                Deque<Integer> newList = new ArrayDeque<>();
                newList.add(num);
                curLists.add(newList);
            }
}

Алгоритм сортировки строк

Я понял почему у вас так медленно получилось.
unshift для массивов работает очень медленно. Похоже что он O(n) стоит. Тест.

Перепишите на список с добавлением в начало за O(1) и сразу гораздо лучше станет.

Алгоритм сортировки строк

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

На вход и на выход поступают коллекции. Чтения и записи нет.

Чтение

    public List<Integer> sort(List<Integer> arr, int runCrater, int passiveCrater, StrangeComparator strangeComparator) {
        for (int i1 = 0; i1 < arr.size(); i1++) {
int num = arr.get(i1); //"прочитали"

Запись

return new ArrayList<>(finalLists.poll()); //"записали"

Алгоритм сортировки строк

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

merge2Lists

Версия уже с компаратором.

    private Deque<Integer> merge2Lists(Deque<Integer> a, Deque<Integer> b) {
        Deque<Integer> c = new ArrayDeque<>();

        while (a.size() > 0 || b.size() > 0) {

            if (a.size() == 0 || b.size() == 0) {
                c.addAll(b);
                c.addAll(a);
                break;
            }

            if (strangeComparator.compare(a.getFirst(),b.getFirst()) < 0) {
                c.add(a.getFirst());
                a.removeFirst();
            } else {
                c.add(b.getFirst());
                b.removeFirst();
            }

        }
        return c;
}

Алгоритм сортировки строк

Чуть выше я выкладывал компаратор. Он ну настолько типовой что я даже не знаю что тут еще написать можно.

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

Алгоритм сортировки строк

Попугаи. Там все в циклах много раз гоняется. Чтобы ошибки измерения или особенности входных данных не влияли. Код посмотрите уже. Все понятно же.

Алгоритм сортировки строк

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

Алгоритм сортировки строк

В проекте всего 5 классов. Найдите как-нибудь. Это несложно. Подсказка: класс StrangeSort вам поможет.

В проект добавил кастомный, специально сильно замедленный компаратор. Мне не сложно.

И sdk и воронка сорт сделал через него. Это достаточно точный симулятор медленного сравнения объектов. Исходники обновлены.

Результаты сблизились. Но sdk по прежнему быстрее.

Результаты с очень медленным компаратором

runCrater=1
TEST SMALL ARRAY SIZE=50
SDK TIME = 492
CRATER TIME = 698
-206
TEST MEDIUM ARRAY SIZE=150
SDK TIME = 2020
CRATER TIME = 2775
-754
TEST BIG ARRAY SIZE=1000
SDK TIME = 19697
CRATER TIME = 25575
-5878
…
более большие массивы с таким медленным компаратором ушли в даль и не вернулись
тенденция и так понятна
…

Вывод: На очень медленных компараторах воронка сорт не сильно проигрывает типовым алгоритмам сортировки. Примерно раза в 1.5

Компаратор

public class StrangeComparator<Integer> implements Comparator<Integer> {

    @Override
    public int compare(Integer o1, Integer o2) {
        try {
            Thread.sleep(1);
        } catch (InterruptedException e) { }

        return (int)o1 - (int)o2;
    }
}

Алгоритм сортировки строк

Без проблем. Результаты ровно такие же.
Больше воронок — ближе к квадрату.
Меньше воронок — ближе к плохонькому логарифму.
Merge sort лучше в разы.

Результаты 10_000_000

runCrater=1
TEST ARRAY SIZE=10_000_000
SDK TIME = 11232
CRATER TIME = 34662
-23429

runCrater=10
TEST ARRAY SIZE=10_000_000
SDK TIME = 11966
CRATER TIME = 36428
-24462

runCrater=100
TEST ARRAY SIZE=10_000_000
SDK TIME = 11535
CRATER TIME = 61468
-49933

runCrater=1000
TEST ARRAY SIZE=10_000_000
SDK TIME = 10834
CRATER TIME = 247625
-236790

Измерения проводятся в попугаях, разные тесты друг с другом сравнивать нельзя. Результаты корректы только в пределах одного теста.