Skip to content

Latest commit

 

History

History
2037 lines (1648 loc) · 170 KB

File metadata and controls

2037 lines (1648 loc) · 170 KB

Coding Interview University

Първоначално създадох това като кратък списък с теми за учене, за това как се става софтуерен инженер, но то прерасна в този огромен списък, който виждате в момента. След като преминах през този учебен план, бях нает като софтуерен инженер в Amazon! Най-вероятно няма да Ви се налага да учите колкото на мен, но все пак всичко, от което се нуждаете е тук.

Учих между 8-12 часа на ден в продължение на няколко месеца. Това е историята ми: Why I studied full-time for 8 months for a Google interview

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

Темите, изредени тук, ще Ви подготвят добре за техническо интервю за почти всяка една компания, включително гигантите Amazon, Facebook, Google и Microsoft

Пожелавам Ви успех!

Преводи:
Текущи преводи:

Какво е това?

Coding at the whiteboard - from HBO's Silicon Valley

Това е моят многомесечен план за ставане на софтуерен инженер към голяма компания.

Изисквания:

  • Малко опит с програмиране (променливи, цикли, методи/функции и т.н)
  • Търпение
  • Време

Обърнете внимание, че това е учебен план за софтуерно инженерство, а не за уеб разработка. Големите компании като Google, Amazon, Facebook и Microsoft различават софтуерното инженерство и уеб разработката. Amazon, например, имат Frontend инженери (FEE) и Software Development инженери (SDE). Това са 2 отделни позиции и интервютата за тях няма да са еднакви, тъй като всяка една от тях има своите специфики. Тези компании изискват знания по компютърни науки за позиции свързани със софтуерно инженерство/разработка.

По принцип в университетска програма по Компютърни науки/Информатика има много неща за учене, но знаейки около 75% от това е достатъчно добре за да се справите на интервю, това е и информацията която покривам тук. За пълна програма по Компютърни науки за самоуки записките от моя план за учене са включени в Пътеката по Компютърни науки на Камран Ахмед: https://roadmap.sh/computer-science


Съдържание

Учебният план

Теми за учене

Как да спечелите позицията

---------------- Всичко оттук надолу е по желание ----------------

Допълнителни теми и ресурси


Защо да го ползвате?

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

Ако също като мен не сте учили компютърни науки в университет това ще Ви помогне да наваксате и ще Ви спести години.

Когато започнах този проект не знаех какво е стек или опашка, нямах представа какво е Big-O, не знаех нищо за дървета или как да pобхождам графи. Ако трябваше да напиша сортиращ алгоритъм мога да Ви кажа, че бих се справил ужасно. Всяка от структурите от данни, които бях използвал досега бяха имплементирани в езика, който ползвах и нямах представа как работят реално. Никога не ми се беше налагало да управлявам памет освен ако някой от процесите, които бях пуснал не връщаха грешка "out of memory"- тогава се налагаше да търся заобиколен път. Бях ползвал хиляди асоциативни масиви и многоизмерни масиви няколко пъти, но никога преди не бях имплементирал структури от данни от нулата.

Планът е дълъг. Може да Ви отнеме месеци. Ако вече сте запознати с повечето от темите ще Ви отнеме много по-малко.

Как да го ползвате

Всичко надолу е само схематично изложение и трябва да преминете през темите от горе до долу.

Аз използвам специалния маркдаун на ГитХъб, включително листове със задачи за да следвам прогреса си.

Ако не желаете да използвате git

На тази страница кликнете върху бутона Code най-отгоре, а след това изберете "Download ZIP". Накрая разархивирайте файла и можете да работите с текстовите файлове.

Ако сте отворили файловете с текстов редактор, който разбира markdown, ще видите всичко форматирано подредено и красиво.

Как да изтеглим хранилище като zip файл

Ако се чувствате сигурни да ползвате git

Създайте нов бранч за да може да отбелязвате елементи по този начин, като просто вкарате един х в скобите: [x]

  1. Направете Fork на GitHub хранилището: https://github.com/jwasham/coding-interview-university като кликнете върху бутона Fork.

    Направете Fork на GitHub хранилище

  2. Клонирайте хранилището на персоналния Ви компютър:

    git clone git@github.com:<your_github_username>/coding-interview-university.git
    cd coding-interview-university
    git checkout -b progress
    git remote add jwasham https://github.com/jwasham/coding-interview-university
    git fetch --all
    
  3. Маркирайте всички кутийки с Х след като сте готови с промените си:

    git add .
    git commit -m "Marked x"
    git rebase jwasham/main
    git push --set-upstream origin progress
    git push --force
    

Не мислете, че не сте достатъчно умни

Бележка за видео ресурсите

Някои видеа са достъпни само след записване в курс на Coursera или EdX- т.нар. MOOCs. Понякога се налага да изчакате няколко месеца, за да стартира ново издание на курса, така че няма да имате достъп до тях.

Би било чудесно такива ресурси да бъдат заменени с безплатни и свободнодостъпни публични източници като YouTube видеа (по възможност университетски лекции), за да могат всички да учат навсякъде и по всяко време, а не само когато даден курс върви в момента.

Изберете език за програмиране

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

Желателно е този език да е един и същ, така ще Ви се налага да владеете само един език.

За този учебен план

Когато преминавах през учебния план ползвах 2 езика за по-голямата част от нещата: C и Python

  • C: Език на много ниско ниво. Дава Ви възможност да се справяте с пойнтъри и управляване на паметта, за да разберете структурите от данни и алгоритмите на много дълбоко ниво. В езици за програмиране на по-високо ниво тези неща са скрити от Вас. В ежедневната работа това е прекрасно, но когато се учите как тези структури от данни работят е хубаво да усещате как става всичко.
    • C е навсякъде. Ще виждате примери в книги, лекции, видеа навсякъде докато учите.
    • The C Programming Language, Vol 2
      • Това е кратка книга, но ще Ви даде добра представа за езика и с малко упражнения бързо ще имате добро владение над него. Ако разбирате C значи разбирате как програмите и паметта работят.
      • Не трябва да се зачитате много надълбоко в книгата (или дори да я прочитате докрай). Нужно е само да сте уверени в способността си да четете и пишете в C.
      • Отговори на въпросите в книгата
  • Python: модерен и много експресивен. Научих го защото е наистина много полезен и ми позволява да пиша по-малко код когато съм на интервю.

Това е моя личен избор. Вие можете да изберете каквото пожелаете, разбира се.

Може да не Ви трябват, но ето някои сайтове за учене на нов език:

За интервюто Ви по програмиране

Може да изберете език, в който се чувствате комфортно за интервюто Ви, но за големите компании това са най-добрите опции:

  • C++
  • Java
  • Python

Може да ползвате и тези, но поразгледайте преди това, защото може да има уловки:

  • JavaScript
  • Ruby

Това е статия, която написах за избирането на език за вашето интервю: Pick One Language for the Coding Interview. Това е оригиналната статия, на която базирах моя пост: http://blog.codingforinterviews.com/best-programming-language-jobs/

Трябва да се чувствате много удобно с вашия език и да сте знаещи.

Повече за вариантите:

Вижте ресурси за специфични езици тук

Книги за структури от данни и алгоритми

Тази книга ще положи вашата основа в компютърните науки.

Просто изберете една в език, с който ще се чувствате комфортно. Ще трябва да четете и да пишете код доста.

C

Python

Java

Изборът е ваш:

C++

Изборът е ваш:

Книги за подготовка за интервю

Няма нужда да купувате цял куп от тези книги. Честно казано "Cracking the Coding Interview" най-вероятно ще Ви бъде достатъчна, но аз си купих повече, за да се упражня по-добре. Но аз винаги правя прекалено много.

Купих тези двете, дадоха ми предостатъчно упражнение.

Ако имате изобилие от време:

Изберете една:

Не повтаряйте грешките ми

Този списък се разрасна с времето и да, нещата излязоха извън контрол.

Споделям някои от грешките, които направих, за да имате по-добро преживяване и за да си спестите месеци с време.

1. Няма да запомните всичко

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

Моля, прочетете това, за да не повторите грешките миЛ

Да запазваме знания свързани с компютърни науки.

2. Използвайте флаш карти

За да се справя с проблема си направих малък сайт за флаш карти, където можех да добавям 2 вида карти: общи и такива с код. Всяка карта има ралично форматиране. Направих сайта mobile-first, за да мога да ги разглеждам от телефона или таблета си, навсякъде където съм.

Направете свои безплатно:

НЕ ПРЕПОРЪЧВАМ да ползвате моите флаш карти. Има прекалено много и някои от тях съдържат информация, която не е нужно да знаете.

Но ако не искате да ме послушате, ето:

Забележете, че аз прекалих и имам карти, които покриват всичко от assembly language и Python Trivia до machine learning и статистика. Прекалено много е за това, което се изисква.

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

3. Решавайте задачи от интервюта по програмиране докато учите

ТОВА Е МНОГО ВАЖНО.

Почнете да решавате задачи от интервюта по програмиране докато учите структури от данни и алгоритми.

Трябва да прилагате това, което учите като решавате задачи иначе ще забравите. Аз направих тази грешка.

Когато сте научили някоя тема и се чувствате що годе комфортно с нея, например linked lists:

  1. Отворете една от книгите за интервю за програмиране (или един от сайтовете със задачи, изредени по-долу)
  2. Решете 2-3 задачи свързани с linked lists.
  3. Продължете към следващата тема.
  4. По-късно се върнете и отново решете 2-3 задачи свързани с linked lists.
  5. Повтаряйте това с всяка нова тема, която учите.

Продължавайте да решавате задачи докато учите всичко това, а не след това.

Няма да ви наемат за знанията, които имате, а за това как ги прилагате.

Има много ресурси свързани с това надолу. Продължавайте да четете.

4. Фокусирайте се

Има много неща, които могат да отвлекат вниманието Ви и да Ви загубят ценно време. Да сте концентрирани е трудно. Пуснете си музика без текст и ще можете да се фокусирате сравнително добре.

Какво няма да намерите тук

Това са широко разпространени технологии, но не и част от учебния план:

  • SQL
  • Javascript
  • HTML, CSS, и други front-end технологии

Дневния план

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

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

Можете да видите моя код тук:

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

Подготовка за въпроси за програмиране

Защо това е тук? Аз не съм готов да се явя на интервю.

Тогава се върни и прочети това.

Защо трябва да се упражнявате да решавате задачи по програмиране:

  • Разпознаване на проблеми и знанието кога и къде да ползвате дадена структура от данни или алгоритъм
  • Събиране на изискванията за задачата
  • Изговаряне на мислите Ви докато решавате както ще правите на интервюто
  • Писане на код върху дъска или лист хартия вместо на компютър
  • Намиране на времевата и пространствената сложност на решенията Ви (вижте Big-O надолу)
  • Тестване на решенията Ви

Пишете код на дъска или лист хартия вместо на компютър. Тествайте с няколко различни входни данни. След това го напишете и тествайте на компютър.

Ако нямате дъска за писане вкъщи можете да си купите голям тефтер от магазин за арт материали. Можете просто да седите на дивана и да се упражнявате. Това е моята "дъска за дивана". Добавих химикала към снимката за съпоставка на размера. Ако използвате химикал бързо ще ви се поиска да можеше да триете написаното - бързо става мазало. Аз ползвам молив и гума.

моята дъска за дивана

Когато се упражнявате да решавате задачи по програмиране не трябва да помните решенията наизуст.

Задачи по програмиране

Не забравяйте основните книги за подготовка за интервюто по програмиране тук

Решаване на задачи:

Клипове за задачи от интервюта по програмиране:

Сайтове със задачи:

  • LeetCode
    • Любимият ми сайт със задачи. Струва си парите за абонамент за времето, в което ще се подготвяте.
    • Вижте клиповете на Nick White и FisherCoder Videos по-горе за насоки с някои задачи.
  • HackerRank
  • TopCoder
  • Geeks for Geeks
  • InterviewBit
  • Project Euler

Да започваме

Добре, стига сме говорили, нека да учим!

Но не забравяйте да решавате задачи от източниците по-горе докато учите!

Алгоритмична сложност / Big-O / Асимптотичен анализ

Е, това е достатъчно за тази тема.

Когато четете "Cracking the Coding Interview" ще срещнете главата, която разглежда тази тема. Накрая на главата има кратък тест, който проверява дали можете да намерите сложността на различни алгоритми. Това е супер преговор и тест.

Структури от данни

  • Масиви

    • За масивите:
    • Имплементирайте вектор (променлив масив с автоматично преоразмеряване):
      • Упражнявайте се да пишете код, ползвайки масиви и пойнтъри. Ползвайте пойнтъри за преместване към индекс вместо индексиране
      • New raw data array with allocated memory
        • can allocate int array under the hood, just not use its features
        • start with 16, or if starting number is greater, use power of 2 - 16, 32, 64, 128
      • size() - номер на елементите
      • capacity() - номер на елементите, които може да побира
      • is_empty()
      • at(index) - връща елемента на дадения индекс, ако индекса е извън границите на масива връща грешка
      • push(item)
      • insert(index, item) - вкарва елемента на дадения елемент, измествайки съществуващия елемент на този индекс и всички елементи след него надясно
      • prepend(item) - може да добавя елементи на индекс 0
      • pop() - премахва елемент от края и връща стойността му
      • delete(index) - изтрива елемента на дадения индекс и измества всички елементи след него наляво
      • remove(item) - търси стойността на елемента и премахва всички индекси, които я съдържат
      • find(item) - търси стойността на елемента и връща първия индекс, който я съдържа, или -1 ако няма такъв елемент
      • resize(new_capacity) // private function
        • когато достигнете максималния обем, преоразмерете като дублирате обема
        • когато pop-вате елемент, ако обема на масива е 1/4 от капацитета му, преоразмерете масива наполовина
      • Време
        • O(1) за добавяне/премахване към края, индексиране или актуализиране
        • O(n) за добавяне/премахване другаде
      • Пространство
        • contiguous in memory, so proximity helps performance
        • нужно място = (капацитета на масива, който е >= n) * размера на елемента, но дори 2n, пак е O(n)
  • Свързани списъци

    • Описание:
    • Код в C (клип) - не цялото видео, само частите за Node structs и алокация на памет
    • Свързани списъци срещу масиви:
      • Core Linked Lists Vs Arrays (клип)
      • Свързани списъци срещу масиви в истинския свят (клип)
      • Защо да избягваме свързаните списъци (клип)
      • Аха: трябват Ви pointer to pointer знания: (за да можете да подавате pointer към функция, която може да промени адреса, към който сочи pointer-a) Тази страница служи само да схванете ptr to ptr. Не препоръчвам този стил на обхождане на списъка. Четливостта и поддържаемостта страдат заради хитрости.
      • Имплементация:
        • size() - връща броя на елементите
        • empty() - булева стойност, връща true ако списъка е празен
        • value_at(index) - връща стойността на n-тия елемент (почвайки от 0 за първия елемент)
        • push_front(value) - добавя стойност към началото на списъка
        • pop_front() - премахва първия елемент и връща стойността му
        • push_back(value) - добавя елемент към края
        • pop_back() - премахва последния елемент и връща стойността му
        • front() - взима стойността на първия елемент
        • back() - взима стойността на последния елемент
        • insert(index, value) - вкарва елемента на дадения индекс, така че новия елемент да сочи към стария елемент на този индекс
        • erase(index) - изтрива node-а на дадения индекс
        • value_n_from_end(n) - връща стойността на node-а, седящ на позиция n от края на списъка
        • reverse() - обръща списъка
        • remove_value(value) - премахва първия елемент от списъка, съдържащ тази стойност
      • Двойно свързан списък
  • Стек

  • Опашка

    • Опашка (клип)
    • Circular buffer/FIFO
    • [Review] Queues in 3 minutes (video)
    • Имплементирайте със свързан списък с tail pointer:
      • enqueue(value) - добавя стойност на опашката
      • dequeue() - връща стойността и премахва най-предния елемент на опашката (front)
      • empty()
    • Имплементрайте с масив с фиксирана големина:
      • enqueue(value) - добавя елемента в края на наличното пространство
      • dequeue() - връща стойността и премахва най-предния елемент на опашката
      • empty()
      • full()
    • Разход:
      • лоша имплементация, ползвайки свързан списък където правим enqueue в началото и dequeue в края би била O(n) защото ще се нуждаете от предпоследния елемент, което ще предизвиква цялостно обхождане при всяко dequeue
      • enqueue: O(1) (amortized, свъзран списък и масив [probing])
      • dequeue: O(1) (свъзран списък и масив)
      • empty: O(1) (свъзран списък и масив)
  • Хеш таблици

Повече знания

Дървета

Сортиране

Като обобщение, това е визуализация на 15 алгоритъма за сортиране. Ако ви трябват повече детайли на тази тема вижте секцията "Сортиране" вДопълнителни детайли по някои теми

Графи

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

Още повече знания


Последен преглед

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

Актуализирайте резюмето си

Намерете позиция

Процесът на интервюто & обща подготовка

Mock интервюта:

Мислете за това, когато дойде интервюто

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

  • Защо искате тази работа?

  • Дайте пример за труден проблем, който сте разрешили.

  • Кое е най-голямото предизвикателство, с което сте се сблъсквали?

  • Best/worst designs seen?

  • Дайте идея за подобрение на съществуващ продукт.

  • Как работите най ефективно- самостоятелно или като част от екип?

  • Кои от уменията Ви ще са важни активи в позицията и защо?

  • Какво най-много Ви хареса на [работа x / проейт y]?

  • Какво беше най-голямото предизвикателство, с което се сблъскахте на [работа x / проект y]?

  • Кой е най-трудния bug, с който сте се сблъсквали на [работа x / проект y]?

  • Какво научихте на [работа x / проект y]?

  • Какво можехте да направите по-добре на [работа x / проект y]?

  • Ако Ви се струва трудно да давате отговор на подобни въпроси, ето някои идеи:

Подгответе въпроси за интервюиращия

Ето някои от моите (може вече да знам отговорът им когато ги задавам, но искам да чуя тяхното мнение и да видя перспективата им):

  • Колко е голям екипът Ви?
  • What does your dev cycle look like? Ползвате ли waterfall/sprints/agile методологии?
  • Често ли се случва да гоните срокове? Или има гъвкавост?
  • Как вземате решения във вашия екип?
  • Колко срещи имате на седмица?
  • Как работната среда Ви помага да се концентрирате, според Вас?
  • Върху какво работите в момента?
  • Какво Ви харесва за него?
  • Как е работният Ви живот?
  • Как е балансът Ви работа/свободно време?

След като са Ви наели

Поздравления!

Продължавайте да учите.

Никога не сте свършили наистина.


*****************************************************************************************************
*****************************************************************************************************

Всичко оттук надолу е по желание. НЕ е нужно за entry-level интервю, но ако научите тези неща ще сте изложени пред повече концепции от компютърните науки и ще сте добре подготвени за всяка работа за софтуерно инженерство. Ще сте много по-добър софтуерен инженер.

*****************************************************************************************************
*****************************************************************************************************

Допълнителни книги

Книгите тук ще ви позволят да се гмурнете в теми, които са интересни за вас.
  • The Unix Programming Environment
    • An oldie but a goodie
  • The Linux Command Line: A Complete Introduction
    • A modern option
  • TCP/IP Illustrated Series
  • Head First Design Patterns
    • A gentle introduction to design patterns
  • Design Patterns: Elements of Reusable Object-Oriente​d Software
    • AKA the "Gang Of Four" book, or GOF
    • The canonical design patterns book
  • Algorithm Design Manual (Skiena)
    • As a review and problem recognition
    • The algorithm catalog portion is well beyond the scope of difficulty you'll get in an interview
    • This book has 2 parts:
      • Class textbook on data structures and algorithms
        • Pros:
          • Is a good review as any algorithms textbook would be
          • Nice stories from his experiences solving problems in industry and academia
          • Code examples in C
        • Cons:
          • Can be as dense or impenetrable as CLRS, and in some cases, CLRS may be a better alternative for some subjects
          • Chapters 7, 8, 9 can be painful to try to follow, as some items are not explained well or require more brain than I have
          • Don't get me wrong: I like Skiena, his teaching style, and mannerisms, but I may not be Stony Brook material
      • Algorithm catalog:
        • This is the real reason you buy this book.
        • This book is better as an algorithm reference, and not something you read cover to cover.
    • Can rent it on Kindle
    • Answers:
    • Errata
  • Write Great Code: Volume 1: Understanding the Machine
    • The book was published in 2004, and is somewhat outdated, but it's a terrific resource for understanding a computer in brief
    • The author invented HLA, so take mentions and examples in HLA with a grain of salt. Not widely used, but decent examples of what assembly looks like
    • These chapters are worth the read to give you a nice foundation:
      • Chapter 2 - Numeric Representation
      • Chapter 3 - Binary Arithmetic and Bit Operations
      • Chapter 4 - Floating-Point Representation
      • Chapter 5 - Character Representation
      • Chapter 6 - Memory Organization and Access
      • Chapter 7 - Composite Data Types and Memory Objects
      • Chapter 9 - CPU Architecture
      • Chapter 10 - Instruction Set Architecture
      • Chapter 11 - Memory Architecture and Organization
  • Introduction to Algorithms
    • Important: Reading this book will only have limited value. This book is a great review of algorithms and data structures, but won't teach you how to write good code. You have to be able to code a decent solution efficiently
    • AKA CLR, sometimes CLRS, because Stein was late to the game
  • Computer Architecture, Sixth Edition: A Quantitative Approach
    • For a richer, more up-to-date (2017), but longer treatment

System Design, Scalability, Data Handling

You can expect system design questions if you have 4+ years of experience.

Допънителни теми за учене

Добавих тези теми, за да Ви помогна да бъдете по-добри софтуерни инженери и да сте наясно с определени технологии и алгоритми, което ще разшири "инструментите", с които можете да работите

Допълнителни детайли по някои теми

Добавих тези, за да подкрепя някои от темите и материалите посочени по горе, но не исках да ги добавям там, защото са прекалено много. Лесно е да научите прекалено много по някоя тема. Искате да Ви наемат този век, нали?

Видео серии

Настанете се удобно и се наслаждавайте.

Курсове по компютърни науки

Имплементация на алгоритми

Статии и други ресурси

Лиценз

CC-BY-SA-4.0