Расскажу немного о себе
Я являюсь действующим PHP middle разработчиком в одной средней компании. Занимаемся разработкой highload микросервисов в B2B сфере. Клиентами являются крупные интернет-магазины, в 5 странах (РФ в их числе), которые на слуху у каждого. Суммарно обрабатываем около 50к запросов в секунду, храним миллиарды записей и отвечаем за качество и жизнеспособность около тысячи интернет-магазинов. В команде я являюсь единственным PHP разработчиком. При том, что все ключевые сервисы написаны на PHP, с итальянскими нотками (наш любимый аля‑спагетти код).
Имею опыт в техническом собеседовании, в том числе и других middle php разработчиков. За свою карьеру провёл пару десятков таких собеседований, по результатам которых было нанято около 5 разработчиков и 2 аутсорс компании. (это происходило на предыдущей работе)
Почему ВК?
Текущая работа меня по большей части устраивает. Но на HH и хабр карьере держу резюме в статусе «рассмотрю предложения». В основном, чтобы мониторить актуальное положение на рынке.
HR из вконтакте меня нашли самостоятельно и сами со мной связались. На выбор было предложено 3 вакансии с рассмотрением middle php программиста. Однако, выбор на текущем этапе делать было не обязательно, так как технические интервью проводятся общими для всех.
Также, мне сразу же сообщили, что первичный этап «собеседование с HR» мы можем пропустить, так как они связались со мной сами. Далее, предполагается техническое интервью, с обзором теоретических знаний и лайвкодингом. (Сколько в последствии может быть таких этапов, не уточнялось)
Организация
К организации процесса найма у меня вопросов практически нет. Здесь всё правда было хорошо. В течение суток была согласована дата и время проведения технического интервью, были отправлены соответствующие ссылки. Интервьюеры подключились вовремя. Со стороны HR было напутствие по формату собеседования и укрупнённым темам, к которым можно подготовиться.
Несмотря на обещанный фидбек в течение 2-3 дней, пришлось напоминать HR об этом самостоятельно через неделю. Но с моей точки зрения - это вполне себе простительно.
Моя подготовка
Особо много времени уделено подготовке не было. Освежил в памяти самые известные паттерны разработки, быстро пробежался по основным угрозам безопасности. На практике, отражение атак достигается обычным здравым смыслом.
Как это вижу я
SQL инъекции - просто не нужно класть сырой ввод пользователя в SQL запрос. Валидацию никто не отменял. Добавить туда prepared statements и инъекции не страшны
DDoS атаки - проводить нагрузочное тестирование продукта. Рассчитывать 5x-10x увеличение запросов от текущих средний показателей RPM. НЕ ДЕЛАТЬ ЗАПРОСЫ К БД В ЦИКЛЕ!
XSS атаки - снова валидация пользовательского ввода, html escape
Ну и совсем очевидное - хеширование паролей, надёжное хранение секретных ключей, разграничение прав и доступа к БД.
Больше всего подготовки уделил изучению особенностей KPHP - PHP диалекта, на котором ведётся основная разработка в ВК. Изучал принципы его работы, компиляцию в C++, и связанные с этим особенности.
Техническое интервью
Здесь меня сбили с толку буквально с самого начала. Интервью началось с вопроса о том, на основе какого ЯП мне удобнее всего будет проводить интервью (мы же вроде на PHP разработчика подавались, нет?).
Подтвердив, что я действительно хочу проводить интервью на основе PHP, я слышу первый вопрос: что такое указатели? Немая сцена, занавес.
Здесь я судорожно пытаюсь вспомнить свои эксперименты с C++ в университете, и то как указатели связаны с памятью. Указываю интервьюеру, что указателей в PHP не завезли, рассказываю про ссылки и принципы работы с ними. Этот ответ интервьюера судя по всему не удовлетворил.
Следующим этапом стала игра "угадай значение термина". Вопрос: что такое "О-нотация". Я отвечаю, что не знаю, прошу подсказать о чём вообще идёт речь. В итоге оказывается, что это про сложность алгоритмов, на что я полно и развёрнуто отвечаю, вспоминая даже сколько байт весит каждый тип переменной и про сложность лучших и худших случаев пузырька.
Сильно выбесил такой формат. Я мог десятки раз работать или реализовывать тот, или иной подход, но я просто не знаю тот вариант терминологии, который задаёт интервьюер. Собеседование начинает скатываться в викторину, причём подсказки даются не всегда.
Следующую часть я назову "вопросы стажёру". Можете закидать меня тапками, но нет, я не помню, чем бинарный поиск отличается от линейного, не помню по какому принципу там эти деревья строятся, я не помню как работает хеш-таблица, и что такое очередь с приоритетом. Нет, мне ни разу не пригодились эти знания за суммарные 4 года решения задач для бизнеса и 2 года работы мидлом.
На этапе вопросов с БД, всё было очевидно и хорошо. В этой теме у меня нет никаких препятствий, могу рассказать и про типы индексов с их use-case, и про уровни изоляции транзакций с разницей между ними, и про оптимизацию производительности, с партицированием, шардированием, репликацией, и про прикладное использование подхода CQRS. Рассказал также про аналитические СУБД, особенности работы с Clickhouse, работу с движком поиска Elasticsearch, кеши редиса. Все эти темы были выстраданы практическим опытом и прикладными решениями, помогающими бизнесу работать и быть эффективным.
В заключение теоретической части были вопросы про работы сетей и безопасность. Снова срезался на терминологии. Я - тот кто настраивал на сервере ssl шифрование через certbot-а, устанавливал локальную сеть на основе DHCP сервера с распределением IP, писал bash скрипты и линуксовых демонов, не знал что ответить на вопрос: что такое DNS?
Завершилось техническое интервью 10 минутной сессией лайвкодинга, в виде скопированной алгоритмической задачи из leetcode, и оптимизацией решения. К этому у меня особо претензий пожалуй нет, если смотреть на лайвкодинг со стороны проверки софтскиллов, на взаимодействие с интервьюером и показом принципов мышления и решения задач.
Чего на интервью не было?
Совершенно не было вопросов про их диалект KPHP. Здесь были вопросы интервьюеру с моей стороны, про то, как он взаимодействует с последними версиями PHP и режимом use-strict, а также пару вопросов про подкапотное преобразование в C++.
Что больше всего удивило - полное отсутствие вопросов про паттерны разработки, про архитектурные подходы и методологии проектирования. Не было вопросов про оптимизацию и решения около-бизнесовых кейсов. Не было вопросов про системы контроля версий. Не было упоминания методологий процесса разработки и стратегического планирования развития продукта. Даже unix системы не упомянули.
Как собеседовал я?
Как уже упоминал в начале текущей статьи, мне также доводилось проводить собеседования на позицию middle php разработчиков.
Мне искренне непонятен смысл «прогона» по теории и формат викторины. Моё собеседование выглядело как разбор около‑бизнесового кейса. Давалась проблема, разработчику предлагалось предоставить пути для её решения. В процессе интервью между нами шёл диалог, в результате которого можно было как уходить «вбок», углубляясь в прикладные знания того, или иного обсуждаемого аспекта, так и узнавать напрямую потенциальные решения, а главное пути, по которым разработчик планирует их достигать. В процессе такого диалога, мне хватало получаса, чтобы узнать:
Какие у человека софт‑скиллы? Может ли он обсуждать решение задачи, способен ли на кооперацию, готов ли отстаивать собственное мнение?
Сработаемся ли мы с человеком по характеру, как он себя ведёт в ситуациях, когда ему необходимо найти решение?
Понимает ли человек что‑то в обсуждаемом вопросе? Или его готовили к «викторинам» на курсе «войти в айти».
Был ли у разработчика реальный опыт работы, и понимает ли он как решать прикладные задачи, которые (сюрприз!) ему предстоит решать у нас, в случае успешного трудоустройства.
За полчаса, не тратя ни своё время, ни время кандидата, я с уверенностью мог дать ответ: Да, или Нет. И по моему скромному мнению — это должно быть единственной целью хорошего интервью. Единственного технического интервью.
Что в итоге?
В итоге, через неделю, по запросу фидбека, мне пришёл ответ, что со мной было приятно общаться, но ищут кандидата с более углублёнными знаниями (знаниями чего?).
Резюмируя: на собеседовании на позицию middle php разработчика, в VK ищут не middle, не PHP, и даже не уверен, что разработчика.
Вопрос к VK — а вам точно оно надо?
Kerman
О-нотация, это даже не базовые знания. Это базовый язык, на котором я могу объяснить, что этот кусок будет дико тормозить на больших данных, потому что N-квадрат, а надо лог N. Если что, я не в VK работаю.
Вот этим и отличается. У бинарного поиска O=log(N), у линейного O=N
Странно с такими пробелами претендовать на миддла.
Впрочем, не стоит расстраиваться. По собеседованиям полезно ходить, чтобы узнать про свои пробелы и эти пробелы закрывать. К десятому собеседованию уже будет представление, чего ожидают от вас.
AdrianoVisoccini
Про BigO вынужден согласиться, за последние годы это стало мастхев даже на джуна.
А вот про сравнение алгоритмов поиска или сортировки... Не уверен, что помнить наизусть все реализации и их сложность это адекватная метрика. Я бы сказал, в таком случае стоит дать человеку два алгоритма и сказать - оцени сложность и сравни какой лучше. Все же, собственная реализация таких алгоритмов поиска или сортировки это не ежедневная задача для... да не для кого в общем то, неужели вы хоть раз в проект тянули не готовое решение этих вопросов из публичных репозиториев или средств языка, а сами реализовывали?
Про DNS сам не могу понять свое отношение. С одной стороны, у разработика необходимость с этим сталкиваться может годами не возникать, с дургой стороны, как сказал классик "Это база, Это знать надо". У меня понятие DNS навечно запечено горячим клеймом прямо на мозге со времен настройки ADSL интернетов во времена беззаботной юности и младших классов школы
Kyoki
Никто его не просил сравнивать, никто не спрашивал про реализации и сложности, никто не просил реализовывать... но, странно, не знать отличие линейного поиска от бинарного. И да, чтобы знать,что тянуть из публичных репозитариев, неплохо знать ключевое различие этого, а по хорошему еще и краевых случаев.
VladimirFarshatov
Чел мог просто растеряться и забыть, или пользоваться в посведневке иными терминами. Так, году в 2009-м меня не взяли по причине того, что не смог ответить на вопрос: "Что такое EAV?" .. оказывается это банальное продольное хранение данных, которым пользовался с 2001года "вдоль и поперек", а мой коллега так аж 1997года. Ктож знал, что какой-то Тенцер в 2004-м наклепал статью про этот подход и обозвал его Entity-Attribute-Value? :)
Kyoki
Не натягивайте сову. Его не спросили, что такое SFINAE или шаблонный ADL, ECS, KISS, ...
voldemar_d
И даже про DRY.
40kTons
Самое противное, что алгоритмы как здрасьте забываются. Основную идею помнишь, но сходу не напишешь, детали реализации забываются
Farongy
Это действительно странно выглядит, что человек настрадался с различными типами индексов в БД, редисом, но не знает как работает хэш таблица.
ZetaTetra
Действительно, это как работать всю жизнь с PE файлами и не знать как рассчитывается RVA (Relative Virtual Address).
Скорее всего автор просто забыл ибо с нуля не реализовывал как минимум N-лет.
Retifff
Мне, как системному адиминистратору, вообще непонятно, как может у программистов "годами не возникать необходимость сталкиваться с DNS". А мы потом сталкиваемся с захардкоженными IP-адресами в ПО, вот счастье-то какое.
Alexsey
У этой монеты есть две стороны. Админы приносят не меньше счастья разработчикам когда, спустя часов 5 диагностики и уверений что никто ничего не трогал, вскрывается что все таки в DNS своими шаловливыми руками кто-то залез или изначально криво настроил.
Kekeluy
Ну, ваш пример про хардкод - это из другой оперы, которая называется "а нафиг нужно выносить параметры, если можно быстренько накидать вот так". А про DNS - лично я встречал разрабов, которые не в курсе что это такое, как и в принципе модель OSI. Будучи по образованию безопасником и по текущей профессии абапером когда-то собеседовался на бэкэндера с нулевыми знаниями веб разработки. Интервьюер сказал, что даже с моими малыми знаниями у меня их больше, чем у выпускников программной инженерии. Также из личного опыта работы сложилось мнение, что в некоторых местах уровень знаний разрабов сильно ограничивается их текущими задачами (не всегда по их вине), из-за чего даже когда-то имея знания о каких-либо технологиях человек эти знания утрачивает со временем. Поэтому вроде как с одной стороны он не знает базу, которую должен знать любой джун, а с другой стороны он и правда на текущем месте может быть отличным спецом. Я вот как абапер комплексную по поводу отсутствия знаний по многим темам (тот же гит и системы контроля версий), потому что это все берет на себя сап, из-за чего нет даже потребности в каком-либо контроле версий (это один из примеров, есть ещё куча других вещей, которые на себя берет платформа).
Tony-Sol
это действительно проблема, раз от разу мешающая проходить собесы - знания, если их не использовать, неизбежно выветриваются из головы
xSVPx
Зато понимание остается.
Фиг знает как можно забыть, что такое указатели. Не смочь быстро сформулировать можно. Но забыть ? Примерно тоже самое касается линейного поиска и деревьев, что тут забыть можно ?
mvv-rus
Александр, а мне вот, как программисту, хоть и ненастоящему, совершенно понятно, как у программистов годами не возникает необходимость сталкиваться с DNS (особенно - именно с DNS). Программисту ведь достаточно того, что есть некая служба, которая преобразует имя сервера в сети в его сетевой адрес, с которым сетевые службы устанавливают соединение. А настройкой этой службы (а то и вообще вопросом, что там за служба используется) занимаются уже специально обученные люди.
Программисту даже необязательно знать, как там сетевой адрес протокола внутри выглядит. Я, к примеру, так и не удосужился узнать, как там внутри выглядит адрес протокола NetBIOS Frames, при том, что в своих программах, работавших c БД на сервере Interbase, я этот протокол некоторое время активно использовал. Правда, имя сервера (не говоря об адресе) указывалось не прямо в моей программе а в псевдониме IDAPI (она же BDE), но это мало что меняло: ответственность на создании образца псевдонима IDAPI была на программистах, а эникейщики просто настраивали ПК пользователей по этому образцу (обычно - копированием файла конфигурации, но бывали нюансы).
А вот за жестко прописанное в прграмме (а не вконфигурации) даже имя сервера, не говоря уж о его адресе, программистам таки надо действительно
давать по башкеставить на вид.PS Ну да, я тоже много работал системным администратором (и, возможно вы меня помните в этом качестве по Зеленому), и как бороться с DNS знаю хорошо. Но это - потому что я работал администратором сетевой инфрасруктуры предприятия (AD, Exchange и пр.) - там да, без знания DNS (причем, с весьма глубоким погружения в ее специфику) работать просто невозможно. Но это - совсем другая профессия IMHO (впрочем, изначально мне пришлось совмещать ее с программированием).
Samhuawei
Плюсую и докину аргументов. Сейчас информации так много что специалист в одной сфере может шарить очень хорошо, а в другой - поверхностно, и вот это "поверхностно" может придать излишней уверенности в своих силах и человек напортачит, а ошибка всплывёт в самый неожиданный момент.
Вот вчера было. Я админ одной широко известной системы уже 15 лет, осертифицировался, знаю подноготную от и до. У нас есть юзеры с админскими правами в подсистеме, такие часто выдаются продакт менеджерам. Попросили меня настроить их проект. Я всё сделал по фен шую. Полез продакт и переделал так как он видит. В итоге подсистема не работает. Он жалуется своему начальнику что всё сломалось. Тот идёт к моему начальнику. Полчаса времени четырёх высокооплачиваемых специалистов на выяснения отношений. А если бы он сразу признал что ничего не понимает в подсистеме и сказал мне что ему надо - заняло бы 5 минут одного человека. То есть в 24 раза эффективнее.
Когда меня на собеседовании спрашивают про что-то не относящееся к вакансии я сразу отвечаю что кое-что могу но не стану, потому что есть более грамотные специалисты чем я. О-нотация понятно, это в школе проходят. Но все тонкости настройки ДНС это тонкий лёд где легко огрести проблем - пусть этим занимаются сетевики, а не программисты. А если нет сетевика - тем более не нужно ничего выдумывать, лучше загуглить ответ на профильном сайте.
Fideloin
Господа, ну вы же немного передёргиваете. В статье ни слова не написано про тонкости настройки или детали реализации.
Если я правильно прочитал, вопрос был конкретно "что такое DNS". Не оправдываю интервьюера, который мог бы и по другому сформулировать вопрос. Но всё-таки знание концепции, как именно мой компьютер находит в сети условный гугл, это важное умение для любого технического специалиста.
RTFM13
Ну DNS на уровне пользователя еще куда ни шло спросить. Но тут вон в комментариях предлягают BGP для общего развития изучить. Если это не стёб, то клиника.
Metotron0
Вы учились в СССР или в 2000-х? Потому что в девяностых точно не проходили. Если первое, то понятно, почему ругают нынешнее образование, а если второе, то не понятно, почему ругают, если там даже такое проходят. А вообще говоря, вдалбливать школьникам про сложность алгоритмов — это как всем школьникам насаживать умение программировать. Зачем всем, если кто-то из них будет работать мясником, водителем автобуса или точить садовый инвентарь? С той же аргументацией можно всех обучать работать на фрезерном станке и различать номиналы резисторов по полоскам.
Независимо от того, что это может быть полезно и перенастраивает мозги, оно всё равно неминуемо забудется. Я на PHP писал в течение 10 лет, но прошло лет 6, а я уже сомневаюсь, как там в классах переменные создавать, нужно ли писать запятые, точки с запятой, нужен ли знак доллара, писать ли значения через двоеточие или знак равенства, как статические "переменные" задавать (даже не помню, как это называется, свойства что ли?), какие у классов есть магические методы.
pyatyispyatil
Да его же не спрашивали про устройство DNS и протокола TCP/IP. Можно было хотя бы базовыми словами ответить: "Система доменных имён, которая позволяет преобразовать домен в айпишник".
Это просто проверка на то, что человек хоть чуть-чуть вылезает за пределы ide и интересуется тем, как магические коробочки, называемые компьютером, таки работают.
И да, если он ни разу не загуглил ради интереса что такое DNS_PROBE_FINISHED_NXDOMAIN в хроме или не настраивал свой роутер/впн, где всегда есть опция по DNS, то какой он вообще программист?)
Newbilius
Ни разу не загугливал, потому что хром ни разу ему такую ошибку не выдавал?)
pyatyispyatil
Ага, а если и выдавал, то он не вчитывался и просто говорил "давай работай интернет грёбаный", перезагружал роутер и всё чинилось.)
Ну в крайнем случае звонил в техподдержку провайдера, когда уже три раза ребутнулся, перезагрузил ОС, а хром всё равно не открывает чатжпт, которого можно было бы спросить что же с этим делать.
Newbilius
Я оттого оставил свой комментарий, что реально в своей недолгой жизни ровно 0 раз жизни видел такую ошибку) Да и для настройки VPN'а какие-то настройки связанные с DNS руками нынче вводить не нужно. Настройка роутера... ну да, давным-давно - было необходимостью, в инструкции от провайдера провайдера обычно был такой момент, но нынче часто и этого не нужно.
И я не оправдываю отсутствие любопытства, но в реальной жизни действительно можно ни разу не столкнуться с проблемами с DNS и прекрасно себя чувствовать.
ManulVRN
"есть некая служба, которая преобразует имя сервера в сети в его сетевой адрес, с которым сетевые службы устанавливают соединение."
Как я понимаю, примерно такой ответ и ожидался.
piton_nsk
У меня вопрос строго противоположный, а что там делать с DNS? Есть служба которая имя в адрес преобразует, а как оно там работает, да черт его знает. Разработчик вполне возможно ни разу в жизни это не настраивал ни на работе, ни дома. Я, к примеру, ни разу в жизни не обжимал витую пару, что теперь)
А это вообще причем?
Tsimur_S
Если нужен пример из практики то например натыкались на проблемы резолвинга в образе myalpine(mysl). Он резолвит через udp, и не полностью поддерживает стандарт. По итогу если ответ от сервера >512b то можно сказать "потрачено". Если про DNS не знать то можно долго хвататься за голову с мыслью "а че здесь собственно происходит?".
Да и вообще между "а что такое DNS?" и "могу написать аналог Bind 9 на ассемблере с закрытыми глазами" очень много промежуточных вариантов. Крайности всегда плохо.
piton_nsk
Тут конечно неплохо бы расшифровывать термин "сталкиваться с DNS", одно дело не знать в смысле "первый раз слышу такой набор букв", другое дело не знать в смысле "не знаю как настраивать на древней версии линуха".
Согласен. Меня как-то сильно удивила категоричность в смысле "вообще непонятно". Ну пишет кто-то бэк, десктоп, базовщину, кады какие-нить, ну какой там DNS?
Tsimur_S
Ну так автор задал тему этому разговору: "не знал что ответить на вопрос: что такое DNS". Отсюда и пошло обсуждение.
Никто вроде в ветке не писал что нужно знать RFC от корки до корки, скорее наоборот.
DMGarikk
раз образы и альпайн взяли, в докере и прочих куберах, вполне себе внутренние dns имена используются и надо хоть базово понимать почему и как мы обращаемся к сервисам внутри них
это конечно больше уже в сторону девопсов, но сейчас базовое понимание ci/cd и основы знаний как собрать локально стенд, уже требуется на миддл должностях
RTFM13
Я узнал как называются алгоритмы поиска и сортировки лет через 15 после их фактического использования. Узнал кажется тут на хабре в комментариях к постам про собеседования.
Конечно терминологию хорошо бы знать, но что-то я сомневаюсь что к ним такая очередь, что незнание пары терминов достаточный повод для выкидывания кандидатов.
В принципе, это тысяче первое подтверждение того, что навык работы и навык прохождения собеса слабо пересекаются. Особенно в "бигтехе".
povargek
same story, про знания терминов, да …
только в моем случае по юности я некоторым алгоритмам вообще придумал свои названия (порой даже забавные)
Dmitry_604
Думаю, из тех кто не может ответить на вопросы из статьи - именно что очередь.
pes_loxmaty
Да, можно некоторых терминов не знать или забыть, волноваться, все дела. Обычно в таких ситуациях интервьюер начинает подходить к вопросу с другой стороны, например определяет понимание темы через какие-то практические примеры.
Косвенно можно предположить, что в статье это и произошло:
Интервьюер: что такое О-нотация знаете?
Кандидат: первый раз слышу
И: ну давайте попробуем понять какой алгоритм поиска будет "сложнее в исполнении" линейного поиска или бинарного
К: я не знаю таких алгоритмов, что за чушь вы ваще спрашиваете?
И: я подскажу. При линейном поиске мы в общем случае должны в цикле пройти по всем элементам массива, а в как будет осуществляться поиск, если данные у нас не в массиве а в отсортированном дереве?
К: видел деревья в лесу, перестаньте давить на меня и морочить голову. Давайте перейдем уже к нормальным вопросам
Metotron0
К слову о деревьях. Я понимаю, что это односвязный граф, где от каждого элемента, идя по "предкам", можно дойти до единственного общего предка. Но что считать отсортированностью в такой структуре, это можно узнать только читая соответствующую литературу. Я, например, не представляю. Односвязные списки, кроме литкода, использовал раз в жизни, ради прикола. Так бы обычным массивом обошёлся, но в него сложно добавлять что-то в середину, а мне нужно было сделать драг-н-дроп внутри списка элементов на странице.
Но я и не претендую на работу в корпорациях.
// Если мне показать пример отсортированного дерева, то я пойму и смогу придумать что-то с поиском.
mk2
Двоичное/бинарное дерево можно описать как "есть начальная вершина-корень, в каждой вершине записано значение, и у каждой вершины могут быть левый и правый потомок"
Отсортированное дерево - то, в котором у каждой вершины - все элементы левого потомка и его потомков меньше элемента в вершине, а все элементы правого потомка и его потомков - больше элемента в вершине.
Или [на Википедии](https://ru.m.wikipedia.org/wiki/Двоичное_дерево_поиска) прочитать
Hochmuch
В отсортированном дереве, в каждом узле значение левого потомка меньше, чем в зафиксированном, а в правом больше
kogemrka
Этого недостаточно. Вот пример сбалансированного дерева удовлетворяющего условию, однако абсолютно не упрощающего поиск.
платоновского человекадерево поискаВыше в соседней ветке - более удачное определение.
VladimirFarshatov
Вообще-то это не "программерское", а больше чисто математическое и даже "матановское" понятие О-малое, О-большое.. Отсутствие знаний говорит только лишь про отсутствие базовой математики у претендента, которая нужна далеко не всем и не всегда, даже сеньорам.
sergey-gornostaev
У меня нет "базовой математики", но я читал книги, а в любой книге про алгоритмы и во многих по языкам программирования есть про О-нотацию.
VladimirFarshatov
Так в книгах про алгоритмы, алгоритмическая сложность есть основа. Не удивительно, что там это есть. Но .. Вы точно уверены, что автор в курсе наличия книг по алгоритмам? (Кнута на вас нет!) если он не различает бинарный поиск от пузырька?
Интересно, в какой книге по алгоритмам нет бинарного поиска?
sergey-gornostaev
Видимо, я слишком стар и не поспеваю за новыми веяниями, но меня очень удивляет, что человек может стать программистом, не прочитав ни одной книжки, а тем более добраться до мидла в хайлоад проекте.
dph
Ну, понятие "хайлоад" сейчас довольно расплывчатое. 50k rps - может быть и очень мало и очень много, смотря какие запросы.
ZetaTetra
Сейчас понятие хайлоад немного не про бирарный поиск или про сортировку пузырьком, а про балансер или шардирование через оркестратор. Ну или failover накрайняк (но я не фанат).
Я php не знаю, но думаю там уже есть open source решение которое содержит разнообразные реализованные методы сортировки, которые протестированы, опробованы и с подробными инструкциями при каком сценарии что лучше использовать.
ManulVRN
Вы точно уверены, что автор в курсе наличия книг по алгоритмам?
Вот собеседующий и выяснил это одним простым вопросом.
xSVPx
В любой статье на хабре про собеседования есть про о-нотацию :).
dv0ich
Слушайте, когда я только начал изучать программирование, я буквально в первых же книгах и статьях столкнулся с асимптотической сложностью алгоритмов. При том что я самоучка. Как программист может этого не знать, я не очень понимаю.
Metotron0
Ну, я сталкивался, но так и не запомнил, как там что считается. Я просто понимаю, что цикл в цикле — это дольше, чем один цикл. Могу даже сходу сказать, что зависимость квадратичная. А вот если второй цикл прерывается один раз на первом элементе, второй раз на втором, третий — на третьем, то я даже с листочком и ручкой не смогу сказать, какая это зависимость. <N умноженное на арифметическую прогрессию>, что-то такое.
Это незнание не мешает избегать вложенных циклов там, где можно их избежать. А так как мой код работает в браузере, то я могу хоть лишних 100 мс потратить или задействовать на мегабайт больше оперативки. Оперативки на то и нужна, чтобы её использовать, а вряд ли будет какое-то устройство, где не найдётся 1 МБ. Дело не в том, что я нарочно буду это делать, просто, мне приятнее написать [].forEach() или [].some(), чем гонять for(;;). За последние лет 5 я for использовал только на литкоде.
pes_loxmaty
Мне для общего развития, чем [].forEach() и for(;;) отличаются?
p07a1330
ФорИч не позволяет выйти раньше.
Грубо говоря, там нет break
Rorg
Из forEach можно выйти по return
p07a1330
return не прерывает цикл, а выходит из функции
Hidden text
Rorg
Формально, как мы видим из вашего примера v===3 мы так и не получили. Соотвественно, если использовать if (v >= 3) return мы получим только значения 1 и 2. Я не говорю, что это правильно, я просто говорю что это есть.
withkittens
Это получился
continue
, но неbreak
.pes_loxmaty
получается "... я for использовал только на литкоде" так себе предмет для гордости )
Metotron0
Он мне кажется слишком многословным. Если я буду вместо каждого .filter, .map, .every, .some, .forEach писать for(), то, во-первых, не смогу делать цепочки, а во-вторых, придётся вчитываться в этот for, чтобы понять, что внутри творится, тогда как .every заранее говорит о том, что будет происходить.
Не говоря о том, что для map нужно будет подготовить пустой массив, заполнить его, потом всё переприсвоить.
Metotron0
Там же внутри ещё одна функция создаётся
OldNileCrocodile
Это если нет условий выхода или условий отсечения. На leetcode метод отсечений ветвей в задачах реализуют именно через двойной цикл (цикл в цикле). И получают либо O(n) либо логарифм. (Обычно, такая сложность возникает при работе с двоичными данными, aka строка битов).
"А вот если второй цикл прерывается один раз на первом элементе, второй раз на втором, третий — на третьем..." - то в итоге всё равно будет сложность O(n^2) квадратная. Потому что по формуле арифметической прогрессии получаем сумму элементов как
S = n * (n + 1) / 2
В итоге будут два переменных множителя с константой (const = 1/2)
n * (n + 1) * 1/2 => n * (n + 1) * const. => n * n => O(n ^ 2).
Тут всё просто, внутри О лежит именно функция, а не число.
Metotron0
Что такое отсечение ветвей? Ветвей чего?
wataru
Не всегда. Вот алгоритм решета Эратосфена, работающий за линейную сложность, хоть там и 2 вложенных цикла.
И там сложность будет такая же квадратичная. На самом деле будет N^2/2 итераций, если арифметическую прогрессию.
И еще какой-нибудь find/contains там внутри навернуть, или что там у вас есть, которое внутри по всему массиву бегает. В результате на ровном месте получаются квадратичные алгоритмы и без вложенных циклов.
Надо все-таки уметь оценивать сложность.
Metotron0
Если нужно делать .find для каждого элемента в цикле, то этого всё равно не избежать, даже если сверху будет for().
У меня массивы на единицы, иногда на сотни элементов. Не десятки тысяч, в браузере мне на моей работе (тут делаю акцент) не приходится такие огромные данные перебирать. Запрос данных с сервера всё равно займёт больше времени, чем я буду их перерабатывать, хоть бы даже четырьмя вложенными циклами.
wataru
Можно отдельным проходом все элементы запихать в какую-нибудь хеш-таблицу, и уже там вместо find в массиве за O(1) проверять в основном цикле. Его тоже можно сделать как forEach.
Ну вот уже кусок кода можно ускорить в несколько, иногда в сотни раз.
Так на бакенде же тоже самое.
Metotron0
Да даже сам GET-запрос займёт больше времени, чем любой проход по циклу из 100 элементов. Это же всё микрооптимизации получаются.
Metotron0
Сходил по ссылке
Я хлебушек. Если бы я и смог продраться через подобные выкрутасы, то те времена прошли 20 лет назад. Я даже не уверен, что там понимают под фигурными скобками, массив, множество, или ещё что похлеще. Просто поверю, что такой алгоритм есть, но я крайне сомневаюсь, что сам буду такое писать, и что мне придётся выбирать между разными вариантами. И уж точно я не смогу определить сложность чего-либо, чтобы сравнить их между собой. Я осознаю свой уровень и уровень решаемых мной задач. Внутри того, что я делаю, я могу интуитивно определить, что будет работать быстрее, без явного выведения формул для N.