Budimo iskreni, problemi s algoritmom još su uvijek dio pretraživanja posla. Iako postoji sve širi popis tvrtki koje vas ne natjeraju da preskačete kodiranje, prosječni programer će se susresti s izazovom algoritma uživo negdje u potrazi za poslom. Pogotovo ako želite raditi za Veliku četvorku ili etablirani startup. Pa kroz obruče skačemo.
Ne trebam govoriti o tome koliko tehnički razgovori mogu biti stresni. Siguran sam da većina nas zna frustraciju izlaska iz intervjua koji smo upravo bombardirali i vožnje bicikla kroz sve načine na koje smo to mogli preokrenuti. To nije zabavan osjećaj.
Zato ovo i pišem. Za one od vas koji završe u izazovu algoritma, način na koji mu pristupite može učiniti sve razlike. Jeste li tip osobe koja zaroni glavom i usput to skuži? Ili imate postupak koji slijedite kako biste problem raščlanili na upravljačke dijelove? Iako prva metoda nekima može uspjeti, drugu provodim.
Za mene je presudno imati niz koraka za rješavanje problema. Iako mi ne garantira rješenje ili ponudu posla, omogućuje mi upravljanje vlastitim odgovorom na stres. Održavanje panike na podnošljivoj razini pomaže mi da se usredotočim. Napokon, tehnički razgovori trebali bi se odnositi na pokazivanje vaše sposobnosti za rješavanje problema, a ne na sposobnost rukovanja s više ljudi koji vas šutke osuđuju bez propadanja.
U ovom članku želim vam pokazati postupak koji sam usavršio kroz nekoliko tehničkih zaslona i desetke lažnih intervjua. Na njega snažno utječe sustav PEDAC škole pokretanja. Koristim ga svaki put i dobro mi je poslužio.
"Zaljubite se u proces i rezultati će doći." - Eric ThomasNajbolji način da pokažem svoj postupak je da ga pokažem na djelu. Pa hajde da zajedno riješimo problem. Da bih ovo učinio što autentičnijim, odabrat ću problem koji nikada prije nisam riješio. Iako ćeš mi morati vjerovati na riječ.
Prema Leetcodeu, algoritam String to Integer popularno je pitanje u intervjuu. Također ima najnižu stopu dovršenosti od bilo kojeg problema srednjeg ranga. Ovo bi trebao biti dobar izazov.
Također sam izabrao ovaj problem jer je donekle praktičan. Ovo je stvarni algoritam koji je implementiran u većini programskih jezika. Za razliku od mnogih drugih izazova u intervjuu (gledajući vašu promjenu novčića), inženjeri su taj algoritam zapravo koristili u stvarnom životu.
Uz to, zaronimo. Slobodno slijedite na bilo kojem jeziku. Koristit ću JavaScript. Možete isprobati moj pristup ili koristiti svoj. Na kraju ovog posta provjerite možete li to uopće riješiti prije nego što to učinim. Možda ćete završiti korak bliže stvaranju vlastitog jezika.
1. korak: Preformulirajte problem vlastitim riječima
Za mene je ovo najvažniji korak. Ovo je moja prilika da svom ispitivaču postavim pitanja kako bih pojasnio zahtjeve i raščlanio sve ključne informacije. Nadalje, prepisivanje problema u moje riječi daje mi priliku da oblikujem mentalni model i probavim ga.
Za ovaj problem jedno pitanje koje bih postavio je smijem li koristiti lijevanje tipova. Iako ga opis ne navodi, za pretvaranje po jednog znaka koristit ću samo lijevanje nativnog tipa JavaScripta. To bih ograničenje očekivao pronaći u stvarnom intervjuu.
Nakon što sam pročitao opis, ovo su ključni detalji koje sam smislio.
// 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).Upravo iz ovih zahtjeva, već počinjem zamišljati kako ću stvoriti ovaj algoritam. Vjerojatno će trebati malo petlje i podosta uvjetne logike.
Neki bi ljudi vjerojatno počeli kodirati nakon ovog koraka. Za mene je još uvijek prerano za formuliranje bilo kakvih konkretnih planova - ali zupčanici mi se okreću.
Korak 2: Tipovi ulaza i izlaza
Mnogi će to vidjeti kao besmislen korak, ali uvijek se pobrinem za ulaze i izlaze algoritma. Bilo kao komentar koda ili u kutu ploče.
Služi za dvije funkcije. Prvo, učvršćuje koji će biti parametri moje funkcije i kako će izgledati potpis. Leetcode je već stvorio potpis funkcije za mene, ali to neće biti slučaj u stvarnom intervjuu.
Drugo, podsjećam na vrste s kojima ću raditi. Nije nečuveno da kandidat padne na svim testnim slučajevima jer je zaboravio vratiti niz, a ne niz. Mogu ili ne moram govoriti iz iskustva ...
Za naš problem, ulazi i izlazi su lijepo definirani u naslovu.
Input: stringOutput: 32-bit signed integerSignature: myAtoi(str)Korak 3: Primjeri i rubni slučajevi
Sad kad sam siguran u ulaze i izlaze, želim smisliti nekoliko test slučajeva. Ovi primjeri trebaju pokriti sve rubne slučajeve kojih se mogu sjetiti. Mogu samo zamisliti koliko je puta kandidat stvorio djelotvorno rješenje, samo da bi anketar došao do oštrog slučaja koji su propustili - zbog čega bi se njihovo rješenje raspadalo.
Moguće je da će ih vaš anketar pružiti nekoliko, ali ja bih ih smislio i više - pogotovo ako nisu iscrpni. Na primjer, Leetcode mi je dao nekoliko pristojnih testnih slučajeva.
In: “4193 with words”Out: 4193In: “words and 987”Out: 0In: “-91283472332”Out: -2147483648Međutim, ovim primjerima nedostaju neke mogućnosti. Što ako broj započinje s +? Ili što ako više znakova dolazi ispred broja, kao što je -+-50?
Napravimo neke bolje.
Input: “+50.890”Output: 50Input: “ -+100”Output: 0Input: “ !another invalid -10”Output: 0Step 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 valueIt 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!”
Doista, puno vremena provodim u planiranju raspoloženja. Ako mi anketar da 45 minuta da završim, potrošit ću 15–30 minuta razmišljajući i mentalno probavljajući.
"Dajte mi šest sati da sječem drvo, a prva četiri ću provesti oštreći sjekiru." - Abraham LincolnZapravo, kodiranje mi je najmanje važan korak. Sva dizanja teških tereta već su obavljena. Sad samo moram svoj mentalni model protumačiti u kod.
Uz to, kako kodiram ovo rješenje u postavkama intervjua, neće biti isto kao i kako ga kodiram u stvarnom životu. Dovraga, stvarno rješenje za intervju izgledalo bi drugačije od odgovora koji sam smislio za ovaj članak. Nekoliko čimbenika utječe na to kako kodiram u intervjuu, poput vremena i reakcije anketara.
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.
For example, you may have noticed the use of constants, helper functions, and regex in my solution. Those are all tricks I’ve picked up that help me isolate complexity in an interview. The more my code reads like English, the less confused I get when writing it, and the faster I work. It may be a bit verbose, but I like it. Do what works for you.
If there’s already a procedure you use, practice and perfect it. Don’t wait until your onsite interview to start fine-tuning. Experiment in mock interviews. Pramp and Interviewing.io are perfect tools for that.
Remember, if all else fails, trust the process.
If this article has resonated with you, please leave some claps ? !
As always, happy coding!