Kaya nandiyan ka. Nakahinga. Napapaso. Sa wakas ay nakagawa ka ng isang diskarte upang malutas ang nakakalito na coding na tanong ng iyong tagapanayam sa iyo. Marahil ay isinulat mo rin ito sa whiteboard, ayon sa linya. At gumawa ka ng magandang oras! 20 minuto ka lamang sa pagpupulong. Kailangang humanga ang iyong tagapanayam.
Tama ba?
"Ito ay gagana, ngunit ang anumang mga ideya para sa kung paano ito gawin nang mas mahusay?"
Ang iyong puso ay lumulubog. Akala mo tapos ka sa nakagagalit na bahagi ng disenyo ng algorithm! Sinusubukan mong mag-isip ng mas maraming mga paraan upang malutas ang problema, ngunit ang maaari mong isipin ay ang isang diskarte na naabot mo na.
Nangyayari ito sa halos lahat. At hindi ito dahil tanga sila. Ito ay dahil ang karamihan sa mga tao ay walang paraan para sa pagpapabuti ng kahusayan ng kanilang mga algorithm.
Ngunit ang totoo, maraming. Sa susunod na masaksak ka, subukang ilapat ang tatlong karaniwang pamamaraang ito.
1. Gumamit ng Hash Map
Tama iyan. Ang mga mapa ng / mga nakalarawan na mga / mga diksyonaryo ng Hash (dumadaan sila ng maraming mga pangalan, depende sa kung anong programming language ang ginagamit mo) ay may isang kahanga-hangang kakayahan upang maibagsak ang runtime ng mga algorithm.
Halimbawa, ipagpalagay na ang tanong ay upang mahanap ang pinaka-paulit-ulit na numero sa isang hanay ng mga numero.
Ang iyong unang pag-iisip ay maaaring tumalon sa ilang mga loop. Para sa bawat isa sa aming mga numero, alamin ang bilang nito at tingnan kung ito ang pinakamalaking. Paano natin makukuha ang bilang para sa bawat bilang? Loop sa pamamagitan ng array, bilangin kung gaano karaming beses na nangyayari ito! Kaya pinag-uusapan namin ang tungkol sa dalawang mga ness loops. Sa pseudocode:
def get_mode (bilang): max_count = 0 mode = null para sa potensyal namode sa mga bilang: count = 0 para sa numero sa our_array: count + = 1 kung mabilang> = max_count: mode = potensyal_mode max_count = count return mode
Sa ngayon, nag-iikot kami sa aming buong hanay ng isang beses para sa bawat item sa hanay - ngunit makakagawa kami ng mas mahusay. Sa malaking O notasyon, iyon ang O (n 2 ) oras sa kabuuan.
Kung nag-iimbak kami ng aming mga bilang sa isang mapa ng hash (mapa ng mga numero sa kanilang mga bilang), malulutas natin ang problema sa isang lakad lamang sa pamamagitan ng array (O (n) oras!):
def get_mode (bilang): max_count = 0 mode = null counts = bagong HashMap, nagsisimula ang bawat halaga sa 0 para sa potensyal na bilang sa: bilang, + = 1 kung mabibilang> max_count: mode = potential_mode max_count = count count return mode
Mas mabilis!
2. Gumamit ng Bit Manipulation
Ito ay talagang ibukod sa iyo mula sa pack. Hindi ito nalalapat sa bawat problema, ngunit kung itinatago mo ito sa iyong likod na bulsa at suso ito sa tamang oras, magmukhang rockstar ka.
Narito ang isang halimbawa: Ipagpalagay na mayroon kaming isang hanay ng mga numero, kung saan ang bawat numero ay lilitaw nang dalawang beses, maliban sa isang numero na nagaganap lamang ng isang beses. Nagsusulat kami ng isang function upang mahanap ang malungkot, hindi paulit-ulit na numero.
Ang iyong unang likas ay maaaring gumamit ng isang mapa ng hash, dahil napag-usapan lang namin ito. Iyon ay isang magandang likas na magkaroon! At gagana ito para sa isang ito. Maaari kaming gumawa ng isang katulad na mapa na "count", at gamitin iyon upang makita kung aling numero ang nagtatapos sa isang bilang ng 1.
Ngunit mayroong isang mas mahusay na paraan. Kung pamilyar ka sa kaunting pagmamanipula, maaaring pamilyar ka sa XOR. Isang bagay na espesyal tungkol sa XOR ay kung ikaw ay XOR ng isang numero sa sarili nito, ang mga bits na "kanselahin" hanggang sa 0. Para sa problemang ito, kung XOR namin ang bawat numero sa magkasama, maiiwan kami sa isang numero na nagawa hindi ko kanselahin
def find_unrepeated (nums): hindi naipalabas = 0 para sa bilang sa mga numero: hindi nabigyan ng saysay = hindi naalis na XOR num bumalik na hindi na-post
3. Pumunta sa Bottom-up
Sumulat ng isang function na naglalabas ng "nth" na numero ng Fibonacci, na binigyan ng isang numero n. Ang isang tao ay isang klasikong, at ipinagpapahiram ito ng mabuti sa pag-urong:
def fib (n): kung n ay 0 o 1: bumalik 1 return fib (n-1) + fib (n-2)
Ngunit ang simpleng sagot ay hindi lamang ang isa! Pag-isiping mabuti ang ginagawa ng pagpapaandar na ito. Ipagpalagay na ang n ay 5. Upang makuha ang sagot, recursively ito na tinatawag na fib (4) at fib (3). Ngayon, ano ang ginagawa ng tawag sa fib (4)? Tinatawag itong fib (3) at fib (2). Ngunit sinabi lang namin na mayroon kaming isang tawag sa fib (3)! Ang nakatutuwang pag-andar na ito ay gumagawa ng maraming paulit-ulit na gawain. Ang kabuuang gastos sa oras ay naging O (2 n ). Masama iyon - mas masahol pa kaysa sa O (n 2 ).
Sa halip na pumunta mula sa pabalik-balik hanggang sa 1, pumunta tayo sa "ilalim-up, " mula 1 hanggang n. Pinapayagan kaming laktawan ang recursion:
def fib (n): nakaraan = 0 nakaraang_previous = 1 para sa ako sa saklaw 1 hanggang n: kasalukuyang = naunang + naunang + naunang_nakilala = nakaraang nakaraan = kasalukuyang bumalik kasalukuyang
Mas mahaba ang code, ngunit mas mahusay! Down hanggang O (n) oras. Bilang isang idinagdag na bonus na may hindi nakokontrol na mga algorithm ng recursive, nagse-save kami ng puwang. Ang lahat ng mga tawag na recursive ay bumubuo sa tawag na stack, na nakaupo sa memorya at binibilang patungo sa gastos sa aming puwang. Ang aming pag-andar ng recursive ay nagkaroon ng O (n) na gastos sa espasyo, ngunit ang iterative na ito ay tumatagal ng O (1) espasyo.
Sa susunod na hinihiling sa iyo ng iyong tagapanayam na pagbutihin ang kahusayan ng iyong solusyon, subukang lakarin ang mga diskarte na ito at makita kung makakatulong ito. Na may sapat na kasanayan, marahil ay makikita mo ang iyong sarili na tumalon nang diretso sa na-optimize na solusyon, na nilaktawan ang mas walang muwang na solusyon. At iyon ay isang mahusay na bagay. Hindi ito nangangahulugang ikaw ay nagiging isang mas mahusay na tagapanayam - nangangahulugan ito na ikaw ay maging isang mas mahusay na inhinyero.
