Можно за один проход и без стека, просто обходить массив не с одной стороны, а идти с обоих концов
Про это решение я тоже знаю, но у меня в голове "один проход" как-то плохо сочетается с random-access к входу. Ведь сначала нам нужно прочитать весь вход в массив ("первый" проход), а потом искать в нём, используя random-access ("второй" проход).
Решение, которое я предложил, считывает по одному элементу из списка и обновляет состояние алгоритма. Суммарные требования к памяти у обоих алгоритмов примерно одинаковые (может потребоваться хранить весь вход в памяти).
А, у вас в ревью попадает код, который не компилируется и не проходит линтер?
Жаль, что вы не умеете внимательно читать то, что вам пишут.
Дано: код компилируется и проходит линтер.
Нужно: предложить полезное (!) изменение в одной (!) строке так, чтобы не нарушить инвариант в "Дано".
Очень редко можно поправить одну строку кода так, чтобы результат компилировался и не огорчал форматтер кода.
Я разве что опечатки так правлю.
В остальных случаях это просто способ оставить комментарий к части длинной строки, что является просто убогим хаком ввиду отсутствия возможности комментировать произвольный регион кода.
Например, обсуждение внезапно может не быть привязано к коду.
А вот это вообще мясо в GH. Обсуждение, не привязанное к коду нельзя склеить в один тред. Остаётся только квотить весь тред в каждом комменте, удобненько!
В Critique (помимо комментариев к кускам кода) есть специальные треды per file и один глобальные тред на весь патч.
Я прихожу на работу, открываю глагне cr/ и вижу все свои входящие и исходящие ревью. Те, что требуют моего внимания ("мяч на моей стороне"), помечены жирным. Сразу понятно, куда смотреть и что делать.
Вот посылаю я diff на ревью. Кому послать? Добрый автокомплит показывает мне наиболее подходящих кандидатов, учитывая временные зоны и отпуска. Он так же подсказывает, какие условия нужно удовлетворить до полного комплекта ревьюеров (что-то вроде "я смотрю вы не сильны в JavaScript, и ваш ревьюер тоже, добавьте эксперта, например, x@").
Если ревьюер вдруг уходит в отпуск, срабатывает линтер. Если ревью горит, можно легко найти замену через тот же автокомплит.
Если поставить пару галочек в ревью, система автоматически смёржит ваш код в мастер когда ревьюеры поставят LGTM все комментарии будут отвечены, а тесты пройдены, делая ребейз по мере необходимости (ala mergify.io, только гораздо лучше).
Весь код живёт в одном большом репозитории. Можно делать сквозные изменения в проектах нескольких команд, каждый коммит на мастере сохранит билд всех команд зелёным (за редким исключением длинных тестов, исполняемых асинхронно после коммита). Это не избавляет вас о необходимости релизить в правильном порядке, но всё равно устраняет огромное количество попоболи.
Есть куча ботов, для которой конфиги в репе являются источником правды, они автоматически обновляют состояние внешних систем так, чтобы оно соответствовало конфигам (к примеру, при изменении настроек репликации данных бот сам переложит данные туда, где они должны быть).
Недавно сделали удобное решение для Stacked Diffs ala Differential.
Об эргономике код ревью
Ключевая проблема GH для меня: на сколь нибудь серьёзных код ревью очень сложно понять, какие из комментариев остались без внимания. Как только код изменился, GH помечает комментарии как Outdated. Чтобы убедиться, что ты ничего не пропустил, нужно постоянно прыгать между вкладками и пытаться понять, изменился ли код нужным образом.
Комментирование кода в Critique работает только в "пакетном" режиме. Пишешь себе комментарии, когда просмотрел весь код, нажимаешь кнопку и все комментарии уходят разом. Это означает что
Ревьюер получит только один e-mail, а не по сообщению на каждый коммент.
Ревью-тула поймёт, что теперь теперь мяч на стороне автора, и пометит ревью жирным в его дашборде.
У ревьюера будет возможность удалить или поменять комментарии после того, как он увидит весь код (очень часто некоторые вопросы разрешаются сами собой).
У GH тоже есть "пакетный" режим, он частично решает проблемы (1) и (3), но там много странностей и багов. Например,
На странице Conversation нет возможности объединять комментарии в "пакеты". Поскольку отвечают все там, GH спаммит нотификациями.
Ответы в тредах, сделанные в "пакетном" режиме, появляются в Conversation дважды (sic!).
Поскольку треды, относящиеся к "старым версиям", исчезают из "Files Changed", на них можно отвечать только отдельно.
Все комментарии в Critique относятся к конкретному снэпшоту кода. Critique понимает алгебру патчей и показывает ваш комментарий в новых версиях кода в правильном месте.
Для сравнения, GH поднимает лапки кверху и помечает комментарий Outdated. Особо радует, когда пишешь комментарий, а автор решает сделать rebase. Отослать комментарий в GH будет нельзя: нужно скопировать текст, обновить страницу, снова найти нужное место и вставить комментарий. Удобненько.
В Critique есть удобные ползунки, которые позволяют вам видеть эволюцию версий на код-ревью, система автоматически выставляет их так, чтобы показывать только непросмотренные изменения (на GH можно выбирать отдельные отрезки коммитов для просмотра, но комментировать старые версии обычно нельзя, Viewed там тоже есть, но его нужно тыкать вручную).
В общем, у меня есть документ с двумя страницами багов и странностей GH.
Большинство предпочитает жевать кактус и делать вид, что GH является удобной системой для код-ревью, но на мой взгляд это просто Стокгольмский синдром.
Средний срок жизни разработчика в Гугле — 1 года 1 месяц.
Эта статистика верна только для Mountain View.
вот тебе небольшая зп, вот там раз в год будет бонус огромный (если пройдешь перфоманс ревью), вот тебе акции (которые сможешь получить через 5 лет).
ЗП в Google зависят от региона. В Цюрихе, к примеру, вполне можно получать 165.000 CHF на старте (что уже ощутимо выше рынка). Плюс ежегодный бонус 15-20% от зарплаты. Акции выдают не через пять лет, а каждый квартал. В сумме может запросто получится в 2 раза выше рынка уже через год.
Как правило, в больших компаниях куча своих каких-то инструментов.
Инструменты в Google такие, что индустрии до них ещё десятилетие расти. К примеру, после Critique (код-ревью тула в Google) от код-ревью на GitHub просто люто, бешено бомбит.
при переходе в другую компанию твой опыт просто обнуляется
Я бы не сказал. Умение готовить Protobuf и gRPC много где нужно. Ну и C++ в Google хороший.
Уже давно из компании добра это превратилось в галеры, где менеджеры за счет наивных разрабов решают какие-то свои задачи.
Краски сильно сгущены. Политики много, но по ночам никто не работает, и зарплаты никто не снижает.
Вот такие компании, на всяких собеседованиях относятся к тебе, как говну.
У меня такое только с Amazon было. От собеседований в Facebook и Google впечатления были очень положительные.
Яндекса
Я работал в Яндексе (в Картах), мне там очень понравилось. Много умных талантливых коллег и интересные задачи.
Например, с помощью сжатой битовой карты с поддержкой rank/select можно допольно просто отобразить табилицу-построчник на сырой байтовый массив, с возможностью произвольной навигации по с строкам
Есть JSON-парсеры, основанные на этой идее, например, hw-json.
Пишу на Rust full-time, на мой взгляд, язык это довольно нишевый, я слабо понимаю хайп вокруг него.
Писать на нём высокоуровневый (a-la Haskell) код совершенно неприятно из-за необходимости много думать о том, кто чем владеет. В Haskell всё есть value, как только в языке появляются ссылки, composability вылетает в трубу.
Писать на нём низкоуровневый код (я работаю над runtime для нативного кода полученного из Wasm, кругом адок из контекстов, mmap/mprotect и обработчиков сигналов; недавно простенький рантайм для Future написали) тоже занятие малоприятное (как минимум с точки зрения бывалого разработчика на C++ и C). Помню по началу убил часа два чтобы понять, как правильно преобразовать указатель в ссылку в одном запутанном случае (практически noop с точки зрения С++).
Реализовать многие структуры данных эффективно без unsafe у вас не получится (давно хочу взяться за реализацию HAMT которая должна побить im).
Типичный инфраструктурный код (перекладыватели байтов, интерпретаторы, компиляторы, рендереры) писать на нём относительно приятно (ADT + pattern-matching, всё что нужно человеку), вполне можно оставаться в safe-подмножестве.
Писать на Rust просто ради удовольствия я бы не стал (часто пишу для удовольствия на других языках).
Помогает отвечать на вопросы, замечать закономерности и принимать решения.
Сколько в среднем малыш спит в сутки? Сколько из этого днем?
Что-то в последнюю неделю укладывание на третий сон занимает по 40 минут. Не пора ли поменять график?
Если во второй сон малыш спит полтора часа, то с укладыванием на ночь проблемы. Надо попробовать будить пораньше.
Малыш не ходил в туалет сутки. Не пора ли дать волшебного порошка?
Можно отмечать дни «начали делать Х» и потом смотреть, решилась проблема или нет.
Особенно актуально когда малыш переходит из одних заботливых рук в другие. Да и в принципе жизнь молодого родителя — день сурка, полагаться на память бесполезно.
Мы просто отмечаем ручкой на листе бумаги (шаблона на одной странице хватает на неделю). Не только сон, но и кормления, укладывания и туалет. Это требует очень мало времени по сравнению с остальной рутиной: взял со стола ручку, поставил точку/заштриховал область.
Зато одного взгляда на страницу достаточно, чтобы понять, как прошёл день. Начали вести с четырёх месяцев, жалеем, что не начали раньше. Очень помогает.
Настоящий азиатский гик выбрал бы шаблон для одеяла заранее (с какой-нибудь вразумительной картинкой или надписью), а challenge был бы в том, чтобы укладывать малыша согласно шаблону.
Это решение работает за экспоненту по времени и памяти. Посчитайте, сколько нужно времени для входа
[4000000, 0, 4000000].Про это решение я тоже знаю, но у меня в голове "один проход" как-то плохо сочетается с random-access к входу. Ведь сначала нам нужно прочитать весь вход в массив ("первый" проход), а потом искать в нём, используя random-access ("второй" проход).
Решение, которое я предложил, считывает по одному элементу из списка и обновляет состояние алгоритма. Суммарные требования к памяти у обоих алгоритмов примерно одинаковые (может потребоваться хранить весь вход в памяти).
Что-то вроде такого
Можно решить за один проход, если использовать дополнительный стэк. Но это не самое простое решение, конечно.
Также рекомендую к просмотру: https://www.youtube.com/watch?v=ftcIcn8AmSY
Комментарий, не привязанный к коду:
Тредов не формирует, уходит в общий поток нотификаций в Conversation.
Комментарий, привязанный к коду:
Формирует тред.
Жаль, что вы не умеете внимательно читать то, что вам пишут.
Дано: код компилируется и проходит линтер.
Нужно: предложить полезное (!) изменение в одной (!) строке так, чтобы не нарушить инвариант в "Дано".
Очень редко можно поправить одну строку кода так, чтобы результат компилировался и не огорчал форматтер кода.
Я разве что опечатки так правлю.
В остальных случаях это просто способ оставить комментарий к части длинной строки, что является просто убогим хаком ввиду отсутствия возможности комментировать произвольный регион кода.
Suggestion — это такая практически бесполезная фича в которой можно предложить патч для одной строчки кода.
Комментировать конкретную строчку кода можно было давно.
Возможность комментировать несколько строк кода завезли несколько месяцев назад.
Возможность комментировать произвольный регион кода (например, кусок строки) не завезли и вряд ли завезут в ближайшее время.
Вспомнилась ещё пара интеграций Critique:
А вот это вообще мясо в GH. Обсуждение, не привязанное к коду нельзя склеить в один тред. Остаётся только квотить весь тред в каждом комменте, удобненько!
В Critique (помимо комментариев к кускам кода) есть специальные треды per file и один глобальные тред на весь патч.
Простота, эффективность и интеграция.
Взять, к примеру, ревью тул.
Я прихожу на работу, открываю глагне
cr/и вижу все свои входящие и исходящие ревью. Те, что требуют моего внимания ("мяч на моей стороне"), помечены жирным. Сразу понятно, куда смотреть и что делать.Вот посылаю я diff на ревью. Кому послать? Добрый автокомплит показывает мне наиболее подходящих кандидатов, учитывая временные зоны и отпуска. Он так же подсказывает, какие условия нужно удовлетворить до полного комплекта ревьюеров (что-то вроде "я смотрю вы не сильны в JavaScript, и ваш ревьюер тоже, добавьте эксперта, например, x@").
Если ревьюер вдруг уходит в отпуск, срабатывает линтер. Если ревью горит, можно легко найти замену через тот же автокомплит.
Если поставить пару галочек в ревью, система автоматически смёржит ваш код в мастер когда ревьюеры поставят LGTM все комментарии будут отвечены, а тесты пройдены, делая ребейз по мере необходимости (ala mergify.io, только гораздо лучше).
Весь код живёт в одном большом репозитории. Можно делать сквозные изменения в проектах нескольких команд, каждый коммит на мастере сохранит билд всех команд зелёным (за редким исключением длинных тестов, исполняемых асинхронно после коммита). Это не избавляет вас о необходимости релизить в правильном порядке, но всё равно устраняет огромное количество попоболи.
Есть куча ботов, для которой конфиги в репе являются источником правды, они автоматически обновляют состояние внешних систем так, чтобы оно соответствовало конфигам (к примеру, при изменении настроек репликации данных бот сам переложит данные туда, где они должны быть).
Недавно сделали удобное решение для Stacked Diffs ala Differential.
Об эргономике код ревью
Ключевая проблема GH для меня: на сколь нибудь серьёзных код ревью очень сложно понять, какие из комментариев остались без внимания. Как только код изменился, GH помечает комментарии как Outdated. Чтобы убедиться, что ты ничего не пропустил, нужно постоянно прыгать между вкладками и пытаться понять, изменился ли код нужным образом.
Комментирование кода в Critique работает только в "пакетном" режиме. Пишешь себе комментарии, когда просмотрел весь код, нажимаешь кнопку и все комментарии уходят разом. Это означает что
У GH тоже есть "пакетный" режим, он частично решает проблемы (1) и (3), но там много странностей и багов. Например,
Все комментарии в Critique относятся к конкретному снэпшоту кода. Critique понимает алгебру патчей и показывает ваш комментарий в новых версиях кода в правильном месте.
Для сравнения, GH поднимает лапки кверху и помечает комментарий Outdated. Особо радует, когда пишешь комментарий, а автор решает сделать rebase. Отослать комментарий в GH будет нельзя: нужно скопировать текст, обновить страницу, снова найти нужное место и вставить комментарий. Удобненько.
В Critique есть удобные ползунки, которые позволяют вам видеть эволюцию версий на код-ревью, система автоматически выставляет их так, чтобы показывать только непросмотренные изменения (на GH можно выбирать отдельные отрезки коммитов для просмотра, но комментировать старые версии обычно нельзя, Viewed там тоже есть, но его нужно тыкать вручную).
В общем, у меня есть документ с двумя страницами багов и странностей GH.
Большинство предпочитает жевать кактус и делать вид, что GH является удобной системой для код-ревью, но на мой взгляд это просто Стокгольмский синдром.
К счастью, требуется оно примерно также часто как
unsafeв Rust.Эта статистика верна только для Mountain View.
ЗП в Google зависят от региона. В Цюрихе, к примеру, вполне можно получать 165.000 CHF на старте (что уже ощутимо выше рынка). Плюс ежегодный бонус 15-20% от зарплаты. Акции выдают не через пять лет, а каждый квартал. В сумме может запросто получится в 2 раза выше рынка уже через год.
Инструменты в Google такие, что индустрии до них ещё десятилетие расти. К примеру, после Critique (код-ревью тула в Google) от код-ревью на GitHub просто люто, бешено бомбит.
Я бы не сказал. Умение готовить Protobuf и gRPC много где нужно. Ну и C++ в Google хороший.
Краски сильно сгущены. Политики много, но по ночам никто не работает, и зарплаты никто не снижает.
У меня такое только с Amazon было. От собеседований в Facebook и Google впечатления были очень положительные.
Я работал в Яндексе (в Картах), мне там очень понравилось. Много умных талантливых коллег и интересные задачи.
Есть JSON-парсеры, основанные на этой идее, например, hw-json.
Статья с детальным описанием идеи semi-indices: https://www.researchgate.net/publication/221613393_Semi-indexing_semi-structured_data_in_tiny_space
Вообще говоря, звучит неоднозначно.
Так кажется только тем, кто не пробовал писать реальные вещи на Haskell. На Haskell легко и приятно писать код, который выглядит императивно.
Пишу на Rust full-time, на мой взгляд, язык это довольно нишевый, я слабо понимаю хайп вокруг него.
Писать на нём высокоуровневый (a-la Haskell) код совершенно неприятно из-за необходимости много думать о том, кто чем владеет. В Haskell всё есть value, как только в языке появляются ссылки, composability вылетает в трубу.
Писать на нём низкоуровневый код (я работаю над runtime для нативного кода полученного из Wasm, кругом адок из контекстов, mmap/mprotect и обработчиков сигналов; недавно простенький рантайм для Future написали) тоже занятие малоприятное (как минимум с точки зрения бывалого разработчика на C++ и C). Помню по началу убил часа два чтобы понять, как правильно преобразовать указатель в ссылку в одном запутанном случае (практически noop с точки зрения С++).
Реализовать многие структуры данных эффективно без unsafe у вас не получится (давно хочу взяться за реализацию HAMT которая должна побить
im).Типичный инфраструктурный код (перекладыватели байтов, интерпретаторы, компиляторы, рендереры) писать на нём относительно приятно (ADT + pattern-matching, всё что нужно человеку), вполне можно оставаться в safe-подмножестве.
Писать на Rust просто ради удовольствия я бы не стал (часто пишу для удовольствия на других языках).
Да, я тоже сразу подумал об этой статье в Кванте.
Помогает отвечать на вопросы, замечать закономерности и принимать решения.
Можно отмечать дни «начали делать Х» и потом смотреть, решилась проблема или нет.
Особенно актуально когда малыш переходит из одних заботливых рук в другие. Да и в принципе жизнь молодого родителя — день сурка, полагаться на память бесполезно.
Мы просто отмечаем ручкой на листе бумаги (шаблона на одной странице хватает на неделю). Не только сон, но и кормления, укладывания и туалет. Это требует очень мало времени по сравнению с остальной рутиной: взял со стола ручку, поставил точку/заштриховал область.
Зато одного взгляда на страницу достаточно, чтобы понять, как прошёл день. Начали вести с четырёх месяцев, жалеем, что не начали раньше. Очень помогает.
Настоящий азиатский гик выбрал бы шаблон для одеяла заранее (с какой-нибудь вразумительной картинкой или надписью), а challenge был бы в том, чтобы укладывать малыша согласно шаблону.