Честно скажу, имея почти 20 лет стажа в разработке высоконагруженных систем, если бы мне задали такой вопрос на телефонном собеседовании, то я бы не смог на него ответить. На очном, с бумажкой, даже с учётом стресса самого собеседования, думаю проблем бы не было. Очень мне прохождение собеседований напоминает школьные курсы для олимпиадников, набор паттернов, главное иметь загруженную в память базу этих паттернов. :) Вообще, из практики, подобные задачки чаще встречаются 2 раза за проект, первый раз когда проектируешь решение, второй раз после релиза, когда всплыают косяки проектирования. До третьего кейса и далее мало кто доживает, поому что обычно после запуска и некоторого периода мейнтенанса уходишь проектировать следующий сервис. :) Даже в продуктовых компаниях.
дело не количестве задач за всё время работы, а в том имеешь ли ты знания(либо мышление) для оптимизированного решения задачи. Я работал почти 7 лет над физикой движка в компании Unity Technologies, там куда чаще возникают задачи оптимизации.
Я последний раз с алгоритмами в проекте сталкивался в играх 14 лет назад. Основная работа в современных проектах протянуть данные туда, протянуть данные сюда и выстроить для этого архитектуру почище (хотя это везде так или иначе страдает). Вместо алгоритмов готовые сервисы и компоненты. Но у меня нет опыта с Фаангами, может там по другому. В стартапе кстати тоже почти все готовое использовали.
Проблем с олимпиадниками две. Во-первых, наловчившись решать определенные типы задач, они при этом не могут распознать их в реальной жизни, если условие сформулировано иначе, непривычно (об этом еще Фейнман писал). Во-вторых, распознав задачу, они далее радостно решают ее по знакомому паттерну. Но в реальной жизни не бывает арифметических задачек в чистом виде. Например, если вопрос "знаешь ли ты А" дорогой (например, если это запрос во внешний сервис) - то это одно, а если матрица знакомств у тебя уже в памяти - другое, может, там вообще какими-нибудь битовыми операциями можно обойтись. Или, что более реалистично, если данные лежат в базе - то знакомства лучше не по одному дергать, а выполнить какой-нибудь запрос с группировками. Общая сложность алгоритма при этом будет выше (если учитывать операции на стороне СУБД), но работать будет быстрее. Хотя как тест на умение думать все равно очень полезно. Вот только другая проблема - тяжеловесы так вот пылесосят всех думающих с рынка, а потом сажают их кодить тупые выборки из списка заказов, а мелким компаниям приходится довольствоваться теми, кто школьные задачи на пропорции-то с трудом решают... Некрокоммент, да :)
@@cityrattube Вдохнем немного жизни. )) Вы все верно сказали. Могу лишь добавить, что лично меня давно удивлял тот факт, что несмотря на отбор лучших из лучших в софтверные гиганты софт становится все медленнее и все глючнее, даже если сделать скидку на бОльший объем данных и сделать вид, что за последние 10-20 лет вычислительные мощности и объемы памяти не выросли на порядки. Очень похоже на то, что реальной оптимизацией кроме как в играх и критических реалтаймовых приложениях никто больше не занимается. И даже в гейминдустрии становится все больше ААА проектов, которые релизятся сырыми - новые жэдаи, the last of us на ПК. То есть можно предположить, что или всех этих гениев-олимпиадников отправляют работать на Марс, или им просто говорят: "забейте со своими оптимизациями, у нас сроки горят". ))
Можно сократить время поиска, так как при первом прогоне наверняка кандидатура уже давала понять каких людей она не знает или знают ли ее другие. При втором прогоне исключив их, можно сократить количество итераций проверки. Например, если знаменитость окажется самой первой или самой последней то оптимизация на k.
если человек знает кого либо значить не нужно проверять знает ли кто-то его ибо знаменитость никого не знает, автор об этом сказал но в следующем кадре ввел нас в заблуждение, пожалуй в не сортированом массиве то что он показал самый оптимальный вариант
Для нахождения "знаменитости" можно применить алгоритм Капоне! Он заключается в следующем: "При помощи доброго вопроса и пистолета можно добиться гораздо большего, нежели одним только добрым вопросом." Таким образом, мы значительно сокращаем количество вопросов и легко узнаем кто является знаменитостью! 😃😃😃
Первая мысль после условия. Представляем направленный граф. Проверяем любого на знакомства. Если он с кем-то знаком, он нам не доходит, переходим к тому, с кем он знаком. Проверяем его таким же образом и так переходим, пока не придем к знаменитости.
Из-за того, что есть условие знаменитость не знает никого - задача имеет и простое решение с двумя переборами как написано ниже в комментах. Но убрав первое условие задача становится интересней и более жизненной и включает все варианты. Интересная задача.
ответ: (n-1) - выкинули всех + 2(n-1) -1 (потому что для потенциального короля не все 2(n-1) вариантов надо смотреть, а учесть, что одно сравнение мы знаем, когда его на последнем шаге выбирали с другим), т.е. 3n-4 шага. И можно заморочиться и строго доказать, что это аналитический (и практический) минимум при подлой "игре" ответчика. Поэтому, если бы требовалось, к примеру, вывести наименьшее число вопросов, то это было бы cout 1
Можно слегка изменить первый этап и получить возможность оптимизации на втором этапе. Спрашиваем второго, знает ли он первого. Если не знает, то вычеркиваем первого и проверяем 3го и 2го. Если же знает, то вычеркиваем второго, а первый остается как "потенциальный селеб". В какой-то момент мы увидим что все справа от "потенциального селеба", точно его знают. Что уменьшит кол-во итераций на втором этапе на кол-во человек справа от "потенциального селеба". В итоге - в худшем случае (селеб самый последний) - (3k - 2) итераций, в лучшем (селеб самый первый) - (2k - 2) итераций.
На самом деле даже 3k-4 в худшем случае: k-1 - на отсечение потенциальных знаменитостей. 2k-2 - на проверку последнего кандидата. Но как минимум один из этих запросов уже сделан на предыдущем шаге. Это и есть математически (а не алгоритмически) минимальное кол-во запросов вида "знает ли n-ый человек m-того?" в принципе необходимое для гарантированного обнаружения "знаменитости" в группе. Алгоритмически же, действительно, сложность в любом случае линейная.
@@alexandrvoevodsky4247 Именно так, алгоритмически в обоих случаях O(k). Просто не мог упустить момент и добавить, что можно слегка оптимизировать. В реальном коде так будет дешевле.
о = очередь(получитьЛюдей()) i = 0 чел = о.следующий while (i < o.размер){ следующий = o.следующий if (чел.знает(следующий)){ чел = следующий } i++ } вывести(чел)
Потом в мейтенансе встречаешь эти конструкции и дебажишь их 2 часа. Рулят самые простые методы, решение показанное выше - оптимизация, и оптимизировать нужно только то, что потребляет слишком много ресурсов.
Ты что, это же великая честь устроиться в Амазон за копейки и веслать с переработками. Поэтому это только 1 из 10 задач, которую нужно сразу оптимизированно решить на собеседовании, чтобы устроиться на должность Junior Naive Veslyar-Кодерок
Можно попытаться усидеть на двух стульях разбивая эти сложные конструкции на функции. В случае автора как минимум еще 2 функции просится, чтобы было понятно что по итогу этот цикл находит.
@@eugenehawkins783 25 функций нужно, все лямбдами, по одному оператору. И обязательно фреймворки использовать, не менее двух на каждую лямбду. У нас тут функциональное программирование любят.
В свое время я получил этот ответ совсем другим методом) Мне эта задача попалась в 2007 году, когда я после выпуска из ВУЗ'а на свою первую официальную работу устраивался. Представим, что все связи между людьми нам уже известны. Если записать эти связи в виде матрицы смежности некого графа, то как бы она выглядела и как бы происходит поиск в ней? Очевидно, что карта связей по условию задачи (в общем случае)- это ориентированный несимметричный граф... при этом в процессе поиска связь человека с самим собой не учитывается (т.е. главная диагональ матрицы смежности игнорируется). Перебирая все элементы матрицы смежности ниже главной диагонали мы за одну итерацию цикла проверяем ячейку [i,j] и симметричную ей [j,i]... вот от этого рассуждения я и "танцевал" =)
Вот этим самоучка и отличается от квалифицированного специалиста: берет наивное решение и считает это выдающимся достижением, даже не подозревая, что алгоритм может быть эффективнее на порядки.
Можно еще несколько ускорить, будет все равно О(к), но в среднем 2.5к, а не 3к. Один курсор идет просто слева направо, о ком будем спрашивать и запоминаем потенциальную знаменитость. 1 изначально потенциальная знаменитость, спрашиваем знает ли он второго, если нет знает ли третьего и т.д., если натыкаемся кого знает, этот человек становится потенциальной знаменитостью и спрашиваем его о следующем стоящем справа. Таким образом когда дойдем до конца, получится, что мы уже знаем о потенциальной знаменитости, что она не знает всех кто справа, и останется спросить только про тех, кто слева. Ну и потом уже у всех, знают ли они эту потенциальную знаменитость.
Я ещё не дослушал решение задачи(возможно там есть такое решение), но слушайте. Знаменитость никого не знает и все её знают, да ведь? Значит не может быть 2 человек которые никого не знают. Решение:мы просто ищем того, кто никого не знает
Для нахождения "знаменитости" можно применить алгоритм Капоне! Он заключается в следующем: "При помощи доброго вопроса и пистолета можно добиться гораздо большего, нежели одним только добрым вопросом." Таким образом, мы значительно сокращаем количество вопросов и легко узнаем кто является знаменитостью! 😃😃😃
суть алгоритма: собрать весь массив persons[ ] в одном помещении и сказать, если за O(1) не выдадите мне знаменитость, буду -расстреливать- декрементировать по одному.👍☺
Не задумываясь сложность задачи вышла 2k: первый перебор с поиском кандидата на знаменитость, для этого следует проверить массив его знакомст, такой по умолчанию существует так как данные о связях в любом случае должны где-то хранится, но во время первого прохода нас интересует просто его длинна, или его наличие, если кандидатов не 1 то знаменитости нет, второй проход уточняет все ли знакомы с кандидатом, тут простой вопрос, а знаешь ли ты его, если не знаешь вернем нул, если все знают то вернем объект. Базовая сложность задачи надумонно переусложнена... Но за видос лайк
Не обязательно массив, вопрос "знаешь ли ты Х" может быть функцией, а данные могут распределенно храниться в разных хранилищах или у тебя вообще может не быть прямого доступа к этим данным, так как используется интерфейс (апишка) внешнего сервиса. Не надо выдумывать из головы дополнительных упрощений в таких задачах.
@@VItarcheg Интересное замечание, но намного интереснее почитать ваше обоснование хранения одного типа данных, связанных с одним пользователем на разных серверах (для меня это как хранить ФИО на трех разных серверах), это что-то новое для меня, какой профит вы планируете получить от этого? Не менее интересно узнать что же вас заставляет выдумывать из головы усложнения задачи?
@@KreesKiss Вам никто не сообщал о способе хранения этой информации, и что она вообще из себя представляет. У вас лишь известно одно - метод boolean know(Person person) класса Person дает понять, знает ли текущий пользователь пользователя, передаваемого в метод. А что и как делает этот метод вам не известно, да и не нужно. В конечном итоге, даже с вашим допущением, которого в условии не было, решение, как минимум с точки зрения сложности алгоритмов, работает также, как предложенное в видео - за линейное время. Про хранение данных. Ситуации, особенно в высоконагруженных системах, могут быть разными. Сходу действительно сложно придумать ситуацию, в которой хранение "однородной" информации в разных источниках имеет какой либо ощутимый профит. Но, возможно, кто-нибудь подкинет хороший пример. Я бы больше обратил внимание на то, что сама форма информации может совсем отличаться от желаемой вами. Ее может поставлять вам не непосредственно сам источник информации (например, БД), откуда вы можете получать ее так, как захотите, а какой-нибудь промежуточный сервис (например, в микросервисной архитектуре), который лишь предоставляет API для работы с этим сервисом. А вот как он будет предоставлять информацию вам, от вас уже не зависит. И в API этого сервиса не обязан быть метод верни_всех_друзей_by_id(person_id), и может лишь быть метод knows(person_id) Поэтому я соглашусь с комментарием на один выше - вы делаете допущение, которое не обязано выполняться. Но похвально, что вы думаете над задачей шире, чем, казалось бы, это нужно. Пускай в алгоритмических задачах от этого не так много толку, но на практике бывает ой как полезно. Успехов! :))
Спустя восемь месяцев все же отвечу на комментарий) Недавно решал такую же задачу на олимпиаде по проге, и там в условии информация о связях между людьми была представлена двумерным квадратным массивом, где 1 - человек знает другого человека, 0 - не знает. Поэтому в этом случае ваш алгоритм не сработает)
Получается, задача не совсем решена. Ведь нужно использовать минимальное количество вопросов. Это можно сделать только если во втором шаге ты не будешь дублировать вопросы, которые задавал на первом. Хотя, разумеется, код от этого станет значительно сложнее.
Я всё думал как программно реализовать слово "знает", немного офигел от того что он его просто так и написал, как будто компилятор знает что означает это слово. Не знаю джаву вашу, но ваша джава знает меня...
Это есть самый первый алгоритм перебора, но с условием выхода, если нашли знаменитость. В худшем случае О(N^2) а не O(N). O(N) будет только если он самым первым стоит.
Пишу свой вариант алгоритма до того, как узнаю правильный ответ, чтобы себя проверить: Сначала из условия делаю простой вывод, что если знаменитость есть, то она может быть только 1. 1) Начинаем спрашивать Первого знает ли он человека от 2 до N по очереди. 2) Останавливаемся при ответе "Да" 3) Переходим к Следующему и проделываем с ним всё из 1 пункта. 3) Если каждый знает хотя бы 1 одного другого, то знаменитостей нет. 4) Если мы находим такого человека с номером X, который не знает никого, то знаменитостью может быть только он, так как знаменитость должны знать все из группы. 5) Далее проверяем записанные ответы от всех предыдущих опрошенных (от 1 до X-1), если кто-то из них не знает X, то знаменитостей нет. 6) Если все они знают X, то начинаем по очереди спрашиваnm людей с номером от X+1 до N, если кто-то из них не знает X, то знаменитостей нет. 7) Если все от (X+1 до N) также знают X, то он знаменитость. P.S. редактировать ответ не буду, даже если ошибся.
Саша, привет. Я предлагаю сократить количество проходов по массиву до 2к. По факту, ты в первом цикле уже проверяешь значит ли "потенциальный celebrity" остальных. Поэтому validation можно слегка сократить. В среднем должно дать прирост производительности.
я тоже об этом подумал, но нужно учитывать то что в таком случае придется проверять, проверяли ли мы уже эту пару на знание друг друга, и в некоторых случаях это менее оптимизированно. Но если каждый ответ приходится ждать по 30 минут, то да, ты прав.
@@kolyakars5248 Относительно каждого что он подумает?) Принципе то не меняется...если человек не знает человека, то внезапно знать его он не будет, что бы ты не спросил) Усложняете через чур) так можно всё вообще вывернуть в теорию вероятности и прочую лабуду)
@@TacerFMM каждый должен будет посмотреть на другого, чтобы понять, знает ли он его. А это k-1 итераций, в итоге всё равно получим O(k^2). Посадив за один стол вы просто распараллелили на k потоков. Что, кстати, можно предложить, как альтернативное решение - map/reduce.
Есть такой нюанс. По условиям задачи сказано, что нужно именно минимизировать число вопросов. Допустим, у нас есть 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)). С точки зрения программирования разница невелика, но если рассмативать задачу как математическую, нужна точность.
Что-то как-то если по условию есть только одна знаменитость - как-то сложно минимизировать вопросы. Допустим мы вообще рандомно выбрали человека, спросили всех, "кто его знает?", спросили его о всех, кого он знает и выяснили, что он знаменитость. Всё. минимальный счёт. Ни один алгоритм с каким-то нерандомным вычислением такого чувака наш тест не побьёт, потому что будет предварительно что-то выяснять дополнительными вопросами, а потом должен будет провести наш тест - итого задаст больше вопросов. Т.е. количество вопросов зависит от порядка выбора чуваков для проверок.
Элементарный но долгий по исполнению: Если ответ да - удалять отвечащего в лупе пока один не останется. Короткий по исполнению: Если ответ да - удалять отвечащего. Если ответ нет - удалять того про кого отвечали. И не надо снова проверять.
А ещё более хороший вариант - попросить поставщика добавить метод, который возвращает сразу список тех, кого знает персона - тогда можно в одно действие найти кандидата на знаменитость, а во второе - проверить, знает ли его каждый, просто обойдя массив. Гораздо более читаемо, гораздо более поддерживаемо и удобно для интеграции.
@@glukmaker понятие "знаменитость" относится к контексту решаемой задачи, поэтому нет. У нас же есть метод, возвращий информацию о том, знает ли персона А персону Б - внутри он же работает на основании какой-то информации о взаимоотношениях между персонами. Почему не отдать её наружу? Нету никакого смысла скрывать этот функционал. Более того, если бы это было REST API, то метод был бы спроектирован именно таким образом, чтобы отдавать список всех, кого знает персона (так как это, по факту, прямое свойство конкретной сущности - список связей).
Если бы фраза звучала: "Я буду использовать язык БрейнФак, но на любых других языках всё будет выглядеть практически точно также", то стало бы этак немного интересней. XD
Я конечно только ещё начинающий можно сказать программист, но: т.е. если функция не найдёт знаменитость она вернёт null, т.е. создаст переменную Person в которой ничего нет, которая к примеру в c++ так и будет валяться где то там, сожрав кусочек памяти, а в c# будет ждать пока ей займётся сборщик мусора. И интервьюеры от Амазона такие - молодец ты справился такие нам и нужны! Дичь какая-то:/...
Если можно задать любой вопрос, как это было в условии, то оптимольнее: 1) у всех спросить Сколько человек он знает 2) убедиться, что такой человек 1 3) проверить его на селебритость. Выйдет 2к
В общем, нельзя просто взять и спросить "Кто здесь никого не знает" или "кто здесь знаменитось" и т.д. Даже в реальной жизни прежде чем получить ответ каждый подумает над каждым, прежде чем дать ответ. Если вас в комнате трое и я задам такой вопрос, каждый из вас создаст ещё по 2 вопроса самому себе, прежде чем ответить. "Знаю ли я 1" и "Знаю ли я 2". По сути, получается обычный перебор из начала видео. А так, вам задают 1 вопрос, над которым нужно подумать.
Стоп, знаменитость же всего одна(я тут долгих комментарий писал, где половина это поиск знаменитости из возможных знаменитостей). Проходим по первому человеку, если он кого-то знает, то уберем всех кого он не знает, если он ни кого не знает, он знаменитость(это если знаменитость по-любому должна быть), и повторяем до k раз. Если знаменитость не обезательно должна быть, тогда проходим по первому человеку, но если знает хоть одного то тех кого он не знает переносим во второй список. Когда мы находим человека который никого не знает, проверяем всех оставшихся м тех кто в другой таблице, знают ли они его, если нет - нету знаменитостей
Все просто. Смотри. Возьмём, условно, любой двор города миллионика. 4 дома, по 9 этажей, по 4 подъезда с ±2 человека в квартире. И вот ты у этой толпы можешь спросить: "Кто здесь никого никого не встречал?". И если ты спросишь "кто здесь не знает никого из присутсвующих", то ты заставляешь каждого из присутствующих подумать относительно каждого, знает ли он его. Т.е. если вас 3 стоит в комнате. Чтобы узнать, знаешь ли ты кого-то, ты подумаешь : Сашу знаю, Володю не знаю. Или Сашу знаю и Володю знаю и т.д. это уже больше, чем если бы у тебя спросили : Сашу знаешь?
Александр, судя по решению, в Амазон Вас не взяли, ибо оно не корреткное. В последней части нельзя возвращать null, если Вы дошли до l. Надо пропустить это значение: if (i == l) continue;.
@@F6BF792C 1. Меньше вероятности словить NullPiontException 2. В другой функции, которая примет от этой возвращаемый объект, мы избавляемся от лишней проверки на null и см. п.1.
Нельзя ли сделать так: 1. Создать массив Links с нулевыми значениями, размер массива соответствует количеству людей. 2. В цикле проходимся по массиву с людьми и спрашиваем кого они знают, в массиве Links для элементов сооветствующих нужным людям (по индексу) если текущее значение >=0 увеличиваем значение на 1. Также, если этот человек знает хоть кого-то, выставляем у элемента массива Links с индексом равным индексу человека, значение -1. 3. Когда цикл завершится, ищем единственное положительное значение массива Links и дополнительно проверяем, что оно равно длине массива с людьми. Это первое что пришло в голову, думаю должно работать.
Ответ k-1, нужен алгоритм для простого перебора. Ведь при каждом вопросе персоне Kx "знаешь ли Ky?" мы точно определяем что один из них не знаменитость. Соответственно при k=2 нам нужен всего 1 вопрос, при k=3 нам нужно 2 вопроса и так далее.
Это работало бы только при условии, что в группе всегда есть знаменитость - тогда можно просто отбросить всех неподходящих кандидатов и останется нужный.
Объясните пожалуйста, почему в последнем условии используется «или», если нам нужно чтоб оба условия выполнялись (и person[i] должен знать person[l], и person[l] должен не знать person[i])?
Саша Лукин, а тут нет баги? Ведь человек может знать сам себя! В первой части алгоритма нашли i = 3, а во второй части мы просто пробегаемся от 0 до length . При этом 3 как раз в этот [0, length) попадает.
> Ведь человек может знать сам себя! Ах вот зачем знаменитости то под алкоголем то под коксом! Чтобы мало того никого не знать, так ещё и себя забыть! :-))))))
Самый простой способ, спросить у каждого знает ли он кого либо из этих людей, если находим кого либо кто не знает никого из группы, то он по условиям задачи и есть знаменитость. Зачем придумывать сложные алгоритмы? Т.к. условия при котором есть человек о котором кто то не знает, но при этом этот человек не знает никого, нет.
Задачка то с подвохом ) А что если первый человек НЕ знает второго НО знает третьего а мы его спросили знает ли он второго, он ответит НЕТ и сразу попадет в подмножество знаменитостей? А может ли быть кандидат который знает кого то или всех, а его не знает ни кто? В этом случае на вопрос другим кандидатам они ответят что его НЕ знают и знаменитость, т к она не знает ни кого то и его то же не знает.
я бы немного поменял алгоритм, проверяя не 1 с 2 а после 3 с 4 и тд как у автора, а проверял бы 1 с 2, а после оставшегося из них неизвестным с третьим, потом с четвертым и тд. на производительность это не повлияет, но алгоритм будет выглядеть проще
А разве в условии не должно быть наообород что проверяемый кондидат должен знать нашего предпологаемого селебрити а селебрити в свою очередь не должен знать проверямоего кондидата ??
Работаю в никому неизвестной продуктовой компании, аутсорс, Лондон. Моя задача на техническом собеседовании была распарсить в несколько потоков эксельку, смапить полученные данные в объекты, которые ты сам создаёшь по описанию конечно же, объекты сразу же собрать в список и отсортировать кастомным компаратором. К реализации докапываются на 58 из 10. А почему написал поток в отдельном классе, а не использовал Тред Экзекьютор с лямбдами, цикломатик комплексити высокое для добавления элементов в список, а библа для парсинга экселя старая, надо было новую от Apache юзнуть… Когда узнаю что на собесах в Амазон, решают задачи с codewars, понимаю что что-то делаю не так. З.Ы учился так же в Германии, на Informatik, Uni Rostock
@@lollol267 это же не меняет сути. Я больше привык к придирчивым ЧСВшным интервьюерам и необоснованным предъявам во время собеседований. Я рассказал про свой опыт скорей потому, что название видео кликбейтное (без какой-либо критики содержания видео это говорю) и увидев такое название у людей которые ищут свою первую работу или собираются подаваться в Амазон, могут сложиться ложные ожидания. Хотя в целом я и в Амазон не подавался. Может туда и правда попасть легче чем в мелкие продуктовые конторы, хотя я очень сомневаюсь.
Пример для первого человека страный. Какой смысл опрашивать, все ли знают первого человека, если по условиям в компании должна быть знаменитость? Тот, кто никого не знает и является знаменитостью в таком случае - тк в компании не может быть 2х человек, которые никого не знают, ибо по условиям там должна быть знаменитость, которую знают все. Или налиие знаменитости в группе - не обязательно?
Как мне кажется это не самое простое решение. Предлагаю свое с 2k/ Начать переборку с начала и по очереди спрашивать знает ли он второго, если нет, то перейти к третьему и так до момента, когда он кого-то узнает (всех кого мы пропустили не были знаменитостями). Предположим первый узнал четвертого, а это означает, что либо 4-ый знаменитость или же он знает знаменитость, которая уже точно находится за четвертым. Теперь мы четвертого спрашиваем о пятом и так пока не найдем человека, который дальше никого не знает, и он либо будет знаменитостью, либо же знаменитостей не было в массиве. И второй цикл, мы просто всех по очереди спрашиваем, знают ли они предполагаемую знаменитость. Если да, то это она, иначе нет знаменитостей, все уехали из России
Привет! Отвечу, хоть и с запозданием, потому что другие лайкнувшие коммент, видимо, не заметили ошибки в логике твоего решения. Вообще, это очень любопытная мысль, что последующего кандидата, которого знали предыдущие, можно не спрашивать о прошлых людях, так как они точно не знаменитости, раз до этого их никто не знал. В твоем примере 4-го не обязательно спрашивать о 2 и 3, людях т.к. до этого 1-й их не знал. Но это допущение неверно, ввиду того, что по условию задачи могут быть группы, не содержащие знаменитостей вообще, и выбранный тобой кандидат может знать кого-то до него - а потому не являясь знаменитостью по второму критерию: "знаменитость не должна знать никого". Так, 4-го человека в твоем примере действительно могли знать все, но при это сам он мог знать, к примеру, 2-го, о чем ты его (к слову, не очень любезно) не спросил 😥 Поэтому для проверки этого критерия нужен третий цикл, в котором мы дополнительно спросим кандидата в селебрити о том, знает ли он людей до него. В худшем случае, ты спросишь про k-1 людей, откуда делаем вывод, что такое решение тоже будет иметь скорость в районе 3k, или же O(k).
Объясните, пожалуйста, почему сложность первого алгоритма О(k^2), a не О(k^3)? Как я мыслю: чтобы рассмотреть одного претендента на роль знаменитости, нам нужно, задать k-1 вопрос остальным «знаете ли, вы этого человека?», если все знают, то теперь нам надо задать k-1 вопрос претенденту. Итак, мы рассмотрели. Является ли конкретный человек знаменитостью. Но только одного. А их k. В итоге, чтобы в лоб всех перебрать нужно (k-1)^2 * k = k^3 + … => O(k^3). Где косяк?
а в цикле for разве должно быть (!person[i].knows(persons[l], а не (person[i].!knows(persons[l]? если это переводить, то получается не i знает кандидата l, а не (как сказано) i не знает кандидата l. Или я чего-то не понимаю?)
Здравствуйте, Александр! А не подскажите хорошие курсы для начинающих? Просто сейчас занимаюсь программирование в 1С (не знаю, знакомо Вам такое или нет))), а хотелось бы окунуться так сказать во что то глубокое))
Классный метод, а еще можно загнать массив в стэк и доставая элемент, сравнивать попарно вершину стека со вторым элементом (для этого вершину предварительно вычитывам в переменную)
А почему используешь именно цикл while Ведь если использовать тот же цикл for а потом еще один (не друг в друге) то тоже выйдет 2К и сложность по биг о выйдет О(к)
Не знаю увидит кто или нет. А что если делать так: спрашиваем у первого - знает ли второго. Если нет, то у первого спрашиваем, знает ли третьего... и т.д., пока не добьемся того, что какого-то он знает, либо дошел до конца списка. К примеру, дошли, что он знает пятого. Далее идем к пятому и спрашиваем, знает ли он шестого.. и т.д. Доходим до момента, когда, например из 50 человек, 47ой не знает ни 48, ни 49, ни 50. Считаем его потенциальной знаменитостью. И идем обратно, только с ним: знает ли он 46, 45, 44.... если он хоть одного из них знает - то в списке нет знаменитости. Если доходим до 1ого и его никто не знает, то начинаем снова с 1ого и до 45 и спрашиваем, знают ли 47. Блин, пока расписывал, понял свой косяк и количество вопросов выросло с 2к-1 до 3к-2 :(
Хм, я бы использовал проход по условию "знаешь ли кого-то", а потом проход по обратной рекурсивной связи. Разумеется, если связи описаны каким-либо образом.
А на собесах на какую позицию задают такие вопросы? Условно из "джун миддл сеньор" (знаю что каждая крупная делит грейды как ей нравится, поэтому обобщаю))
Думаю, это задача не на "джун-мидл-сеньор", а на знание алгоритмов и умение их применять, то есть насколько хорош человек в информатике и насколько он сообразителен. Это базовые знания, а джун-мидл-сеньор - это практический опыт. Поэтому ее можно встретить на любой позиции. Частенько можно получить оффер даже если завалил задачу, но ход мыслей интервьюеру понравился.
Это просто задача на решить с ходу из головы за 3 сек. Для разогрева. Чтоб сразу ред-флаг или дальше пойти. Эта задача ничего не показывает потому что она вообще ничего не показывает.
@@katskosta На работе часто приходится брать коллекции каких-то данных и преобразовывать их по какой-то хитрой логике. Любой найдет неэффективное решение "в лоб" для подобной задачи, но не каждый задаст себе вопрос "а можно ли сделать лучше" и далеко не каждый действительно сделает лучше. Кандидат, который хорошо справляется с такими задачами, предположительно, в повседневной работе тоже будет использовать эффективные алгоритмы.
@@baetz2 мне кажется вы все усложняете, в 90% задачах это не нужно лучше пусть код будет более понятен, чем придумавать эффективное решение там где нет в этом надобности, я не спорю что иногда нужно быстрое и эффективные решения.
задача состоит в ПОИСКЕ знаменитости, а где сказано что поиск надо оптимизировать?? где в задании сказано что надо найти МИНИМАЛЬНОЕ КОЛИЧЕСТВО ДЕЙСТВИЙ для поиска?
Быстрее будет собрать всех вместе и спросить одной фразой: «есть ли тут кто-то, кто не знает никого?». Всего один вопрос и один ответ. И нахрен не нужны эти формулы.
в стек всех сложить и достать первого, у него спрашивать до тех пор, пока он не будет никого знать, и выбрасывать со стека этих людей. как только он узнал, то заменяем первого допрашиваемого на нового кандидата и спрашиваем уже у него до тех пор, пока ....
@@baetz2 но ведь в память все равно придется загружать k элементов в виде массива, наверно все дело в реализации (я не специалист), и в итоге будет одно и то же, массив и 2 указателя. Просто стек это абстракция для человека.. если я правильно понимаю
@@shickulaairships Сам массив из k элементов загружен в память, от этого никуда не деться. Но ваш стек - это дополнительное выделение памяти размером 4*k байт (4 байта на каждую ссылку). На каждый миллион человек этот алгоритм будет отъедать по 4МБ памяти чисто под стек. А L и r - это 2 области памяти по 4 байта = 8 байт.
А не проще спросить например у первого, знает ли он кого либо? И если это знаменитость, то всё закончится одной итерацией. Если нет, то продолжить опрос других членов группы
@@erkin7138 нет, не интересуюсь каждым, а спрашиваю кого он знает. Алгоритм туп, он спрашивает каждого о каждом, человек же может задать вопрос в общем, получив один развернутый ответ. Суть задачи задать минимум вопросом для выяснения цели. Вот собственно и задаётся вопрос общего характера. Другое дело описать это алгоритмом.
@@gen2365 спросить у каждого, знает ли он хоть одного другого это 1 этап решения задачи. Нужно ещё, чтобы другие его все знали. Одной итерацией это не сделать, имхо.
@@erkin7138 изначально речь не идёт об итерациях. Речь о том чтобы задав минимум вопросом выяснить. Изначально задача чисто человеческая. Поэтому с человеческим подходом и задаём очевидный вопрос: кого знаешь?
@@gen2365 Если по-человечески, это допустимо. Просто тут на алгоритм задача от Амазона, можно любой псевдокод использовать, но без обычной логики не решить ничего.
Насколько, всё-таки, классно, что, будучи далёким от программирования, я сумел не только дожить до пенсии, но ещё и заработать, реально, очень достойную пенсию, достаточную для того, чтобы жить во Флориде, ни в чём себе не отказывая, во времена, когда вокруг свирепствует программирование...
Ну я тоже зарабатываю достойно, будучи индустриальным инженером, но при этом моя работа программирования не требует. Хотя справедливости ради надо сказать что пару простых языков я все-таки достаточно хорошо знаю. Но это скорее для личного пользования нежели для работы
Создал Telegram канал, в котором рассказываю о жизни в Лондоне, работе в Google и подготовке к собеседованиям. Подписывайтесь: t.me/saschalukin
Ох и загадки у Амазона,чтоб стать обычным сборщиком заказов)
сборщик заказов должен быть тупой, что б не наебал. А умный это плохо, наебёт хрен разберёшь. Вывод очевиден...
@А P Так это и работает, при чём везде. Работникам платят мало, а те где то, что то, как то подворовывают...
@А P
А смысл?
Найдут и посадят. Банально же.
не приняли, теперь видео записывает
@@vasilypokrashchenko1793 , просто попасть к ним на собеседование - это уже достижение
Ничего не понял, но очень интересно. Вы приняты
Честно скажу, имея почти 20 лет стажа в разработке высоконагруженных систем, если бы мне задали такой вопрос на телефонном собеседовании, то я бы не смог на него ответить. На очном, с бумажкой, даже с учётом стресса самого собеседования, думаю проблем бы не было.
Очень мне прохождение собеседований напоминает школьные курсы для олимпиадников, набор паттернов, главное иметь загруженную в память базу этих паттернов. :)
Вообще, из практики, подобные задачки чаще встречаются 2 раза за проект, первый раз когда проектируешь решение, второй раз после релиза, когда всплыают косяки проектирования. До третьего кейса и далее мало кто доживает, поому что обычно после запуска и некоторого периода мейнтенанса уходишь проектировать следующий сервис. :) Даже в продуктовых компаниях.
дело не количестве задач за всё время работы, а в том имеешь ли ты знания(либо мышление) для оптимизированного решения задачи. Я работал почти 7 лет над физикой движка в компании Unity Technologies, там куда чаще возникают задачи оптимизации.
@@whatsuphope Тогда я понял, почему оптимизация в Unity страдает )) (Сразу говорю, что это не упрек в твою сторону, а просто шутка :)
Я последний раз с алгоритмами в проекте сталкивался в играх 14 лет назад. Основная работа в современных проектах протянуть данные туда, протянуть данные сюда и выстроить для этого архитектуру почище (хотя это везде так или иначе страдает). Вместо алгоритмов готовые сервисы и компоненты. Но у меня нет опыта с Фаангами, может там по другому. В стартапе кстати тоже почти все готовое использовали.
Проблем с олимпиадниками две. Во-первых, наловчившись решать определенные типы задач, они при этом не могут распознать их в реальной жизни, если условие сформулировано иначе, непривычно (об этом еще Фейнман писал). Во-вторых, распознав задачу, они далее радостно решают ее по знакомому паттерну. Но в реальной жизни не бывает арифметических задачек в чистом виде. Например, если вопрос "знаешь ли ты А" дорогой (например, если это запрос во внешний сервис) - то это одно, а если матрица знакомств у тебя уже в памяти - другое, может, там вообще какими-нибудь битовыми операциями можно обойтись. Или, что более реалистично, если данные лежат в базе - то знакомства лучше не по одному дергать, а выполнить какой-нибудь запрос с группировками. Общая сложность алгоритма при этом будет выше (если учитывать операции на стороне СУБД), но работать будет быстрее.
Хотя как тест на умение думать все равно очень полезно. Вот только другая проблема - тяжеловесы так вот пылесосят всех думающих с рынка, а потом сажают их кодить тупые выборки из списка заказов, а мелким компаниям приходится довольствоваться теми, кто школьные задачи на пропорции-то с трудом решают...
Некрокоммент, да :)
@@cityrattube Вдохнем немного жизни. )) Вы все верно сказали. Могу лишь добавить, что лично меня давно удивлял тот факт, что несмотря на отбор лучших из лучших в софтверные гиганты софт становится все медленнее и все глючнее, даже если сделать скидку на бОльший объем данных и сделать вид, что за последние 10-20 лет вычислительные мощности и объемы памяти не выросли на порядки.
Очень похоже на то, что реальной оптимизацией кроме как в играх и критических реалтаймовых приложениях никто больше не занимается. И даже в гейминдустрии становится все больше ААА проектов, которые релизятся сырыми - новые жэдаи, the last of us на ПК.
То есть можно предположить, что или всех этих гениев-олимпиадников отправляют работать на Марс, или им просто говорят: "забейте со своими оптимизациями, у нас сроки горят". ))
очень понятное видео, большое вам спасибо, оформление супер
Можно сократить время поиска, так как при первом прогоне наверняка кандидатура уже давала понять каких людей она не знает или знают ли ее другие. При втором прогоне исключив их, можно сократить количество итераций проверки. Например, если знаменитость окажется самой первой или самой последней то оптимизация на k.
если человек знает кого либо значить не нужно проверять знает ли кто-то его ибо знаменитость никого не знает, автор об этом сказал но в следующем кадре ввел нас в заблуждение, пожалуй в не сортированом массиве то что он показал самый оптимальный вариант
Для нахождения "знаменитости" можно применить алгоритм Капоне! Он заключается в следующем: "При помощи доброго вопроса и пистолета можно добиться гораздо большего, нежели одним только добрым вопросом." Таким образом, мы значительно сокращаем количество вопросов и легко узнаем кто является знаменитостью! 😃😃😃
Плюс "к" минус "к".. все равно это О(к)..))
У того кто придумал задачу)@@magoshemeshe6841
Спасибо! Отличное объяснение. Особенно дидактически очень классно указание сложности О-большое первого алгоритма, а потом и более эффективного.
Саша, огромное Вам спасибо за замечательные видео.
Первая мысль после условия. Представляем направленный граф. Проверяем любого на знакомства. Если он с кем-то знаком, он нам не доходит, переходим к тому, с кем он знаком. Проверяем его таким же образом и так переходим, пока не придем к знаменитости.
Из-за того, что есть условие знаменитость не знает никого - задача имеет и простое решение с двумя переборами как написано ниже в комментах. Но убрав первое условие задача становится интересней и более жизненной и включает все варианты. Интересная задача.
Последний алгоритм с двумя указателями на начало и конец массива очень любопытный🤔 лайк и подписка!
ответ: (n-1) - выкинули всех + 2(n-1) -1 (потому что для потенциального короля не все 2(n-1) вариантов надо смотреть, а учесть, что одно сравнение мы знаем, когда его на последнем шаге выбирали с другим), т.е. 3n-4 шага. И можно заморочиться и строго доказать, что это аналитический (и практический) минимум при подлой "игре" ответчика. Поэтому, если бы требовалось, к примеру, вывести наименьшее число вопросов, то это было бы cout 1
Отличное объяснение! Спасибо Саша за твои видео :)
Красава)учу языки,с тобой проще это дедать)спасибо)
Можно слегка изменить первый этап и получить возможность оптимизации на втором этапе.
Спрашиваем второго, знает ли он первого. Если не знает, то вычеркиваем первого и проверяем 3го и 2го. Если же знает, то вычеркиваем второго, а первый остается как "потенциальный селеб". В какой-то момент мы увидим что все справа от "потенциального селеба", точно его знают. Что уменьшит кол-во итераций на втором этапе на кол-во человек справа от "потенциального селеба". В итоге - в худшем случае (селеб самый последний) - (3k - 2) итераций, в лучшем (селеб самый первый) - (2k - 2) итераций.
Не сильно разбираюсь в сложностях алгоритма, но разве если 3k-2 это не одно и то же что и просто k?
На самом деле даже 3k-4 в худшем случае:
k-1 - на отсечение потенциальных знаменитостей.
2k-2 - на проверку последнего кандидата. Но как минимум один из этих запросов уже сделан на предыдущем шаге.
Это и есть математически (а не алгоритмически) минимальное кол-во запросов вида "знает ли n-ый человек m-того?" в принципе необходимое для гарантированного обнаружения "знаменитости" в группе.
Алгоритмически же, действительно, сложность в любом случае линейная.
@@alexandrvoevodsky4247 Именно так, алгоритмически в обоих случаях O(k). Просто не мог упустить момент и добавить, что можно слегка оптимизировать. В реальном коде так будет дешевле.
Так разве не придется доьавлять какое то условие
Если то
о = очередь(получитьЛюдей())
i = 0
чел = о.следующий
while (i < o.размер){
следующий = o.следующий
if (чел.знает(следующий)){
чел = следующий
}
i++
}
вывести(чел)
Потом в мейтенансе встречаешь эти конструкции и дебажишь их 2 часа. Рулят самые простые методы, решение показанное выше - оптимизация, и оптимизировать нужно только то, что потребляет слишком много ресурсов.
@en1ight 2 часа? А 2 дня не хочешь? ))
Ты что, это же великая честь устроиться в Амазон за копейки и веслать с переработками.
Поэтому это только 1 из 10 задач, которую нужно сразу оптимизированно решить на собеседовании, чтобы устроиться на должность Junior Naive Veslyar-Кодерок
Можно попытаться усидеть на двух стульях разбивая эти сложные конструкции на функции. В случае автора как минимум еще 2 функции просится, чтобы было понятно что по итогу этот цикл находит.
@@eugenehawkins783 25 функций нужно, все лямбдами, по одному оператору. И обязательно фреймворки использовать, не менее двух на каждую лямбду. У нас тут функциональное программирование любят.
когда устраивался на завод у меня тоже самое спрашивали. Показал на 3его. Взяли на работу.
Хорошо объясняет парень. Жаль видео мало на канале.
Очень внятная постановка задачи и разбор. Смотрю уже не первое видео, везде так. Очень круто, спасибо большое!
В свое время я получил этот ответ совсем другим методом) Мне эта задача попалась в 2007 году, когда я после выпуска из ВУЗ'а на свою первую официальную работу устраивался. Представим, что все связи между людьми нам уже известны. Если записать эти связи в виде матрицы смежности некого графа, то как бы она выглядела и как бы происходит поиск в ней? Очевидно, что карта связей по условию задачи (в общем случае)- это ориентированный несимметричный граф... при этом в процессе поиска связь человека с самим собой не учитывается (т.е. главная диагональ матрицы смежности игнорируется). Перебирая все элементы матрицы смежности ниже главной диагонали мы за одну итерацию цикла проверяем ячейку [i,j] и симметричную ей [j,i]... вот от этого рассуждения я и "танцевал" =)
Если я правильно понял, то это и будет первое решение из видео с квадратичной сложностью
@@ilyaskhalitov5608 нет, оно будет эффективнее первого, но хуже наиболее оптимального. Где-то посередине
@@Yury_Dergachev так какая конкретно сложность и почему? O(k^2/2) = O(k^2) на всякий случай напоминаю)
В начале ошибся с подсчётом макс. количества запросов, но решение с алгоритмом перебора неплохое для самоучки.
Вот этим самоучка и отличается от квалифицированного специалиста: берет наивное решение и считает это выдающимся достижением, даже не подозревая, что алгоритм может быть эффективнее на порядки.
Можно еще несколько ускорить, будет все равно О(к), но в среднем 2.5к, а не 3к. Один курсор идет просто слева направо, о ком будем спрашивать и запоминаем потенциальную знаменитость. 1 изначально потенциальная знаменитость, спрашиваем знает ли он второго, если нет знает ли третьего и т.д., если натыкаемся кого знает, этот человек становится потенциальной знаменитостью и спрашиваем его о следующем стоящем справа. Таким образом когда дойдем до конца, получится, что мы уже знаем о потенциальной знаменитости, что она не знает всех кто справа, и останется спросить только про тех, кто слева. Ну и потом уже у всех, знают ли они эту потенциальную знаменитость.
Я ещё не дослушал решение задачи(возможно там есть такое решение), но слушайте. Знаменитость никого не знает и все её знают, да ведь? Значит не может быть 2 человек которые никого не знают. Решение:мы просто ищем того, кто никого не знает
а как кодом это выразить? чтобы не получился цикл в цикле с квадратичной сложностью если я ничего не путаю
Для нахождения "знаменитости" можно применить алгоритм Капоне! Он заключается в следующем: "При помощи доброго вопроса и пистолета можно добиться гораздо большего, нежели одним только добрым вопросом." Таким образом, мы значительно сокращаем количество вопросов и легко узнаем кто является знаменитостью! 😃😃😃
Это уже константное время O(1)
Герой! Решил за O(1)
суть алгоритма: собрать весь массив persons[ ] в одном помещении и сказать, если за O(1) не выдадите мне знаменитость, буду -расстреливать- декрементировать по одному.👍☺
Не задумываясь сложность задачи вышла 2k: первый перебор с поиском кандидата на знаменитость, для этого следует проверить массив его знакомст, такой по умолчанию существует так как данные о связях в любом случае должны где-то хранится, но во время первого прохода нас интересует просто его длинна, или его наличие, если кандидатов не 1 то знаменитости нет, второй проход уточняет все ли знакомы с кандидатом, тут простой вопрос, а знаешь ли ты его, если не знаешь вернем нул, если все знают то вернем объект. Базовая сложность задачи надумонно переусложнена...
Но за видос лайк
Не обязательно массив, вопрос "знаешь ли ты Х" может быть функцией, а данные могут распределенно храниться в разных хранилищах или у тебя вообще может не быть прямого доступа к этим данным, так как используется интерфейс (апишка) внешнего сервиса. Не надо выдумывать из головы дополнительных упрощений в таких задачах.
@@VItarcheg Интересное замечание, но намного интереснее почитать ваше обоснование хранения одного типа данных, связанных с одним пользователем на разных серверах (для меня это как хранить ФИО на трех разных серверах), это что-то новое для меня, какой профит вы планируете получить от этого? Не менее интересно узнать что же вас заставляет выдумывать из головы усложнения задачи?
@@KreesKiss Вам никто не сообщал о способе хранения этой информации, и что она вообще из себя представляет. У вас лишь известно одно - метод boolean know(Person person) класса Person дает понять, знает ли текущий пользователь пользователя, передаваемого в метод. А что и как делает этот метод вам не известно, да и не нужно. В конечном итоге, даже с вашим допущением, которого в условии не было, решение, как минимум с точки зрения сложности алгоритмов, работает также, как предложенное в видео - за линейное время.
Про хранение данных. Ситуации, особенно в высоконагруженных системах, могут быть разными. Сходу действительно сложно придумать ситуацию, в которой хранение "однородной" информации в разных источниках имеет какой либо ощутимый профит. Но, возможно, кто-нибудь подкинет хороший пример. Я бы больше обратил внимание на то, что сама форма информации может совсем отличаться от желаемой вами. Ее может поставлять вам не непосредственно сам источник информации (например, БД), откуда вы можете получать ее так, как захотите, а какой-нибудь промежуточный сервис (например, в микросервисной архитектуре), который лишь предоставляет API для работы с этим сервисом. А вот как он будет предоставлять информацию вам, от вас уже не зависит. И в API этого сервиса не обязан быть метод верни_всех_друзей_by_id(person_id), и может лишь быть метод knows(person_id)
Поэтому я соглашусь с комментарием на один выше - вы делаете допущение, которое не обязано выполняться. Но похвально, что вы думаете над задачей шире, чем, казалось бы, это нужно. Пускай в алгоритмических задачах от этого не так много толку, но на практике бывает ой как полезно. Успехов! :))
@@АлексПотапыч Спасибо за ваше время. Это было действиетльно полезно. Желаю и вам успехов ;)
Спустя восемь месяцев все же отвечу на комментарий)
Недавно решал такую же задачу на олимпиаде по проге, и там в условии информация о связях между людьми была представлена двумерным квадратным массивом, где 1 - человек знает другого человека, 0 - не знает. Поэтому в этом случае ваш алгоритм не сработает)
можно использовать доп память для того чтобы сократить время работы
Получается, задача не совсем решена. Ведь нужно использовать минимальное количество вопросов. Это можно сделать только если во втором шаге ты не будешь дублировать вопросы, которые задавал на первом. Хотя, разумеется, код от этого станет значительно сложнее.
Я всё думал как программно реализовать слово "знает", немного офигел от того что он его просто так и написал, как будто компилятор знает что означает это слово.
Не знаю джаву вашу, но ваша джава знает меня...
Тут явно не весь код, т.к. не обозначенно, кто кого знает. Только алгоритм решения
Алгоритм сложностью до N. Достаточно пройтись по списку до первого, кто не знает никого, он и будет знаменитостью
Это есть самый первый алгоритм перебора, но с условием выхода, если нашли знаменитость. В худшем случае О(N^2) а не O(N). O(N) будет только если он самым первым стоит.
Если у нас нет информации и количестве ссылок на каждого персонажа, то да, O(N^2).
Пишу свой вариант алгоритма до того, как узнаю правильный ответ, чтобы себя проверить:
Сначала из условия делаю простой вывод, что если знаменитость есть, то она может быть только 1.
1) Начинаем спрашивать Первого знает ли он человека от 2 до N по очереди.
2) Останавливаемся при ответе "Да"
3) Переходим к Следующему и проделываем с ним всё из 1 пункта.
3) Если каждый знает хотя бы 1 одного другого, то знаменитостей нет.
4) Если мы находим такого человека с номером X, который не знает никого, то знаменитостью может быть только он, так как знаменитость должны знать все из группы.
5) Далее проверяем записанные ответы от всех предыдущих опрошенных (от 1 до X-1), если кто-то из них не знает X, то знаменитостей нет.
6) Если все они знают X, то начинаем по очереди спрашиваnm людей с номером от X+1 до N, если кто-то из них не знает X, то знаменитостей нет.
7) Если все от (X+1 до N) также знают X, то он знаменитость.
P.S. редактировать ответ не буду, даже если ошибся.
Саша, привет. Я предлагаю сократить количество проходов по массиву до 2к. По факту, ты в первом цикле уже проверяешь значит ли "потенциальный celebrity" остальных. Поэтому validation можно слегка сократить. В среднем должно дать прирост производительности.
я тоже об этом подумал, но нужно учитывать то что в таком случае придется проверять, проверяли ли мы уже эту пару на знание друг друга, и в некоторых случаях это менее оптимизированно. Но если каждый ответ приходится ждать по 30 минут, то да, ты прав.
А можно собрать их вместе за обеденным столиком и просто спросить: Кто не знает никого из присутвующих)
Нельзя) Все равно каждый подумает относительно каждого, прежде чем даст ответ) Т.е. "под капотом" вопросы добавяться)
@@kolyakars5248 Относительно каждого что он подумает?) Принципе то не меняется...если человек не знает человека, то внезапно знать его он не будет, что бы ты не спросил) Усложняете через чур) так можно всё вообще вывернуть в теорию вероятности и прочую лабуду)
@@TacerFMM каждый должен будет посмотреть на другого, чтобы понять, знает ли он его. А это k-1 итераций, в итоге всё равно получим O(k^2). Посадив за один стол вы просто распараллелили на k потоков. Что, кстати, можно предложить, как альтернативное решение - map/reduce.
Есть такой нюанс. По условиям задачи сказано, что нужно именно минимизировать число вопросов.
Допустим, у нас есть 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)). С точки зрения программирования разница невелика, но если рассмативать задачу как математическую, нужна точность.
Что-то как-то если по условию есть только одна знаменитость - как-то сложно минимизировать вопросы.
Допустим мы вообще рандомно выбрали человека, спросили всех, "кто его знает?", спросили его о всех, кого он знает и выяснили, что он знаменитость. Всё. минимальный счёт. Ни один алгоритм с каким-то нерандомным вычислением такого чувака наш тест не побьёт, потому что будет предварительно что-то выяснять дополнительными вопросами, а потом должен будет провести наш тест - итого задаст больше вопросов. Т.е. количество вопросов зависит от порядка выбора чуваков для проверок.
на 4:36
Уже не нужно никого спрашивать уже спрошенные в первом туре вопросы, касающиеся кандидата
Элементарный но долгий по исполнению: Если ответ да - удалять отвечащего в лупе пока один не останется.
Короткий по исполнению: Если ответ да - удалять отвечащего. Если ответ нет - удалять того про кого отвечали. И не надо снова проверять.
А ещё более хороший вариант - попросить поставщика добавить метод, который возвращает сразу список тех, кого знает персона - тогда можно в одно действие найти кандидата на знаменитость, а во второе - проверить, знает ли его каждый, просто обойдя массив.
Гораздо более читаемо, гораздо более поддерживаемо и удобно для интеграции.
несмефно
Тогда уж лучше попросить поставщика добавить метод, который будет нам возвращать знаменитость.
@@glukmaker понятие "знаменитость" относится к контексту решаемой задачи, поэтому нет.
У нас же есть метод, возвращий информацию о том, знает ли персона А персону Б - внутри он же работает на основании какой-то информации о взаимоотношениях между персонами. Почему не отдать её наружу? Нету никакого смысла скрывать этот функционал.
Более того, если бы это было REST API, то метод был бы спроектирован именно таким образом, чтобы отдавать список всех, кого знает персона (так как это, по факту, прямое свойство конкретной сущности - список связей).
Если бы фраза звучала: "Я буду использовать язык БрейнФак, но на любых других языках всё будет выглядеть практически точно также", то стало бы этак немного интересней. XD
Я конечно только ещё начинающий можно сказать программист, но: т.е. если функция не найдёт знаменитость она вернёт null, т.е. создаст переменную Person в которой ничего нет, которая к примеру в c++ так и будет валяться где то там, сожрав кусочек памяти, а в c# будет ждать пока ей займётся сборщик мусора. И интервьюеры от Амазона такие - молодец ты справился такие нам и нужны!
Дичь какая-то:/...
Если можно задать любой вопрос, как это было в условии, то оптимольнее:
1) у всех спросить Сколько человек он знает
2) убедиться, что такой человек 1
3) проверить его на селебритость.
Выйдет 2к
В общем, нельзя просто взять и спросить "Кто здесь никого не знает" или "кто здесь знаменитось" и т.д. Даже в реальной жизни прежде чем получить ответ каждый подумает над каждым, прежде чем дать ответ.
Если вас в комнате трое и я задам такой вопрос, каждый из вас создаст ещё по 2 вопроса самому себе, прежде чем ответить. "Знаю ли я 1" и "Знаю ли я 2". По сути, получается обычный перебор из начала видео.
А так, вам задают 1 вопрос, над которым нужно подумать.
Стоп, знаменитость же всего одна(я тут долгих комментарий писал, где половина это поиск знаменитости из возможных знаменитостей).
Проходим по первому человеку, если он кого-то знает, то уберем всех кого он не знает, если он ни кого не знает, он знаменитость(это если знаменитость по-любому должна быть), и повторяем до k раз. Если знаменитость не обезательно должна быть, тогда проходим по первому человеку, но если знает хоть одного то тех кого он не знает переносим во второй список. Когда мы находим человека который никого не знает, проверяем всех оставшихся м тех кто в другой таблице, знают ли они его, если нет - нету знаменитостей
Купил такую же футболочку в Египте :)
Можно выстроить всех в ряд и спросить у всех сразу: Кто не знаком ни с одним из присутствующих здесь.
Ответит один человек - он и главный кандидат )
очень простая задача изи левела но очень хорошо завуалирована, что делает ее более интересной
а можно у всех сразу спросить "кто здесь не знает никого с присутствующих ?"
Все просто. Смотри. Возьмём, условно, любой двор города миллионика.
4 дома, по 9 этажей, по 4 подъезда с ±2 человека в квартире. И вот ты у этой толпы можешь спросить: "Кто здесь никого никого не встречал?".
И если ты спросишь "кто здесь не знает никого из присутсвующих", то ты заставляешь каждого из присутствующих подумать относительно каждого, знает ли он его.
Т.е. если вас 3 стоит в комнате. Чтобы узнать, знаешь ли ты кого-то, ты подумаешь : Сашу знаю, Володю не знаю. Или Сашу знаю и Володю знаю и т.д. это уже больше, чем если бы у тебя спросили : Сашу знаешь?
@@kolyakars5248 задача была об двух вопросах и 4 человеках , там не говорилось сколько будет отвечать)
Ответ простой: Я знаю Джеффа Безоса - он знаменитость. Можно добавить еще, что вчера вместе бухали - Работа ваша!
рисунки действительно великолепные ;) знаменитость изображена прям по американским канонам: подтянутая и жизнерадостная ))
не то, что остальной плебс
Александр, судя по решению, в Амазон Вас не взяли, ибо оно не корреткное. В последней части нельзя возвращать null, если Вы дошли до l. Надо пропустить это значение: if (i == l) continue;.
оно и не вернет. условие (i != l && что-то) в случае если i == l будет ложно. return null не произойдет. будет переход к следующей итерации.
простая задача, решение за 2 минуты придумал )
Похоже на быструю сортировку Хоара, там похожий принцип работает с 2-мя mark сначала и конца массива
Александр, спасибо, интересно следить за развитием решения. Единственный момент - возвращать null, не очень хорошая идея.
> возвращать null, не очень хорошая идея
почему?
@@F6BF792C 1. Меньше вероятности словить NullPiontException
2. В другой функции, которая примет от этой возвращаемый объект, мы избавляемся от лишней проверки на null и см. п.1.
Знаменитость - единственный, кто никого не знает. И не надо больше вопросов))
В условии сказано, что его должны все знать, кроме того, что он не знает никого
@@АндрейБелимов-я4у двоих таких, которые никого не знают при таких условиях быть не может ))
Нельзя ли сделать так:
1. Создать массив Links с нулевыми значениями, размер массива соответствует количеству людей.
2. В цикле проходимся по массиву с людьми и спрашиваем кого они знают, в массиве Links для элементов сооветствующих нужным людям (по индексу) если текущее значение >=0 увеличиваем значение на 1. Также, если этот человек знает хоть кого-то, выставляем у элемента массива Links с индексом равным индексу человека, значение -1.
3. Когда цикл завершится, ищем единственное положительное значение массива Links и дополнительно проверяем, что оно равно длине массива с людьми.
Это первое что пришло в голову, думаю должно работать.
работать должно, но медленно.
пройтись по всем людям и спросить кого знают это уже квадратичная сложность.
Ответ k-1, нужен алгоритм для простого перебора. Ведь при каждом вопросе персоне Kx "знаешь ли Ky?" мы точно определяем что один из них не знаменитость. Соответственно при k=2 нам нужен всего 1 вопрос, при k=3 нам нужно 2 вопроса и так далее.
Это работало бы только при условии, что в группе всегда есть знаменитость - тогда можно просто отбросить всех неподходящих кандидатов и останется нужный.
Объясните пожалуйста, почему в последнем условии используется «или», если нам нужно чтоб оба условия выполнялись (и person[i] должен знать person[l], и person[l] должен не знать person[i])?
Я так понял, что в Амазон стоит очередь...
крутая задача
Саша Лукин, а тут нет баги?
Ведь человек может знать сам себя!
В первой части алгоритма нашли i = 3, а во второй части мы просто пробегаемся от 0 до length . При этом 3 как раз в этот [0, length) попадает.
Во второй части мы исключаем i=l из проверки (первая часть условия в if- е)
@@funduk96 Точно, вы правы! На 7:15 об этом. Не внимательно слушал
> Ведь человек может знать сам себя!
Ах вот зачем знаменитости то под алкоголем то под коксом! Чтобы мало того никого не знать, так ещё и себя забыть! :-))))))
Самый простой способ, спросить у каждого знает ли он кого либо из этих людей, если находим кого либо кто не знает никого из группы, то он по условиям задачи и есть знаменитость. Зачем придумывать сложные алгоритмы? Т.к. условия при котором есть человек о котором кто то не знает, но при этом этот человек не знает никого, нет.
Жаль ты канал забросил. Очень крутой контент. Кстати, что за приложение для презентации используешь?
если persons[] будет пустой - всем пока (по коду из видео если судить)
Задачка то с подвохом ) А что если первый человек НЕ знает второго НО знает третьего а мы его спросили знает ли он второго, он ответит НЕТ и сразу попадет в подмножество знаменитостей? А может ли быть кандидат который знает кого то или всех, а его не знает ни кто? В этом случае на вопрос другим кандидатам они ответят что его НЕ знают и знаменитость, т к она не знает ни кого то и его то же не знает.
я бы немного поменял алгоритм, проверяя не 1 с 2 а после 3 с 4 и тд как у автора, а проверял бы 1 с 2, а после оставшегося из них неизвестным с третьим, потом с четвертым и тд. на производительность это не повлияет, но алгоритм будет выглядеть проще
Не думал, что меня будет учить Саша Симпл собеседованию Амазон
Он Lookin от слова look, чтобы его смотрели!!! А мне говорят, что нумерология и имя не влияют на судьбу... Чушь! Все имеет значение!
4:00 - разбить на двойки, потом опять и опять, и получить дерево тем самым?
Как же можно извратить простые как угол дома алгоритмы if/else :-)
А разве в условии не должно быть наообород что проверяемый кондидат должен знать нашего предпологаемого селебрити а селебрити в свою очередь не должен знать проверямоего кондидата ??
Спасибо
Работаю в никому неизвестной продуктовой компании, аутсорс, Лондон. Моя задача на техническом собеседовании была распарсить в несколько потоков эксельку, смапить полученные данные в объекты, которые ты сам создаёшь по описанию конечно же, объекты сразу же собрать в список и отсортировать кастомным компаратором. К реализации докапываются на 58 из 10. А почему написал поток в отдельном классе, а не использовал Тред Экзекьютор с лямбдами, цикломатик комплексити высокое для добавления элементов в список, а библа для парсинга экселя старая, надо было новую от Apache юзнуть… Когда узнаю что на собесах в Амазон, решают задачи с codewars, понимаю что что-то делаю не так. З.Ы учился так же в Германии, на Informatik, Uni Rostock
Много я повидал, но, чтобы либу библой называли...
про цикломатик комплексити парятся те, кто кроме этих слов ничего не сумел выучить.
@@lollol267 это же не меняет сути. Я больше привык к придирчивым ЧСВшным интервьюерам и необоснованным предъявам во время собеседований. Я рассказал про свой опыт скорей потому, что название видео кликбейтное (без какой-либо критики содержания видео это говорю) и увидев такое название у людей которые ищут свою первую работу или собираются подаваться в Амазон, могут сложиться ложные ожидания. Хотя в целом я и в Амазон не подавался. Может туда и правда попасть легче чем в мелкие продуктовые конторы, хотя я очень сомневаюсь.
Заслуженный лайк.
Расскажите, как работает GC ?)
Person это был класс, а метод knows is boolean method?
Пример для первого человека страный. Какой смысл опрашивать, все ли знают первого человека, если по условиям в компании должна быть знаменитость?
Тот, кто никого не знает и является знаменитостью в таком случае - тк в компании не может быть 2х человек, которые никого не знают, ибо по условиям там должна быть знаменитость, которую знают все.
Или налиие знаменитости в группе - не обязательно?
Напоминает школьные уроки программирования на бэйсике в 90-е.
Как мне кажется это не самое простое решение. Предлагаю свое с 2k/
Начать переборку с начала и по очереди спрашивать знает ли он второго, если нет, то перейти к третьему и так до момента, когда он кого-то узнает (всех кого мы пропустили не были знаменитостями). Предположим первый узнал четвертого, а это означает, что либо 4-ый знаменитость или же он знает знаменитость, которая уже точно находится за четвертым. Теперь мы четвертого спрашиваем о пятом и так пока не найдем человека, который дальше никого не знает, и он либо будет знаменитостью, либо же знаменитостей не было в массиве.
И второй цикл, мы просто всех по очереди спрашиваем, знают ли они предполагаемую знаменитость. Если да, то это она, иначе нет знаменитостей, все уехали из России
Привет! Отвечу, хоть и с запозданием, потому что другие лайкнувшие коммент, видимо, не заметили ошибки в логике твоего решения.
Вообще, это очень любопытная мысль, что последующего кандидата, которого знали предыдущие, можно не спрашивать о прошлых людях, так как они точно не знаменитости, раз до этого их никто не знал. В твоем примере 4-го не обязательно спрашивать о 2 и 3, людях т.к. до этого 1-й их не знал. Но это допущение неверно, ввиду того, что по условию задачи могут быть группы, не содержащие знаменитостей вообще, и выбранный тобой кандидат может знать кого-то до него - а потому не являясь знаменитостью по второму критерию: "знаменитость не должна знать никого". Так, 4-го человека в твоем примере действительно могли знать все, но при это сам он мог знать, к примеру, 2-го, о чем ты его (к слову, не очень любезно) не спросил 😥
Поэтому для проверки этого критерия нужен третий цикл, в котором мы дополнительно спросим кандидата в селебрити о том, знает ли он людей до него. В худшем случае, ты спросишь про k-1 людей, откуда делаем вывод, что такое решение тоже будет иметь скорость в районе 3k, или же O(k).
Объясните, пожалуйста, почему сложность первого алгоритма О(k^2), a не О(k^3)? Как я мыслю: чтобы рассмотреть одного претендента на роль знаменитости, нам нужно, задать k-1 вопрос остальным «знаете ли, вы этого человека?», если все знают, то теперь нам надо задать k-1 вопрос претенденту. Итак, мы рассмотрели. Является ли конкретный человек знаменитостью. Но только одного. А их k. В итоге, чтобы в лоб всех перебрать нужно (k-1)^2 * k = k^3 + … => O(k^3). Где косяк?
(K-1)*2*k
@@sashalukin а, точно. Спасибо большое!
Спасибо. В зал ходишь? :)
Спрашиваешь у первого кого он знает и те кого он не знает отлетают потом спрашиваем одного из тех кого знает первый кого знает и так же отбираем
А не легче ли проДФСить через любого.
а в цикле for разве должно быть (!person[i].knows(persons[l], а не (person[i].!knows(persons[l]? если это переводить, то получается не i знает кандидата l, а не (как сказано) i не знает кандидата l. Или я чего-то не понимаю?)
Здравствуйте, Александр! А не подскажите хорошие курсы для начинающих? Просто сейчас занимаюсь программирование в 1С (не знаю, знакомо Вам такое или нет))), а хотелось бы окунуться так сказать во что то глубокое))
Здравствуйте, как успехи?
Классный метод, а еще можно загнать массив в стэк и доставая элемент, сравнивать попарно вершину стека со вторым элементом (для этого вершину предварительно вычитывам в переменную)
А почему используешь именно цикл while
Ведь если использовать тот же цикл for а потом еще один (не друг в друге) то тоже выйдет 2К и сложность по биг о выйдет О(к)
И как так вышло что второй цикл (for) это 2к сложность? И это ты просто сплюсовал верхнюю сложность?
Проще спросить всех, знают ли они друг друга, задав всего один вопрос. Сами всё расскажут....
Не знаю увидит кто или нет. А что если делать так:
спрашиваем у первого - знает ли второго. Если нет, то у первого спрашиваем, знает ли третьего... и т.д., пока не добьемся того, что какого-то он знает, либо дошел до конца списка. К примеру, дошли, что он знает пятого. Далее идем к пятому и спрашиваем, знает ли он шестого.. и т.д. Доходим до момента, когда, например из 50 человек, 47ой не знает ни 48, ни 49, ни 50. Считаем его потенциальной знаменитостью. И идем обратно, только с ним: знает ли он 46, 45, 44.... если он хоть одного из них знает - то в списке нет знаменитости. Если доходим до 1ого и его никто не знает, то начинаем снова с 1ого и до 45 и спрашиваем, знают ли 47.
Блин, пока расписывал, понял свой косяк и количество вопросов выросло с 2к-1 до 3к-2 :(
Сделать рассылку на всех со списком кто с кем знаком….
Хм, я бы использовал проход по условию "знаешь ли кого-то", а потом проход по обратной рекурсивной связи. Разумеется, если связи описаны каким-либо образом.
Ну это мифический пример, а в реальности где это применить?
Дискавери графов зависимостей в пакетах например.
как это помогло амазону не облажаться с запуском NW ?
это и помогает помогает Амазону запускать там всякое, а не только ютьюбчик смотреть
А на собесах на какую позицию задают такие вопросы?
Условно из "джун миддл сеньор" (знаю что каждая крупная делит грейды как ей нравится, поэтому обобщаю))
Думаю, это задача не на "джун-мидл-сеньор", а на знание алгоритмов и умение их применять, то есть насколько хорош человек в информатике и насколько он сообразителен. Это базовые знания, а джун-мидл-сеньор - это практический опыт. Поэтому ее можно встретить на любой позиции. Частенько можно получить оффер даже если завалил задачу, но ход мыслей интервьюеру понравился.
Это просто задача на решить с ходу из головы за 3 сек. Для разогрева. Чтоб сразу ред-флаг или дальше пойти. Эта задача ничего не показывает потому что она вообще ничего не показывает.
@@MaruiInfantry как это часто и бывает, проверяют одно а заниматься на работе приходиться совершенно другим
@@katskosta На работе часто приходится брать коллекции каких-то данных и преобразовывать их по какой-то хитрой логике. Любой найдет неэффективное решение "в лоб" для подобной задачи, но не каждый задаст себе вопрос "а можно ли сделать лучше" и далеко не каждый действительно сделает лучше. Кандидат, который хорошо справляется с такими задачами, предположительно, в повседневной работе тоже будет использовать эффективные алгоритмы.
@@baetz2 мне кажется вы все усложняете, в 90% задачах это не нужно лучше пусть код будет более понятен, чем придумавать эффективное решение там где нет в этом надобности, я не спорю что иногда нужно быстрое и эффективные решения.
Самый быстрый способ это каждому задать вопрос "Ты знаменитость?" и не ипать мозг
задача состоит в ПОИСКЕ знаменитости, а где сказано что поиск надо оптимизировать?? где в задании сказано что надо найти МИНИМАЛЬНОЕ КОЛИЧЕСТВО ДЕЙСТВИЙ для поиска?
1:26
Быстрее будет собрать всех вместе и спросить одной фразой: «есть ли тут кто-то, кто не знает никого?». Всего один вопрос и один ответ. И нахрен не нужны эти формулы.
в стек всех сложить и достать первого, у него спрашивать до тех пор, пока он не будет никого знать, и выбрасывать со стека этих людей. как только он узнал, то заменяем первого допрашиваемого на нового кандидата и спрашиваем уже у него до тех пор, пока ....
Не очень эффективно по памяти, потому что вместо двух интов (L и r) придется в память загружать стек из k элементов, коих может быть очень много.
@@baetz2 но ведь в память все равно придется загружать k элементов в виде массива, наверно все дело в реализации (я не специалист), и в итоге будет одно и то же, массив и 2 указателя. Просто стек это абстракция для человека.. если я правильно понимаю
@@shickulaairships Сам массив из k элементов загружен в память, от этого никуда не деться. Но ваш стек - это дополнительное выделение памяти размером 4*k байт (4 байта на каждую ссылку). На каждый миллион человек этот алгоритм будет отъедать по 4МБ памяти чисто под стек. А L и r - это 2 области памяти по 4 байта = 8 байт.
@@baetz2 да, так и есть, затупил
А если ни L, ни R не знают друг друга алгоритм посчитает R-1, хотя не факт, что именно R был не селебрити. Разве не ошибка?
А что, если кто-либо из пяти этих людей соврет, отвечая на вопросы касательно его знакомства с другими людьми пятерки?
это задача другая
задача про того кто врет, говорит правду и дипломат
А не проще спросить например у первого, знает ли он кого либо? И если это знаменитость, то всё закончится одной итерацией. Если нет, то продолжить опрос других членов группы
Это увеличивает сложность алгоритма до O(n^2), так как вы итерируетесь по каждому и сравниваете его с каждым другим.
@@erkin7138 нет, не интересуюсь каждым, а спрашиваю кого он знает. Алгоритм туп, он спрашивает каждого о каждом, человек же может задать вопрос в общем, получив один развернутый ответ. Суть задачи задать минимум вопросом для выяснения цели. Вот собственно и задаётся вопрос общего характера. Другое дело описать это алгоритмом.
@@gen2365 спросить у каждого, знает ли он хоть одного другого это 1 этап решения задачи. Нужно ещё, чтобы другие его все знали. Одной итерацией это не сделать, имхо.
@@erkin7138 изначально речь не идёт об итерациях. Речь о том чтобы задав минимум вопросом выяснить. Изначально задача чисто человеческая. Поэтому с человеческим подходом и задаём очевидный вопрос: кого знаешь?
@@gen2365 Если по-человечески, это допустимо. Просто тут на алгоритм задача от Амазона, можно любой псевдокод использовать, но без обычной логики не решить ничего.
Насколько, всё-таки, классно, что, будучи далёким от программирования, я сумел не только дожить до пенсии, но ещё и заработать, реально, очень достойную пенсию, достаточную для того, чтобы жить во Флориде, ни в чём себе не отказывая, во времена, когда вокруг свирепствует программирование...
😂
Ну я тоже зарабатываю достойно, будучи индустриальным инженером, но при этом моя работа программирования не требует. Хотя справедливости ради надо сказать что пару простых языков я все-таки достаточно хорошо знаю. Но это скорее для личного пользования нежели для работы
Когда вокруг свирепствуют бизнесмены и ты такой со своей Java потихоньку побираешься, а тут ещё олимпиадные задачи тебе на голову и куды бечь?
а что за метод know у массивов? Или он где-то отдельно прописан?
knows - это метод класса Person, а не массивов)