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

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

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

Да разгледаме един пример.

Когато търсенето не изглежда като търсене

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

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

Този тип проблем е особено подвеждащ, тъй като на практика извиква в лицето ви, когато го погледнете за първи път: „Аз съм математически проблем! Решете ме математически!“

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

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

  1. Имаме нужда от подредено пространство за търсене, което може да бъде спретнато разделено на подсекции.
  2. Трябва да можем да поставим висока и ниска граница на нашето пространство за търсене.
  3. Имайки предвид един елемент в нашето пространство за търсене, трябва да можем да разберем дали това, което търсим, е над или под тази точка.

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

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

Какво ще кажете обаче за високи и ниски граници? Знаем, че квадратният корен трябва да бъде по-голям или равен на нула, така че ниската граница е лесна. А високата граница? Е, не може да е по-голямо от входа, нали? Така че можем да зададем нашите ниски и високи граници, свободно, на 0 и n.

Да предположим, например, че искаме да намерим корен квадратен от 36. Нашите първоначални условия на търсене ще имат долната граница при 0, горната граница при 36 и средната точка при (36+0)/2 = 18.

Сега просто трябва да тестваме нашата средна точка, за да видим как се сравнява n. И как да направим това? На квадрат го. 18²=324, което е много по-високо от 36, така че знаем, че трябва да търсим в долната половина на нашето пространство за търсене. Можем да направим това, като зададем нашата висока граница на 17, което дава нов диапазон на търсене с 8 в средата.

Можем да проверим 8 и като го повдигнем на квадрат. 8² = 64, което пак е по-голямо от 36, така че трябва да погледнем отново долната половина на диапазона. Правим това, като зададем нашата висока граница на 7, което дава нова средна точка от 3.

3² = 9, което е по-малко от 36, така че сега знаем, че сме отишли ​​твърде ниско и трябва да погледнем горната половина на нашето пространство за търсене. Можем да направим това, като зададем нашата ниска граница на 4. Това ни дава нова средна точка от (4+7)/2 = 5 (не забравяйте, че целочисленото деление се закръгля надолу).

5² = 25, което все още е по-малко от 36, така че преместваме нашата долна граница отново нагоре до 6. Това ни дава средна точка от (6+7)/2 = 6.

6² = 36, така че намерихме отговора. Намалихме първоначалното пространство за търсене от [0, 36] до само [6, 7], което накрая разкри, че квадратният корен от 36 е 6.

Разбира се, при правилно внедряване ще се нуждаем от малко повече детайлност, за да закръглим правилно решения без четно цяло число, но това е оптималното решение по своята същност. Използвайки двоично търсене, можем да решим този проблем (и целия този жанр от псевдоматематически задачи) за O(log n) време. Просто трябваше да разпознаем проблема такъв, какъвто наистина беше – проблем с търсенето.

Съвпадащ модел

В този момент би било честно да възразите: „Всичко това е чудесно, но как да разбера истинското естество на проблема?“

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

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

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

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

Нека разгледаме друг пример.

Всичко е Графика

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

Дадени са два низа, a и b, определете разстоянието за размяна между тях. Разстоянието за размяна се определя като минималния брой пъти, когато трябва да размените два знака в един низ, за ​​да го превърнете в другия.

Например, разгледайте низовете „abab“ и „baba“. Тези два низа имат разстояние за размяна 2. Размяната на първите два знака на a го трансформира в „baab“, а след това размяната на последните два знака ще го превърне в „baba“. Така можете да трансформирате един низ в друг с минимум две размени.

Как да решим този проблем? Номерът за концептуализиране на този проблем е да се признае, че всяка поредица от трансформации може да бъде моделирана като графика. Ще започнем от един низ, да кажем a, и ще го наречем възел в нашата графика. След това имате избор между две позиции в низа, които да размените. Можете да размените 0 с 1, което ще запишем като (0, 1). Можете също така да размените (0, 2) или (0, 3). Или (1, 2), или (1, 3), или (2, 3). Ще наречем всяка от тези шест възможности ребро, което води до нов възел в графиката, трансформирания низ. Така че първият слой на нашата графика ще изглежда така.

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

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

С проблема, визуализиран по този начин, просто е въпрос на намиране на най-краткия възможен път между изходния възел, „abab“, и целевия възел, „baba“. Превърнахме непрозрачното описание на проблема, което ни беше дадено, в директно търсене по най-краткия път през непретеглена графика, което можем да разрешим с търсене в ширина. В тази графика всъщност има 4 различни пътя с дължина 2, минималното разстояние, от „abab“ до „baba“. Нека подчертаем само един.

Двата слоя

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

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

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

Първата стъпка за пробиване през този първи слой, следователно, е първо да проверите всички предубеждения, които изникват в главата ви, когато за първи път прочетете проблема. Разбира се, може да изглежда като математическа задача, но наистина ли е математическа задача? Преди да губите твърде много време за възможно решение, направете бързо мозъчна атака, за да видите дали можете да измислите някаква причина, че очевидното решение, което имате предвид, няма да работи за този конкретен проблем.

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

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