Първоначално създадох това като кратък списък с теми за учене, за това как се става софтуерен инженер, но то прерасна в този огромен списък, който виждате в момента. След като преминах през този учебен план, бях нает като софтуерен инженер в Amazon! Най-вероятно няма да Ви се налага да учите колкото на мен, но все пак всичко, от което се нуждаете е тук.
Моля обърнете внимание: Няма да Ви се налага да учите колкото мен. Загубих много време, учейки неща, които няма нужда да знам. Може да прочетете повече за това надолу. Ще Ви помогна да достигнете до крайната цел без да прахосвате скъпото си време.
Темите, изредени тук, ще Ви подготвят добре за техническо интервю за почти всяка една компания, включително гигантите Amazon, Facebook, Google и Microsoft
Това е моят многомесечен план за ставане на софтуерен инженер към голяма компания.
Изисквания:
Малко опит с програмиране (променливи, цикли, методи/функции и т.н)
Търпение
Време
Обърнете внимание, че това е учебен план за софтуерно инженерство, а не за уеб разработка. Големите компании като Google, Amazon,
Facebook и Microsoft различават софтуерното инженерство и уеб разработката. Amazon, например, имат Frontend инженери (FEE)
и Software Development инженери (SDE). Това са 2 отделни позиции и интервютата за тях няма да са еднакви, тъй като всяка една от
тях има своите специфики. Тези компании изискват знания по компютърни науки за позиции свързани със софтуерно инженерство/разработка.
По принцип в университетска програма по Компютърни науки/Информатика има много неща за учене, но знаейки около 75% от това е
достатъчно добре за да се справите на интервю, това е и информацията която покривам тук.
За пълна програма по Компютърни науки за самоуки записките от моя план за учене са включени в Пътеката по Компютърни науки на Камран
Ахмед: https://roadmap.sh/computer-science
Ако искате да работите като софтуерен инженер в голяма компания, това са нещата, които трябва да знаете.
Ако също като мен не сте учили компютърни науки в университет това ще Ви помогне да наваксате и ще Ви спести години.
Когато започнах този проект не знаех какво е стек или опашка, нямах представа какво е Big-O, не знаех нищо за дървета или как да
pобхождам графи. Ако трябваше да напиша сортиращ алгоритъм мога да Ви кажа, че бих се справил ужасно. Всяка от структурите от данни,
които бях използвал досега бяха имплементирани в езика, който ползвах и нямах представа как работят реално. Никога не ми се беше
налагало да управлявам памет освен ако някой от процесите, които бях пуснал не връщаха грешка "out of memory"- тогава се налагаше
да търся заобиколен път. Бях ползвал хиляди асоциативни масиви и многоизмерни масиви няколко пъти, но никога преди не бях
имплементирал структури от данни от нулата.
Планът е дълъг. Може да Ви отнеме месеци. Ако вече сте запознати с повечето от темите ще Ви отнеме много по-малко.
Как да го ползвате
Всичко надолу е само схематично изложение и трябва да преминете през темите от горе до долу.
Аз използвам специалния маркдаун на ГитХъб, включително листове със задачи за да следвам прогреса си.
На тази страница кликнете върху бутона Code най-отгоре, а след това изберете "Download ZIP". Накрая разархивирайте файла и можете да
работите с текстовите файлове.
Ако сте отворили файловете с текстов редактор, който разбира markdown, ще видите всичко форматирано подредено и красиво.
Ако се чувствате сигурни да ползвате git
Създайте нов бранч за да може да отбелязвате елементи по този начин, като просто вкарате един х в скобите: [x]
Направете Fork на GitHub хранилището:https://github.com/jwasham/coding-interview-university като кликнете върху бутона Fork.
Клонирайте хранилището на персоналния Ви компютър:
Някои видеа са достъпни само след записване в курс на Coursera или EdX- т.нар. MOOCs. Понякога се налага да изчакате няколко месеца,
за да стартира ново издание на курса, така че няма да имате достъп до тях.
Би било чудесно такива ресурси да бъдат заменени с безплатни и свободнодостъпни публични източници като YouTube видеа (по възможност
университетски лекции), за да могат всички да учат навсякъде и по всяко време, а не само когато даден курс върви в момента.
Изберете език за програмиране
Трябва да изберете език за програмиране за интервютата на които ще се явявате, но също така трябва да изберете език, който можете да ползвате за учене на концепции от компютърните науки.
Желателно е този език да е един и същ, така ще Ви се налага да владеете само един език.
За този учебен план
Когато преминавах през учебния план ползвах 2 езика за по-голямата част от нещата: C и Python
C: Език на много ниско ниво. Дава Ви възможност да се справяте с пойнтъри и управляване на паметта, за да разберете структурите
от данни и алгоритмите на много дълбоко ниво. В езици за програмиране на по-високо ниво тези неща са скрити от Вас. В ежедневната
работа това е прекрасно, но когато се учите как тези структури от данни работят е хубаво да усещате как става всичко.
C е навсякъде. Ще виждате примери в книги, лекции, видеа навсякъде докато учите.
Това е кратка книга, но ще Ви даде добра представа за езика и с малко упражнения бързо ще имате добро владение над него. Ако разбирате C значи разбирате как програмите и паметта работят.
Не трябва да се зачитате много надълбоко в книгата (или дори да я прочитате докрай). Нужно е само да сте уверени в способността си да четете и пишете в C.
Няма нужда да купувате цял куп от тези книги. Честно казано "Cracking the Coding Interview" най-вероятно ще Ви бъде достатъчна, но аз си купих повече, за да се упражня по-добре. Но аз винаги правя прекалено много.
Купих тези двете, дадоха ми предостатъчно упражнение.
Този списък се разрасна с времето и да, нещата излязоха извън контрол.
Споделям някои от грешките, които направих, за да имате по-добро преживяване и за да си спестите месеци с време.
1. Няма да запомните всичко
Изгледах часове с клипове и водих записки за всичко, но след месеци имаше доста неща, които не си спомнях. Прекарах 3 дена преразглеждайки бележките си, за да си припомня някои неща. Не се нуждаех от всичките тези знания.
Моля, прочетете това, за да не повторите грешките миЛ
За да се справя с проблема си направих малък сайт за флаш карти, където можех да добавям 2 вида карти: общи и такива с код. Всяка карта има ралично форматиране. Направих сайта mobile-first, за да мога да ги разглеждам от телефона или таблета си, навсякъде където съм.
Забележете, че аз прекалих и имам карти, които покриват всичко от assembly language и Python Trivia до machine learning и статистика. Прекалено много е за това, което се изисква.
Бележка за флаш картите: Първия път когато видите, че знаете отговора, не я отбелязвайте като "позната". Трябва да видите същата карта и отговора няколко пъти, преди наистина да знаете отговора. Повторението ще накара мозъка Ви наистина да запамети знанието.
3. Решавайте задачи от интервюта по програмиране докато учите
ТОВА Е МНОГО ВАЖНО.
Почнете да решавате задачи от интервюта по програмиране докато учите структури от данни и алгоритми.
Трябва да прилагате това, което учите като решавате задачи иначе ще забравите. Аз направих тази грешка.
Когато сте научили някоя тема и се чувствате що годе комфортно с нея, например linked lists:
По-късно се върнете и отново решете 2-3 задачи свързани с linked lists.
Повтаряйте това с всяка нова тема, която учите.
Продължавайте да решавате задачи докато учите всичко това, а не след това.
Няма да ви наемат за знанията, които имате, а за това как ги прилагате.
Има много ресурси свързани с това надолу. Продължавайте да четете.
4. Фокусирайте се
Има много неща, които могат да отвлекат вниманието Ви и да Ви загубят ценно време. Да сте концентрирани е трудно. Пуснете си музика без текст и ще можете да се фокусирате сравнително добре.
Какво няма да намерите тук
Това са широко разпространени технологии, но не и част от учебния план:
SQL
Javascript
HTML, CSS, и други front-end технологии
Дневния план
Този курс преминава през множество от теми. Всяка от тях най-вероятно ще Ви отнеме няколко дена или дори седмица, или
повече. Зависи отграфика Ви.
Всеки ден взимайте следващата тема в списъка, изгледайте няколко клипа по тази тема и след това напишете имплементацията
на въпросната структура от данни или алгоритъм в езика за програмиране, който сте избрали за този курс.
Защо трябва да се упражнявате да решавате задачи по програмиране:
Разпознаване на проблеми и знанието кога и къде да ползвате дадена структура от данни или алгоритъм
Събиране на изискванията за задачата
Изговаряне на мислите Ви докато решавате както ще правите на интервюто
Писане на код върху дъска или лист хартия вместо на компютър
Намиране на времевата и пространствената сложност на решенията Ви (вижте Big-O надолу)
Тестване на решенията Ви
Пишете код на дъска или лист хартия вместо на компютър. Тествайте с няколко различни входни данни. След това го напишете
и тествайте на компютър.
Ако нямате дъска за писане вкъщи можете да си купите голям тефтер от магазин за арт материали. Можете просто да седите
на дивана и да се упражнявате. Това е моята "дъска за дивана". Добавих химикала към снимката за съпоставка на размера.
Ако използвате химикал бързо ще ви се поиска да можеше да триете написаното - бързо става мазало. Аз ползвам молив и гума.
Когато се упражнявате да решавате задачи по програмиране не трябва да помните решенията наизуст.
Задачи по програмиране
Не забравяйте основните книги за подготовка за интервюто по програмиране тук
Когато четете "Cracking the Coding Interview" ще срещнете главата, която разглежда тази тема. Накрая на главата има
кратък тест, който проверява дали можете да намерите сложността на различни алгоритми. Това е супер преговор и тест.
Аха: трябват Ви pointer to pointer знания:
(за да можете да подавате pointer към функция, която може да промени адреса, към който сочи pointer-a)
Тази страница служи само да схванете ptr to ptr. Не препоръчвам този стил на обхождане на списъка. Четливостта
и поддържаемостта страдат заради хитрости.
Имплементирайте със свързан списък с tail pointer:
enqueue(value) - добавя стойност на опашката
dequeue() - връща стойността и премахва най-предния елемент на опашката (front)
empty()
Имплементрайте с масив с фиксирана големина:
enqueue(value) - добавя елемента в края на наличното пространство
dequeue() - връща стойността и премахва най-предния елемент на опашката
empty()
full()
Разход:
лоша имплементация, ползвайки свързан списък където правим enqueue в началото и dequeue в края би била O(n)
защото ще се нуждаете от предпоследния елемент, което ще предизвиква цялостно обхождане при всяко dequeue
enqueue: O(1) (amortized, свъзран списък и масив [probing])
Графите могат да се ползват за онагледяване на много проблеми в компютърните науки, така че тази секция е дълга, също както тази за дърветата и сортирането..
Бележки:
Има 4 основни начина една графа да бъде представена в паметта:
обекти и пойнтъри
матрици на съседство
списъци на съседство
мап на съседство
Запознайте се с всяка от начините за представяне и плюсовете, и минусите, които предоставят
BFS и DFS - знайте изчислителната им сложност, компромисите, които носят и как да ги имплементирате в истински код
Когато Ви зададат въпрос, първо потърсете решение с граф и преминете нататък ако няма такова
Най-вероятно няма да срещнете задачи с динамично програмиране в интервютата си, но си струва да можете да разпознавате задачи, които са годни за решаване с динамично програмиране.
Тази тема може да е доста сложна защото всяка задача, която може да се решава с ДП трябва да бъде дефинирана чрез рекурсивна връзка, а понякога може да е сложно да се измисли такава.
Препоръчвам да разгледате много примери за задачи с ДП докато имате стабилно разбиране на структурата им.
Клипове:
клиповете от Skiena могат да бъдат сложни за проследяване, тъй като той понякога ползва дъската, която е прекалено малка, за да се види
Знайте за най-известните задачи за NP-завършеност като пътуващия търговец и бъдете сигурни, че можете да ги разпознавате, когато интервюиращия ви ги даде прикрити
Ресурси, от които се нуждаят процесите (памет: код, статично пространство, стек, heap, и file descriptors, i/o)
Ресурси, от които се нуждаят нишките (споделя същите като по-горе (без стек) с други нишки в същия процес, но всяка има свой pc, стек брояч, регистри и стек)
Forking is really copy on write (read-only) until the new process writes to memory, then it does a full copy.
Смяна на контекста
Как смяната на контекста се инициира от операционната система и хардуера?
Обърнете внимание, че има различни видове tries. Някои имат prefixes, а други нямат, също така някои ползват низове вместо битове за да следят пътеката
Тази секция съдържа по-кратки клипове за най-важните понятия, които можете да изгледате сравнително бързо. Полезни са ако искате да си припомните нещо от време на време.
Серия от 2-3 минутни кратки клипове по различни теми (23 клипа)
Бележка от автора: "Това се отнася към резюмета за САЩ. Към CV-тата за Индия и други държави има различни изисквания, но много от точките ще са същите."
Get hands-on practice with over 100 data structures and algorithm exercises and guidance from a dedicated mentor to help prepare you for interviews and on-the-job scenarios.
Помислете за около 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 интервю, но ако научите тези неща ще сте изложени пред повече концепции от компютърните науки и ще сте добре подготвени за всяка работа за софтуерно инженерство. Ще сте много по-добър софтуерен инженер.
*****************************************************************************************************
*****************************************************************************************************
Допълнителни книги
Книгите тук ще ви позволят да се гмурнете в теми, които са интересни за вас.
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
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.
Scalability and System Design are very large topics with many topics and resources, since
there is a lot to consider when designing a software/hardware system that can scale.
Expect to spend quite a bit of time on this
For even more, see "Mining Massive Datasets" video series in the Video Series section
Practicing the system design process: Here are some ideas to try working through on paper, each with some documentation on how it was handled in the real world:
Добавих тези теми, за да Ви помогна да бъдете по-добри софтуерни инженери и да сте наясно с определени технологии и алгоритми, което ще разшири "инструментите", с които можете да работите
Познавайте поне един вид двоични балансирани дървета(и как се имплементират):
"Among balanced search trees, AVL and 2/3 trees are now passé, and red-black trees seem to be more popular.
A particularly interesting self-organizing data structure is the splay tree, which uses rotations
to move any accessed key to the root." - Skiena
Of these, I chose to implement a splay tree. From what I've read, you won't implement a
balanced search tree in your interview. But I wanted exposure to coding one up
and let's face it, splay trees are the bee's knees. I did read a lot of red-black tree code
Splay tree: insert, search, delete functions
If you end up implementing red/black tree try just these:
Search and insertion functions, skipping delete
I want to learn more about B-Tree since it's used so widely with very large data sets
In practice:
From what I can tell, these aren't used much in practice, but I could see where they would be:
The AVL tree is another structure supporting O(log n) search, insertion, and removal. It is more rigidly
balanced than red–black trees, leading to slower insertion and removal but faster retrieval. This makes it
attractive for data structures that may be built once and loaded without reconstruction, such as language
dictionaries (or program dictionaries, such as the opcodes of an assembler or interpreter)
In practice:
Splay trees are typically used in the implementation of caches, memory allocators, routers, garbage collectors,
data compression, ropes (replacement of string used for long text strings), in Windows NT (in the virtual memory,
networking and file system code) etc
These are a translation of a 2-3 tree (see below).
In practice:
Red–black trees offer worst-case guarantees for insertion time, deletion time, and search time.
Not only does this make them valuable in time-sensitive applications such as real-time applications,
but it makes them valuable building blocks in other data structures which provide worst-case guarantees;
for example, many data structures used in computational geometry can be based on red–black trees, and
the Completely Fair Scheduler used in current Linux kernels uses red–black trees. In the version 8 of Java,
the Collection HashMap has been modified such that instead of using a LinkedList to store identical elements with poor
hashcodes, a Red-Black tree is used
In practice:
For every 2-4 tree, there are corresponding red–black trees with data elements in the same order. The insertion and deletion
operations on 2-4 trees are also equivalent to color-flipping and rotations in red–black trees. This makes 2-4 trees an
important tool for understanding the logic behind red–black trees, and this is why many introductory algorithm texts introduce
2-4 trees just before red–black trees, even though 2-4 trees are not often used in practice.
Fun fact: it's a mystery, but the B could stand for Boeing, Balanced, or Bayer (co-inventor).
In Practice:
B-Trees are widely used in databases. Most modern filesystems use B-trees (or Variants). In addition to
its use in databases, the B-tree is also used in filesystems to allow quick random access to an arbitrary
block in a particular file. The basic problem is turning the file block i address into a disk block
(or perhaps to a cylinder-head-sector) address
MIT 6.851 - Memory Hierarchy Models (video) - covers cache-oblivious B-Trees, very interesting data structures - the first 37 minutes are very technical, may be skipped (B is block size, cache line size)
Добавих тези, за да подкрепя някои от темите и материалите посочени по горе, но не исках да ги добавям там, защото са прекалено много. Лесно е да научите прекалено много по някоя тема.
Искате да Ви наемат този век, нали?