Задача из Собеседования в Амазон: Поиск Знаменитости. Метод двух указателей

Пример использования метода двух указателей для решения задачи из собеседования в Амазон.
Эта задача на GeeksforGeeks: practice.geeksforgeeks.org/pr...
Она же на LeetCode, но требуется платная подписка: leetcode.com/problems/find-th...

[@sashalukin]

Создал Telegram канал, в котором рассказываю о жизни в Лондоне, работе в Google и подготовке к собеседованиям. Подписывайтесь: t.me/saschalukin

[@Rayzervs]

Ох и загадки у Амазона,чтоб стать обычным сборщиком заказов)

[@seral777]

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

[@seral777]

@А P Так это и работает, при чём везде. Работникам платят мало, а те где то, что то, как то подворовывают...

[@alexglikman8629]

@А P А смысл? Найдут и посадят. Банально же.

[@vasilypokrashchenko1793]

не приняли, теперь видео записывает

[@faketeam460]

@@vasilypokrashchenko1793 , просто попасть к ним на собеседование - это уже достижение

[@alexandershubert573]

Спасибо! Отличное объяснение. Особенно дидактически очень классно указание сложности О-большое первого алгоритма, а потом и более эффективного.

[@jury2753]

Саша, огромное Вам спасибо за замечательные видео.

[@eva_pugacheva]

очень понятное видео, большое вам спасибо, оформление супер

[@igorgrigorov4858]

Ничего не понял, но очень интересно. Вы приняты

[@debugeres]

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

[@SunIsForUs]

Здравствуйте, Александр! А не подскажите хорошие курсы для начинающих? Просто сейчас занимаюсь программирование в 1С (не знаю, знакомо Вам такое или нет))), а хотелось бы окунуться так сказать во что то глубокое))

[@user-uy4qk8sg2v]

Красава)учу языки,с тобой проще это дедать)спасибо)

[@erzhanski_krg]

Можно сократить время поиска, так как при первом прогоне наверняка кандидатура уже давала понять каких людей она не знает или знают ли ее другие. При втором прогоне исключив их, можно сократить количество итераций проверки. Например, если знаменитость окажется самой первой или самой последней то оптимизация на k.

[@dmytro9196]

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

[@magoshemeshe6841]

Для нахождения "знаменитости" можно применить алгоритм Капоне! Он заключается в следующем: "При помощи доброго вопроса и пистолета можно добиться гораздо большего, нежели одним только добрым вопросом." Таким образом, мы значительно сокращаем количество вопросов и легко узнаем кто является знаменитостью! 😃😃😃

[@georgydyagilev1602]

Плюс "к" минус "к".. все равно это О(к)..))

[@sergeysakara4842]

У того кто придумал задачу)​@@magoshemeshe6841

[@alexeymozgoball3803]

Жаль ты канал забросил. Очень крутой контент. Кстати, что за приложение для презентации используешь?

[@syavorskiy]

Очень внятная постановка задачи и разбор. Смотрю уже не первое видео, везде так. Очень круто, спасибо большое!

[@lessgrep]

Честно скажу, имея почти 20 лет стажа в разработке высоконагруженных систем, если бы мне задали такой вопрос на телефонном собеседовании, то я бы не смог на него ответить. На очном, с бумажкой, даже с учётом стресса самого собеседования, думаю проблем бы не было. Очень мне прохождение собеседований напоминает школьные курсы для олимпиадников, набор паттернов, главное иметь загруженную в память базу этих паттернов. :) Вообще, из практики, подобные задачки чаще встречаются 2 раза за проект, первый раз когда проектируешь решение, второй раз после релиза, когда всплыают косяки проектирования. До третьего кейса и далее мало кто доживает, поому что обычно после запуска и некоторого периода мейнтенанса уходишь проектировать следующий сервис. :) Даже в продуктовых компаниях.

[@MrOligapx]

дело не количестве задач за всё время работы, а в том имеешь ли ты знания(либо мышление) для оптимизированного решения задачи. Я работал почти 7 лет над физикой движка в компании Unity Technologies, там куда чаще возникают задачи оптимизации.

[@optima1super2star]

@@MrOligapx Тогда я понял, почему оптимизация в Unity страдает )) (Сразу говорю, что это не упрек в твою сторону, а просто шутка :)

[@aruh5baruh528]

Я последний раз с алгоритмами в проекте сталкивался в играх 14 лет назад. Основная работа в современных проектах протянуть данные туда, протянуть данные сюда и выстроить для этого архитектуру почище (хотя это везде так или иначе страдает). Вместо алгоритмов готовые сервисы и компоненты. Но у меня нет опыта с Фаангами, может там по другому. В стартапе кстати тоже почти все готовое использовали.

[@cityrattube]

Проблем с олимпиадниками две. Во-первых, наловчившись решать определенные типы задач, они при этом не могут распознать их в реальной жизни, если условие сформулировано иначе, непривычно (об этом еще Фейнман писал). Во-вторых, распознав задачу, они далее радостно решают ее по знакомому паттерну. Но в реальной жизни не бывает арифметических задачек в чистом виде. Например, если вопрос "знаешь ли ты А" дорогой (например, если это запрос во внешний сервис) - то это одно, а если матрица знакомств у тебя уже в памяти - другое, может, там вообще какими-нибудь битовыми операциями можно обойтись. Или, что более реалистично, если данные лежат в базе - то знакомства лучше не по одному дергать, а выполнить какой-нибудь запрос с группировками. Общая сложность алгоритма при этом будет выше (если учитывать операции на стороне СУБД), но работать будет быстрее. Хотя как тест на умение думать все равно очень полезно. Вот только другая проблема - тяжеловесы так вот пылесосят всех думающих с рынка, а потом сажают их кодить тупые выборки из списка заказов, а мелким компаниям приходится довольствоваться теми, кто школьные задачи на пропорции-то с трудом решают... Некрокоммент, да :)

[@alexgetmansky751]

@@cityrattube Вдохнем немного жизни. )) Вы все верно сказали. Могу лишь добавить, что лично меня давно удивлял тот факт, что несмотря на отбор лучших из лучших в софтверные гиганты софт становится все медленнее и все глючнее, даже если сделать скидку на бОльший объем данных и сделать вид, что за последние 10-20 лет вычислительные мощности и объемы памяти не выросли на порядки. Очень похоже на то, что реальной оптимизацией кроме как в играх и критических реалтаймовых приложениях никто больше не занимается. И даже в гейминдустрии становится все больше ААА проектов, которые релизятся сырыми - новые жэдаи, the last of us на ПК. То есть можно предположить, что или всех этих гениев-олимпиадников отправляют работать на Марс, или им просто говорят: "забейте со своими оптимизациями, у нас сроки горят". ))

[@user-qj1sp9ve9c]

Последний алгоритм с двумя указателями на начало и конец массива очень любопытный🤔 лайк и подписка!

[@Peredatochajafunctio]

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

[@palashkortik3872]

Хорошо объясняет парень. Жаль видео мало на канале.

[@MazaFakaHare]

Расскажите, как работает GC ?)

[@lDonKaban]

Объясните пожалуйста, почему в последнем условии используется «или», если нам нужно чтоб оба условия выполнялись (и person[i] должен знать person[l], и person[l] должен не знать person[i])?

[@egorrichmining1069]

ответ: (n-1) - выкинули всех + 2(n-1) -1 (потому что для потенциального короля не все 2(n-1) вариантов надо смотреть, а учесть, что одно сравнение мы знаем, когда его на последнем шаге выбирали с другим), т.е. 3n-4 шага. И можно заморочиться и строго доказать, что это аналитический (и практический) минимум при подлой "игре" ответчика. Поэтому, если бы требовалось, к примеру, вывести наименьшее число вопросов, то это было бы cout 1

[@envilogger]

Можно слегка изменить первый этап и получить возможность оптимизации на втором этапе. Спрашиваем второго, знает ли он первого. Если не знает, то вычеркиваем первого и проверяем 3го и 2го. Если же знает, то вычеркиваем второго, а первый остается как "потенциальный селеб". В какой-то момент мы увидим что все справа от "потенциального селеба", точно его знают. Что уменьшит кол-во итераций на втором этапе на кол-во человек справа от "потенциального селеба". В итоге - в худшем случае (селеб самый последний) - (3k - 2) итераций, в лучшем (селеб самый первый) - (2k - 2) итераций.

[@user-uc1uq6ez7x]

Не сильно разбираюсь в сложностях алгоритма, но разве если 3k-2 это не одно и то же что и просто k?

[@alexandrvoevodsky4247]

На самом деле даже 3k-4 в худшем случае: k-1 - на отсечение потенциальных знаменитостей. 2k-2 - на проверку последнего кандидата. Но как минимум один из этих запросов уже сделан на предыдущем шаге. Это и есть математически (а не алгоритмически) минимальное кол-во запросов вида "знает ли n-ый человек m-того?" в принципе необходимое для гарантированного обнаружения "знаменитости" в группе. Алгоритмически же, действительно, сложность в любом случае линейная.

[@envilogger]

@@alexandrvoevodsky4247 Именно так, алгоритмически в обоих случаях O(k). Просто не мог упустить момент и добавить, что можно слегка оптимизировать. В реальном коде так будет дешевле.

[@user-nd5ow2vj7m]

Так разве не придется доьавлять какое то условие

[@user-nd5ow2vj7m]

Если то

[@apristen]

4:00 - разбить на двойки, потом опять и опять, и получить дерево тем самым?

[@en1ight375]

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

[@TalkerTube]

@en1ight 2 часа? А 2 дня не хочешь? ))

[@kordaxmint533]

Ты что, это же великая честь устроиться в Амазон за копейки и веслать с переработками. Поэтому это только 1 из 10 задач, которую нужно сразу оптимизированно решить на собеседовании, чтобы устроиться на должность Junior Naive Veslyar-Кодерок

[@eugenehawkins783]

Можно попытаться усидеть на двух стульях разбивая эти сложные конструкции на функции. В случае автора как минимум еще 2 функции просится, чтобы было понятно что по итогу этот цикл находит.

[@lollol267]

@@eugenehawkins783 25 функций нужно, все лямбдами, по одному оператору. И обязательно фреймворки использовать, не менее двух на каждую лямбду. У нас тут функциональное программирование любят.

[@Yury_Dergachev]

В свое время я получил этот ответ совсем другим методом) Мне эта задача попалась в 2007 году, когда я после выпуска из ВУЗ'а на свою первую официальную работу устраивался. Представим, что все связи между людьми нам уже известны. Если записать эти связи в виде матрицы смежности некого графа, то как бы она выглядела и как бы происходит поиск в ней? Очевидно, что карта связей по условию задачи (в общем случае)- это ориентированный несимметричный граф... при этом в процессе поиска связь человека с самим собой не учитывается (т.е. главная диагональ матрицы смежности игнорируется). Перебирая все элементы матрицы смежности ниже главной диагонали мы за одну итерацию цикла проверяем ячейку [i,j] и симметричную ей [j,i]... вот от этого рассуждения я и "танцевал" =)

[@ilyaskhalitov5608]

Если я правильно понял, то это и будет первое решение из видео с квадратичной сложностью

[@Yury_Dergachev]

@@ilyaskhalitov5608 нет, оно будет эффективнее первого, но хуже наиболее оптимального. Где-то посередине

[@ilyaskhalitov5608]

@@Yury_Dergachev так какая конкретно сложность и почему? O(k^2/2) = O(k^2) на всякий случай напоминаю)

[@Hell5426]

Похоже на быструю сортировку Хоара, там похожий принцип работает с 2-мя mark сначала и конца массива

[@user-be2cy2fb9u]

Спасибо. В зал ходишь? :)

[@learpcss9569]

интересная задача, не приходилось ее встречать. спасибо за разбор. а с чем связан английский текст на презентации? для того чтобы сделать охват на англоязычную аудиторию?)

[@sashalukin]

Я тоже на собеседовании первый раз ее встретил. Причем в начале спросили задачу, которую я уже решал, в чем я честно признался. Поэтому вместо нее дали эту, попроще, потому что уже времени мало было. Но все закончилось хорошо :) Выбор английского ни с чем особо не связан, в следующих видео буду использовать русский. Спасибо за фидбек!

[@alexsanches2516]

А что плохого в том, чтобы писалось на англ?! Или в Амазон стали собеседовать и давать задачи на русском?))

[@michaelro4181]

Какой еще англ. текст? Это он про операторы языка?

[@alexpavlov9097]

7:46 почему 2k? Там же один проход по массиву в цикле for. Объясните, пожалуйста.

[@tudorbuzu6842]

(K - 1) checks for (!persons[i].knows(persons[l])) + (K - 1) checks for (persons[l].knows(persons[i])). So, you have at most 2 * (K - 1) checks in that 'for loop'

[@alexpavlov9097]

@@tudorbuzu6842 thanks

[@user-cg7ht6pg7o]

можно использовать доп память для того чтобы сократить время работы

[@calmingnaturesounds6761]

Саша, привет. Я предлагаю сократить количество проходов по массиву до 2к. По факту, ты в первом цикле уже проверяешь значит ли "потенциальный celebrity" остальных. Поэтому validation можно слегка сократить. В среднем должно дать прирост производительности.

[@legotechnicbuilderua7692]

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

[@KreesKiss]

Не задумываясь сложность задачи вышла 2k: первый перебор с поиском кандидата на знаменитость, для этого следует проверить массив его знакомст, такой по умолчанию существует так как данные о связях в любом случае должны где-то хранится, но во время первого прохода нас интересует просто его длинна, или его наличие, если кандидатов не 1 то знаменитости нет, второй проход уточняет все ли знакомы с кандидатом, тут простой вопрос, а знаешь ли ты его, если не знаешь вернем нул, если все знают то вернем объект. Базовая сложность задачи надумонно переусложнена... Но за видос лайк

[@VItarcheg]

Не обязательно массив, вопрос "знаешь ли ты Х" может быть функцией, а данные могут распределенно храниться в разных хранилищах или у тебя вообще может не быть прямого доступа к этим данным, так как используется интерфейс (апишка) внешнего сервиса. Не надо выдумывать из головы дополнительных упрощений в таких задачах.

[@KreesKiss]

@@VItarcheg Интересное замечание, но намного интереснее почитать ваше обоснование хранения одного типа данных, связанных с одним пользователем на разных серверах (для меня это как хранить ФИО на трех разных серверах), это что-то новое для меня, какой профит вы планируете получить от этого? Не менее интересно узнать что же вас заставляет выдумывать из головы усложнения задачи?

[@user-dh8dw2hs6u]

@@KreesKiss Вам никто не сообщал о способе хранения этой информации, и что она вообще из себя представляет. У вас лишь известно одно - метод boolean know(Person person) класса Person дает понять, знает ли текущий пользователь пользователя, передаваемого в метод. А что и как делает этот метод вам не известно, да и не нужно. В конечном итоге, даже с вашим допущением, которого в условии не было, решение, как минимум с точки зрения сложности алгоритмов, работает также, как предложенное в видео - за линейное время. Про хранение данных. Ситуации, особенно в высоконагруженных системах, могут быть разными. Сходу действительно сложно придумать ситуацию, в которой хранение "однородной" информации в разных источниках имеет какой либо ощутимый профит. Но, возможно, кто-нибудь подкинет хороший пример. Я бы больше обратил внимание на то, что сама форма информации может совсем отличаться от желаемой вами. Ее может поставлять вам не непосредственно сам источник информации (например, БД), откуда вы можете получать ее так, как захотите, а какой-нибудь промежуточный сервис (например, в микросервисной архитектуре), который лишь предоставляет API для работы с этим сервисом. А вот как он будет предоставлять информацию вам, от вас уже не зависит. И в API этого сервиса не обязан быть метод верни_всех_друзей_by_id(person_id), и может лишь быть метод knows(person_id) Поэтому я соглашусь с комментарием на один выше - вы делаете допущение, которое не обязано выполняться. Но похвально, что вы думаете над задачей шире, чем, казалось бы, это нужно. Пускай в алгоритмических задачах от этого не так много толку, но на практике бывает ой как полезно. Успехов! :))

[@KreesKiss]

@@user-dh8dw2hs6u Спасибо за ваше время. Это было действиетльно полезно. Желаю и вам успехов ;)

[@user-oq9yk2sy4t]

Спустя восемь месяцев все же отвечу на комментарий) Недавно решал такую же задачу на олимпиаде по проге, и там в условии информация о связях между людьми была представлена двумерным квадратным массивом, где 1 - человек знает другого человека, 0 - не знает. Поэтому в этом случае ваш алгоритм не сработает)

[@I_tolko_cprocit]

когда устраивался на завод у меня тоже самое спрашивали. Показал на 3его. Взяли на работу.

[@obrechenny]

Получается, задача не совсем решена. Ведь нужно использовать минимальное количество вопросов. Это можно сделать только если во втором шаге ты не будешь дублировать вопросы, которые задавал на первом. Хотя, разумеется, код от этого станет значительно сложнее.

[@hmixa]

Заслуженный лайк.

[@Obesanjo]

а что за метод know у массивов? Или он где-то отдельно прописан?

[@ivankprod]

knows - это метод класса Person, а не массивов)

[@baronromer2767]

В начале ошибся с подсчётом макс. количества запросов, но решение с алгоритмом перебора неплохое для самоучки.

[@alienhazzard7201]

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

[@a.osethkin55]

Спасибо

[@sanekase2]

для чётного количества это сработает?

[@eugeneshcherbo9821]

Да, обратите внимание, что в цикле всегда уменьшается только один индекс, либо левый, либо правый. Соответственно не будет ситуации, когда индексы перепрыгнут друг через друга, а значит цикл всегда остановится, когда l == r, что будет означать, что остался только один человек.

[@user-be9yp5yq4h]

Можно еще несколько ускорить, будет все равно О(к), но в среднем 2.5к, а не 3к. Один курсор идет просто слева направо, о ком будем спрашивать и запоминаем потенциальную знаменитость. 1 изначально потенциальная знаменитость, спрашиваем знает ли он второго, если нет знает ли третьего и т.д., если натыкаемся кого знает, этот человек становится потенциальной знаменитостью и спрашиваем его о следующем стоящем справа. Таким образом когда дойдем до конца, получится, что мы уже знаем о потенциальной знаменитости, что она не знает всех кто справа, и останется спросить только про тех, кто слева. Ну и потом уже у всех, знают ли они эту потенциальную знаменитость.

[@ntvisigoth]

Саша Лукин, а тут нет баги? Ведь человек может знать сам себя! В первой части алгоритма нашли i = 3, а во второй части мы просто пробегаемся от 0 до length . При этом 3 как раз в этот [0, length) попадает.

[@funduk96]

Во второй части мы исключаем i=l из проверки (первая часть условия в if- е)

[@ntvisigoth]

@@funduk96 Точно, вы правы! На 7:15 об этом. Не внимательно слушал

[@apristen]

> Ведь человек может знать сам себя! Ах вот зачем знаменитости то под алкоголем то под коксом! Чтобы мало того никого не знать, так ещё и себя забыть! :-))))))

[@luyt2]

Александр, спасибо, интересно следить за развитием решения. Единственный момент - возвращать null, не очень хорошая идея.

[@F6BF792C]

> возвращать null, не очень хорошая идея почему?

[@luyt2]

@@F6BF792C 1. Меньше вероятности словить NullPiontException 2. В другой функции, которая примет от этой возвращаемый объект, мы избавляемся от лишней проверки на null и см. п.1.

[@Selex95]

Я всё думал как программно реализовать слово "знает", немного офигел от того что он его просто так и написал, как будто компилятор знает что означает это слово. Не знаю джаву вашу, но ваша джава знает меня...

[@academikpavlov4014]

Тут явно не весь код, т.к. не обозначенно, кто кого знает. Только алгоритм решения

[@eugenefedorov3498]

Купил такую же футболочку в Египте :)

[@vladsosnov3749]

Спасибо за видео. Можно ли проходить собес в Амазон на JavaScript (интересует позиция Front-end) или лучше учить например пайтон?

[@sashalukin]

Можно

[@MaruiInfantry]

Лучше выиграть чемп мира по программированию

[@big_shatel]

а в цикле for разве должно быть (!person[i].knows(persons[l], а не (person[i].!knows(persons[l]? если это переводить, то получается не i знает кандидата l, а не (как сказано) i не знает кандидата l. Или я чего-то не понимаю?)

[@HopeOfMankind_]

Я ещё не дослушал решение задачи(возможно там есть такое решение), но слушайте. Знаменитость никого не знает и все её знают, да ведь? Значит не может быть 2 человек которые никого не знают. Решение:мы просто ищем того, кто никого не знает

[@inna1305]

а как кодом это выразить? чтобы не получился цикл в цикле с квадратичной сложностью если я ничего не путаю

[@736939]

А не легче ли проДФСить через любого.

[@andrewsolopov3597]

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

[@carwashdevelopment3582]

на 4:36 Уже не нужно никого спрашивать уже спрошенные в первом туре вопросы, касающиеся кандидата

[@TacerFMM]

А можно собрать их вместе за обеденным столиком и просто спросить: Кто не знает никого из присутвующих)

[@kolyakars5248]

Нельзя) Все равно каждый подумает относительно каждого, прежде чем даст ответ) Т.е. "под капотом" вопросы добавяться)

[@TacerFMM]

@@kolyakars5248 Относительно каждого что он подумает?) Принципе то не меняется...если человек не знает человека, то внезапно знать его он не будет, что бы ты не спросил) Усложняете через чур) так можно всё вообще вывернуть в теорию вероятности и прочую лабуду)

[@airn587]

@@TacerFMM каждый должен будет посмотреть на другого, чтобы понять, знает ли он его. А это k-1 итераций, в итоге всё равно получим O(k^2). Посадив за один стол вы просто распараллелили на k потоков. Что, кстати, можно предложить, как альтернативное решение - map/reduce.

[@halil-js]

намного был бы интересно если покажешь в редакторе (коды)

[@ljlj]

о = очередь(получитьЛюдей()) i = 0 чел = о.следующий while (i < o.размер){ следующий = o.следующий if (чел.знает(следующий)){ чел = следующий } i++ } вывести(чел)

[@egordubovik3447]

А разве в условии не должно быть наообород что проверяемый кондидат должен знать нашего предпологаемого селебрити а селебрити в свою очередь не должен знать проверямоего кондидата ??

[@kolyakars5248]

В общем, нельзя просто взять и спросить "Кто здесь никого не знает" или "кто здесь знаменитось" и т.д. Даже в реальной жизни прежде чем получить ответ каждый подумает над каждым, прежде чем дать ответ. Если вас в комнате трое и я задам такой вопрос, каждый из вас создаст ещё по 2 вопроса самому себе, прежде чем ответить. "Знаю ли я 1" и "Знаю ли я 2". По сути, получается обычный перебор из начала видео. А так, вам задают 1 вопрос, над которым нужно подумать.

[@user-mk6le1br5x]

Александр, судя по решению, в Амазон Вас не взяли, ибо оно не корреткное. В последней части нельзя возвращать null, если Вы дошли до l. Надо пропустить это значение: if (i == l) continue;.

[@SergeyVavilonov]

оно и не вернет. условие (i != l && что-то) в случае если i == l будет ложно. return null не произойдет. будет переход к следующей итерации.

[@yaroslavyatsyk6475]

Person это был класс, а метод knows is boolean method?

[@user-xh3oo5qe9e]

Есть такой нюанс. По условиям задачи сказано, что нужно именно минимизировать число вопросов. Допустим, у нас есть 4 человека. Пусть мы идём по указанному алгоритму и узнаём: 1 знает 4, 2 не знает 4, 2 знает 3. Тогда нам нужно задать ещё 5 вопросов, чтобы узнать, знаменит ли 3, итого 8 вопросов. А если мы спросим 1, знает ли он 2, затем спросим 3, знает ли он 4, а затем зададим вопрос двум финалистам, то этап первый мы также пройдём за 3 вопроса. Но зато второй этап мы пройдём за 4 вопроса, так как уже знаем про кандидата в селебрити две вещи из 6. Таким образом, можно обойтись семью вопросами. То есть указанный алгоритм не минимален, если вопрос очень дорог - при неудаче придётся задать 3n-4 вопроса, когда достаточно 3n - 3 - floor(log_2(n)). С точки зрения программирования разница невелика, но если рассмативать задачу как математическую, нужна точность.

[@kosiak10851]

Что-то как-то если по условию есть только одна знаменитость - как-то сложно минимизировать вопросы. Допустим мы вообще рандомно выбрали человека, спросили всех, "кто его знает?", спросили его о всех, кого он знает и выяснили, что он знаменитость. Всё. минимальный счёт. Ни один алгоритм с каким-то нерандомным вычислением такого чувака наш тест не побьёт, потому что будет предварительно что-то выяснять дополнительными вопросами, а потом должен будет провести наш тест - итого задаст больше вопросов. Т.е. количество вопросов зависит от порядка выбора чуваков для проверок.

[@apristen]

а если массив большой и знаменитостей несколько как и непересекающихся групп ("кластеров") людей кто кого знает и кто кого не знает? не найдём ли мы "локальную" знаменитость (локальный минимум) вместо более знаменитой знаменитости? мне кажется для поиска нелокального решения тут без т.н. "матрицы смежности" (теория графов) не обойтись...

[@user-hz9zz6ob2q]

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

[@MichaelKondrashin]

если знаменитость кто-то не знает, это уже не знаменитость. так по условиям задачи

[@willius8463]

Как же можно извратить простые как угол дома алгоритмы if/else :-)

[@Roy-hp9nm]

А на собесах на какую позицию задают такие вопросы? Условно из "джун миддл сеньор" (знаю что каждая крупная делит грейды как ей нравится, поэтому обобщаю))

[@baetz2]

Думаю, это задача не на "джун-мидл-сеньор", а на знание алгоритмов и умение их применять, то есть насколько хорош человек в информатике и насколько он сообразителен. Это базовые знания, а джун-мидл-сеньор - это практический опыт. Поэтому ее можно встретить на любой позиции. Частенько можно получить оффер даже если завалил задачу, но ход мыслей интервьюеру понравился.

[@MaruiInfantry]

Это просто задача на решить с ходу из головы за 3 сек. Для разогрева. Чтоб сразу ред-флаг или дальше пойти. Эта задача ничего не показывает потому что она вообще ничего не показывает.

[@katskosta]

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

[@baetz2]

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

[@katskosta]

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

[@ReAgent003]

крутая задача

[@Son-of-the-God---]

Эта задача решается виртуальным переопределением методов класса.

[@takiekakmi7532]

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

[@magoshemeshe6841]

Для нахождения "знаменитости" можно применить алгоритм Капоне! Он заключается в следующем: "При помощи доброго вопроса и пистолета можно добиться гораздо большего, нежели одним только добрым вопросом." Таким образом, мы значительно сокращаем количество вопросов и легко узнаем кто является знаменитостью! 😃😃😃

[@shluhogon_42]

Это уже константное время O(1)

[@vanyam1]

Герой! Решил за O(1)

[@user-qj1sp9ve9c]

суть алгоритма: собрать весь массив persons[ ] в одном помещении и сказать, если за O(1) не выдадите мне знаменитость, буду -расстреливать- декрементировать по одному.👍☺

[@user-en7pi4pj9x]

Я конечно только ещё начинающий можно сказать программист, но: т.е. если функция не найдёт знаменитость она вернёт null, т.е. создаст переменную Person в которой ничего нет, которая к примеру в c++ так и будет валяться где то там, сожрав кусочек памяти, а в c# будет ждать пока ей займётся сборщик мусора. И интервьюеры от Амазона такие - молодец ты справился такие нам и нужны! Дичь какая-то:/...

[@fanchji6288]

Сделать рассылку на всех со списком кто с кем знаком….

[@cphr__]

простая задача, решение за 2 минуты придумал )

[@TheDanily4]

Можно выстроить всех в ряд и спросить у всех сразу: Кто не знаком ни с одним из присутствующих здесь. Ответит один человек - он и главный кандидат )

[@alexandermfrei]

Ответ k-1, нужен алгоритм для простого перебора. Ведь при каждом вопросе персоне Kx "знаешь ли Ky?" мы точно определяем что один из них не знаменитость. Соответственно при k=2 нам нужен всего 1 вопрос, при k=3 нам нужно 2 вопроса и так далее.

[@AleksandrYgA]

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

[@aruh5baruh528]

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

[@Ldarro]

А что, если кто-либо из пяти этих людей соврет, отвечая на вопросы касательно его знакомства с другими людьми пятерки?

[@user-vo9kn3pp6p]

это задача другая

[@user-vo9kn3pp6p]

задача про того кто врет, говорит правду и дипломат

[@rexdraconis1703]

Стоп, знаменитость же всего одна(я тут долгих комментарий писал, где половина это поиск знаменитости из возможных знаменитостей). Проходим по первому человеку, если он кого-то знает, то уберем всех кого он не знает, если он ни кого не знает, он знаменитость(это если знаменитость по-любому должна быть), и повторяем до k раз. Если знаменитость не обезательно должна быть, тогда проходим по первому человеку, но если знает хоть одного то тех кого он не знает переносим во второй список. Когда мы находим человека который никого не знает, проверяем всех оставшихся м тех кто в другой таблице, знают ли они его, если нет - нету знаменитостей

[@user-iv9sh9fc3c]

Работаю в никому неизвестной продуктовой компании, аутсорс, Лондон. Моя задача на техническом собеседовании была распарсить в несколько потоков эксельку, смапить полученные данные в объекты, которые ты сам создаёшь по описанию конечно же, объекты сразу же собрать в список и отсортировать кастомным компаратором. К реализации докапываются на 58 из 10. А почему написал поток в отдельном классе, а не использовал Тред Экзекьютор с лямбдами, цикломатик комплексити высокое для добавления элементов в список, а библа для парсинга экселя старая, надо было новую от Apache юзнуть… Когда узнаю что на собесах в Амазон, решают задачи с codewars, понимаю что что-то делаю не так. З.Ы учился так же в Германии, на Informatik, Uni Rostock

[@alexanders8928]

Много я повидал, но, чтобы либу библой называли...

[@lollol267]

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

[@user-iv9sh9fc3c]

​@@lollol267 это же не меняет сути. Я больше привык к придирчивым ЧСВшным интервьюерам и необоснованным предъявам во время собеседований. Я рассказал про свой опыт скорей потому, что название видео кликбейтное (без какой-либо критики содержания видео это говорю) и увидев такое название у людей которые ищут свою первую работу или собираются подаваться в Амазон, могут сложиться ложные ожидания. Хотя в целом я и в Амазон не подавался. Может туда и правда попасть легче чем в мелкие продуктовые конторы, хотя я очень сомневаюсь.

[@dronx1218]

Если бы фраза звучала: "Я буду использовать язык БрейнФак, но на любых других языках всё будет выглядеть практически точно также", то стало бы этак немного интересней. XD

[@user-nf7dc5tz4s]

Если можно задать любой вопрос, как это было в условии, то оптимольнее: 1) у всех спросить Сколько человек он знает 2) убедиться, что такой человек 1 3) проверить его на селебритость. Выйдет 2к

[@Lionman177]

Напоминает школьные уроки программирования на бэйсике в 90-е.

[@Chekist2008]

Не совсем понятно, зачем после того как вы поняли что каждый опрашиваемый знает первого - спрашивать у него самого? Ведь этого разве не достаточно чтобы уже понять что он и есть знаменитость? 2:40

[@MikhailDyukov]

Нет, ведь выполняется только одно условие. А вдруг эта "знаменитость" знает кого-то из оставшихся, тогда се ля ви

[@user-kg9hu7oo3w]

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

[@user-od1it3ru3o]

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

[@alexanders8928]

несмефно

[@glukmaker]

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

[@user-od1it3ru3o]

@@glukmaker понятие "знаменитость" относится к контексту решаемой задачи, поэтому нет. У нас же есть метод, возвращий информацию о том, знает ли персона А персону Б - внутри он же работает на основании какой-то информации о взаимоотношениях между персонами. Почему не отдать её наружу? Нету никакого смысла скрывать этот функционал. Более того, если бы это было REST API, то метод был бы спроектирован именно таким образом, чтобы отдавать список всех, кого знает персона (так как это, по факту, прямое свойство конкретной сущности - список связей).

[@antonsedov3785]

Ответ простой: Я знаю Джеффа Безоса - он знаменитость. Можно добавить еще, что вчера вместе бухали - Работа ваша!

[@krokenstiv8777]

прикольно

[@310384Alex]

Задачка то с подвохом ) А что если первый человек НЕ знает второго НО знает третьего а мы его спросили знает ли он второго, он ответит НЕТ и сразу попадет в подмножество знаменитостей? А может ли быть кандидат который знает кого то или всех, а его не знает ни кто? В этом случае на вопрос другим кандидатам они ответят что его НЕ знают и знаменитость, т к она не знает ни кого то и его то же не знает.

[@NarutoUzumaki-hq7do]

Как мне кажется это не самое простое решение. Предлагаю свое с 2k/ Начать переборку с начала и по очереди спрашивать знает ли он второго, если нет, то перейти к третьему и так до момента, когда он кого-то узнает (всех кого мы пропустили не были знаменитостями). Предположим первый узнал четвертого, а это означает, что либо 4-ый знаменитость или же он знает знаменитость, которая уже точно находится за четвертым. Теперь мы четвертого спрашиваем о пятом и так пока не найдем человека, который дальше никого не знает, и он либо будет знаменитостью, либо же знаменитостей не было в массиве. И второй цикл, мы просто всех по очереди спрашиваем, знают ли они предполагаемую знаменитость. Если да, то это она, иначе нет знаменитостей, все уехали из России

[@asethone]

Привет! Отвечу, хоть и с запозданием, потому что другие лайкнувшие коммент, видимо, не заметили ошибки в логике твоего решения. Вообще, это очень любопытная мысль, что последующего кандидата, которого знали предыдущие, можно не спрашивать о прошлых людях, так как они точно не знаменитости, раз до этого их никто не знал. В твоем примере 4-го не обязательно спрашивать о 2 и 3, людях т.к. до этого 1-й их не знал. Но это допущение неверно, ввиду того, что по условию задачи могут быть группы, не содержащие знаменитостей вообще, и выбранный тобой кандидат может знать кого-то до него - а потому не являясь знаменитостью по второму критерию: "знаменитость не должна знать никого". Так, 4-го человека в твоем примере действительно могли знать все, но при это сам он мог знать, к примеру, 2-го, о чем ты его (к слову, не очень любезно) не спросил 😥 Поэтому для проверки этого критерия нужен третий цикл, в котором мы дополнительно спросим кандидата в селебрити о том, знает ли он людей до него. В худшем случае, ты спросишь про k-1 людей, откуда делаем вывод, что такое решение тоже будет иметь скорость в районе 3k, или же O(k).

[@user-bb9zr7qv8l]

Это по телефону?

[@Kykuch1]

Объясните, пожалуйста, почему сложность первого алгоритма О(k^2), a не О(k^3)? Как я мыслю: чтобы рассмотреть одного претендента на роль знаменитости, нам нужно, задать k-1 вопрос остальным «знаете ли, вы этого человека?», если все знают, то теперь нам надо задать k-1 вопрос претенденту. Итак, мы рассмотрели. Является ли конкретный человек знаменитостью. Но только одного. А их k. В итоге, чтобы в лоб всех перебрать нужно (k-1)^2 * k = k^3 + … => O(k^3). Где косяк?

[@sashalukin]

(K-1)*2*k

[@Kykuch1]

@@sashalukin а, точно. Спасибо большое!

[@grumpresents2218]

а можно у всех сразу спросить "кто здесь не знает никого с присутствующих ?"

[@kolyakars5248]

Все просто. Смотри. Возьмём, условно, любой двор города миллионика. 4 дома, по 9 этажей, по 4 подъезда с ±2 человека в квартире. И вот ты у этой толпы можешь спросить: "Кто здесь никого никого не встречал?". И если ты спросишь "кто здесь не знает никого из присутсвующих", то ты заставляешь каждого из присутствующих подумать относительно каждого, знает ли он его. Т.е. если вас 3 стоит в комнате. Чтобы узнать, знаешь ли ты кого-то, ты подумаешь : Сашу знаю, Володю не знаю. Или Сашу знаю и Володю знаю и т.д. это уже больше, чем если бы у тебя спросили : Сашу знаешь?

[@grumpresents2218]

@@kolyakars5248 задача была об двух вопросах и 4 человеках , там не говорилось сколько будет отвечать)

[@BadMusic666]

Чем-то на метод Шелла похоже.

[@user-qf3og9kw9k]

Занимаешься переводом и озвучкой? Если да, где ссылка на оригинал? Если нет, то какого текст на английском для русскоговорящей аудитории?

[@Kykuch1]

А какая разница?) Кодинг тоже не на русском, но тем не менее русские туда идут. Или для вас и там переводчик нужен?

[@sergklg]

задача состоит в ПОИСКЕ знаменитости, а где сказано что поиск надо оптимизировать?? где в задании сказано что надо найти МИНИМАЛЬНОЕ КОЛИЧЕСТВО ДЕЙСТВИЙ для поиска?

[@user-rw3cy9rb5j]

1:26

[@maximpolsky2683]

Знаменитость - единственный, кто никого не знает. И не надо больше вопросов))

[@user-gt6by4md9d]

В условии сказано, что его должны все знать, кроме того, что он не знает никого

[@maximpolsky2683]

@@user-gt6by4md9d двоих таких, которые никого не знают при таких условиях быть не может ))

[@vasylstavinskyi7697]

если persons[] будет пустой - всем пока (по коду из видео если судить)

[@egor_krytoi]

Не думал, что меня будет учить Саша Симпл собеседованию Амазон

[@alexanders8928]

Он Lookin от слова look, чтобы его смотрели!!! А мне говорят, что нумерология и имя не влияют на судьбу... Чушь! Все имеет значение!

[@user-sw4qe9ch3m]

А если человек соврет что он никого не знает?

[@PointWand]

Алгоритм сложностью до N. Достаточно пройтись по списку до первого, кто не знает никого, он и будет знаменитостью

[@ilya2226]

Это есть самый первый алгоритм перебора, но с условием выхода, если нашли знаменитость. В худшем случае О(N^2) а не O(N). O(N) будет только если он самым первым стоит.

[@PointWand]

Если у нас нет информации и количестве ссылок на каждого персонажа, то да, O(N^2).

[@mikle4421]

А почему используешь именно цикл while Ведь если использовать тот же цикл for а потом еще один (не друг в друге) то тоже выйдет 2К и сложность по биг о выйдет О(к)

[@mikle4421]

И как так вышло что второй цикл (for) это 2к сложность? И это ты просто сплюсовал верхнюю сложность?

[@helloworld5469]

А можете объяснить почему время работы O(k), если у нас 3k выходит?

[@nikitabarysheve]

При подсчёте трудоемкости алгоритма коэффициенты обычно опускаются, потому что при увеличении величины к количество действий будет расти в любом случае линейно , как в случае О(к) так и в случае О(3к) и допустим при К равным 1000 необходимо будет сделать либо 1000 либо 3000 действий , а тут разница несущественна. Существенна будет разница между линейной и квадратичной сложностью алгоритма , ведь если К все ещё равно 1000, то при сложности алгоритма О(к) мы получим 1000 действий , а при О(к^2) - 1000000 действий , а вот это уже различается серьезно. Короче говоря коэффициент не так сильно влияет на трудоемкость

[@helloworld5469]

@@nikitabarysheve Спасибо за объяснение, решил сам углубится в тему оценки и интересно, что данный вид оценки называется асимптотический

[@andyunity]

Прочитайте Грокаем Алгоритмы. Книга короткая и простая, но отлично объясняет базовые понятия алгоритмизации.

[@shickulaairships]

@@nikitabarysheve потому что o(C*k) = o(k) по свойствам как большого так и малого O

[@MichaelKondrashin]

время работы определяется скоростью работы проверки знает ли кто-то кого-то и накладными расходами. Если пренебречь накладными расходами, то время работы будет "некое время умножить на 3 и на k". так как это некое время мы все равно не знаем, но не так уж важно, умножается ли оно на три или нет. Важна асимптотика - то есть как себя ведет время работы в зависимости от k при росте этого k.

[@Vitalyfeyler]

Можно же просто спросить у любого, кто тут знаменитость!

[@zl0wka723]

Нашел.

[@stormwerk]

Я так понял, что в Амазон стоит очередь...

[@TheEhion]

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

[@alekseybay6394]

Потому, что если он никого не знает но его самого знают не все то он *не* знаменитость. Незнание никого условие необходимое но не достаточное.

[@TheEhion]

@@alekseybay6394 погоди по условию знаменитость только одна так? И незнание других обязательное условие, получается если он не знает никого но его знают не все то задача нерешаема

[@alekseybay6394]

@@TheEhion То, что знаменитость только одна в условии никак не указано. Но из условия что его знают все следует, что не может более одной знаменитости (если бы их было больше одного то они должны бы были знать друг друга а знаменитость никого не знает). Если он незнает никого а его знают не все то он *не* знаменитость, и в группе нет знаменитостей. Задача решается с ответом "знаменитостей нет". И в дополнение к первоначальному вопросу, проверить каждого на знания всех это k^2 (спросить у каждого про каждого).

[@TheEhion]

@@alekseybay6394 спасибо теперь понял, я просто думал что знаменитость обязательно есть и не подумал что ее может не быть

[@shickulaairships]

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

[@baetz2]

Не очень эффективно по памяти, потому что вместо двух интов (L и r) придется в память загружать стек из k элементов, коих может быть очень много.

[@shickulaairships]

​@@baetz2 но ведь в память все равно придется загружать k элементов в виде массива, наверно все дело в реализации (я не специалист), и в итоге будет одно и то же, массив и 2 указателя. Просто стек это абстракция для человека.. если я правильно понимаю

[@baetz2]

@@shickulaairships Сам массив из k элементов загружен в память, от этого никуда не деться. Но ваш стек - это дополнительное выделение памяти размером 4*k байт (4 байта на каждую ссылку). На каждый миллион человек этот алгоритм будет отъедать по 4МБ памяти чисто под стек. А L и r - это 2 области памяти по 4 байта = 8 байт.

[@shickulaairships]

@@baetz2 да, так и есть, затупил

[@DracoDeeN]

как это помогло амазону не облажаться с запуском NW ?

[@MichaelKondrashin]

это и помогает помогает Амазону запускать там всякое, а не только ютьюбчик смотреть