Så där är du. Lättad. Utmattad. Du har äntligen kommit med en metod för att lösa den svåra kodningsfrågan som din intervjuare ställer dig. Du kanske till och med skrev det upp på whiteboardtavlan, rad för rad. Och du fick god tid! Du är bara 20 minuter in i mötet. Din intervjuare måste bli imponerad.
Höger?
"Det här fungerar, men några idéer för hur man gör det mer effektivt?"
Ditt hjärta sjunker. Du trodde att du var klar med den knepiga algoritmdesigndelen! Du försöker tänka på fler sätt att lösa problemet, men allt du kan tänka på är den strategi du redan har kommit fram till.
Detta händer med nästan alla. Och det är inte för att de är dumma. Det beror på att de flesta inte har någon metod för att förbättra effektiviteten i sina algoritmer.
Men sanningen är att det finns gott om. Nästa gång du är stubbad kan du försöka använda dessa tre vanliga metoder.
1. Använd en Hash-karta
Det är rätt. Hash-kartor / associerande matriser / ordböcker (de har många namn, beroende på vilket programmeringsspråk du använder) har en magisk förmåga att minska körtiden för algoritmer.
Anta till exempel att frågan var att hitta det mest upprepade siffran i en rad siffror.
Din första tanke kan vara att hoppa in i några öglor. För vart och ett av våra nummer, räkna ut antalet och se om det är det största. Hur får vi räkningen för varje nummer? Gå igenom matrisen och räkna hur många gånger det inträffar! Så vi pratar om två kapslade öglor. I pseudokod:
def get_mode (nums): max_count = 0 mode = null for potential_mode in nums: count = 0 for number in our_array: count + = 1 if count> = max_count: mode = potential_mode max_count = count count mode
Just nu släpper vi igenom hela matrisen en gång för varje artikel i matrisen - men vi kan göra bättre. I stor O-notation är det totalt O (n 2 ) -tid.
Om vi lagrar våra räkningar på en haschkarta (kartlägger nummer till deras antal), kan vi lösa problemet på bara en promenad genom array-tiden (O (n) -tid!):
def get_mode (nums): max_count = 0 mode = null count = new HashMap, startar varje värde på 0 för potential_mode i nums: räknar + = 1 om count> max_count: mode = potential_mode max_count = räknar returläge
Mycket snabbare!
2. Använd bitmanipulation
Detta skiljer dig verkligen från förpackningen. Det gäller inte alla problem, men om du håller detta i rygfickan och slår ut det vid rätt tidpunkt ser du ut som en rockstjärna.
Här är ett exempel: Anta att vi hade en mängd siffror, där varje nummer visas två gånger, med undantag för ett nummer som bara inträffar en gång. Vi skriver en funktion för att hitta det ensamma, icke upprepade numret.
Din första instinkt kan vara att använda en hashkarta, eftersom vi bara pratade om den. Det är en bra instinkt att ha! Och det fungerar för den här. Vi kan göra en mycket likadan "räknar" -karta och använda den för att se vilket nummer som slutar med ett räkning på 1.
Men det finns ett ännu bättre sätt. Om du är bekant med bitmanipulering kanske du känner till XOR. En sak som är speciell med XOR är att om du XOR ett nummer med sig själv, bitarna "avbryta" till 0. För detta problem, om vi XOR varje nummer i matrisen tillsammans, kommer vi att sitta kvar med det nummer som inte gjorde avbryter inte:
def find_unrepeated (nums): unrepeated = 0 for num in nums: unrepeated = unrepeated XOR num return unrepeated
3. Gå nerifrån och upp
Skriv en funktion som matar ut det "nionde" Fibonacci-numret, med ett nummer n. Den här är en klassiker, och den lämpar sig mycket snäll till rekursion:
def fib (n): om n är 0 eller 1: return 1 return fib (n-1) + fib (n-2)
Men det enkla rekursiva svaret är inte det enda! Tänk noga över vad den här funktionen gör. Anta att n är 5. För att få svaret kallar det rekursivt fib (4) och fib (3). Vad gör det då för att kalla fib (4)? Den kallar fib (3) och fib (2). Men vi sa just att vi redan hade ett samtal till fib (3)! Denna söta rekursiva funktion gör mycket upprepande arbete. Den totala tidskostnaden visar sig vara O (2 n ). Det är dåligt - mycket värre än O (n 2 ).
I stället för att gå från n rekursivt till 1, låt oss gå "nerifrån och upp", från 1 till n. Detta låter oss hoppa över rekursionen:
def fib (n): föregående = 0 föregående_previous = 1 för i i området 1 till n: ström = föregående + föregående_previous föregående_previous = föregående föregående = nuvarande returström
Koden är längre, men den är mycket effektivare! Ned till O (n) tid. Som en extra bonus med rullande rekursiva algoritmer sparar vi utrymme. Alla dessa rekursiva samtal byggs upp i samtalstacken, som sitter i minnet och räknar mot våra rymdkostnader. Vår rekursiva funktion hade en O (n) rymdkostnad, men den iterativa tar O (1) utrymme.
Nästa gång din intervjuare ber dig förbättra effektiviteten i din lösning, prova att gå igenom dessa strategier och se om de hjälper. Med tillräckligt med övning kommer du förmodligen att hitta dig hoppa direkt till den optimerade lösningen och hoppa över den mer naiva lösningen. Och det är en fantastisk sak. Det betyder inte bara att du blir en bättre intervjuare - det betyder att du blir en bättre ingenjör.
