Собеседование в Facebook - Разбор Для Начинающих 

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

@@runneso Да, наличие отрицательных чисел существенно влияет на способ решения. Задания с отрицательными числами пока официально не встречались, но во всяких тренировочных сборниках изредка попадаются. Зато можно почти серьёзно говорить старшеклассникам: осилите 27-е - получите задел на FAANG.

​@@IvanYugovтак 27 часто сложнее этой задачи. Она придумывается за минуту (не преувеличение). Такие подарки в 27 редкость. Обычно что-то посложнее. В этом году например (я писал ИГЭЭЭ) была задачка на префиксы, нужно было максимизировать сумму трёх чисел, разность индексов у любых двух из них хотя бы k. Делается за линию, но идейно сложнее, чем это. Так что да, алгоритмическая база в последних двух задачах нужна нормальная, больше, чем для этой задачи.

@@user-jp8jl5mg3v то что ты назвал тоже очень легко, это прямо база информатики 27

@@nixxik__ Ну да, просто первое в голову пришло - пример 27, который похож по теме задачи, но сложнее идейно. Понятно, это не сложнейший из типов.

Тоже восхищён - усыпить меня буквально за минуту - это талант! 😆

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

@@gggppp228 согласен, надо готовиться к такому. Изниоткуда такой скил не появится

Адитья Бхаргава "Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих"

Алгоритмы это 3-4 вопроса из пары десятков на онсайте.

Роберт Лафоре "Структуры данных и алгоритмы"

leetcode

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

Вот у меня тоже возник вопрос, если я правильно понял, похожий, что будет, если после того, как мы взяли в ответ количество подмассивов с суммой 4, например, а потом снова плавится подмассив с такой же суммой и он нам снова потребуется. Тогда в ответе появится лишний +1 в ответе.

у нас скорее всего на бумажке попросят прикинуть.. т.е. как-то так не ходу.. я на одном просто рогом упёрся и какие-то вещи на пальцах объяснял, чтобы каракули долго не писать

Он же сказал в видео - 20 минут

эт специальо мысли вслух тк видос на задаче поставил на паузе, и я не программист

Попробуй в коде перед тем, как задавать вопрос. Может оказаться, что вопрос бессмысленный.

Конечно нет, мы в мапе по ключу храним число подмассивов, которые начинаются в 0, заканчиваются где-то до текущего элемента и имеют сумму равную ключу. Её обнулять нет смысла.

надо считать все числа подмассива, а вы видимо считали выборочно. для K=5 и массива [4,2,1] ответ 0, а не 1, нельзя складывать 4 и 1 без двойки. проще всего это проверить квадратичным алгоритмом с полным перебором. он дает ответ 5.

[-5, 5, -5, 5] на втором шаге сумма = 0, в ансвер добавится по ключу [-5], т.е. 1, записанная на первом шаге. т.к. второй элемент [5] нам подходит как подмассив. на 4м шаге опять 0, по ключу [-5] уже значение 2, записанное туда на третьем шаге. ансвер = 1+2 = 3. это потому, то на четвертом шаге подходят два подмассива: последний элемент [5] и [5,-5,5] "зачем от 0 отрезать кусок с суммой -5, чтобы получить 5?": 0 - (-5) = 5, вот поэтому "Может случится ситуация, когда to_remove будет 0 и тогда к answer добавится 2, вместо 1": нет, в ансвер плюсуется по ключу [ту_ремув], но счетчик увеличивается по ключу [субаррай_сум] [5, 0, 0, 0, 0] начиная со второго шага ту_ремув всегда ноль, но по ключу ноль находится единица, т.к. увеличиваться постоянно значение по ключу [5]. в итоге ансвер = 1+1+1+1+1 = 5

@@SayXaNow спасибо за подробное объяснение! Действительно, даже если {0: 1} увеличивается, то всё правильно работает, и эти отрезки с 0 суммой учитываются в ответе

Привет! Тоже фронтендер, но поменьше) Решать задачи, просто решать задачи, тренировать мозг и глаза, формировать насмотренность. имхо такая микросфера, где опыт очень сильно решает. Я открываю Литкод - делаю простые - усложняю, пока не сломаюсь - изучаю решения, записываю/учусь применять/решаю подобные. В алгосах главное уметь в пространные концепции, «Грокаем Алгоритмы» очень мне помогло в свое время с освоением и пониманием что вообще в таких задачах происходит, у тебя на самом деле есть небольшое количество концепций, которые надо изучить и, самое важно, понять, чтобы уметь применять

@@mityaoreh привет. Благодарен за совет, буду наверстывать упущенное хоть это и очень тяжело мне дается

@@LonelyRiderStonerBand отлично понимаю) удачи, сил и терпения, всё обязательно получится :)

@@mityaoreh Thanks mate ;)

А он через что решил?

Имеется ввиду что можно не использовать хэш мапу

Код на питоне понятен даже если впервые видишь язык. Собственно его популярность отчасти обусловлена простотой

@@Deletedeletedelete Не преувеличивайте, там достаточно фишек в синтаксисе, вопрос в другом используются они или нет!

а, позже в видео сказали)

надо

Надо говорить. 99% что задачу не поменяют, «видеть», «знать как решать» это еще не«решить», плюс 80% успеха прохождения алгоритмической сессии - много говорить, объяснять логику и трейдоффы

Для развития алгоритмического мышления.

@@user-vo2fq6my8x Т.е. этот алгоритм ни где не используется ;)?

@@101picofarad можно представить, например, что вы ищете временной период, когда денежный баланс на счёте был равен определенной сумме

Sliding window сработает только если все числа >= 0

​@@mrxDotsсработает в любом случае, просто он медленный

Да.

В терминах Big O (O-большое), константы не учитываются при рассчете алгоритмической сложности, поэтому итоговая сложность записывается именно как O(n). Рекомендую подробнее почитать про оценку сложности алгоритмов.

@@asethone согласен;-) но алгоритм с O(n) используемый в цикле m раз, всегда будет быстрее, чем тот же цикл с алгоритмом с неправильной оценкой сложности O(3*n). сложности у алгоритмов одинаковы - скорости разные

​@@Sergey-Primak Ну вопрос оптимизации - это уже отдельная тема. Уменьшить количество проходов по циклу после того, как ты придумал быстрое решение всегда можно успеть. Главное, и самое сложное на собеседованиях - это как раз придумать такое решение, которое именно в терминах Big O будет наиболее оптимальным. А то, что ты там лишний раз добавишь O(n) вне цикла - это никого даже не смутит, ведь O(n) + O(n) все еще O(n).

Я тоже обратил внимание. Интересно, какая должна быть сумма за рекламу, чтобы даже чел, работающий мидлом в лондоне, согласился ее опубликовать у себя на канале) Без негатива. Просто тоже любопытно.

благодарю

@@SayXaNow да, я прочитал вашу дискуссию ) жаль, что после того, как свой коммент написал. Отличный тест, спасибо!

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

тогда вообще ответ поменяется

@@user-qp9tg5pn5e да я это уже понял )

С двумя индексами, кажется, можно и без хеш-мап решить

Петухон, Жава, какя разница?

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

Это как это через гистограмму?

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

@@user-jp8jl5mg3v n шагов, на каждом шаге n проверок, если хэш совпадает

@@sergeev_oleg вообще в алгоритмических задачах всегда обговаривают тип, если это важно для решения.

О(5*N)==O(N), т.е. речь о решении задачи за время сопоставимое с количеством данных, когда N стремится к бесконечности. Поэтому особо разницы нет, конечный пользователь зачастую не заметит разницу в обработке чего-либо за 1мс или 5мс, но если функция уйдет в степени, то дело плохо

@@alfagamma2499 а откуда Вы взяли 5х, почему время построения хешмапа сопоставимо с его размером, а не, скажем, квадратом его размера?

@@sidhott если ты за конкретное конечное количество шагов его достраиваешь, а не собственно строишь с нуля, то ответ напрашивается сам собой. Да за каждый новый сегмент тебе приходится по сути делать много действий, но по итогу то ты прошел по массиву чисел раз и получил ответ

@@alfagamma2499 а какая разница достраиваю я хеш или строю с нуля, если мне память двигать? n раз передвинуть n/2 ячеек памяти -- это O(n)? "много действий" -- это сколько конкретно, О(индекса)? P.S. прошёл по массиву чисел раз -- только звучит красиво, т.к. O(n) + O(n2) = O(n2).

​@@sidhottможно родить массив с упреждением и удваивать его при переполнении чтобы не перекидывать его в памяти при каждой записи.

Так тут int используется, то коллизий вообще нет, то есть get(key) будет работать за константу

@@h00per12 Коллизии могут быть, даже если хранятся обычные инты, хэш-функция будет вычисляться по модулю от длины массива

@@h00per12 коллизии появляются из-за того, что хеш функции для бесконечного кол-ва ключей дают ограниченное кол-во хешей и тут не важно инт или нет. Нужно будет либо растить мапу до более чем n^2 памяти (ведь парадокс дней рождение root(n)) либо будут коллизии

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

Ох, уже столько дискуссий на эту тему в комментариях развели. Это довольно странно. Так как Саша сказал про хеш-мапы, то речь именно про unordered_map, а не map. В *_среднем_* время извлечения и вставки нового элемента в хеш-таблицу именно O(1) - тут не может быть каких-то споров. Да, в случае большого количества коллизий, и в случае добавления нового элемента при превышении коэффициента загрузки, что в свою очередь ведет к рехешированию всего содержимого хеш-мапы, это время может быть близко к O(n). Но, опять таки, в подобных задачках тебя, как правило, должна интересовать именно *_средняя_* сложность алгоритма, поэтому тут все корректно оценено. Мораль: не нужно быть *пессимистом* и всегда смотреть на _худший_ случай. Будьте *программистом* и смотрите на _усредненный_ 😉

Это как

@@HopeOfMankind_ почему-то мой комментарий был удален. Почитайте про дерево отрезков для суммы. Оно позволяет достаточно быстро, за logN отвечать на запрос от нахождении суммы на любом отрезке tree[l;r] , хотя в данном случае префиксы будут эффективнее, потому что у нас же не один отрезок.

значения из словаря всегда за О(1) же

Реализация конкретного словаря зависит от библиотеки, но в основном - это хеш-таблицы. К примеру, стандартная библиотека шаблонов STL в C++ предлагает unordered_map, в документации, к которой, можно увидеть, что средняя скорость извлечения, удаления и добавления нового элемента O(1). Аналоги: HashMap в Java, dict в Python. Возвращаясь к STL в C++, там есть и обычный контейнер map, который реализован как раз на красно-черном двоичном дереве - в нем-то, все аналогичные действия и занимают O(log n). В основном, когда говорят про словари, имеются в виду именно хеш-мапы, о чем как раз Саша и говорит на 10:05. Поэтому алгоритмическая сложность последнего решения действительно O(n), и ошибки здесь нет.

под капотом обычно массив

​@@asethone Добавление нового элемента в хеш-таблицы не o(1), необходимо добавлять сложность увеличения и ребалансировки хеш-таблиц, так что *среднняя сложность* равна все той-же o(log n). В общих условиях, где не выделяется 2 ГБ память на все int hashtable.

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

@@mrxDots Яндекс просит от 50 000 до 250 000 р. (скидки не рассматриваем) за то что, ...Яндекс дает каркас, это цель курса - научиться САМОСТОЯТЕЛЬНО изучать недостающую информацию... Повторюсь, ищите материалы самостоятельно, но платите за это деньги и не малые - именно в этом у меня основная претензия. На одно из Финальных Заданий - нужно было использовать HTML страницу, которую предоставлял ЯП. И именно из-за этой страницы, часть проекта не работало. Причина, которой она не работала, не расскрывалась в материалах ЯП. (собственно для решения того Финального задания матреиалы ЯП вообще не нужны были, так как в них не содержалась информация нужная для написания требуемого кода в ФЗ.)

и чего там питон дают или что ещё?

Это как

@@HopeOfMankind_ последнее решение у Саши. Поиск по хеш мапе это О(1)

что такое префиксная сумма?