Како приступити било којем интервјуу за алгоритам без панике

Будимо искрени, проблеми с алгоритмом још су увијек дио тражења посла. Иако постоји све већа листа компанија које вас не присиљавају да прескачете обруче за кодирање, просечни програмер ће наићи на изазов живог алгоритма негде у потрази за послом. Нарочито ако желите да радите за Велику четворку или етаблирани стартуп. Па кроз обруче скачемо.

Не треба да причам о томе колико технички интервјуи могу бити стресни. Сигуран сам да већина нас зна фрустрацију изласка из интервјуа који смо управо бомбардирали и вожње бицикла кроз све начине на које смо то могли преокренути. То није забаван осећај.

Зато ово и пишем. За оне од вас који заврше у изазову алгоритма, начин на који му приступите може учинити све разлике. Да ли сте тип особе која зарони главом и успут то смисли? Или имате поступак који следите да бисте проблем рашчланили на делове који се могу контролисати? Иако прва метода може некоме успети, ја вежбам другу.

За мене је кључно имати низ корака за решавање проблема. Иако ми не гарантује решење или понуду посла, омогућава ми да управљам реакцијом на стрес. Одржавање панике на подношљивом нивоу помаже ми да се усредсредим. На крају, технички разговори би требало да се тичу доказивања ваше способности за решавање проблема, а не ваше способности да рукујете са више људи који вас тихо осуђују без пропадања.

У овом чланку желим да вам покажем процес који сам усавршио кроз неколико техничких екрана и десетине лажних интервјуа. На њега снажно утиче систем ПЕДАЦ школе покретања. Користим га сваки пут и добро ми је послужио.

„Заљубите се у процес и резултати ће доћи.“ - Ериц Тхомас

Најбољи начин да покажем свој процес је да га покажем на делу. Па хајде да заједно решимо проблем. Да бих ово учинио што аутентичнијим, изабраћу проблем који никада раније нисам решио. Иако ћете морати да ми верујете на реч.

Према Леетцоде-у, алгоритам Стринг то Интегер је популарно питање у интервјуу. Такође има најнижу стопу завршетка од било ког проблема средњег ранга. Ово би требао бити добар изазов.

Такође сам изабрао овај проблем јер је донекле практичан. Ово је стварни алгоритам који је имплементиран у већини програмских језика. За разлику од многих других изазова у интервјуу (гледајући вашу промену новчића), инжењери су заправо користили овај алгоритам у стварном животу.

Уз то, заронимо. Слободно пратите на било ком језику. Користићу ЈаваСцрипт. Можете испробати мој приступ или користити свој. На крају овог поста погледајте да ли то уопште можете да решите пре мене. Можда ћете завршити корак ближе стварању нашег сопственог језика.

1. корак: Преформулишите проблем својим речима

За мене је ово најважнији корак. Ово је моја прилика да свом испитивачу поставим питања како бих појаснио захтеве и рашчланио све кључне информације. Даље, преписивање проблема у моје речи даје ми шансу да формирам ментални модел и пробавим проблем.

За овај проблем, једно питање које бих поставио је да ли ми је дозвољено да користим ливење типа. Иако га опис не наводи, за конверзију по један знак користићу само ливење нативног типа ЈаваСцрипт-а. То је врста ограничења коју бих очекивао да нађем у стварном интервјуу.

Након читања описа, ово су кључни детаљи до којих сам дошао.

// Given a string, return its appropriate number value.
// Ignore all white-space at the beginning of the string.
// Number may begin with a negative or positive.
// All characters that come after the number should be ignored.
// String is invalid if a character that is not a white-space or sign comes before the number.
// If string does not contain any integer values, it is invalid.
// The return value for any invalid string is 0.
// Resulting integer cannot be larger than (2^31) — 1 or smaller than -(2^31).

Управо из ових захтева, већ почињем да замишљам како ћу створити овај алгоритам. Вероватно ће бити потребно петље и прилично условна логика.

Неки људи би вероватно почели да кодирају након овог корака. За мене је још увек мало прерано за формулисање било каквих конкретних планова - али зупчаници ми се окрећу.

Корак 2: Типови улаза и излаза

Многи људи ће ово видети као бесмислен корак, али ја увек водим рачуна о улазима и излазима алгоритма. Било као коментар кода или у углу табле.

Служи две функције. Прво, учвршћује који ће бити параметри моје функције и како ће изгледати потпис. Леетцоде је већ креирао потпис функције за мене, али то неће бити случај у стварном интервјуу.

Друго, подсећам на врсте са којима ћу радити. Није нечувено да кандидат падне на свим тест случајевима јер је заборавио да врати низ, а не низ. Могу или не морам говорити из искуства ...

За наш проблем, улази и излази су лепо дефинисани у наслову.

Input: stringOutput: 32-bit signed integerSignature: myAtoi(str)

Корак 3: Примери и ивични случајеви

Сад кад сам уверен у улазе и излазе, желим да изнесем неколико тест случајева. Ови примери морају да обухвате све ивичне случајеве којих се могу сетити. Могу само да замислим колико је пута кандидат креирао ефикасно решење, само да би анкетар смислио оштар случај који су пропустили - због чега се њихово решење распадало.

Могуће је да ће ваш анкетар пружити неке, али ја бих их смислио још више - посебно ако нису исцрпни. На пример, Леетцоде ми је дао неколико пристојних тестова.

In: “4193 with words”Out: 4193
In: “words and 987”Out: 0
In: “-91283472332”Out: -2147483648

Међутим, овим примерима недостају неке могућности. Шта ако број почиње са а +? Или шта ако више знакова долази испред броја, као што је -+-50?

Направимо неке боље.

Input: “+50.890”Output: 50
Input: “ -+100”Output: 0
Input: “ !another invalid -10”Output: 0

Step 4: Data Structure(s)

Most, if not all, algorithm code challenges involve using a structure to keep track of your data. It’s important to consider which data structure(s) you will use as it will impact your implementation.

I know from the problem description that I will be dealing with strings and integers. But will I use another data structure to help convert from one to the other?

One issue I can already foresee is keeping track of the places of each digit (tens, hundreds, thousands, etc). Since I will not know the length of my integer beforehand, I will use an array to keep track of the integer characters. The array will serve as the interim placeholder for each character before they are converted into the final integer.

While there is most likely a more space efficient solution, I can optimize my solution later. Right now, I just want to go with what makes the most sense for me. It’s better to get a working naive solution than to shoot for the moon and not finish anything.

Step 5: Pseudocode

My penultimate step is to spend some time laying out my algorithm in pseudocode. Interviewers want to see how you think and approach problems. Pseudocode is perfect for that.

An added benefit is that the interviewer will know how to assist you ahead of time. There have been times where I’ve gotten stuck on a problem only to have my interviewer provide subtle hints to keep me going. If you jump into coding without a plan, you could end up confusing both yourself and your interviewer. Do each of you a favor and create an action plan.

This is what I came up with.

// Start with index = 0
// While character at current index is white-space // increment index
// Check if next character is invalid // return 0
// Check if next character is positive or negative sign // If negative sign, mark number as negative // increment index
// Loop through characters starting at current index // If current character is integer // Unshift into front of array // Increment index // Else, break out of loop
// Loop through string integer array // Cast string character into integer // Multiply integer by (10^index) and add to return value
// If string contained negative sign, multiply result value by -1// If result value is less than min, reassign to min// If result value is greater than max, reassign to max
// return value

It may seem like I came up with this out of nowhere, but there was a lot of deliberation and trial-and-error behind the scenes. This is the most time-consuming step because this is where the algorithm is created.

Read over the requirements, inputs/outputs, and edge cases. Ask questions, clarify concepts, and isolate areas of uncertainty to focus on. Find the simplest solution you can think of and work from there.

Will you need a depth-first search? Sliding window? Divide and conquer? Something else?

If this is the step you struggle with the most, don’t worry. It will get easier with practice. And practice you should. A thorough algorithm design in pseudocode will make the next step fast and easy.

Step 6: Code!

Finally!” You’re probably thinking. “That took forever!

Заиста, проводим пуно времена у планирању расположења. Ако ми анкетар да 45 минута да завршим, потрошићу 15–30 минута на размишљање и ментално варење.

„Дајте ми шест сати да посечем дрво, а прва четири ћу оштрити секиру.“ - Абрахам Линколн

У ствари, кодирање је за мене најмање важан корак. Сва дизања тешких терета су већ урађена. Сада само треба да свој ментални модел протумачим у код.

Поред тога, како кодирам ово решење у окружењу интервјуа, неће бити исто као што га кодирам у стварном животу. Дођавола, право решење за интервју изгледало би другачије од одговора који сам смислио за овај чланак. Неколико фактора утиче на то како кодирам интервју, као што су време и одзив анкетара.

Without access to Google or sufficient time to refactor, I just want to write something that works. And there’s no guarantee I would even achieve that.

But that’s not the point of this post. Yes, it’s possible I wouldn’t have solved this question in an interview. But up until this point, I have de-structured the challenge into its key components. I know I can solve it and I have put myself in the best position to do so. A good interviewer will see that.

In a technical screen or onsite, it’s not about the code. It’s how you come up with it.

If you are interested in comparing solutions, here’s the one I came up with:

This solution is not the most efficient. According to Leetcode, it only beats 25% of the other submissions.

However, it would pass most technical interviews. An interviewer might ask me to optimize it for space or time, but those are things that can be included on further iterations if time permits. You don’t need to come up with them on the first try.

The point of using a process is to have a systemic approach to break down any challenge. It works whether you use in your job on a daily basis or in a technical interview. By using it in an interview, you can keep your panic at bay by focusing on the challenge and not your emotions.

If you don’t have a process, start making one. You can use PEDAC or develop your own. Just make sure it helps you create solutions in which you’re confident.

На пример, можда сте приметили употребу константи, помоћних функција и регуларног израза у мом решењу. То су све трикови које сам покупила и помажу ми да изолујем сложеност у интервјуу. Што се мој код више чита као енглески, то ме мање збуњује када га пишем и брже радим. Можда је мало опширно, али свиђа ми се. Радите оно што вам одговара.

Ако већ постоји процедура коју користите, увежбајте је и усавршите. Немојте чекати да ваш интервју на лицу места почне да се фино подешава. Експериментишите у лажним интервјуима. Прамп и Интервиевинг.ио су савршени алати за то.

Запамтите, ако све друго закаже, верујте процесу.

Ако је овај чланак одјекнуо код вас, оставите неколико пљеска? !

Као и увек, срећно кодирање!