• Примитивно-рекурсивные функции и функция Аккермана
    0

    Спасибо, это очень круто! Я не знал раньше об этом свойстве функции Гудстейна.

  • Пережили 2020-й? Готовимся к 2021-му: Яндекс спросил разработчиков о будущем IT-индустрии
    0

    Меня нанимали прямо во время пандемии. Летом 2020-го.


    Но это довольно типично как минимум для биг-теха (и поэтому я думаю, что это скорее правильно, чем нет). Если я много писал на С++ и использовал много разных фреймворков, скорее всего, я смогу освоиться с C# и другими фреймворками. Ну и наоборот.

  • Пережили 2020-й? Готовимся к 2021-му: Яндекс спросил разработчиков о будущем IT-индустрии
    0

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


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


    Грубо говоря, GDBT — это очень хорошо, но в современных реалиях стоит уметь и в BERT. А уж сколько всего сменилось за десять лет в ML, во фронтенде, в облаках, в бекенде — и не перечислить.


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


    При найме уж слишком много внимания уделять конкретной технологии не стоит по той же причине и хорошие компании уже давно так не делают. Опыт адаптации под новые условия важнее, чем умение использовать конкретный фреймворк. Я много лет программировал на C++ и Python, а теперь в основном пишу на Golang в драматически новом окружении и чувствую себя прекрасно. Те, кто меня нанимал, понимал, что человеку с опытом освоиться на новом стеке вполне возможно за небольшое время — так и произошло.

  • На пути к индивидуальному образованию: анализ данных Яндекс.Репетитора
    0

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


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


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

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

    Вполне. Я сейчас написал вот так и зашло с очень хорошим запасом:


    package main
    
    import (
        "bufio"
        "fmt"
        "os"
        "strconv"
    )
    
    func main() {
        scanner := bufio.NewScanner(os.Stdin)
        last := 0
    
        scanner.Scan()
        count, _ := strconv.Atoi(scanner.Text())
        for i := 0; i < count; i++ {
            scanner.Scan()
            current, _ := strconv.Atoi(scanner.Text())
            if i == 0 || last != current {
                fmt.Println(current)
            }
            last = current
        }
    }
  • На пути к индивидуальному образованию: анализ данных Яндекс.Репетитора
    0

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

  • На пути к индивидуальному образованию: анализ данных Яндекс.Репетитора
    0

    Вы совершенно правильно всё пишете! Такая проблема вполне может возникнуть. Мы это регулируем тем, что оптимизируем вероятность хорошего решения целикового экзамена, в котором представлены разные темы. Но вообще надо отдельно это проверить, вы совершенно правы.

  • Агломеративная кластеризация: алгоритм, быстродействие, код на GitHub
    +1

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


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

  • Оценка качества кластеризации: свойства, метрики, код на GitHub
    0

    Есть два важных класса метрик, которые я не рассматривал :) При этом они упоминаются в цитирующейся статье.


    Это информационные метрики на основе энтропии (к этому классу относится описанная вами) и метрики на основе edit distance. В цитируемой статье оба класса коротко рассматриваются, основной проблемой является то, что для них не выполнено условие Rag Bag.


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

  • Оценка качества кластеризации: свойства, метрики, код на GitHub
    0

    Если я всё правильно понял, это BCubed Precision. Для отдельного элемента BCP равняется в точности вероятности того, что другой случайный элемент из того же кластера относится к тому же эталону, что и выбранный элемент, а интегральный показатель — простое усреднение, эквивалентное равновероятному выбору элементов.


    Эта метрика очень хорошая, но учитывает только точность соответствий, но не полноту, так что не может использоваться изолированно.

  • Леммы о разрастании для регулярных и контекстно-свободных языков
    0

    Вот спасибо! Я писал про то, что один из символов не попадёт в часть, которая подвергается итерации, поэтому количества вхождений различных символов будут различными для $k>1$, но далее выразил эту мысль неаккуратно. Сейчас исправил =)


    И опечатку тоже.

  • Леммы о разрастании для регулярных и контекстно-свободных языков
    0
    Тут очень много интересных связей с другими вопросами, и я понял, что даже простое их упоминание увеличит объём статьи раза в два. Так то пришлось отсекать)
  • Какие алгоритмы разработчики Яндекса реализовывают каждый день
    +2
    Ну я так скажу: иногда стоит немного обобщить и вынести в библиотеку, а иногда не стоит, т.к. для каждого использования придётся как-то докручивать, и это превратит жизнь в ад. Бывает так, что простые вещи проще реализовать по месту.

    Приведу другой пример, но очень похожий. За свою жизнь мне пришлось несколько раз реализовывать [DSU](https://en.wikipedia.org/wiki/Disjoint-set_data_structure). При этом, конечно, у нас есть библиотечная реализация DSU, которую я всякий раз пытался использовать, но не получалось. Дело в том, что всякий раз вместе с каждой операцией надо было делать что-то ещё, что не ложилось в стандартный интерфейс структуры. Теоретически, это можно было бы сделать через наследование и какие-то доопределения, но в таких случаях сложность реализации значительно превосходила сложность реализации собственно DSU, плюс терялась локальность кода, плюс местами появлялись сайд-эффекты. Всякий раз я смотрел на это, немного грустил и реализовывал по месту (благо, на написание DSU уходит примерно 2 минуты с ноля). К счастью, штука простая и немногословная, так что структура с добавленной в неё DSU'шностью содержала, типа, 5% кода про DSU и 95% про остальное.

    Ну и фактор времени надо учитывать. Если пытаться обобщать и класть в библиотеки вообще всё, что мы пишем, скорость разработки упадёт, наверное, раз этак в пять. Даже если оставить за скобками конкурентность среды, реализовать в 5 раз меньше классных штук за жизнь не устраивает даже лично меня!
  • Какие алгоритмы разработчики Яндекса реализовывают каждый день
    0
    Ура! Спасибо! :) Так действительно не нужно делать массовых сдвигов и не нужно обрабатывать коллизии за счёт того, что выбранные элементы отправляются в конец массива, это корректный алгоритм!

    Но требуется знать размер заранее и требуется изменять входные данные — т.е. для потоковой обработки всё-таки не подходит.
  • Какие алгоритмы разработчики Яндекса реализовывают каждый день
    0
    Если единичек больше, чем ноликов — будем чаще проваливаться в одну ветку алгоритма; если наоборот — в другую. Заранее не знаешь, какой вариант выгоднее.

    Мне нравится вариант с обновлением в ветке про единичку, потому что в таком случае не возникает корнер-кейса с обработкой последнего элемента.
  • Какие алгоритмы разработчики Яндекса реализовывают каждый день
    0
    Давай ты напишешь код, который имеешь в виду? И его предметно обсудим. А то так обсуждение довольно непонятное. Код из статьи гарантированно работает за линию, проходит по данным один раз и использует O(K) дополнительной памяти, это всё, что нужно.
  • Какие алгоритмы разработчики Яндекса реализовывают каждый день
    0
    1 — Пусть мы знаем N и алгоритм таков: выбрать случайный номер от 1 до N, взять элемент с этой позиции, повторить K раз. Но тут нужно реализовать выбор без повторений: если я выбрал элемент с первой позиции, я не могу выбрать его ещё раз. Так что при повторе выбранной случайно позиции (коллизии) мне надо будет либо выбирать случайное число ещё раз, либо программировать собственно выбор без повторений: при выборе числа k пройтись по массиву и взять k-е ещё не выбранное число. Оба способа работают за в среднем линейное время, так что по итогу алгоритм окажется квадратичным.

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

    3 — Это в любом случае на разных этапах происходит. Как правило, платят за клики, а не за показы.
  • Какие алгоритмы разработчики Яндекса реализовывают каждый день
    0
    Можно, но осторожно. Я в видео разбирал способ неправильно воспользоваться counter'ом.
  • Какие алгоритмы разработчики Яндекса реализовывают каждый день
    +1
    Это тоже вариант, но есть несколько подвохов.
    1. Если K сравнимо по величине с длиной массива, придётся часто сталкиваться с коллизиями: будем выбирать тот номер, что уже был выбран и перебрасывать кубик. В среднем там квадратичный алгоритм получается.
    2. Нужно знать N заранее. Тогда надо либо все данные читать два раза (а это может быть дорого — вдруг их терабайт?), либо ограничивать работоспособность алгоритма только данными, которые влезают в память. Если работаешь на MapReduce — у тебя как правило нет ни одной, ни второй возможности. Нужно реализовать за один проход и при этом не знать полную длину входных данных.
  • Как я впервые стримил университетскую лекцию
    0
    Сейчас я пользуюсь ms whiteboard, встроенной в sufrace, и ужасно доволен)
  • Стратификация, или как научиться доверять данным
    0
    Всё верно :)
  • Стратификация, или как научиться доверять данным
    0
    Они не связаны, более того — они by design являются результатами независиммых измерений. Скажем, для кросс-валидации — результатами независимо проведённых кросс-валидаций с разным seed'ом разбиения. Мне кажется, что такой график хорошо показывает и среднее, и дисперсию.
  • Стратификация, или как научиться доверять данным
    +1
    Это графики вариационных рядов. Берём все полученные значения (например: прогнали CV 100 раз, получили 100 значений), сортируем их в порядке неубывания, выводим на график. Т.е. по оси X — порядковый номер величины в вариационном ряду.
  • Игры с нулевой суммой и условия Каруша-Куна-Таккера
    0
    Задача второго игрока — минимизировать собственный проигрыш, который в точности равен выигрышу первого игрока. (Ap, q) — это как раз и есть выигрыш первого игрока! Поэтом замена равновесной стратегии второго игрока будет эту величину увеличивать.
  • Как я впервые стримил университетскую лекцию
    0
    Можно! Но у меня её нет и я не уверен, что она мне нужна :)
  • Как я впервые стримил университетскую лекцию
    0
    У меня на курсе нет лабораторок в виде очных занятий. По большей части мы используем задачки с leetcode.com и подобных ресурсов, на которых можно проверять решения автоматически. Решения потом студенты коммитят в GitHub, и мы их автоматом же анализируем на списывание и прочее. Так работает уже много лет, и дистанционность обучения совсем не играет никакой роли.

    Ещё раньше я заводил задачки в некоторый аналог Яндекс.Контеста, но потом оказалось, что использовать открытые платформы существенно легче.
  • Примитивно-рекурсивные функции и функция Аккермана
    0
    Эта функция не будет относиться к ПРФ, т.к. она строго больше функции Аккермана, и поэтому для неё не выполнятся свойство из пункта 4.
  • Примитивно-рекурсивные функции и функция Аккермана
    +2
    Да, такая функция будет расти, конечно, быстрее :)

    Вообще, действительно, придумать быстрорастущую функцию — не rocket science. Тут вся суть утверждения в том, что ПРФы в принципе не способны расти сколь угодно быстро.

    Ну а ещё для нас важно, что функция Аккермана растёт быстро, потому что это значит, что обратная к ней функция растёт медленно. И этим обосновывается «почти константная» асимптотика методов DSU.
  • «Это тоже анализ данных». Разговор о биоинформатике с Михаилом Гельфандом
    +3

    Ура! Рад, что понравилось :)

  • Разбор квалификации чемпионата по программированию среди бэкенд-разработчиков
    0
    Числа, которые встретятся в игре, написаны на карточках. Там могут быть, вообще говоря, любые числа в любом порядке.
  • Разбор квалификации чемпионата по программированию среди бэкенд-разработчиков
    +1
    Ей ведь нужно определить не единственного победителя, а кандидатов в победители :) Другими словами — участников финала.
  • Как мы научились предсказывать запрос пользователя и ускорили загрузку поисковой выдачи
    0
    Когда человек ввёл слово, он хочет автоматический пробел. Не увидев его, он начнёт вводить пробел самостоятельно, а это лишнее действие и затраты времени. Неудобно.

    Подсказки тоже нужно показывать для запроса с пробелом, иначе там будет много нерелевантного.
  • Как мы научились предсказывать запрос пользователя и ускорили загрузку поисковой выдачи
    +4
    Это вопрос архитектуры. Мобильные приложения тяжело обновлять, часть из них всегда будет старых версий и так далее, поэтому на сервер хочется перенести настолько много логики, насколько это возможно. В частности, мы можем однажды начать ранжировать на общих основаниях сразу несколько подсказок, часть из которых с пробелом, а часть без, и в текущей архитектуре это легко внедрить на серверной стороне. Если же реализовать какую-то логику работы с пробелами на клиенте, нам будет очень сложно что-то изменить.
  • Как устроены процессы разработки в различных компаниях
    0
    Пока нет. Приезжайте к нам в Москву! :)
  • Как проходят алгоритмические секции на собеседованиях в Яндекс
    0
    Обсуждали выше: я специально упростил входные данные, чтобы можно было особо не задумываться о вводе/выводе, а сосредоточиться на алгоритме.
  • Как проходят алгоритмические секции на собеседованиях в Яндекс
    –1
    Это же общая секция, она у всех примерно одинаково устроена. По тому, как кандидат с ней справляется, часто можно понять, он скорее junior или скорее senior, но вообще для этого и другие секции используются — архитектура, например.
  • Как проходят алгоритмические секции на собеседованиях в Яндекс
    0
    Именно так, да. Я сильно упростил входные данные, чтобы с ними совершенно точно никаких проблем не возникало и можно было бы сосредоточиться на алгоритме.
  • Как проходят алгоритмические секции на собеседованиях в Яндекс
    –24
    Компания считает, что навык алгоритмического программирования важен для разработчиков и публикует материалы, позволяющие разработчикам развивать навыки алгоритмического программирования. Что не так в этой позиции?

    Я совершенно не согласен с тем, что наши задачи — синтетические. Такой же код постоянно приходится писать для продакшена, каждый день. Нужно уметь использовать циклы, if'ы, иногда рекурсию, ассоциативные массивы; нужно использовать их своевременно и не допускать при этом ошибок. Что из этого не относится к работе разработчика? :)

    Ваши аргументы скорее подойдут к задачам-головоломкам, но мы не даём таких задач на алгоритмических секциях.
  • Как проходят алгоритмические секции на собеседованиях в Яндекс
    –9
    Тесты нужно заранее придумать, а их качество зависит от того, насколько разработчик может предугадать проблемные для алгоритма ситуации. Этот же навык проверяется и в ходе алгоритмической секции. Так что тут нет противоречия.

    Когда я пишу о проверке с трассировкой, я имею в виду, например, такие ситуации, как off-by-one error в количестве итераций цикла. Да, такую ошибку очень легко установить трассировкой, но намного лучше уметь заметить её просто взглянув на код. Ещё лучше вообще не допустить :)
  • Как Яндекс изменил Поиск за прошедший год. Обновление «Андромеда»
    0
    Я не пользуюсь блокировщиками :)

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