Досмотрел (предыдущий коммент писал посреди видео). Собеседующий хорошо видит что происходит, адекватно оценивает ситуацию, учитывает все детали и когда что-то для себя прояснил, готов двигать интервью вперед даже самостоятельно подсказывая соискателю. Очень круто и профессионально. Респект.
Второе задание имеет либо некорректную формулировку, либо в результате, мы должны также обработать, как уникальные подстроки “bca” и “cab”) Да, длина будет также 3, но это не обязательно будет длина подстроки “abc” )
Это не живое интервью -) Провел как тим лид несколько сотен собеседований с лайвкодингом, люди не общаются подобным образом в стрессовой обстановке, слишком чистый и рафинированный диалог.
Во второй задаче вместо счётчика наверно лучше хранить позицию символа в строке. Тогда левый указатель можно быстро перемещать на символ, следующий за повторившимся символом.
разве? допустим у нас строка abcadef, к примеру тогда встретив на третьем символе 'a' мы бы перенесли левый указатель сразу на d, таким образом не учтя самую длинную строку без повторений - bcadef если я конечно вас верно поняла, поправьте если нет
@@ourdestruction6851Если так делать то зачем вообще хранить позицию встретившегося символа? Конечно же мы перемещаем левый указатель на 1 от позиции, сохранённой в таблице. Ну и надо не забыть обновить это значение, добавив туда позицию повторно встретившегося символа
А смысл от такого фидбека, какая польза? Это больше на придирки похоже мимо сути дела. Если это не монтаж/склейка, то человек решил две задачи за относительно небольшое время при том в относительно стрессовых условиях (на которые смело можно списать основные недочёты), без существенных ошибок. Как надо было решать ещё лучше? И за подобное собеседование ещё предлагается заплатить круглую сумму, в чём ценность?
Мне сразу предлагали случай данных, который приведет к ошибке. Причём, писал на го, а собесила питонщица. Другой раз по стандартной библиотеке подсказали.
Да, ошибся он, но, задача была сформулирована так: "найдите длину..." то есть функция должна вернуть просто число, и сами подстроки и их количество нас не интересуют. А вообще это типовая задача для паттерна "скользящего окна".
Сколько не прорешивай литкод, фактор стресса никуда не денешь. Когда собеседующий каждые 30 сек. тебя торопит, просит рассуждать вслух при написании кода. Так можно поплыть на элементарных вещах. Вот бы на экз. по матану нужно было решать все задачи под тотальным надзором препода, я думаю процент несдавших увеличился бы напорядок
Во 2й задаче можно уйти от for: в store хранить актуальные позиции встреченных символов и двигать левый указатель сразу на старый + 1, если символ уже встречался и его позиция > текущего левого. Позиции всегда обновляем
Помню откликнулся на резюме из Яндекса. Созвонились с hr. Мне озвучили нужно знать алгоритмы. Я сразу сказал, что не знаю алгоритмы. Мне hr предложил подучить. Больше на вакансии от Яндекса я не откликаюсь
У меня так с Тинькофф было.) Позиция была на мидл ФТ, а потом hr пишет - "Ну, тут это у нас все фулл стак, прогать умеешь? Не? Ну тогда изучай, потом напишешь"
Ты подавался на вакансию разработчика/программиста без знания алгоритмов, и расстроился, что тебе сказали их подучить? А на что ты надеялся? Что на HTML будешь кодить?
@@SaltyRain1 Я уже на тот момент имел опыт разработки 10 лет. Представь себе без знания алгоритмов. И естественно я не расстроился. Я теперь сам заканчиваю все собесы где меня начинают спрашивать знание алгоритмов. Тарам-парам-пам
@@nikolaifedorov685 ну, вот я и спрашиваю, ты на HTML кодишь? Или «готовые библиотечки» для всего используешь, и понятия не имеешь, что там у тебя под капотом варится
Какие map? Вектора надо использовать во второй задаче. С этими map до 100 символов алфавита вектор быстрее будет тупо из за того, что проц хотя бы закешировать значения себе сможет. В map элементы памяти по разным адресам находятся. Это очень медленно.
Контент полезный. Только по первой задаче у сортировки временная сложность O(n log n), а не O(log n). Суммарная сложность для решения, соответственно, тоже O(n log n)
@@vladimir_balun_programmingа можете подсказать, почему вообще такая сложность? Есть 2 сценария: 1) сортируем массив (сложность n*log2n (быстрая, в среднем) + log n, поиск) 2) просто складываем все что видим, сложность n. Сортировки не требуется Итого, выгоднее тупо сложить массивы, если n>3
@@valeryzeryl9145могу ошибаться, но чисто интуитивно, если не отсортировать, придется сравнивать каждый последующий интервал со всеми уже объединенными, соответственно сложность до 0.5n^2 вырастает
Ошибка во второй задаче 33 строка. for store[right] > 1. Пример строки, которая обработается с ошибкой: abcabbcd. Когда left будет 2, а right 5, нужно будет left довести до right, иначе две подряд идущие b создадут ошибку.
В первой задаче в условии ошибка, как выяснилось позже речь не о интервалах как написано в условии, а о отрезках, так как когда конец первого совпадает с началом второго считается что пересечение есть 🧐
@@constantinegeist1854 В том что у интервалов концы не закрыты. Концыу закрыты у отрезков. Тоже смутило. Можно было использовать собирательное слово промежуток.
@@arsenypogosov7206 не знаю, зачем в русском языке понапридумали кучи терминов, если суть одна... в английском, если не ошибаюсь, всегда просто interval: open interval, closed interval, left-open interval, right-open interval а так, просто дрочь на терминологию, как по мне хотя да, может быть недопонимание
Вторую задачу можно решить за линейное время, если воспользоваться словарём на основе хэш-таблицы с поиском\добавлением за O(1). В словарь складывать последовательность уникальных символов и проверять каждый след. символ за О(1). Хз как работает store в go но вроде как я понял, то это не хэш.
intervals = [[1, 6], [1, 3], [8, 10], [15, 18]] temp = [] intervals.sort() ans = [intervals[0]] for i in range(1, len(intervals)): temp = ans[-1] current = intervals[i] if current[0]
@@Kondratyevv название секции в Яндексе, когда тебя собеседует опытный собеседующий (а не рандомный разраб, у которого это первое собеседование за полгода). Обычно оценки таких секций больше весят при принятии решения о найме и грейде.
@@freestylerveevo на всех этапах дают 2 задачи, этапов хз сколько может быть, на стажировку вроде 3-4, читал, что на другие позиции вплоть до 9 таких этапов может быть Сам попал когда набирали людей на стажировку, сначал решаешь задачи типа codeforce на яндекс контесте, если прошёл, то назначают вот такие собесы.
Проблема интервалов не полностью решена с точки зрения временной сложности. 1) Создайте вектор с размером = максимальному концу всех интервалов. 2) Перебрать входные интервалы и сохранить их в векторе: позиция вектора - это начало интервала, если интервал уже существует, объединить эти два интервала. 4) Взаимодействие с вектором для обработки интервалов в соответствии с логикой видео. Временная сложность равна O(n), n - количество введенных интервалов. (нет необходимости сортировать O(n*log(n))). Сортировка подсчетом выполняется за время O(n), что делает ее асимптотически быстрее, чем алгоритмы сортировки на основе сравнения, такие как быстрая сортировка. ================================================================================================= хорошее место для практики (не стесняйтесь поставить звезду :) ) github.com/IhorVodko/Hackerrank_solutions
Вот что получилось на js, первая задача: function getIntervals(intervals) { intervals = intervals.sort((a ,b) => a[0] - b[0]); const result = []; let actualInterval = intervals[0]; for (let i = 1; i < intervals.length; i++) { const current = intervals[i]; if (actualInterval[0] >= current[0] && actualInterval[0] = current[0] && actualInterval[1]
Меня одного смущает что первая задача решена не верно? У него на выходе другие цифры чем в примере, т.е. попал интервал которого не было изначально, это 7
lastItem[1] = max(lastItem[1], intervals[i][1]) В логике кода все правильно. Это для расширения диапазона интервала Если у нас есть последовательность [[1,3],[2,8],[2,6]...] На первой итерации lastItem - [1,3], а intervals[i] - [2,8], и назначается "больший" конец lastItem[1] = max(3, 8) // диапазон lastItem становится [1,8] На следущей итерации lastItem - [1,8], а intervals[i] - [2,6] , и назначается "больший" конец lastItem[1] = max(8, 6) // диапазон lastItem остается [1,8]
Во второй задаче при нахождении неуникального символа я бы ещё проверял длину отрезка от левого указателя до конца строки и сравнивал его с длиной текущей самой длинной строки. Условно: строка на 20 символов. Все символы были уникальны до 11го. Нам нет смысла дальше проверять
не верно. Например, строка s = abcdefaglm: первые 6 символов уникальны, потому встречается символ a, отбрасываем s[0] и теперь уникальная максимальная строка "bcdefaglm" длинною 9
@@undefined4992 а что даст эта оценка, если сортировка неизбежна? Типа, какая разница, сколько стоит товар, если ты в любом случае вынужден его купить? Т.е. как в этом случае поможет знание - O(n) или O (n*log(n))?
Прикольное интервью, но хотелось бы понять: 1. На какой уровень это интервью 2. Такого рода задачи где то применяются на практике? Какие задачи решают?
Большей глупости чем спрашивать аглоритмы на собесе не существует. Это абсурд !!! Сам никогда их не спрашиваю у кандидатов, но по опыту наборов в другие отделы могу сказать следующее: после проверки алгоритмов вы набираете людей 2 типов 1) просто задрочивших литкод ради собесов 2) реальные задроты-токсики с ЧСВ. Потом мои коллеги тимлиды с соседних отделов ноют что у них в команде не те люди которые им видите ли нужны, а у меня нормальные адекватные ребята и дружная команда без алгосов и никаких проблем ... Выводы делайте сами. (работаю в одном очень крупном аутсорсере РФ)
Алгоритмы это способ большим популярным компаниям фильтрануть поток и сбить зп. Если работаешь в рандомной галере, как ты написал, зачем там алгоритмы спрашивать - загадка
@@ChannelCheesecake вместо литкода лучше показать типичный ынтырпрайзный код, в который добавлен говнокод, и попросить поревьюить и порефакторить. Сразу видна куча вещей о кандидате. Задрачивание на литкод для 99% компаний/проектов мимо кассы
@@ChannelCheesecake Мы такое практикуем и отшиваем большинство кандидатов, т.к. в упор не видят проблем в коде, или замечают только небольшую часть, или начинают сильно плавать, когда спрашиваешь, как сделать лучше. Задание простое может быть: напр., в контроллере напрямую запрос в БД, в коде явно присутствует состояние гонки (напр. пример с балансом на счету) и т.п. Спрашиваешь, где в коде проблема -- полбеды, затем спрашиваешь, как бы отрефакторил, и тут тоже многие начинают плавать. Плюс куча тем для беседы отсюда может быть ("окей, напрямую в БД лезть из контроллера если не хорошо, какой паттерн бы использовал?", или "окей, здесь состояние гонки, объясни почему? за уровни серилиазации БД пояснишь?" и т.п.) У нас кандидатов на "синьоров" с рынка было пока что единицы, кто смогли всё ответить приемлемо.
Че за бред? Я думал на мид+ собесе просить будут написать сервис по тз, а тут алгоритмы, так еще и сложность никакая...первая задача это уровень даде не стажера
И все прочие, которые насмотрелись на гугл и его собесы. Я иногда на собесах так и говорю, когда чувствую, что не прохожу по задачам некоторым и собес идет к фейлу. Типа спортивное программирование - это конечно круто, но я нанимаюсь не олимпиады по информатике выигрывать, а решать задачи бизнесса с помощью кода. Столько разной чуши спрашивают, а по факту приходишь и штампуешь CRUDы.
Я был фронтенд разрабом мне такие задачи давали тоже. Опыта во фронте 15 лет. Ни разу за 15 лет интервалы не мёржил. Я вообще не понимаю, зачем это нужно, что фронту, что тим лиду...
@@warmrew9033библеотечные сортировки (про которые и говорил собеседуемый) используют quicksort+heapsort это так называемый introsort он работает и вхудшем случае за nlogn
Блин большое спасибо за видео. Очень понравилось. Впечатлило нахождение ошибки просто взглядом, я такого не видел еще. И вопрос , как прокачевается подрбный навык? Я понимаю что самый очевидный ответ - решай задачи 😂. Я имею ввиду может есть какая та ступенчитая система, от простых задач к сложным?
Провожу подобные интервью больше шести лет. Сугубо моё личное мнение... если оценивать работу интервьювера только по выложенному видео, то (на мой взгляд) отработал не выше середины. Конечно, так оценивать не совсем правильно, т. к. кандидат уже "разогрет" и находится в контексте происходящего (не задачь, но сомой процедуры). Из того, что сразу видно, независимо от контекста: + провёл дружелюбно ("безопасно" для кандидата) + уточнял "понятно ли задание" + провеёл по положительному пути + выявил недочёты, какие-то дал найти самому + обсудили основные тест кейсы + дал фидбэк + позволил задать вопросы - технические ошибки (в сложностях, что является основой задания, если судить по уделённому вниманию) - не обсудили альтернативные решения и использование средств платформы. - не выявлены способы принятия решений (как и сами принятые решения по допустимым входным данным, ошибка или пустое множество на выходе и пр.) - кандидату не показан потенциал для проф. роста (не вызван интерес) - не запрошен фидбэк на интервью от кандидата (возможно будет позже - на отдельном звонке). Моё мнение: интервьюверу стоит озаботиться изучением вопроса о дополнительных целях интервью. Основную задачу интервью (выявить техническое соответствие кандидата, запрашиваемой позиции) с натяжной выполнил. Есть и не менее важные дополнительные цели интервью.
Это стандартный формат 3-го этапа Яндекса, а больше в РФ таких интервью никто не проводят, если, конечно, цель - закрыть позицию, а не найти еще один винтик в систему или почесать свое ЧСВ. >кандидату не показан потенциал для проф. роста (не вызван интерес) Компанию на Я при найме не интересует твой опыт и знания за пределами Литкода (правда, есть еще архитектурная задача), в итоге разве что можно попросить з/п ближе к правому концу вилки. >не запрошен фидбэк на интервью от кандидата По окончании предлагается форма обратной связи. Можно там потыкать, что-то написать про проблемы. По-моему, результат идет в /dev/null.
@heuretic "а больше в РФ таких интервью никто не проводят, если, конечно, цель - закрыть позицию, а не найти еще один винтик в систему или почесать свое ЧСВ." Не уверен, что я правильно понял что Вы хотели сказать в этой части. На всякий случай поясню некоторые моменты. - Интервью с написанием кода в РФ проводит не только Яндекс. Как я уже написал - у нас такие интервью. Только у нас это второй (и как правило последний) этап. Он объединён с выявлением софт-скилов, общей технической беседой и подробным рассказом о процессах в компании или ответом на вопросы кандидата. Первый этап - короткий технический "скрининг" по телефону с целью принятия решения о втором этапе (в том числе кандидатом). - Что касается "почесать ЧСВ" на интервью - это самое плохое, что может делать интервьювер (таких - сразу в лес :)). - Про закрытие вакансии или поиск "винтика в систему". Как раз поиском винтиков (в том числе по довольно специфическим запросам) команды (в аджайл) и отдела (в матричной системе) я занимался. Написание и обсуждение кода отлично подходит для таких задач (конечно, только им не обойтись, о чём я и писал в оригинальном комменте). На моих интервью в том числе можно гуглить (как и в рабочем процессе). - Про "вызвать интерес": тут у Яндекса, конечно, особое положение - к ним многие уже за имя готовы идти. Для компаний без имени стоит задача заинтересовать кандидата. Одна из лучших мотиваций, как показывает моя практика - именно вызвать неподдельный интерес. Это даже деньгами не всегда перекупается. :) - За информацию о наличии фидбэка спасибо - моя догадка о том, что он собирается позже была верна.
У меня в Я было два литкод интервью с рандомными и одно с потенциальным тимлидом. Про процессы я спрашивал сам, человек от ответа ушёл, видимо, было лень обсуждать что-то после того, как уже решил, что не подхожу. Фидбек не спросил ни один.
@@antoneltchaninov2246Печально. Подобная лень портит впечатление о компании. Имхо, собес нужно в любом случае проводить до логической точки и отвечать - тоже, раз "разрешил" задавать вопросы :)
Имхо, пройти собес от Яндекса можно лишь для того, чтобы потешить свое самолюбие, ну и просто прикольно. Я когда-нибудь обязательно это сделаю, когда будет время. Один раз ходил, решал весь собес одну задачку. Решил, но, очевидно, этого мало. Классические алгоритмы, опять же имхо, интересно решать как тренировку для ума
Первую задачу решил бы с использованием set, так как его в перспективе легче поддерживать, тем более что в коммерческом программировании, сложность алгоритма зависит от необходимости выполнения различных запросов, по типу добавить новый интервал, или вывести в каком интервале лежит число x и находится ли оно в этом интервале и т.д и set(или другая сбалансированная структура данных) подходит для этого лучше
Если я что-то и понял про коммерческое программирование - оно стремится написать микрофункции обрабатывающие единицу - сущность, агрегат и тд. Реальная программа и даже SQL работают с множествами. Всегда с множествами. И реальная оптимизация это разбить код на этапы, которые можно параллелить, а не написать черный ящик который сдвигами покажет минимум микросекунд. Потому что в этот ящик потом не влезть чтобы его распилить на два, ибо он совершенно нечитаем! Вопросов нет, он мегабыстр... Но вот на вход не одна строка а 100000 и микросекунды плюсуются. И делая множества всегда почти можно редюсом поделить число операций увидев одинаковость. А потом редюсом же раскопировать результаты обратно во множество. Вот где оптимизация. А это - это развлечение для мажоров.
@@blabla-f7nда там видно склейку. Если прям с нуля там минут 40 надо, если не гуглит, а с помощью gpt 4 версии, она решается за 3 минуты, лучшим алгоритмом, плюс все расписыаается.
По поводу второй задачи. -забавно получилось что интервьюер упомянул что 26 букв алфавито. только в самом условии. неговорилось про буквыалфавита - написано символов, какие. символы могут быть - никто конечно не спросил
@@ChannelCheesecake большая разница, если ты не знаешь конечно множество символов то ты не можешь в решении зарезервировать массив на 26 символов к примеру
@@get_out_itреч о резервировании не шла, символы подсчитываются в рантайме.char почти везеде 1 байт = 256 символов окей даже если мы подключим крутые библиотеки со всем возможными языками мира там не наберется и 2*10^9 а это обычный int. Что считается константой при размере входа стремящегося к бесконечности
да, яндекс уже лет 10 как опустился, самое интересное что там ЗП чуть ниже средних по рынку, но все туда рвутся почему то, подозреваю просто хотят эту ачивку не более ... ))))))
У первой задачи не линия по памяти, а константа, потому что пространственная сложность относится только к промежуточным данным. Странно, что интервьюер это не подметил. По сортировке скорее всего оговорился, потому что странно думать про лог(n)
@@radiosh66 Привет. Мы оцениваем алгоритм, а не среду с которой этот алгоритм взаимодействует для ввода/вывода, иначе минимальная пространственная сложность была бы линией всегда. Мы не используем массив для вычислений, поэтому учитываться в пространственной сложности он не будет. Можно почитать, например, в computational complexity Димитроу.
@Kelb90 спасибо за разъяснения, осталось на литкоде теперь всех переучить новому подходу к оценке пространственной сложности, т.к. на моей памяти во всех объяснениях учитывалась вся новая память, которую аллоцирует функция.
@@radiosh66 да, в литкоде может быть требование выполнять in-space, когда нельзя делать промежуточный массив и возвращать его. Тогда подход к решение сильно меняется.
Собеседующий дает некоторые ответы соискателю. На самом деле это не хорошо и не плохо, можно если человек запутался подтолкнуть его и смотреть на блеск в глазах, все еще понимает он контекст или мы его потеряли. Но может быть и наоборот: кто-то пролезет на энтузиазме собеседующего. Но может быть этот энтузиазм происходит из того, что ребята друг друга знают.
Очередное доказательство, что если повернуть стол и собеседующего превратить в собеседуемого, то он просто не пройдет собес, а завалить его на нем легче легкого).
Хахаха. Порекомендуем тим лиду яндекса (если он данные задачи видел первый раз и это все не "актерская игра") больше сидеть на литкоде. Если таки он видел это первый раз, то непонятно как в яндексе обычные люди становятся (давайте только не будем уподобляться самому яндексу, и скажет что обычные люди с точки зрения данных алгоритмических задач) тим лидами. Потому что, то, что видел и в чем участвовал я не было таким простым. видимо рядята любят тащить себе в команды не кого-то с "улицы", а своего проверенного, а остальных валят. неприятное впечатление от яндекса.
По первой задаче не совсем понимаю почему сложность на этапе мержа интервалов оказалась O(N)? Остальные интервалы то тоже нужно учесть и смержить с остальными, а это уже возрастает до квадратичной зависимости - что огромная разница
для этого можно пройти по всему массиву всего один раз и выполнить по одной операции над каждым значеием из отрезка, в худшем случае будет O(2N) == O(N)
@@igorf243 "Дан массив интервалов, объедините все пересекающиеся интервалы и верните массив непересекающихся" Ну? Имеется же в виду что у нас может быть несколько объединенных интервалов, которые нужно вернуть А вернуть мы сможем, когда совершим операции над всеми НЕобъединенными интервалами По итогу выполнение этой задачи - возвращается один только массив, с которым ищется возможные пересечения
@@IvanGalkin-f8mесли массив отсортирован, то нам надо просто проверять пересечение с предыдущим: пересекаются - объединяем, не пересекаются - отправляем на выход и начинаем собирать новый. Чистейший O(N).
ну и видно что чел готовился и решал уже эти задачи потому что. сходу для первой задачи определил что нужно сортировать, для второй задачи сходу вопсользовался паттерном скользящего окна.
Досмотрел (предыдущий коммент писал посреди видео). Собеседующий хорошо видит что происходит, адекватно оценивает ситуацию, учитывает все детали и когда что-то для себя прояснил, готов двигать интервью вперед даже самостоятельно подсказывая соискателю. Очень круто и профессионально. Респект.
Второе задание имеет либо некорректную формулировку, либо в результате, мы должны также обработать, как уникальные подстроки “bca” и “cab”) Да, длина будет также 3, но это не обязательно будет длина подстроки “abc” )
Это не живое интервью -) Провел как тим лид несколько сотен собеседований с лайвкодингом, люди не общаются подобным образом в стрессовой обстановке, слишком чистый и рафинированный диалог.
Тем более тогда можно было подумать над условиями задачи/формулировками)
Во второй задаче вместо счётчика наверно лучше хранить позицию символа в строке. Тогда левый указатель можно быстро перемещать на символ, следующий за повторившимся символом.
Да, это было бы более оптимально, но кандидат решил именно так
разве?
допустим у нас строка abcadef, к примеру
тогда встретив на третьем символе 'a' мы бы перенесли левый указатель сразу на d, таким образом не учтя самую длинную строку без повторений - bcadef
если я конечно вас верно поняла, поправьте если нет
@@ourdestruction6851Если так делать то зачем вообще хранить позицию встретившегося символа? Конечно же мы перемещаем левый указатель на 1 от позиции, сохранённой в таблице. Ну и надо не забыть обновить это значение, добавив туда позицию повторно встретившегося символа
a -> l,r = 0,0
ab -> r++
abc -> r++
abc "a" -> repeat -> l++ -> bc
bca -> r++
bcad -> r++
bcade -> r++
bcadef -> r++ -> end(len(s)) -> return (r-l+1)
Главное при переносе не забыть взять максимум от текущего left, иначе можно ошибочно переместить его левее текущей позиции
А смысл от такого фидбека, какая польза? Это больше на придирки похоже мимо сути дела. Если это не монтаж/склейка, то человек решил две задачи за относительно небольшое время при том в относительно стрессовых условиях (на которые смело можно списать основные недочёты), без существенных ошибок. Как надо было решать ещё лучше? И за подобное собеседование ещё предлагается заплатить круглую сумму, в чём ценность?
Надо как робот решать всё)
очень хорошо ведут интервью, никогда так не было у меня. обычно сидят молчат, а ты надрываешься )
Поэтому и похоже на подстановку)
вот у меня с точностью все наоборот, наоборот подсказывают
Мне сразу предлагали случай данных, который приведет к ошибке. Причём, писал на го, а собесила питонщица.
Другой раз по стандартной библиотеке подсказали.
Сложность сортировки log(n)👍, отлично
а какая ?
@@bbrother92 n log(n), сортировка
@@bbrother92 теоретический максимум(доказывается при помощи дерева решений) в алгоритмах сортировки сравнением это Ω(n*log(n))
@@alexeysharyy8623 ну да log(n) это бинарный поиск. а для сортировки слишком революционно. А напомните кто так знатно ошибся?
Так ведь ещё и интервьюер знатно лажанулся, об этом не сказав в фидбеке.
18:19, ну я бы не сказал что 2 ответа
скорее, abc, bca, cab, abc, 4 ответа, получается, разве не так?
Хотел это написать, но нашел ваш комментарий
Да, ошибся он, но, задача была сформулирована так: "найдите длину..." то есть функция должна вернуть просто число, и сами подстроки и их количество нас не интересуют. А вообще это типовая задача для паттерна "скользящего окна".
Сколько не прорешивай литкод, фактор стресса никуда не денешь. Когда собеседующий каждые 30 сек. тебя торопит, просит рассуждать вслух при написании кода. Так можно поплыть на элементарных вещах. Вот бы на экз. по матану нужно было решать все задачи под тотальным надзором препода, я думаю процент несдавших увеличился бы напорядок
Если решал литкод, слегкостью повторишь решения) спасибо за контент, приятно смотреть в любом случае
Во 2й задаче можно уйти от for: в store хранить актуальные позиции встреченных символов и двигать левый указатель сразу на старый + 1, если символ уже встречался и его позиция > текущего левого. Позиции всегда обновляем
Помню откликнулся на резюме из Яндекса. Созвонились с hr. Мне озвучили нужно знать алгоритмы. Я сразу сказал, что не знаю алгоритмы. Мне hr предложил подучить. Больше на вакансии от Яндекса я не откликаюсь
У меня так с Тинькофф было.) Позиция была на мидл ФТ, а потом hr пишет - "Ну, тут это у нас все фулл стак, прогать умеешь? Не? Ну тогда изучай, потом напишешь"
@@happyzombie8588что такое фт? Фитнес тренер?😅
Ты подавался на вакансию разработчика/программиста без знания алгоритмов, и расстроился, что тебе сказали их подучить?
А на что ты надеялся? Что на HTML будешь кодить?
@@SaltyRain1 Я уже на тот момент имел опыт разработки 10 лет. Представь себе без знания алгоритмов. И естественно я не расстроился. Я теперь сам заканчиваю все собесы где меня начинают спрашивать знание алгоритмов. Тарам-парам-пам
@@nikolaifedorov685 ну, вот я и спрашиваю, ты на HTML кодишь? Или «готовые библиотечки» для всего используешь, и понятия не имеешь, что там у тебя под капотом варится
Я был на совсем другом собесе в Яндекс. Там были задачи Хард из литкода, где не базовые алгоритмы нужно писать.
Да, травоядненько на видео
яндекс конченый в этом плане. И денег не платит, и дрючит по хард задачам
Какие map? Вектора надо использовать во второй задаче. С этими map до 100 символов алфавита вектор быстрее будет тупо из за того, что проц хотя бы закешировать значения себе сможет. В map элементы памяти по разным адресам находятся. Это очень медленно.
Контент полезный. Только по первой задаче у сортировки временная сложность O(n log n), а не O(log n). Суммарная сложность для решения, соответственно, тоже O(n log n)
Да, действительно, видимо я не расслышал корректно в тот момент - сложность O(n log n)
@@vladimir_balun_programmingа можете подсказать, почему вообще такая сложность?
Есть 2 сценария:
1) сортируем массив (сложность n*log2n (быстрая, в среднем) + log n, поиск)
2) просто складываем все что видим, сложность n. Сортировки не требуется
Итого, выгоднее тупо сложить массивы, если n>3
сложность О-большое - это наихудший сценарий. А 2ой пункт у вас - это наоборот наилучший сценарий@@valeryzeryl9145
@@valeryzeryl9145могу ошибаться, но чисто интуитивно, если не отсортировать, придется сравнивать каждый последующий интервал со всеми уже объединенными, соответственно сложность до 0.5n^2 вырастает
@@valeryzeryl9145 как ты сложишь [[1,10], [20,30], [5,15]] корректно за один проход?
Ошибка во второй задаче 33 строка. for store[right] > 1. Пример строки, которая обработается с ошибкой: abcabbcd. Когда left будет 2, а right 5, нужно будет left довести до right, иначе две подряд идущие b создадут ошибку.
вторая задача это прям типовая задача из 24-ого задания егэ
В первой задаче в условии ошибка, как выяснилось позже речь не о интервалах как написано в условии, а о отрезках, так как когда конец первого совпадает с началом второго считается что пересечение есть 🧐
Открой окно
Интервал с закрытым концом. Проблема в чём?
@@constantinegeist1854 В том что у интервалов концы не закрыты. Концыу закрыты у отрезков. Тоже смутило. Можно было использовать собирательное слово промежуток.
@@arsenypogosov7206 не знаю, зачем в русском языке понапридумали кучи терминов, если суть одна... в английском, если не ошибаюсь, всегда просто interval: open interval, closed interval, left-open interval, right-open interval
а так, просто дрочь на терминологию, как по мне
хотя да, может быть недопонимание
@@constantinegeist1854 в целом да, согласен с вами.
Вроде на собеседованиях в яндекс задачи сильно сложнее спрашивают. Или это не так?
Эфемерность собеседований просто поражает, смысл их вообще тогда проводить....
а в Го-шке нет Set-а? ну или можно было массив булов заюзать во второй задаче.
но то что код не запускали и "я вижу ошибку" - зачет )))
во второй задаче можно и константным массивом булов, и битами на инт32
@@Varkatelхоть кто-то написал про это)
Set'а нет, только мапа
Вторую задачу можно решить за линейное время, если воспользоваться словарём на основе хэш-таблицы с поиском\добавлением за O(1). В словарь складывать последовательность уникальных символов и проверять каждый след. символ за О(1). Хз как работает store в go но вроде как я понял, то это не хэш.
так store здесь - это имя переменной типа map
а поиск в map - O(1)
1 задача sort.Slice и нет функции max 👍 я проверил код - не работает. Ласт айтем переопределяется всякий раз. Мне все это странно.
intervals = [[1, 6], [1, 3], [8, 10], [15, 18]]
temp = []
intervals.sort()
ans = [intervals[0]]
for i in range(1, len(intervals)):
temp = ans[-1]
current = intervals[i]
if current[0]
А на реальной АА какой вердикт бы был? И на какой Грейд?
Что такое АА? Батарейки?
@@Kondratyevv название секции в Яндексе, когда тебя собеседует опытный собеседующий (а не рандомный разраб, у которого это первое собеседование за полгода). Обычно оценки таких секций больше весят при принятии решения о найме и грейде.
@@w01fer86 это не задачи аа
А в go нет структуры множество(set)?
На первый взгляд цикл сдвига l кажется лишним. Ситуация, которую он решает не может произойти.
Есть map[string]struct{}, тот же фунционал
Не совсем, к словарю нужно велосипедить методы - пересечение, объединение множеств, вычитание и т.п.
Для обеспечения уникальности подойдёт, да.
Забавно, что именно эти задачки мне давали год назад на собесе в яндекс)
И че, ты попал в Яндекс?
@@Kondratyevv нет, завалился на одном из след. этапов(
@@MRtheLAGERAT а че за след этап был?
@@MRtheLAGERATи как попал на первый собес в яндекс? если можешь, поделись, пожалуйста
@@freestylerveevo на всех этапах дают 2 задачи, этапов хз сколько может быть, на стажировку вроде 3-4, читал, что на другие позиции вплоть до 9 таких этапов может быть
Сам попал когда набирали людей на стажировку, сначал решаешь задачи типа codeforce на яндекс контесте, если прошёл, то назначают вот такие собесы.
Проблема интервалов не полностью решена с точки зрения временной сложности.
1) Создайте вектор с размером = максимальному концу всех интервалов.
2) Перебрать входные интервалы и сохранить их в векторе: позиция вектора - это начало интервала, если интервал уже существует, объединить эти два интервала.
4) Взаимодействие с вектором для обработки интервалов в соответствии с логикой видео.
Временная сложность равна O(n), n - количество введенных интервалов. (нет необходимости сортировать O(n*log(n))). Сортировка подсчетом выполняется за время O(n), что делает ее асимптотически быстрее, чем алгоритмы сортировки на основе сравнения, такие как быстрая сортировка.
=================================================================================================
хорошее место для практики (не стесняйтесь поставить звезду :) )
github.com/IhorVodko/Hackerrank_solutions
В первой задаче надо проверять длину не на 0, а на
Можно, но не обязательно
Вот что получилось на js, первая задача:
function getIntervals(intervals) {
intervals = intervals.sort((a ,b) => a[0] - b[0]);
const result = [];
let actualInterval = intervals[0];
for (let i = 1; i < intervals.length; i++) {
const current = intervals[i];
if (actualInterval[0] >= current[0] && actualInterval[0] = current[0] && actualInterval[1]
Тесть если ты уже знаешь алгоритм то это не нужно говорить ?
Меня одного смущает что первая задача решена не верно? У него на выходе другие цифры чем в примере, т.е. попал интервал которого не было изначально, это 7
В 1 задачке же вместо lastItem = max... должен быть merged =..?
lastItem[1] = max(lastItem[1], intervals[i][1])
В логике кода все правильно. Это для расширения диапазона интервала
Если у нас есть последовательность [[1,3],[2,8],[2,6]...]
На первой итерации lastItem - [1,3], а intervals[i] - [2,8], и назначается "больший" конец
lastItem[1] = max(3, 8) // диапазон lastItem становится [1,8]
На следущей итерации lastItem - [1,8], а intervals[i] - [2,6] , и назначается "больший" конец
lastItem[1] = max(8, 6) // диапазон lastItem остается [1,8]
Где такой метод slice.Sort ??? С ним НЕ работает. Нигде не могу найти. Заменил на sort.Slice - работает
Во второй задаче при нахождении неуникального символа я бы ещё проверял длину отрезка от левого указателя до конца строки и сравнивал его с длиной текущей самой длинной строки.
Условно: строка на 20 символов. Все символы были уникальны до 11го. Нам нет смысла дальше проверять
не верно.
Например, строка s = abcdefaglm: первые 6 символов уникальны, потому встречается символ a, отбрасываем s[0] и теперь уникальная максимальная строка "bcdefaglm" длинною 9
@@ВячеславБурлаков-м1л перечитай ещё раз, что я написал.
@@ВячеславБурлаков-м1л ок, пример с 20 и 11 был неверен. Но проверка верна
Дали б лучше на литкоде порешать, там хоть тесткейсы можно писать и проверять свой код
для первой задачи time complexity задачи = сложности сортировки - это nlogn а не линейная как сказали на интервью
Он потом поправился
@@undefined4992 он потом сказал log(n) вместо n*log(n) что тоже неправильно, потому что в худшем у квиксорта будет O(n*n)
На что влияет это знание, если сортировки не избежать?
@@TheCharlieGordon на непосредственно оценку времени работы, это и есть финальный ответ на вопрос
@@undefined4992 а что даст эта оценка, если сортировка неизбежна? Типа, какая разница, сколько стоит товар, если ты в любом случае вынужден его купить? Т.е. как в этом случае поможет знание - O(n) или O (n*log(n))?
Прикольное интервью, но хотелось бы понять:
1. На какой уровень это интервью
2. Такого рода задачи где то применяются на практике? Какие задачи решают?
Я то думал там спрашивают какой то ужас, а там чет все слишком легкое
Что за задачи такие где оценить сложность задачи уже сложно )
Владимир красавчик,провел на высшем уровне
Забавно, но первую задачу вот как есть только что давали мне в мете на интервью в конце апреля
Большей глупости чем спрашивать аглоритмы на собесе не существует. Это абсурд !!! Сам никогда их не спрашиваю у кандидатов, но по опыту наборов в другие отделы могу сказать следующее: после проверки алгоритмов вы набираете людей 2 типов 1) просто задрочивших литкод ради собесов 2) реальные задроты-токсики с ЧСВ.
Потом мои коллеги тимлиды с соседних отделов ноют что у них в команде не те люди которые им видите ли нужны, а у меня нормальные адекватные ребята и дружная команда без алгосов и никаких проблем ...
Выводы делайте сами.
(работаю в одном очень крупном аутсорсере РФ)
Алгоритмы это способ большим популярным компаниям фильтрануть поток и сбить зп. Если работаешь в рандомной галере, как ты написал, зачем там алгоритмы спрашивать - загадка
@@ChannelCheesecake вместо литкода лучше показать типичный ынтырпрайзный код, в который добавлен говнокод, и попросить поревьюить и порефакторить. Сразу видна куча вещей о кандидате. Задрачивание на литкод для 99% компаний/проектов мимо кассы
@@constantinegeist1854 да все бы запросто такое проходили. В рамках собеса ничего интересного не уместишь
@@ChannelCheesecake Мы такое практикуем и отшиваем большинство кандидатов, т.к. в упор не видят проблем в коде, или замечают только небольшую часть, или начинают сильно плавать, когда спрашиваешь, как сделать лучше. Задание простое может быть: напр., в контроллере напрямую запрос в БД, в коде явно присутствует состояние гонки (напр. пример с балансом на счету) и т.п. Спрашиваешь, где в коде проблема -- полбеды, затем спрашиваешь, как бы отрефакторил, и тут тоже многие начинают плавать. Плюс куча тем для беседы отсюда может быть ("окей, напрямую в БД лезть из контроллера если не хорошо, какой паттерн бы использовал?", или "окей, здесь состояние гонки, объясни почему? за уровни серилиазации БД пояснишь?" и т.п.) У нас кандидатов на "синьоров" с рынка было пока что единицы, кто смогли всё ответить приемлемо.
Абсолютно согласен
Я нифига не могу собраться на собесах, даже концепции которыми пользовался с трудом могу вспомнить и реализовать
Но ощущение конечно что чел знал какие задачи будут и паттерны
Эти задачи есть на литкоде, вполне вероятно, что он их уже решал
тут задачи достаточно простые
Это очень простые задачи, алё
@@ChannelCheesecake это ваше субъективное мнение
@@get_out_it это статистическое мнение, эти задачи сильно проще, чем те которые можно обычно увидеть
Че за бред? Я думал на мид+ собесе просить будут написать сервис по тз, а тут алгоритмы, так еще и сложность никакая...первая задача это уровень даде не стажера
Как достал этот Яндекс со своими алгоритмами на собесах
И все прочие, которые насмотрелись на гугл и его собесы. Я иногда на собесах так и говорю, когда чувствую, что не прохожу по задачам некоторым и собес идет к фейлу. Типа спортивное программирование - это конечно круто, но я нанимаюсь не олимпиады по информатике выигрывать, а решать задачи бизнесса с помощью кода. Столько разной чуши спрашивают, а по факту приходишь и штампуешь CRUDы.
Почему тимлиду из Яндекса дают задачки для студентов
Я был фронтенд разрабом мне такие задачи давали тоже. Опыта во фронте 15 лет. Ни разу за 15 лет интервалы не мёржил. Я вообще не понимаю, зачем это нужно, что фронту, что тим лиду...
Первая на сортировку, вторая на плавающее окно. Leetcode уровень easy. Даже решение смотреть не стал, тривиально все.
0:43. Was machst du?
Быстрая сортировка сложность n*log(n), хотя собеседуемый сказал log(n)
O(n*n). А n*log(n) - только для среднего случая. А считают по худшему.
@@warmrew9033библеотечные сортировки (про которые и говорил собеседуемый) используют quicksort+heapsort это так называемый introsort он работает и вхудшем случае за nlogn
Молодец хорошо держится! Красавчик!
Здравствуйте Владимир давно смотрю Ваши каналы! Работаю на с++ уже 3 года, стараюсь совершенствоваться! Спасибо за мотивацию!
Блин большое спасибо за видео. Очень понравилось. Впечатлило нахождение ошибки просто взглядом, я такого не видел еще. И вопрос , как прокачевается подрбный навык? Я понимаю что самый очевидный ответ - решай задачи 😂. Я имею ввиду может есть какая та ступенчитая система, от простых задач к сложным?
литкод и аналоги в помощь)
давай в слдщий раз что-нбдь, чего нет в neetcode roadmap, а то неинтересно даже
в цикле будет паника если в матрице пустые массивы без элементов
Провожу подобные интервью больше шести лет.
Сугубо моё личное мнение... если оценивать работу интервьювера только по выложенному видео, то (на мой взгляд) отработал не выше середины. Конечно, так оценивать не совсем правильно, т. к. кандидат уже "разогрет" и находится в контексте происходящего (не задачь, но сомой процедуры).
Из того, что сразу видно, независимо от контекста:
+ провёл дружелюбно ("безопасно" для кандидата)
+ уточнял "понятно ли задание"
+ провеёл по положительному пути
+ выявил недочёты, какие-то дал найти самому
+ обсудили основные тест кейсы
+ дал фидбэк
+ позволил задать вопросы
- технические ошибки (в сложностях, что является основой задания, если судить по уделённому вниманию)
- не обсудили альтернативные решения и использование средств платформы.
- не выявлены способы принятия решений (как и сами принятые решения по допустимым входным данным, ошибка или пустое множество на выходе и пр.)
- кандидату не показан потенциал для проф. роста (не вызван интерес)
- не запрошен фидбэк на интервью от кандидата (возможно будет позже - на отдельном звонке).
Моё мнение: интервьюверу стоит озаботиться изучением вопроса о дополнительных целях интервью. Основную задачу интервью (выявить техническое соответствие кандидата, запрашиваемой позиции) с натяжной выполнил. Есть и не менее важные дополнительные цели интервью.
Это стандартный формат 3-го этапа Яндекса, а больше в РФ таких интервью никто не проводят, если, конечно, цель - закрыть позицию, а не найти еще один винтик в систему или почесать свое ЧСВ.
>кандидату не показан потенциал для проф. роста (не вызван интерес)
Компанию на Я при найме не интересует твой опыт и знания за пределами Литкода (правда, есть еще архитектурная задача), в итоге разве что можно попросить з/п ближе к правому концу вилки.
>не запрошен фидбэк на интервью от кандидата
По окончании предлагается форма обратной связи. Можно там потыкать, что-то написать про проблемы. По-моему, результат идет в /dev/null.
@heuretic "а больше в РФ таких интервью никто не проводят, если, конечно, цель - закрыть позицию, а не найти еще один винтик в систему или почесать свое ЧСВ."
Не уверен, что я правильно понял что Вы хотели сказать в этой части.
На всякий случай поясню некоторые моменты.
- Интервью с написанием кода в РФ проводит не только Яндекс. Как я уже написал - у нас такие интервью. Только у нас это второй (и как правило последний) этап. Он объединён с выявлением софт-скилов, общей технической беседой и подробным рассказом о процессах в компании или ответом на вопросы кандидата.
Первый этап - короткий технический "скрининг" по телефону с целью принятия решения о втором этапе (в том числе кандидатом).
- Что касается "почесать ЧСВ" на интервью - это самое плохое, что может делать интервьювер (таких - сразу в лес :)).
- Про закрытие вакансии или поиск "винтика в систему". Как раз поиском винтиков (в том числе по довольно специфическим запросам) команды (в аджайл) и отдела (в матричной системе) я занимался. Написание и обсуждение кода отлично подходит для таких задач (конечно, только им не обойтись, о чём я и писал в оригинальном комменте). На моих интервью в том числе можно гуглить (как и в рабочем процессе).
- Про "вызвать интерес": тут у Яндекса, конечно, особое положение - к ним многие уже за имя готовы идти. Для компаний без имени стоит задача заинтересовать кандидата. Одна из лучших мотиваций, как показывает моя практика - именно вызвать неподдельный интерес. Это даже деньгами не всегда перекупается. :)
- За информацию о наличии фидбэка спасибо - моя догадка о том, что он собирается позже была верна.
@@Barrrashчепуху какую-то написал, ЧСВ потешил своё очевидно
У меня в Я было два литкод интервью с рандомными и одно с потенциальным тимлидом. Про процессы я спрашивал сам, человек от ответа ушёл, видимо, было лень обсуждать что-то после того, как уже решил, что не подхожу. Фидбек не спросил ни один.
@@antoneltchaninov2246Печально. Подобная лень портит впечатление о компании. Имхо, собес нужно в любом случае проводить до логической точки и отвечать - тоже, раз "разрешил" задавать вопросы :)
У меня бы 30 минут ушло бы на решение одной задачи. Надо больше решать ? Я уже больше года решаю задачи, но быстрее я их решать не стал.
надо перед собесом их всех заучить, а после оставить до следующего собеса.
Имхо, пройти собес от Яндекса можно лишь для того, чтобы потешить свое самолюбие, ну и просто прикольно. Я когда-нибудь обязательно это сделаю, когда будет время. Один раз ходил, решал весь собес одну задачку. Решил, но, очевидно, этого мало. Классические алгоритмы, опять же имхо, интересно решать как тренировку для ума
Стопэ, вторая задача это по моему easy с leetcode
Первую задачу решил бы с использованием set, так как его в перспективе легче поддерживать, тем более что в коммерческом программировании, сложность алгоритма зависит от необходимости выполнения различных запросов, по типу добавить новый интервал, или вывести в каком интервале лежит число x и находится ли оно в этом интервале и т.д и set(или другая сбалансированная структура данных) подходит для этого лучше
Во второй задаче просто любая хэш таблица без повторений и ВСЁ
@@thevirusnvgm2518 скинь решение
Если я что-то и понял про коммерческое программирование - оно стремится написать микрофункции обрабатывающие единицу - сущность, агрегат и тд.
Реальная программа и даже SQL работают с множествами. Всегда с множествами.
И реальная оптимизация это разбить код на этапы, которые можно параллелить, а не написать черный ящик который сдвигами покажет минимум микросекунд.
Потому что в этот ящик потом не влезть чтобы его распилить на два, ибо он совершенно нечитаем!
Вопросов нет, он мегабыстр... Но вот на вход не одна строка а 100000 и микросекунды плюсуются. И делая множества всегда почти можно редюсом поделить число операций увидев одинаковость. А потом редюсом же раскопировать результаты обратно во множество. Вот где оптимизация. А это - это развлечение для мажоров.
Да ладно ребят, там склейка на монтаже. Вы думаете чел просто сел и решил. Конечно нет. Может договорняк, ради контента
Ну хз. Это я решаю литкод 4 месяца. И сразу же решил эти задачи. Врядли постанова
@@blabla-f7nда там видно склейку. Если прям с нуля там минут 40 надо, если не гуглит, а с помощью gpt 4 версии, она решается за 3 минуты, лучшим алгоритмом, плюс все расписыаается.
задачи элементарные, что их решать. просто 2 простейшие свёртки и всё
@@404Negative что значит свертка?
Легко решается
Обе задачи имеют средний уровень на leetcode.
Не изи)
Чот Баламут постарел, в яндексе из него все соки выжимают. Возвращайся в Озон!
Побриться, подстричься и как новенький!
Реально чот похудел вообще
озон овно еще хуже
Он просто тренеруетсч
Глаза пустые
Чушь полная. Работа ежедневная не так строится и не так проверяется
16:35 ну все задачу с первой проходки не решил, в яндекс не берем
По поводу второй задачи. -забавно получилось что интервьюер упомянул что 26 букв алфавито. только в самом условии. неговорилось про буквыалфавита - написано символов, какие. символы могут быть - никто конечно не спросил
Какая разница
@@ChannelCheesecake большая разница, если ты не знаешь конечно множество символов то ты не можешь в решении зарезервировать массив на 26 символов к примеру
@@get_out_it во-первых интервьюер сказал, что там не только буквы, а ASCII, во-вторых делай Map и не думай над таким
@@get_out_itреч о резервировании не шла, символы подсчитываются в рантайме.char почти везеде 1 байт = 256 символов окей даже если мы подключим крутые библиотеки со всем возможными языками мира там не наберется и 2*10^9 а это обычный int. Что считается константой при размере входа стремящегося к бесконечности
По первой задаче
А какие это задачи на литкоде? Чтоб самому порешать
Интервалы - 56
Самая длинная подстрока - 3
Т.е. в яндексе занимаются не интерпрайз программированием, а пишут алгоритмы? Ну-ну.
видно, что человек уже знал алгоритмы решения, просто вспоминал
а когда уже собес с работником другого языка?
все в яндексе и сам яндекс - дно поганое. как компания, так и люди в ней. да еще и куколды)
да, яндекс уже лет 10 как опустился, самое интересное что там ЗП чуть ниже средних по рынку, но все туда рвутся почему то, подозреваю просто хотят эту ачивку не более ... ))))))
🤣 куколды?) в смысле смотрят, как их сотрудников натягивает к себе Тинькофф и наслаждаются?)
У первой задачи не линия по памяти, а константа, потому что пространственная сложность относится только к промежуточным данным.
Странно, что интервьюер это не подметил.
По сортировке скорее всего оговорился, потому что странно думать про лог(n)
Поделитесь плиз ссылочкой на источник, что память на результат не учитывается в пространственной сложности.
@@radiosh66 Привет. Мы оцениваем алгоритм, а не среду с которой этот алгоритм взаимодействует для ввода/вывода, иначе минимальная пространственная сложность была бы линией всегда. Мы не используем массив для вычислений, поэтому учитываться в пространственной сложности он не будет.
Можно почитать, например, в computational complexity Димитроу.
@Kelb90 спасибо за разъяснения, осталось на литкоде теперь всех переучить новому подходу к оценке пространственной сложности, т.к. на моей памяти во всех объяснениях учитывалась вся новая память, которую аллоцирует функция.
@@radiosh66 да, в литкоде может быть требование выполнять in-space, когда нельзя делать промежуточный массив и возвращать его. Тогда подход к решение сильно меняется.
Чел идет на тим лида, использует сортировку и говорит скорость линейная🤦🏻 как их вообще рассматривают с такими знаниями?
Где ты тут увидел что чел идёт на Тим Лида
Нет, это тим лид проведёт собеседование
да чего тут страшного, можно оговориться, переволноваться... если подумает, ответит правильно
Очень простые задачи.
Ты не поверишь, сколько кандидатов надо перебрать прежде, чем найдёшь кого-то, кто их решит
@@w01fer86 вау найти того, кто может решать задачи, но потом двигать и красить кнопку.
Тимлид краш 🔥🔥🔥
Как можно распинаться пол часа при решении столь лёгкой задачи то?
Вы идиот?
Собеседующий дает некоторые ответы соискателю. На самом деле это не хорошо и не плохо, можно если человек запутался подтолкнуть его и смотреть на блеск в глазах, все еще понимает он контекст или мы его потеряли. Но может быть и наоборот: кто-то пролезет на энтузиазме собеседующего. Но может быть этот энтузиазм происходит из того, что ребята друг друга знают.
Чет легенькие задачи
Задачи гавно, к реальной жизни отношения не имеют.
слабенько, хотя бы 1 medium бы дали
это медиум на литкоде
Именно из-за таких собеседований я каждый раз отказываю рекрутерам яндекса
Очередное доказательство, что если повернуть стол и собеседующего превратить в собеседуемого, то он просто не пройдет собес, а завалить его на нем легче легкого).
алгодрочеры не нужны
Звуки глотков еще громче бы сделать ;)
100% постановка. Вам, ребята в театральный надо ;)
дали тимлиду два изяна... а мне хард впаяли с дп на 50 строк кода.
Хахаха. Порекомендуем тим лиду яндекса (если он данные задачи видел первый раз и это все не "актерская игра") больше сидеть на литкоде. Если таки он видел это первый раз, то непонятно как в яндексе обычные люди становятся (давайте только не будем уподобляться самому яндексу, и скажет что обычные люди с точки зрения данных алгоритмических задач) тим лидами. Потому что, то, что видел и в чем участвовал я не было таким простым. видимо рядята любят тащить себе в команды не кого-то с "улицы", а своего проверенного, а остальных валят. неприятное впечатление от яндекса.
А тебе какие задачи дали? Ну эти оч простые, мб с наймом беда сейчас
По первой задаче не совсем понимаю почему сложность на этапе мержа интервалов оказалась O(N)?
Остальные интервалы то тоже нужно учесть и смержить с остальными, а это уже возрастает до квадратичной зависимости - что огромная разница
для этого можно пройти по всему массиву всего один раз и выполнить по одной операции над каждым значеием из отрезка, в худшем случае будет O(2N) == O(N)
@@igorf243 "Дан массив интервалов, объедините все пересекающиеся интервалы и верните массив непересекающихся"
Ну? Имеется же в виду что у нас может быть несколько объединенных интервалов, которые нужно вернуть
А вернуть мы сможем, когда совершим операции над всеми НЕобъединенными интервалами
По итогу выполнение этой задачи - возвращается один только массив, с которым ищется возможные пересечения
@@IvanGalkin-f8mесли массив отсортирован, то нам надо просто проверять пересечение с предыдущим: пересекаются - объединяем, не пересекаются - отправляем на выход и начинаем собирать новый. Чистейший O(N).
Это нумерология какая то что ли? Или астрология?
Как мы дожили до того чтобы писать код на интервью в блокноте с подсветкой синтаксиса языка ? 😮
В колледже информатики когда учил синтаксис писал на бумажке и сдавал преподу или мелом на доске, а потом уже пересаживались за компы
Ого, не знал, что Щербаков в айти вкатился :)
Чет туго пошло у парня
Нифига се туго 2 медиум за 37 минут...
@@dibehemoth401Так это изи уровень
@sb9185 это обе медиум литкод. Хз как в яндексе внутри считают, конечно.
646?@@dibehemoth401
ну и видно что чел готовился и решал уже эти задачи потому что. сходу для первой задачи определил что нужно сортировать, для второй задачи сходу вопсользовался паттерном скользящего окна.
Наш брат головами таких в школе мел с доски вытирал
void task1() {
var initial =
List.of(new StartEnd(3, 5), new StartEnd(4, 6), new StartEnd(7, 8), new StartEnd(1, 2));
var reduced =
initial.stream()
.sorted(Comparator.comparing(StartEnd::start))
.reduce(
new ArrayList(),
(partial, next) -> {
if (!partial.isEmpty()) {
var indexOfLast = partial.size() - 1;
var last = partial.get(indexOfLast);
if (last.overlaps(next)) {
partial.set(indexOfLast, StartEnd.merge(last, next));
return partial;
}
}
partial.add(next);
return partial;
},
(first, second) -> first);
System.out.println(reduced);
}
record StartEnd(int start, int end) {
boolean overlaps(StartEnd other) {
return start
Стримы это очень круто. Стримы это хорошо забытое прошлое и счастливое будущее.
s/second.end/Math.max(first.end, second.end)/