Деконструирани въпроси за интервю с Google: Синонимни заявки

Добре дошли в друго издание на Deconstructed от Google Interview Problems, поредица, в която представям проблемите с интервюто, които използвах, за да интервюирам кандидати в Google, докато те не изтекат и не бъдат забранени за използване в интервюта. Моята загуба обаче е ваша печалба, защото след като излязат на света, мога да ги напиша и да ви ги обясня.

Преди да се потопя, имам вълнуваща новина: напуснах Google! Радвам се да съобщя, че се присъединих към Reddit като инженерен мениджър в NYC! Все още ще публикувам тази поредица, така че бъдете в течение.

Отказ от отговорност: докато интервюирането на кандидати е една от професионалните ми отговорности, този блог представлява моите лични наблюдения, моите лични анекдоти и моите лични мнения. Моля, не грешете това за някакъв вид официално изявление от или от името на Google, азбука, Reddit или друго лице или организация.

Въпроса

Една от критиките, които получавам по въпроса за рицарския набирател, описан в последните две публикации, е, че това не е реалистичен проблем. Колкото и полезно да е да проучите мисленето на кандидата, признавам, че в крайна сметка това е малко нереалистично упражнение. (Имам някои мисли за това дали е важно да има връзка между въпросите за интервюто и реалността, но ще ги запазя за бъдеща публикация. Бъдете уверени, коментирайте раздели навсякъде, чувам ви и имам какво да кажа. Просто не сега.)

Междувременно, когато набирникът на рицаря беше забранен преди няколко години, аз взех присърце отзива и се опитах да го заменя с въпрос, който е малко по-подходящ за Google. И какво може да бъде по-уместно за Google от механиката на заявките за търсене? Намерих този въпрос и го използвах дълго време, преди той също да изтече и да бъде забранен. Както преди, ще представя въпроса, ще се гмурна в неговото обяснение и след това ще обсъдя как използвах този въпрос в интервюта и защо ми харесва:

Представете си, че работите с популярна търсачка и в логовете си наблюдавате две заявки, да кажем „рейтинги за одобрение на obama“ и „процент на популярност на obama.“ (Ако си спомням правилно, това бяха действителните примери, използвани в базата данни за проблеми с интервютата, които дати въпросът малко ...) Тези две заявки са различни низове, но мисля, че всички можем да се съгласим, че основно търсят едно и също нещо и трябва да се считат за еквивалентни при броене на заявки, показване на резултати и т.н. Как можем да открием това две заявки са синонимни?

Нека да формализираме това. Да предположим, че имате два входа. Първо, списък от двойки низове, представляващи синоними, при които двата низа в двойката са синоними един на друг. Второ, списък от двойки низове, представляващи заявки.

За да направите този бетон, ето примерна информация за илюстрация:

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

Въпроси, Въпроси

От гледна точка на това, това е прост проблем. Въпреки това, колкото по-близо гледате, толкова по-сложен става. Веднага след бухалката става ясно, че този проблем е доста дефиниран. Могат ли думите да имат множество синоними? Има ли значение редът на думите? Преходни ли са синонимните връзки, което означава, че ако A е синоним на B, а B е синоним на C, означава ли това, че A е синоним на C? Могат ли синонимите да обхващат няколко думи, например как „САЩ“ е синоним на „Съединени американски щати“ или „Съединени щати“?

Тази неяснота веднага дава възможност на добрите кандидати да се разделят. Първото нещо, което един добър кандидат прави, е да издуши подобни неясноти и да се опита да ги разреши. Как се прави това варира от кандидат до кандидат: някои стъпват до бялата дъска, за да се опитат ръчно да решават конкретни случаи, докато някои хвърлят един поглед върху въпроса и виждат пропуските веднага. Във всеки случай определянето на тези проблеми рано е от решаващо значение.

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

Комплектът Манделброт

Калибърът на инженера до голяма степен се определя от това колко дълбоко могат да разберат проблем. Преобразуването на неясна постановка на проблема в подробен набор от изисквания е стъпка нула в този процес и целенасоченото недостатъчно дефиниране на проблема ми позволява да преценя доколко един кандидат подхожда към нови ситуации.

Настрана има и тривиалните въпроси като „има ли значение капитализацията?“, Които, без да знаем за кандидата, не засягат основния алгоритмичен проблем. За тези въпроси винаги давам какъвто и да е отговор, който е най-лесен за кандидата (в този случай „приемете, че всичко вече е предварително обработено за малки букви“).

Част 1: Простият случай (не толкова)

Въпреки това кандидатите стигат до тези въпроси, те неизбежно в крайна сметка ме питат за отговор и винаги започвам с възможно най-простия случай: думите могат да имат множество синоними, въпроси на поръчката, синонимите не са преходни и синонимите могат да се картографират само от една дума на друг. Това прави доста ограничена функция в търсачката, но има повече от достатъчно тънкости в нея, за да зададете интересен въпрос за интервю.

Прегледът на високо ниво на решението е следният: разбийте заявката до думи (разделянето по интервали е наред) и сравнете двойки от съответните думи, за да видите дали те са еднакви или синоними една на друга. Визуално изглежда така:

В изпълнение изглежда малко подобно:

Лесно, нали? Алгоритмично това е доста просто. Без динамично програмиране, без рекурсия, без сложни структури от данни и т.н. Просто проста, ясна манипулация на стандартната библиотека и линеен алгоритъм за време, нали?

Бихте си помислили, но тук има по-тънкост, отколкото ще видите на пръв поглед. Най-трудният компонент на този прост алгоритъм е сравнението на синонимите. Макар и лесен за разбиране и описание, има много начини, по които компонентът за сравнение на синоними може да се обърка. Ще вляза в някои от по-често срещаните, които видях тук.

За да бъда ясен, нито една от тези грешки не е дисквалифицираща в ума ми; ако кандидатът представи реализация с грешка, просто бих я посочил, те ще коригират решението си и ние ще продължим. Интервюто обаче е преди всичко битка срещу времето. Очаква се правенето, забелязването и коригирането на грешки, но това отнема време, което би могло да бъде прекарано на друго място, като например създаване на по-оптимално решение. Много малко кандидати не правят грешки, но кандидатите, които правят по-малко, постигат по-голям напредък, просто защото прекарват по-малко време на почистване след себе си.

Ето защо ми харесва този проблем: за разлика от рицарския набирател, който изисква проблясък на алгоритмичен поглед, последван от (надяваме се) проста реализация, този въпрос изисква множество малки, постепенни стъпки в правилната посока. Всяка стъпка представлява мъничко препятствие, над което кандидатът може или да изскочи грациозно или да пътува и да се наложи да се възстанови. Добрите кандидати избягват тези малки клопки, използвайки своя опит и интуиция и са възнаградени с по-прецизно и правилно решение, докато по-слабите губят време и енергия за грешки и обикновено са оставени с бъги код.

Докато във всяко интервю се виждаше различна комбинация от скокове и лицеви растения, тук има малка извадка от по-често срещаните грешки, които видях.

Случайни убийци по време на работа

Първо, някои кандидати реализираха откриването на синоними, използвайки просто преминаване на списъка със синоними:

В лицето на това това изглежда разумно. При по-внимателна проверка това е много, много лоша идея. За онези от вас, които не познават Python, ключовата дума в синтактична захар за метод съдържа и работи над всички стандартни Python контейнери. Това е проблем тук, защото synonym_words е списък, който реализира ключовата дума в линейното търсене. Потребителите на Python бяха особено податливи на тази грешка, тъй като езикът крие типове, но потребители на C ++ и Java от време на време правят подобни грешки.

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

По отношение на практическите съвети това всъщност е лесна грешка, която трябва да се избегне. Първо, никога не забравяйте типовете на вашите обекти, дори ако използвате нетипизиран език като python! Второ, не забравяйте, че когато използвате ключовата дума в списък, това е линейно търсене. Освен ако не е гарантирано, че списъкът винаги е много малък, той ще бъде убиец на изпълнението.

Напомнянето на кандидатите, че входната структура е списък, обикновено е достатъчно, за да ги събуди. Това, което се случва, след като дам намек, е много информативно. По-добрите кандидати веднага мислят да преработят синонимите по някакъв начин, което е добро начало. Този подход обаче не е без своите клопки ...

Използвайте правилната структура на данните

От кода по-горе е ясно, че за да реализираме този алгоритъм в линейно време, се нуждаем от търсене на синоним с постоянно време. И b зад всяко търсене в постоянно време, винаги има хешмап или хешсет.

Кое от тези двама избра кандидатът, е по-малко интересно за мен от това, което влагат в него. (Между другото, никога не използвайте dict / hashmap, който отива в True или False. Това се нарича набор.) Повечето кандидати се установяват на някакъв вид dict / hashmap. Най-често срещаната грешка, която виждам, е подсъзнателно предположение, че всяка дума може да има най-много един синоним:

Аз всъщност не санкционирам кандидатите за тази грешка. Примерният вход е целенасочено създаден, за да не се има предвид, че думите могат да имат множество синоними, а някои кандидати просто не са имали този краен случай. Най-бързо се коригират, след като посоча тази грешка. Добрите кандидати си спестяват неприятностите, като го забелязват рано, но обикновено това не е голяма загуба на време.

Малко по-сериозен проблем е несъзнаването, че синонимната връзка върви и в двете посоки. Ще забележите, че горният код прави това. Поправянето на това обаче може да бъде предразположено към грешки. Помислете за следния подход за прилагане на тази собственост:

Защо да правите две вмъквания и да използвате двойна памет, когато не можете да използвате допълнителна памет и да извършите две проверки?

Извличането: винаги се питайте дали можете да свършите по-малко работа! На заден план пермутирането на търсенето е очевиден начин да спестите време, ако го търсите, но използването на неоптимално изпълнение предполага, че кандидатът не е мислил да търси начини за оптимизиране. Отново се радвам да ви намекна, но би било по-добре, ако не трябваше.

Сортиране?

Някои от по-умните кандидати смятат да сортират списъка със синоними и след това използват двоично търсене, за да определят дали две думи са синоними. Този подход всъщност има основното предимство в това, че не изисква никакво допълнително пространство освен списъка със синоними на вход (при условие, че промяната на списъка за въвеждане е приемлива).

За съжаление сложността на времето не е голяма: отнема време Nlog (N) за сортиране на списъка на синонимите и след това време за регистрация (N) за търсене на всяка двойка синоними, докато описаното по-горе решение за предварително обработване се случва в линейно и след това постоянно време. Плюс това, да накарате кандидат да приложи както сортиране, така и двоично търсене на бяла дъска, е не-не в моята книга, тъй като 1. алгоритмите за сортиране са много добре познати, така че за всички, които знам, кандидатът може да регургитира и 2. тези алгоритми са дяволски сложно да се оправят, а често дори и най-добрите кандидати ще правят грешки, които не ми казват нищо за способността им да програмирам.

Всеки път, когато кандидат предложи това решение, аз бих поискал сложността на изпълнението и да попитам дали могат да се справят по-добре. Като страна: ако интервюиращият попита дали можете да се справите по-добре, повечето пъти отговорът е „да“. Ако някога ви задам този въпрос, отговорът винаги е „да“.

И накрая, Решението

Дано в този момент кандидатът да е произвел нещо правилно и оптимално. Ето линейна реализация на линейно време за това уводно изявление:

Няколко супер бързи бележки:

  • Забележете използването на dict.get (). Можете да напишете реализацията „проверете дали ключът е в диктата и след това го вземете“, но това е затруднено, докато по този начин можете да покажете знанията си за стандартната библиотека.
  • Аз лично не съм почитател на кода, който използва много продължения, а някои ръководства за стил забраняват или възпират използването им. Всъщност въведох грешка в първоначалната си реализация на този код, като пропуснах продължението след проверката на дължината на заявката. Не е лошо, просто знайте, че е склонна към грешка

Част 2: Става по-трудно!

С добри кандидати често се озовах с най-малко десет или петнадесет минути. За щастие има много въпроси за последващи действия, които мога да задам, но няма вероятност да напишем много код в това време. В края на деня, въпреки че смятам, че не е нужно. Искам да знам две неща за един кандидат: могат ли да проектират алгоритми? и: могат ли да кодират? Рицарският набирател отговаря първо на въпроса за проектиране на алгоритъма и изследва кодирането след това, докато този въпрос получава отговори в обратен ред.

Докато кандидатът приключи първата част на този въпрос, те вече са решили (изненадващо нетривиално) проблем с кодирането. На този етап мога уверено да говоря за способността им да проектират рудиментарни алгоритми и да превеждат идеите си в код, както и запознаването им с любимия им език и стандартна библиотека. Въпросът след това става много по-забавен за мен, защото изискванията за кодиране могат да бъдат облекчени и можем да се потопим в алгоритмичния компонент.

За тази цел нека се върнем към основните предположения на първата част: въпросите за реда на словото синонимните връзки не са преходни и синонимите не могат да имат множество думи. С напредването на интервюто аз обръщам всяко от тези ограничения и в тази нова фаза след кодиране кандидатът и аз имам чисто алгоритмична дискусия. Ще създавам проби от кодове, за да илюстрирам моето мнение, но в действително интервю ще говоря чисто алгоритмично.

Преди да се гмурна, ще обясня очакванията си, като кажа, че последващите действия са в основата на „допълнителен кредит“. Личният ми подход към този въпрос е да назнакам кандидатите, които абсолютно ноктите на първия раздел дават оценка „Наемете“, и да използвам следващ раздел за разделяне на кандидатите „Наемете“ от кандидатите за „Силен наем“. Оценката „Наем“ е силна оценка, която казва „Вярвам, че този човек е достатъчно добър да работи тук“, докато „Силен наем“ казва „Вярвам, че този човек е отличен и наемането им би представлявало голяма печалба за компанията. "

Транзитивност: наивни подходи

Първото ограничение, което обичам да отпускам, е това около транзитивността, което означава, че ако думите А и В са синоними, а ако думите В и С са синоними, то думите А и С са синоними. Острите кандидати бързо осъзнават, че могат да адаптират по-ранното си решение, за да решат това, тъй като все още определят дали прости двойки думи представляват синонимни двойки, докато другите релаксации обезсилват основната логика на по-ранния алгоритъм.

За тази цел, как да направим това? Един общ подход е да се поддържа пълен набор от синоними за всяка дума, базирани на преходните връзки. Всеки път, когато вмъкнем дума в набор от синоними, ние също я добавяме към съответните набори за всички думи, които в момента са в този набор:

Това решение работи, но е далеч от оптималното. За да видите защо, помислете за сложността на пространството на това решение. Всеки път, когато добавяме синоним, трябва да добавяме не само към набора на началната дума, но и към множествата, принадлежащи на всички думи, с които тази дума е синоним. Ако това е синоним на една дума, трябва да добавим един запис. Ако това е синоним на петдесет думи, трябва да добавим още петдесет записа. Илюстрирано изглежда така:

Обърнете внимание, че преминахме от 3 ключа и 6 записа до 4 клавиша и 12 записа. Една дума с 50 синоними ще изисква 50 клавиша и почти 2500 записа. Пространството, необходимо за представяне на една дума, нараства квадратично с размера на нейния набор от синоними, който е доста разточителен.

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

Транзитивност: Използване на Disjoint Set

Оказва се, че можем да търсим отношенията на синоними в (почти) постоянно време, използвайки структура от данни, наречена разединителен набор. Тази структура се нарича набор, но предлага малко по-различни възможности от онова, което повечето хора си мислят, когато чуят думата „набор“.

Обичайната структура на набор (хешсет, набор дървета) е контейнер, който ви позволява бързо да определите дали обект е в или извън този набор. Един разединен набор решава много различен проблем: вместо да се занимава с това дали определен елемент е в набор, той ви позволява да определите дали два елемента принадлежат на един и същ набор. Нещо повече, това прави с ослепително бързо O (a (n)) време, където a (n) е обратната на функцията на Акерман. Освен ако не сте взели курс за усъвършенствани алгоритми, може да ви бъде простено, че не знаете тази функция и за всички разумни данни е ефективно равна на постоянно време.

На високо ниво алгоритъмът работи както следва. Наборите са представени от дървета, където всеки елемент има родител. Тъй като всяко дърво има корен (което означава елемент, който е негов родител), можем да определим дали два елемента принадлежат на един и същ набор, като следваме техните родители, докато не намерим корен елемент за всеки. Ако двата елемента имат един и същи корен, те трябва да принадлежат на един и същ набор. Присъединяването към набори също е лесно: ние просто намираме коренните елементи и правим единия корен на другия.

Засега е толкова добро, но все още няма ясно ослепително изпълнение. Геният на тази структура е в процедура, наречена уплътняване. Да предположим, че имате следното дърво:

Представете си, че искате да знаете дали „бързи“ и „прибързани“ са синоними. Започвайки от всеки, пресичате родителските отношения и установявате, че и двамата споделят „бързо“ като корен възел, следователно те трябва да са синоними. Сега да предположим, че искате да знаете дали „бързият“ и „бързият“ са синоними. Отново ще започнете от всеки възел и преминете нагоре, докато не достигнете „бързо“, но този път може да забележите, че сте дублирали траверса за „бързи“. Можете ли да избегнете тази дублирана работа?

Да, можете, оказва се. По някакъв начин всеки елемент от това дърво е предназначен да стигне до „бързо“. Вместо да обикаля дървото многократно, защо просто да не промените родителя на всеки елемент по пътя към „бързо“ и да си спестите работата? Този процес се нарича уплътняване и в разединен набор е вграден в операцията за намиране на корен. Например, след като определим дали „бързи“ и „прибързани“ са синоними, горното дърво ще изглежда така:

Всяка дума между „бърз“ и „бърз“ е обновявала родителя си, след това същото се е случило и с „прибързано“ до „бързо“.

Сега всички последващи достъпи ще се случват в постоянно време, защото всеки възел в това дърво сочи „бързо“. Анализът на правилната времева сложност на операциите на тази структура е нетривиален: всъщност не е постоянен, защото зависи от дълбочината на дърветата, но не е много по-лошо от постоянно, защото нещата се амортизират до постоянно време много бързо. За нашия анализ ще направим мързеливото нещо и просто ще го наречем постоянно време.

С тази концепция в ръка, ето едно несъвместимо изпълнение на набор, което предоставя точно функционалността, която ни е необходима за този проблем:

Използвайки тази структура, можем да обработим предварително синонимите и да разрешим този проблем в линейно време.

Оценка и бележки

Към този момент достигнахме границата на това, което видях направено в 40–45 минути на интервю. Дадох на всеки кандидат, който завърши уводната част и постигна значителен напредък към описване (неприлагане) на разделителното решение за оценка „Силен наем“ и продължих да ми позволяват да ми задават въпроси. Никога не съм виждал кандидат да стигне толкова далеч с много време, което да отдели.

Това ни оставя с още няколко последващи действия: версия на този въпрос, където подредбата на думите няма значение и една, при която синонимите могат да обхващат няколко думи. Решенията на всяко от тях са предизвикателни и възхитителни, но в интерес на пространството ще се обърна към тях в следващ пост.

Този въпрос е полезен, защото позволява на кандидатите да правят грешки. Ежедневното софтуерно инженерство се състои от непрекъснат цикъл на анализ, изпълнение и усъвършенстване. Този проблем предоставя на кандидатите възможности да демонстрират своето владеене на всеки от тези етапи. Помислете за необходимите умения, за да спечелите „Силен наем“ по този въпрос:

  • Анализирайте изявление на проблем и разпознайте къде е нееднозначно и недостатъчно дефинирано, като изяснявате, където е необходимо, за да разработите недвусмислено твърдение за проблем. Продължете да правите това, докато напредвате чрез решение и срещате нови въпроси. За максимална ефективност извършете колкото се може повече от този етап възможно най-рано, защото възстановяването от грешки става по-скъпо с напредването на работата ви.
  • Оформете проблема по такъв начин, който улеснява подхода и решаването му. В този случай най-важният момент е наблюдението, че можете да подредите съответните думи в заявките.
  • Приложете вашето решение. Това включва избор на оптимална структура на данни и алгоритми, както и проектиране на вашата логика за четене и лесно модифициране в бъдеще.
  • Върнете се назад и се опитайте да откриете грешки и грешки. Това могат да бъдат действителни грешки като това как съм забравил да вмъкна оператор „продължение“ по-горе или грешки в производителността като използване на неправилна структура на данните.
  • Когато дефиницията на проблема се промени, повторете този процес и адаптирайте решението си, когато е подходящо, и го запишете, където не. Да знаеш кога да правиш и двете е критично умение, както в интервю, така и в реалния свят.
  • Дръжте знанията си за структурите на данните и алгоритмите под ръка. Несъвместимата структура на данни не е съвсем обща структура, но всъщност не е толкова рядка и усъвършенствана. Единственият начин да гарантирате, че знаете инструмента за работата е, като научите колкото можете повече.

Нито едно от тези умения не може да се научи от учебниците (освен може би за структурите на данните и алгоритмите). Единственият начин да придобиете тези умения е чрез редовна и обширна практика, която добре се привежда в съответствие с това, което компаниите искат: кандидати, овладели уменията си, и са достатъчно практикувани, за да ги прилагат ефективно. Разпознаването на тези хора е смисълът на интервюто и този въпрос ми служи добре дълго време.

Очаквам

Както вероятно можете да заключите от моето писане на този пост, този въпрос в крайна сметка също изтече. Оттогава използвам няколко въпроса, в зависимост от настроението ми (задаването на един въпрос непрекъснато ми става скучно) и това, което бяха задали предишните интервюиращи кандидати. Някои от тях все още се използват, така че ще ги пазя в тайна, но някои не са! Можете да очаквате с нетърпение да видите по-късните в бъдещите постове.

В краткосрочен план обаче имам още два поста, които слизат от щуката. Първо, както беше обещано по-горе, ще напиша и публикувам останалите две последващи действия по този въпрос. Не защото някога са излизали в интервюта, а защото са интересни сами по себе си. Ще споделя и своите разсъждения и лични мнения относно процеса на наемане на работа в света на технологиите, което е особено интересно за мен сега, когато наемам инженери за моя собствен екип в Reddit.

Както винаги, ако искате да сте в крак с тази поредица, следвайте ме в Twitter или Medium. Ако ви е харесала тази публикация, не забравяйте да плеснете или да оставите коментар. Обичам отзивите и го използвам, за да разкажа какво работи и какво не.

Благодаря за четенето!

Актуализация: Сега, когато имам няколко публикации, ето списък на всички останали публикации от тази серия:

  • Въведение
  • Рицар набиране
  • Проследяване на рицар на набиране
  • Търсач на съотношение

P.S .: Можете да проверите кода в репортажа на GitHub на тази серия или да играете с кода на живо благодарение на добрите ми приятели от repl.it: