Популярная в собеседованиях гугл задача. Разбор и решение

Решаем самую частую в собеседованиях гугл задачу по версии leetcode.com
Ссылка на задачу: leetcode.com/problems/guess-t...
Ссылка на код решения: gist.github.com/oybek/6f968e9...
#программирование #scala #рекурсия #google #собеседование #алгоритмы

[@wolf_code]

Ребят leetcode рекламу у меня не заказывал Просто я хотел обосновать почему я назвал задачу популярной в собесах гугл) Если Вам показалось что задача очень простая - попробуйте решить ее самостоятельно и пройти тесты литкод P. S. 100% работающего решения не существует - попробуйте это доказать

[@alexnovik6223]

Такая задача очень похожа на игру Быки и Коровы ))

[@user-jv6ks7cd3i]

Доказательство отсутсвтия 100% решения - тест: AAAAAA BBBBBB CCCCCC .... ZZZZZZ кол-во различных букв > 10, А ответ на запрос будет 0, 6, -1, что не даёт нам информации(потому что всё симметрично)

[@ytar6501]

Автоматизация подбора пароля к терминалам в Fallout.)

[@PaulGanarara]

если в списке будут присутствовать 26 слов, отличающихся всего на одну букву, то нет гарантии, что за 10 попыток вы угадаете слово

[@wolf_code]

Абсолютно верно

[@igortunev6163]

Автор снова ошибся. В условии на литкоде не 10 попыток. Число попыток определяется входным параметром (от 10 до 30)

[@Khashimova_wellness]

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

[@user-fu5jx4ki7e]

Спасибо! Прикольный формат)

[@hrenaki7787]

Решение ломается, если все слова из списка, кроме загаданного, имеют одинаковые буквы в одинаковых позициях. Например, пусть список слов формируется следующим образом: list[i] = "w" + a[i] + "rd", где a[i] - i-ая буква латинского алфавита, загаданное слово - "word". Если случайно выберем любое слово из такого списка, и оно не совпадет с загаданным, то получим число = 3. Пробежав по списку слов, окажется, что все слова имеют число совпадений = 3. В итоге сократить исходный список не выйдет, а полный перебор в худшем случае будет осуществлен за 26 вызовов.

[@user-ni9tf5yr6m]

Задача идиотская изначально. Нельзя проверять список элементами этого же списка. Очевидно, ни к чему не приведёт

[@blackgolddev4023]

Спасибо вы лучший

[@zhanbolatnurutdin30]

Спасибо за классное видео))) Но, вопрос такой, на 4:16 на 23 строке, разве не должно быть >= больше или равно, потому что, если в списке есть слово, который отличается от загаданной на 1 букву лишь, то, по логике countMatch вернет больше, и он отсеется??? Или я что то не допонял?

[@wolf_code]

если слово отличается от загаданного на 1 символ в позиции, countMatch вернет 1

[@Khashimova_wellness]

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

[@wolf_code]

Попробую

[@alexnovik6223]

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

[@wolf_code]

Да, это должно сработать Можно попробовать, minimax получается

[@sosad9521]

Как ты это сделаешь, если при каждом вызове master.guess будет засчитываться попытка отгадывания?

[@alexnovik6223]

@@sosad9521 элементарно. Вместо рандома надо брать слово с максимальным количеством совпадений. На дальнейший код это не влияет никак.

[@sosad9521]

@@alexnovik6223 так а как ты узнаешь, больше или нет совпадений у слова, без использования master.guess?)

[@wolf_code]

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

[@ainr_dev]

Если убрать ограничение количества букв в словах, задача стала бы интересней)

[@wolf_code]

Можно попробовать))

[@user-ni9tf5yr6m]

Вообще нисколько

[@Disorrder]

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

[@goodwin_for_you]

На python проще) пусть дан список слов A=['море','мыло','сало','мало','рано','село','лось','кола','мама','папа','баба','речь','чёрт','сорт','трос','торт','брод','дрон','горе','трон','урон','нора','рана'] z='рано' #загадаем слово import random # импортируем библиотеку, хотя можно реализовать и без рандома. #Опишем того кто отвечает с условием, что если мы угадали ф-я возвращает слово в противном случае число совпадений от 0 и более. def ASK_ANSWER(word2): if z==word2:return z # для работы с анаграммами else: return chek(z,word2) #функция для проверки двух слов на количество совпадений def chek(word1,word2): return len(set(word1).intersection(set(word2))) #Реализуем ф-ю поиска, будем её вызывать в теле цикла while def find_word_in_words(words): word=random.choice(words) ABC=ASK_ANSWER(z,word) # или мы угадали или получили число совпадений if type(ABC)==str: return ABC if ABC==0: #если ни одна буква из слова word не совпала с загаданным return [i for i in words if not(chek(word,i)>=0)] # выкидываем все слова в которых есть такие же буквы что и в слове word else: # если есть совпадения return [i for i in words if (chek(word,i)==ABC and i!=word)] # генерим список в котором у слов число совпадений со словом word равно ABC #Запускаем проверку #создадим копию списка А, не обязательно:) ZZ=[i for i in A] I=1 while (True): ZZ=find_word_in_words(ZZ) print(I,ZZ) # печатаем номер запроса и новый список, эта строка необязательна if type(ZZ)==str or len(ZZ)==1:break # нашли ответ, выходим из цикла. I- число запросов, ZZ- угаданное слово I+=1 P.S. можно написать короче.

[@wolf_code]

почему это проще?

[@goodwin_for_you]

@@wolf_code строчек меньше 😉 да и синтаксис языка понятней

[@wolf_code]

@@goodwin_for_you разница сложности на эпсилон

[@binart2601]

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

[@pavelosipov5951]

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

[@binart2601]

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

[@pavelosipov5951]

@@binart2601 да, прошу прощения по поводу обращения, сейчас поправлю коммент. Речь не шла конкретно о вас, я просто написал как думал. Для поломки решения не обязательно иметь 0 совпадений. Примеры можно придумать для любого количества совпадений, кроме, естественно, полного совпадения.

[@Helsus49]

За гачи отсылку рэспэкт

[@wolf_code]

Дань уважения легенде

[@Disorrder]

в слове мастер тоже 6 букв. Уверен, оно и есть секретное!

[@rad9587]

2:23 почему у weewee 0?

[@wolf_code]

ошибся - прошу простить(

[@tym32167]

Сколько раз был на собесах в Гугле, ни разу такаая задача не попадалась. Выглядит слишком легкой :)

[@wolf_code]

Возможно она вам не попадалась, ну или вы шли на более высокую позицию) Когда я давно собесился в гугл, алгоритмические задачи примерно такого уровня мне давали Ну или более 1000 людей сговорились и соврали) P. S. Мое решение не всегда работает верно и не является лучшим, если попробуете решить задачу самостоятельно - то поймете что она не такая простая как кажется)

[@tym32167]

@@wolf_code не не, вполне может быть, я только поделился опытом. Обычно на собесе в Гугл дают задачу на минимум минут 30-40 решения, если собес по алгоритмам онсайт. Ну, или, например, такую задачу дать могут на телефонном интевью, там да, задачи попроще идут.

[@wolf_code]

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

[@tym32167]

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

[@wolf_code]

@@tym32167 Раньше там были этапы, этап по алгоритмам, потом по дизайну, потом архитектуре Возможно щас по другому

[@igorbia1079]

За 10 ну никак не выходит при таком алгоритме, при множественном запуске на случайно сгенерированном массиве доходит до 16 раз, среднее число попыток действительно меньше 10. Но если взять побольше алфавит например букв 60, то сразу максимум до 26 убегает. Хотя справедливости ради, увеличение массива слов со 100 до 10000 не сильно вляет на кол-во попыток на алфавите около 60 символов - 35

[@user-si7bd9vf6z]

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

[@wolf_code]

На это будет отдельное видео

[@illsonr6s887]

А чем скала хорош?

[@wolf_code]

docs.scala-lang.org/scala3/book/why-scala-3.html

[@illsonr6s887]

@@wolf_code спасибо, я подумаю о переходе

[@wolf_code]

@@illsonr6s887 с какого языка?

[@illsonr6s887]

@@wolf_code Питон/С++ , но я еще думаю джаву изучить, также будет проще?

[@wolf_code]

@@illsonr6s887 джаву необязательно знать для понимания скалы, но желательно)

[@felixdzerzhinsky1337]

А можно доказательства, что это работает за 10 или менее попыток?

[@wolf_code]

Можно доказать что это не будет работать за 10 или менее попыток)

[@felixdzerzhinsky1337]

@@wolf_code А можно прочитать где-нибудь?)

[@wolf_code]

@@felixdzerzhinsky1337 если перейти по ссылке в описании к задаче, там к задаче прилагается обсуждение, там есть доказательство но оно несложное на самом деле, давайте рассмотрим список слов aaaaaa, bbbbbb, cccccc, ..., zzzzzzz Каждый раз мастер будет отвечать 0, и даже через 9 попыток вероятность того что мы угадаем будет всего лишь 1/17

[@___________S_t_a_s___________]

@@wolf_code да тут задача скорее на твою логику, чем на практическое применение где либо.

[@wolf_code]

@@___________S_t_a_s___________ ну да, задача довольно синтетическая и скорее придумана чиста оценить смекалку

[@alexnovik6223]

А можно решения писать на Java ))))

[@wolf_code]

Одна из целей канала - популяризация скала, поэтому увы(

[@vladimirmokeev2856]

Совсем плохо. Никакого разбора. Ни единой оптимизации, ни эвристик, ни дерева решений, мин/максов, ничего. Только рандом. Мда. А ещё понял, что выпуск будет совсем плох, на фразе "задача простая".