Comments 16
Интересный момент про "Нет вложенным циклам". Легко нарваться случайно, когда глаз замыливается.
Не знаю на каком там языке, похоже на Go, но стрелочки и двоеточия которых в Go точно нет. (UPD судя по контексту "iOS разработка" это Swift :) ) Бросилось в глаза что какой-то слишком большой объем кода, какие-то префиксы, ни черта не понятно. ИМХО должно быть короче. На С++:
std::vector<int> sorted_merge(const std::vector<int> &A, const std::vector<int>&B)
{
int ai=0, bi=0, ci=0;
std::vector<int> C(A.size() + B.size());
while(ai<A.size() && bi<B.size())
C[ci++] = A[ai] < B[bi] ? A[ai++] : B[bi++];
while(ai<A.size())
C[ci++] = A[ai++];
while(bi<B.size())
C[ci++] = B[bi++];
return C;
}
можно и так, за несколько минут набросал:
можно и короче, но тут вроде наглядно видны этапы работы алгоритма. Писал в без проверки, как на собеседовании, мог ошибиться )), так как думать и гонять в голове тесты не охота. А в примере, в статье, лишняя память задействована, да и на первый взгляд плохо читается, я правильно понимаю, что удаляется постоянно первый элемент? А что потом происходит с массивом, перестраивается или за O(1) эта операция проходит?
Если в процессе реализации появляется понимание того, что число x уходит далеко за пределы диапазона 2–3, что-то идет не так, и стоит пересмотреть свое решение.
Что-то первый раз такое слышу. Если число x фиксированное, то какое бы большое оно ни было, сложность решения O(x*n) всё-равно будет считаться O(n). Да, для малых n разница может быть существенна, но для малых n обычно и не заморачиваются с алгоритмами. А когда n это миллионы и миллиарды, линейное решение всё-равно будет лучше, чем O(n*log n) и тем более O(n^2). Конечно, если x не будет само порядка миллиона при этом, но что же это за такой алгоритм вообще с константным числом в миллион шагов? А когда x это 2, 3, 10 или даже 100 - большой разницы нет. Никто этим не заморачивается.
Обычно могут спросить другое: "А какова сложность вашего алгоритма по требуемой памяти?" Вот это может быть существенным. Бывает так, что быстрый алгоритм требует много памяти (например, под словарь со счётчиками или указателями) и тут уже нужно искать компромисс между скоростью алгоритма и потребляемой им памятью.
Статья хорошая, но как будто больше про алгоритмический собес. Мне вот недавно с live-coding пришел отзыв "компилировал код в терминале, не пользуясь хоткеями vscode" – к такому меня жизнь не готовила.
"Собеседующий не этого ожидал", а откуда кандидат должен знать что он ожидает, решил поставленную задачу и все на этом, к чему этот лайф рефакторинг?)
Это live-coding, пиджаки с какими-то details. И это всё on design
У меня безоговорочный приоритет получил бы кандидат, который, перед тем как писать код задал бы несколько вопросов.
какого размера массивы в параметрах, есть ли смысл тут писать оптимальное решение в ущерб читаемости кода
нет ли возможности отрефакторить, вызывающий код так, чтобы избежать написания алгоритма и обойтись сортировкой из стандартной библиотеки
приватный это метод или публичный, нужна ли проверка на то, что массивы отсортированы
Ну и так далее. Это если конечно мы проверяем "насколько хорошо варит голова кандидата в бою".
То есть, если по условию задачи массивы отсортированы, а собеседуемый спрашивает, нужно ли это программно проверять, это плюс? Насчет размера согласен, но тут же поступит ответ, что массивы очень большого размера и требуется оптимальный алгоритм, быстрее чем n log n.
Выше привел пример решения на свифт, в котором все читаемо и просто. Его тоже можно изменить по пожеланиям собеседующего, уменьшив или немного оптимизировав. Но на мой взгляд, нормально. Прошел бы с таким решением собеседование или нет?
Ваш код на порядок или два лучше чем то, то в статье. По крайней мере он читается на лету, в отличии от. Код, который приведен как пример грамотного решения в статье, не должен пройти ревью. Да, я считаю, что разработчик, начиная с уровня мидла должен в этом случае попросить контекст, в котором вызывается метод, или явно указать, что он бы в первую очередь попытался бы отрефакторить код снаружи. Насчет входных параметров, если эта функция вызывается из любого места кода, то это просто вопрос времени, когда ее кто-то вызовет с неотсортированными массивами, и тогда первый неоптимальный вариант не является неоптимальным, он будет единственным правильным ответом. Если бы собеседуемый указал на это, это было бы ему в плюс. Насчет прошли бы или нет, это зависело бы от других факторов а не только от того как вы написали эту функцию. Возможно в голове у меня отложилось бы, что вы скорее склонны писать понятный и читаемый код, а автор статьи код пишет тяжелый и неприятный.
Сегодня на рынке IT трудно представить собеседование без того или иного варианта Live Coding
Громкое заявление. Сегодня на рынке IT трудно представить собеседования с такими непопулярными подходами, ведь у кандидата за воротами очередь желающих предложить оффер.
В первой задаче неплохо бы выдать в качестве ответа оба варианта. Первый: для реальной разработки, как поддерживаемый и читаемый код на основе уже имеющихся средств ЯП. Второй: как нечитабельное, сложноподдерживаемое и обычно никому не нужное изобретение велосипеда. Еще и вводящее в заблуждение читающего код своим названием. Так как название функции неплохо бы сменить на mergeSortedArrays иначе нихрена не будет работать, если мы в аргументы зарядим несортированные массивы. Во входных параметрах подсказки для этого тоже нет. Навести прочий рефакторинг.
Ну и изначально, как писали уже выше, нужно интересоваться целями кода:
1) требования/ ограничения к диапазону, типу и т.д данных (constraints)
2) временные рамки на задачу
3) цель (где, как и с какими constraints будет работать данный код в целом, т.е функция у нас не в вакууме)
Никогда не понимал зачемчем таскать кандидатов по сложным алгоритмическим задачам ведь в 95% вакансий это не нужно. К тому же если кандидат заучил сотни алгоритмических задач это не значит что он научился их решать.
При собеседование надо проверять базовые знания, особенности языка ну и то что человек умеет думать и не обязательно он должен знать все и вся.
Вообщем от собесов в наше время вообще в шоке, грамотных специалистов не сышещь, насмотрятся блогеров, а думать головой не хотят.
Как подготовиться к live-coding сессии на собеседовании