Class Author: Giovanni Pascotto Bonin
-
I am more than willing, and would be happy to mentor anyone - who is highly motivated - in any stage and give advice based on my experiences. I am also just in the start of my career, but I've had to overcome all kinds of obstacles and there is plenty of advice I can give for people looking for jobs in the Bay Area. Feel free to email me: [email protected]
-
I decided to create this class to teach while I am the president of IEEE at the University of Miami to supplement the school's curriculum, open doors for students to engage in discussions and interactions on the subject, as well as create a foundational framework for our organization on campus for future semesters.
-
If someone else decides to run something similar to this on their campus, I am also running guest speakers (in addition to each of these sessions), and that's a really good way to engage professional experience in your organization, as well as have experienced engineers potentially help you with the program.
- There are many other sources I have used to create this guide and I am very thankful for all the people that have put them together. I have heavily used resources and structure from @jwasham's Google Interview University guide.
I was initially going to use a Slack channel for this, but then I realized that most people don't have their Slack account open all the time, and realistically most won't download the app and have notifications on. So we will be using the IEEE Facebook group chat, to take advantage of the sad fact that people are on Facebook all the time and thus will receive the notifications. Send me an email or let me know in class that you want to be added to the group. We will also send announcements on orgsync, so if you don't have fb it's ok.
- Week 0
- Announcement
- Tech Talk
- Week 1
- About Silicon Valley, Google, Facebook, and Startups - Motivation
- Interview Process & General Interview Prep
- Emacs and vi(m)
- Unix and Command Line Tools
- Week 2
- Algorithmic complexity / Big-O / Asymptotic analysis
- An Overview of Data Structures and Algorithms
- Week 3 2. Basic Algorithms: Binary Search and Sorting 3. Recursion
- Week 4
- Machine Learning - Supervised Learning
- Machine Learning - Unsupervised Learning
- Week 5
- Heaps and Balanced Trees
- Dynamic Programming
- Week 6 1 & 2: Graphs and Search
- Week 7
- Knapsack problem and More Dynamic Programming
- Shortest Paths Revisited, NP-Complete Problems and What To Do About Them
- Week 8
- Bitwise operations, Discrete Mathematics, and NP Completeness and Computability
- Caches, Processes and Threads, and other topics
- Week 9
- Testing and System Design
- Putting it all together and Review
- Week 10
- Practice
First meeting and announcement:
Here the plan is to announce the program to the general body meeting, get input from the students on final things they might be interested in learning on top of the program, as well as finding out times that will work for most people.
Guest Speaker (CEO of Kairos Analytics): Feb 23rd 6:30 pm at MEA 202
Before anything else:
- Few people would reference professional athletes when talking about software engineering tips, but by having an attitude toward your career similar to that of an athlete toward his, there is a lot I've learned. One of my favorite athletes, Muhammad Ali, was asked how many sit-ups he would do and his reply was: "I don't count my sit-ups, I only count when it starts hurting, because that's when it really counts."
There is nothing like working your hardest in the road to achieving your dreams. This lecture series is just a compilation of advice both from various amazing people I have met, and some I observed on my own. I am passing this advice along, but keep in mind the only way for you to be able to solve new problems is to develop the foundation through discovery yourself. Practicing to solve these problems on your own is the only way to create those neural pathways.
I actually learned a lot about learning in this Coursera class I took in my last semester in college:
To practice, get one of the recommended books with a list of exercises and hammer through it! Do all these problems, do one per day, or do two, or three, depending on how much time you have. There's no excuse to not do at least one of them a day until you feel comfortable enough to go to an interview feeling that you will make it.
Success leads to confidence (conversely from what people believe), so the more you successfully solve problems the more confident you will be. Start small, build your skills, and you will make it. It's hard to properly emphasize just how helpful these books are.
- Programming Interviews Exposed: Secrets to Landing Your Next Job, 2nd Edition
- Cracking the Coding Interview, 6th Edition
- Elements of Programming Interviews
This program will help you understand computer systems, algorithm efficiency, data structure performance, low-level languages, and how it all works together. These subjects are extremely important, and the hiring process for Google (and Silicon Valley companies in general) places a huge importance on them. There is no shortage of studying, the more you know about these subjects, the better.
Before I started college I started learning computer science on my own, although I'd wish I had started even earlier given I was already 17. But due to some obstacles in my career choices I didn't dive in until that point, but when I did I committed as if I was born to do this. Before college, I had a gap year. During that period, when I found websites such as Coursera, MIT OpenCourseware, and a multitude of other content on the internet such as free textbooks and all that, I realized there is nothing short of motivation that can stop any of us from becoming one of the best at any field we want to excel in.
When I started college, I realized that I could actually learn better on my own than I could learn in class, so if that's the case for you, embrace it and pursue your passion in the way you know works best. The goal of this is to be a list of resources that can be followed and give you a good coverage on what's important, specifically filling in the gaps left by a typical computer science or software engineering curriculum. It turned out for me that by the end of my college career I wanted to work for a startup, as that way I can have a bigger impact in something that is in its early stages and really needs to be pushed forward. These experiences with learning told me to go work for a startup fixing education with technology.
This is a long plan, and some interviewers will even tell you that some of this stuff is more advanced than you need. In fact, I found this guide after accepting my full-time offer with my favorite startup in the world (Coursera), and I am going through it now (for fun) since practice is never too much, and some of this stuff I haven't had time to cover before, but it is well worth it to be good at what we do.
So yes, it might be true that some of these things don't often show up in an interview. But that's until it does, and you start thinking to yourself DAMN this is my favorite company, I should really have spent that weekend learning about this, now I have to wait a year to reapply.
This is not the SAT or MCAT. The reason why software companies want us to know these subjects is because it is important for our jobs, and the more we know about it the more we can build, the faster we can create, and innovate. Although you might not be designing algorithms on a daily basis as a software engineer (although some engineers do exactly that), becoming good at this will develop the right way of thinking that you need to solve problems of all sorts in systematic and efficient ways.
I remodeled the guide as a curriculum to be conducted on a weekly basis, as well as adding a lot to it. Again, it's a work in progress that I am doing in my free time, and I plan on properly breaking down the outline so that it evenly fits across weeks. We will try to meet twice a week and have extra content for the ambitious who want to do more at home, but the idea is that during the sessions we will cover one or two pieces of content for each subject and have extra to be done at home.
For those wanting to track their progress at home, just fork the repo and mark an [x] on the items you have done, commit and push it.
Instructions: not familiar with git yet? No worries http://rogerdudler.github.io/git-guide/ Or, if you are a University of Miami student, you have a free subcription to Lynda.com and you can take this quick start Git and GitHub course: https://www.lynda.com/Git-tutorials/Up-Running-Git-GitHub/409275-2.html
-
People put too much emphasis on IQ as opposed to emotional intelligence. After a certain level of IQ what really matters is dedication, passion, and good discipline toward your work. Most of the famous genius engineers that we all know and heard of struggled with these topics too at one point, but with the right discipline and passion they became really good at it by sticking to it. So never be discouraged!
-
Check the home assigned readings and videos for "The Myth of the Genius Programmer"
Inspiration for these technical challenges we will tackle:
- The Evolution of Search (video)
- How Search Works - Matt Cutts (video)
- How Google makes improvements to its search algorithm (video)
- How to Work at Google: Prepare for an Engineering Interview (video)
- How to Work at Google - Candidate Coaching Session (video)
- Google Recruiters Share Technical Interview Tips (video)
- How to Work at Google: Tech Resume Preparation (video)
- Code2040: a wonderful fellowship program for Latinos and African-American students who want to work in Silicon Valley. It made a huge impact in my career by exposing me to the industry, and I spent a whole summer meeting extremely talented people working in companies across Silicon Valley who are also motivated to fix the world's greatest problems: www.code2040.org
- Google: Seriously, use it. If you have a question, instead of beating your head against the wall, just Google it, unless you are doing an exercise and you are not supposed to Google the answer. But no one is supposed to know what a Turing Machine is without first learning it. So if you feel discouraged, just remember that it's never too late to pick up on something. There are so many resources out there for free.
- Coursera (www.coursera.org): With the above in mind, Coursera made a huge impact in my career. When I realized I could learn anything I wanted from the best professors in the world, and for free. And that if I wanted to impress recruiters I could also get a certificate from Stanford. It really pays off to show you are investing in your skills. Disclaimer: the favorite startup in the world I mentioned I will be joining is Coursera, but that's the reason why I will be joining them, because it made a huge impact in my life. www.coursera.org
- Pramp: I used this a couple times, it's a cool platform where you can schedule mock interviews with strangers
Reading at home:
- A list of resources that was created by Google: Google Careers: Technical Development Guide
- Cassidoo's getting a gig guide https://github.com/cassidoo/getting-a-gig
- Conference, you should definitely watch this Made by Google announcement - Oct 2016 (video)
- How Search Works - the story
- Phone Screen Questions
- How Search Works
- Get That Job at Google
- How Google Search Dealt With Mobile
- Google's Secret Study To Find Out Our Needs
- Google Search Will Be Your Next Brain
- The Deep Mind Of Demis Hassabis
- The myth of the Genius Programmer](https://www.youtube.com/watch?v=0SARbwvhupQ)
[ ] Start reading 20 minutes a day (or whatever fits your learning style/routine): Book: How Google Works
Talk points:
- Be confident, but not arrogant
If running out of time and need shortcuts, explain how you would not do the shortcut in a real scenario
-
If they give you a hint, take it, don't be cocky
-
Discuss last session's coverage, and home readings. Very encouraged for students to share their insights with each other and motivations (20 minutes of discussion)
-
Cracking the Coding Interview with Author Gayle Laakmann McDowell (video)
-
'How to Get a Job at the Big 4 - Amazon, Facebook, Google & Microsoft' (video)
Reading at home:
- ABC: Always Be Coding
- Four Steps To Google Without A Degree
- Whiteboarding
- How Google Thinks About Hiring, Management And Culture
- Effective Whiteboarding during Programming Interviews
- Failing at Google Interviews
- [_] http://www.byte-by-byte.com/choose-the-right-language-for-your-coding-interview/
- http://blog.codingforinterviews.com/best-programming-language-jobs/
- https://www.quora.com/What-is-the-best-language-to-program-in-for-an-in-person-Google-interview See language resources here
1: You can use a language you are comfortable in to do the coding part of the interview, but for Google, these are solid choices:
- C++
- Java
- Python
You need to be very comfortable in the language, and be knowledgeable, so pick one, and do all the practice problems in that language. The more you practice the more natural it will look like you feel at developing with the language, and that's important even though knowing the syntax itself isn't. But there is a subconscious feeling we get by looking at the flow of someone working with something, and it's important to give interviewers that feeling
- You won't remember it all
Use methods that will improve your memory for leaning, like spaced repetition, diffusive and focus modes of thinking, and etc (the learning how to learn course on Coursera was the most helpful resource on learning I used, but I continue to learn about this). But here's some basics stuff for you to get started:
I personally don't use flash cards because I just scan my notes and upload to Drive so they are always accessible from my phone.
- Review, review, review
Again, though interviewers say they don't care about you memorizing details, they do want to see that you're really good at what you do, so if you easily recall the details, you will look much better.
- Focus
One of my struggles was trying to do too much at the same time. I not only wanted to get a job at my favorite companies, despite not going to a school where those companies would recruit, I also wanted to take a bunch of online classes on things that wouldn't help me with the interview or school, but would benefit my personal learning goals and career (such as machine learning and even stuff like philosophy and history and business). It is indeed possible to be good at all these things, but you can't do them all at once. ****Forget multi-tasking. ***** just schedule time in your calendar and focus on one thing at each time. If you can dedicate 2 hours of focused time to this guide every day, you will go a long way.
- Studying strategy:
For each subject covered, read and watch the content covering it, and then implement it. Please, don't skip the implementation part, this is the most important one. Do not look at AVL trees and think "Oh we covered that in my algorithms class", the interviewer will never care what your class covered, he or she will ask you to implement it.
Also, write tests to make sure the code works. Most interviewers also ask you to do that. (Or at least run through test cases, but run them on paper, not simply by plugging the input in, because on the whiteboard they want to see if you can think through the code you just wrote.
So basically the process is:
- understand an algorithm or subject
- implement it on paper (preferably whiteboard while talking through it as an interview)
- test it by running through examples by hand and thinking through it
- Implement on a computer and test with real inputs
Note: you should use standard libraries of python when practicing. Unless, for example, the question is sorting an array, then you should ask the interviewer whether he expects you to use the standard library or implement it yourself. When in doubt, always ask for clarification! Don't make assumptions, and don't be afraid to ask questions, it's a good thing.
The right answer is: the one that makes you the best. Period. Every artist and craftsman has the tools that make them the best as they can be. If that's Vim (which is for me) or Emacs, or Eclipse it's up to you. But try new stuff out. Check out some stuff about vim and emacs and you will understand how many different useful things editors can do beyond the basics:
-
You should be so comfortable (afte preparing and going through this) with algorithm complexity and Big-O notation that it is a natural process for you.
-
You should be able to look at algorithms and spit out what the algorithm complexity is, and as the name might suggest otherwise, it is not complex at all. In fact it is a method for quickly managing complexity while getting a good evaluation on how the algorithm will run for large-scale applications.
-
Imagine if you could do math, and simply get rid of all constants and lower order terms, and just say how the given function grows as the input grows, this is basically it.
Home reading
- Cheat sheet
- Big O Notation (and Omega and Theta) - best mathematical explanation (video)
- Skiena: video
- Orders of Growth (video)
- Asymptotics (video)
- A Gentle Introduction to Algorithm Complexity Analysis
- UC Berkeley Big O (video)
- UC Berkeley Big Omega (video)
- Amortized Analysis (video)
-
Here I will give a lecture on how data structures and algorithms relate to Big-O, why choosing the appropriate data structures and algorithms
-
can have a significant impact on asymptoptic complexity (Big-O). Furthermore I will make a clear distinction between algorithms and data structures,
-
and show that at the same time they work together, and that efficient algorithms make use of efficient data structures to boost performance.
-
I will focus on the big picture, giving an overview of popular and extremely useful data structures and algorithms, and in the future sessions we will dive into understanding the list of algorithms and data structures that students are expected to know.
- A data structure is exactly what it sounds like: a structure in a computer used to store and organize data in a form that will be useful. - As you begin to think about them, you can draw on a paper to come up with a picture of how the data is organized. When doing this, don't worry about the lower levels of how computer might handle memory, or physically store it, just worry about how the data is organized. For example: an array is a data structure, and you could represent it as [3, 2, 3, 4, 5], or (4, 5, 1, 2), it doesn't matter. As you progress in computer science, you will learn that we use notations such as [] to represent data structure of certain behaviors and () for another, but when the notation is introduced then you learn about it. - We have data structures in the real world, a bookshelf is a data structure, except that the data are books. A line in front of your favorite Disney ride is a queue, where the data is people. Queues are useful to preserve the order in which the elements arrived, in computing that's a very useful concept, for many systems, ranging from simple design of systems where users might be placed on a queue to chat with an agent, or even search algorithms which we will cover later, such as breadth-first search.
- So why do we need anything beyond arrays? Well, if you simply want to access or update an element in the array, they are very efficient for the job and it takes constant time to do so. But imagine if you wanted to insert an element in the beginning of the array. It would take O(n) operations to do so, since we have to shift all the elements to the end by one. Video
- Arrays (video)
- If we use a list however, which is a series of items (call them nodes) connected by links, all we have to do is make the new element point to the first element of the array. If we want to insert elsewhere, it's similar, we just need to get the preceeding element and have its link point to the new element, and have the new element point to the one after the original element. And it follows that this takes O(1), whereas retrieving the Nth element takes O(N)
Video:
- Singly Linked Lists (video)
- Core Linked Lists Vs Arrays (video)
- In The Real World Linked Lists Vs Arrays (video)
-
We use queues in our daily lives everywhere, in front of lines in our rollercoaster rides, medical systems, banking, finance, everywhere. And they come in all sorts of forms. The most basic takes only time in consideration, namely the first elements will be the first to be attended.
- But there are also variations, such as priority queues, which take into consideration a series of factors. For example, in medical organ donation, we might consider the risk of death and urgency for the patient to receive a transplant (very complex system with some simplifications here, and in fact could be optimized with software).
- The same applies to computer science, where these queues are useful for designing these systems as well as supporting algorithms such as breadth-first search, and priority queues for A* search.
Breadth-first search basically starts with an element and considers all the elements connected to it, before going to the next level. Whereas A* search looks into factors such as the cost of moving to the node and the estimated distance reduction to the goal. Video:
-
Hash Tables are beautiful things and extremely useful in a very large and diverse domain of applications. If you have seen them before, and you are under the impression that they are complicated, just forget anything you know about them. They are quite straightforward:
- Starting with the easy part, "table", we have a data structure that represents a table mapping a value generally represented as a string, to another value of any type. That's what a table is, and if hash tables were just the running time to find a value in the table would be O(n), and it wouldn't be very useful. -> That's the power of "hashing", where we take the key which is the value that maps to another, and process it with a function (for example adding the ascii characters modulo the number of entries in the table, which works but we will later see can be optimized substantially), and finds where in the table it belongs - Know how hash tables are implemented, but more importantly know how to use them to build new systems.
Videos: - [ ] [Core Hash Tables (video)](https://www.coursera.org/learn/data-structures-optimizing-performance/lecture/m7UuP/core-hash-tables) - [ ] [Data Structures (video)](https://www.coursera.org/learn/data-structures/home/week/3) - [ ] [Phone Book Problem (video)](https://www.coursera.org/learn/data-structures/lecture/NYZZP/phone-book-problem)
- Trees are again just another form of organizing data in a way that provides benefits for certain applications. It is called a Tree because it has branches, like real life trees do. Most think of it as an upside down tree. For example:
3
/
5 1 /
0 2- Trees come in all sorts and forms, depending on the application we are desigining them for there are advantages in choosing one type from another, and we will look at each of those indidually as well as examine the trade-offs in future sessions. But it is easy to understand the great advantage of trees at all by talking about binary search trees (BSTs). Their one rule is that:
- For every node, its left child contains a value smaller than or equal to itself, and its right child is larger. E.g:
4
/
2 5 /
1 3
We can see that finding an element here only takes O(log(n)) time for a generally balanced tree. We will also looking at the problem of unbalenced trees later (where most the height of one of the children is much larger than the other, and worst case run time is O(n), to solve this we have balancing algorithms)
Videos:
- Graphs, just like trees, are another way to represent data. A tree is actually just a specific form of a graph. Graphs are very important when we want to model items that have a relationship with one another, like trees. Every tree is a graph, but not every graph is a tree because some graphs can contain cycles (loops) and trees cannot.
Videos:
- MIT (video)
- [Priority Queues] (https://www.youtube.com/watch?v=-WEku8ZnynU)
- CSE373 2012 - Lecture 11 - Graph Data Structures (video)
- CSE373 2012 - Lecture 12 - Breadth-First Search (video)
Concept:
- https://www.coursera.org/learn/principles-of-computing-2/lecture/CVJBS/the-importance-of-recursion
- https://www.coursera.org/learn/principles-of-computing-2/lecture/ccrwD/recursion
- https://www.coursera.org/learn/principles-of-computing-2/lecture/pubjS/visualizing-recursion
- https://www.coursera.org/learn/principles-of-computing-2/lecture/ylfQH/recurrences
Example Application:
Binary search https://www.coursera.org/learn/object-oriented-java/lecture/Zmla4/core-binary-search
Quicksort
- https://www.coursera.org/learn/algorithms-divide-conquer/lecture/Zt0Ti/quicksort-overview
- https://www.coursera.org/learn/algorithms-divide-conquer/lecture/xUd8B/partitioning-around-a-pivot
- https://www.coursera.org/learn/algorithms-divide-conquer/lecture/QCLVL/choosing-a-good-pivot
- https://www.coursera.org/learn/algorithms-divide-conquer/lecture/KMyzr/correctness-of-quicksort-review-optional
- TopCoder (includes recurrence relations and master theorem):
- Computational Complexity: Section 1
- Computational Complexity: Section 2 Counting inversions
- https://www.coursera.org/learn/algorithms-divide-conquer/lecture/GFmmJ/o-n-log-n-algorithm-for-counting-inversions-i
- https://www.coursera.org/learn/algorithms-divide-conquer/lecture/IUiUk/o-n-log-n-algorithm-for-counting-inversions-ii
Talk points: Here we will see the importance of algorithms in designing efficient applications, and how we can benefit from using the advantages of efficient data structures and algorithms together to create very powerful systems.
One of the most basic algorithms is sorting. Everyone is familiar with sorting. In real life we might have a bookshelf sorted by alphabetical order, which is useful for retrieving and finding the correct book at a later time.
There are many problems where sorting first will help to solve the problem more efficiently.
Home:
Advanced String searching & manipulations - [ ] Sedgewick - Suffix Arrays (video) - [ ] Sedgewick - Substring Search (videos) - [ ] 1. Introduction to Substring Search - [ ] 2. Brute-Force Substring Search - [ ] 3. Knuth-Morris Pratt - [ ] 4. Boyer-Moore - [ ] 5. Rabin-Karp - [ ] Search pattern in text (video)
Home Videos:
- https://www.coursera.org/learn/algorithms-on-strings
- https://www.youtube.com/watch?v=CLHDr1tqaFQ
- CS 61B Lecture 29: Sorting I (video)
- CS 61B Lecture 30: Sorting II (video)
- CS 61B Lecture 32: Sorting III (video)
- CS 61B Lecture 33: Sorting V (video)
- 1. Quicksort
- 2. Selection
- 3. Duplicate Keys
- 4. System Sorts
- Analyzing Bubble Sort (video)
- Insertion Sort (video)
- Selection Sort (video)
Intro:
- https://www.coursera.org/learn/machine-learning/lecture/RKFpn/welcome
- https://www.coursera.org/learn/machine-learning/lecture/1VkCb/supervised-learning Regression:
- https://www.coursera.org/learn/machine-learning/lecture/db3jS/model-representation
- https://www.coursera.org/learn/machine-learning/lecture/rkTp3/cost-function
- https://www.coursera.org/learn/machine-learning/lecture/N09c6/cost-function-intuition-i
Classification:
- https://www.coursera.org/learn/machine-learning/lecture/wlPeP/classification
- https://www.coursera.org/learn/machine-learning/lecture/RJXfB/hypothesis-representation
- https://www.coursera.org/learn/machine-learning/lecture/OAOhO/non-linear-hypotheses
- https://www.coursera.org/learn/machine-learning/lecture/4h5X4/prioritizing-what-to-work-on
Intro:
- https://www.coursera.org/learn/machine-learning/lecture/olRZo/unsupervised-learning
- https://www.coursera.org/learn/machine-learning/lecture/czmip/unsupervised-learning-introduction
K-Means:
- https://www.coursera.org/learn/machine-learning/lecture/93VPG/k-means-algorithm
- https://www.coursera.org/learn/machine-learning/lecture/G6QWt/optimization-objective
Applications:
- https://www.coursera.org/learn/machine-learning/lecture/0EJ6A/motivation-i-data-compression
- https://www.coursera.org/learn/machine-learning/lecture/t6pYD/motivation-ii-visualization
- https://www.coursera.org/learn/machine-learning/lecture/Rhg6r/problem-formulation
- https://www.coursera.org/learn/machine-learning/lecture/uG59z/content-based-recommendations
- https://www.coursera.org/learn/machine-learning/lecture/2WoBV/collaborative-filtering
- Neural Networks for Machine Learning
- How Google Is Remaking Itself As A Machine Learning First Company
- Large-Scale Deep Learning for Intelligent Computer Systems (video)
- Deep Learning and Understandability versus Software Engineering and Verification by Peter Norvig](https://www.youtube.com/watch?v=X769cyzBNVw)
- Google's Cloud Machine learning tools (video)
- Google Developers' Machine Learning Recipes (Scikit Learn & Tensorflow) (video)
- Tensorflow (video)
- Tensorflow Tutorials
- Practical Guide to implementing Neural Networks in Python (using Theano)
For interviews, definitely know the properties and implementation of binary search trees. For balanced trees, know the general advantages of each, but you will probably not be asked to straight up implement an AVL Tree. You might have to do something that uses that idea where you would more or less end up inventing it on the fly.
-
AVL trees - https://www.coursera.org/learn/data-structures/lecture/Qq5E0/avl-trees - https://www.coursera.org/learn/data-structures/lecture/PKEBC/avl-tree-implementation - https://www.coursera.org/learn/data-structures/lecture/22BgE/split-and-merge
-
2-3 search trees
-
Red-black trees
-
B-trees
-
Splay trees - 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. - [ ] [CS 61B: Splay Trees (video)](https://www.youtube.com/watch?v=Najzh1rYQTo&index=23&list=PL-XXv-cvA_iAlnI-BQr9hjqADPBtujFJd
-
MIT Lecture: Splay Trees: - Gets very mathy, but watch the last 10 minutes for sure. - Video
-
Red/black trees - 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. - [ ] Aduni - Algorithms - Lecture 4 (link jumps to starting point) (video) - [ ] Aduni - Algorithms - Lecture 5 (video) - [ ] Black Tree - [ ] An Introduction To Binary Search And Red Black Tree - https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/8acpe/red-black-trees - https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/JV7KI/rotations-advanced-optional - https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/jPL2x/insertion-in-a-red-black-tree-advanced
-
2-3-4 Trees (aka 2-4 trees) - 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. - [ ] CS 61B Lecture 26: Balanced Search Trees (video) - [ ] Bottom Up 234-Trees (video) - [ ] Top Down 234-Trees (video)
-
B-Trees - 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. - [ ] B-Tree - [ ] Introduction to B-Trees (video) - [ ] B-Tree Definition and Insertion (video) - [ ] B-Tree Deletion (video) - [ ] 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)
-
- note: the N or K is the branching factor (max branches)
- binary trees are a 2-ary tree, with branching factor = 2
- 2-3 trees are 3-ary
- K-Ary Tree
- note: the N or K is the branching factor (max branches)
Some Applications of Trees:
-
Heaps:
-
- https://www.coursera.org/learn/data-structures-optimizing-performance/lecture/08Xyf/core-introduction-to-tries
- https://www.coursera.org/learn/data-structures-optimizing-performance/lecture/PvlZW/core-performance-of-tries
- https://www.coursera.org/learn/data-structures-optimizing-performance/lecture/DFvd3/core-implementing-a-trie
-
- Sedgewick - Tries (3 videos)
- 1. R Way Tries
- 2. Ternary Search Tries
- 3. Character Based Operations - [ ] Notes on Data Structures and Programming Techniques - [ ] Short course videos:
- Introduction To Tries (video)
- Performance Of Tries (video)
- Implementing A Trie (video) - [ ] The Trie: A Neglected Data Structure - [ ] TopCoder - Using Tries - [ ] Stanford Lecture (real world use case) (video) - [ ] Series (video)
- Sedgewick - Tries (3 videos)
-
- visualized as a tree, but is usually linear in storage (array, linked list)
- Heap
- https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/iIzo8/heaps-operations-and-applications
- https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/KKqlm/heaps-implementation-details-advanced-optional
- Naive Implementations (video)
- Binary Trees (video)
- Basic Operations (video)
- Complete Binary Trees (video)
- Pseudocode (video)
- Heap Sort - jumps to start (video)
- Heap Sort (video)
- Building a heap (video)
- CS 61B Lecture 24: Priority Queues (video)
- Linear Time BuildHeap (max-heap)
- Implement a max-heap:
- insert
- sift_up - needed for insert
- get_max - returns the max item, without removing it
- get_size() - return number of elements stored
- is_empty() - returns true if heap contains no elements
- extract_max - returns the max item, removing it
- sift_down - needed for extract_max
- remove(i) - removes item at index x
- heapify - create a heap from an array of elements, needed for heap_sort
- heap_sort() - take an unsorted array and turn it into a sorted array in-place using a max heap
- note: using a min heap instead would save operations, but double the space needed (cannot do in-place).
-
- Combination of a binary search tree and a heap
- Treap
- Data Structures: Treaps explained (video)
- Applications in set operations
- https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/NX0BI/graph-search-overview till 6:50
- https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/JZRXz/breadth-first-search-bfs-the-basics
- https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/ZAaJA/bfs-and-shortest-paths <-
- https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/BTVWn/bfs-and-undirected-connectivity
- https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/pKr0Y/depth-first-search-dfs-the-basics
Dijkstra Graph Search Algorihtm
- https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/rxrPa/dijkstras-shortest-path-algorithm till 10:00
- https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/Jfvmn/dijkstras-algorithm-examples
- https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/VCHYw/correctness-of-dijkstras-algorithm
- https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/Pbpp9/dijkstras-algorithm-implementation-and-running-time
- https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/yeKm7/topological-sort till 10:00
- https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/rng2S/computing-strong-components-the-algorithm
- https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/f11at/structure-of-the-web-optional
- Iterative Deepening Depth-First Search (IDDFS): the best of both BFS and DFS and has a much better time and space complexity. (https://www.youtube.com/watch?v=7QcoJjSVT38)
Use this: https://www.coursera.org/learn/algorithms-on-graphs
Graphs are a huge subject in computer science, there are many applications in which they are powerful. From modeling the relationships between people in social networks, to representing connections of genomic data in trying to understand patterns of diseases, they are very useful. There are many ways to represent them and we will understand them below:
-
Union-Find
-
Advanced Graph Processing (videos)
-
use resources from here https://www.coursera.org/learn/algorithms-on-graphs
-
https://www.coursera.org/learn/algorithms-graphs-data-structures
Knapsack:
- https://www.coursera.org/learn/algorithms-greedy/lecture/LIgLJ/the-knapsack-problem
- https://www.coursera.org/learn/algorithms-greedy/lecture/0n68L/a-dynamic-programming-algorithm
- https://www.coursera.org/learn/algorithms-greedy/lecture/LADQc/example-review-optional
Optimal Substructure:
- https://www.coursera.org/learn/algorithms-greedy/lecture/QJkyp/optimal-substructure
- https://www.coursera.org/learn/algorithms-greedy/lecture/tNmae/a-dynamic-programming-algorithm
Dynamic programming is quite simple. It takes advantages of two things seen previously: data structures and recursion.
-
Videos:
-
Weighted independent sets:
-
https://www.coursera.org/learn/algorithms-greedy/lecture/VEc7L/principles-of-dynamic-programming
-
Optimal Substructure
-
https://www.coursera.org/learn/algorithms-greedy/lecture/GKCeN/problem-definition
-
https://www.coursera.org/learn/algorithms-greedy/lecture/rUDLu/optimal-substructure
-
https://www.coursera.org/learn/algorithms-greedy/lecture/0qjbs/proof-of-optimal-substructure
-
https://www.coursera.org/learn/algorithms-greedy/lecture/3wrTN/a-dynamic-programming-algorithm-i
-
https://www.coursera.org/learn/algorithms-greedy/lecture/5ERYG/a-dynamic-programming-algorithm-ii
-
List of individual DP problems (each is short): Dynamic Programming (video)
-
More Dynamic Programming (videos)
- 6.006: Dynamic Programming I: Fibonacci, Shortest Paths
- 6.006: Dynamic Programming II: Text Justification, BlackjackDu
- 6.006: DP III: Parenthesization, Edit Distance, Knapsack
- 6.006: DP IV: Guitar Fingering, Tetris, Super Mario Bros.
- 6.046: Dynamic Programming & Advanced DP
- 6.046: Dynamic Programming: All-Pairs Shortest Paths
- 6.046: Dynamic Programming (student recitation)
See from skiena's slides, and within the extra content here in the guide and:
Edit distance: https://www.coursera.org/learn/dna-sequencing/lecture/ZDDOH/practical-implementing-dynamic-programming-for-edit-distance TSP: https://www.coursera.org/learn/advanced-algorithms-and-complexity/lecture/71PHI/tsp-dynamic-programming
Backtracking https://www.coursera.org/learn/comparing-genomes/lecture/TDKlW/dynamic-programming-and-backtracking-pointers
https://www.coursera.org/learn/algorithms-greedy
- Math Skills: How to find Factorial, Permutation and Combination (Choose) (video)
- Bayes theorem: https://www.youtube.com/watch?v=2Df1sDAyRvQ
- Expected value: https://www.youtube.com/watch?v=q27iV8y4fdM
- https://www.coursera.org/learn/algorithms-npcomplete/lecture/8HT5O/polynomial-time-solvable-problems
- https://www.coursera.org/learn/algorithms-npcomplete/lecture/o1CGE/reductions-and-completeness
- https://www.coursera.org/learn/algorithms-npcomplete/lecture/vZ9Bc/definition-and-interpretation-of-np-completeness-i
- https://www.coursera.org/learn/algorithms-npcomplete/lecture/3JqiX/definition-and-interpretation-of-np-completeness-ii
- https://www.coursera.org/learn/algorithms-npcomplete/lecture/VZY2Z/the-p-vs-np-question
- https://www.coursera.org/learn/algorithms-npcomplete/lecture/jugfP/algorithmic-approaches-to-np-complete-problems
Probability:
-
MIT Probability (mathy, and go slowly, which is good for mathy things) (videos)
-
- Given a Bloom filter with m bits and k hashing functions, both insertion and membership testing are O(k)
- Bloom Filters
- Bloom Filters | Mining of Massive Datasets | Stanford University
- Tutorial
- How To Write A Bloom Filter App
-
- also see videos below
- make sure to watch information theory videos first
- Khan Academy Series
- Cryptography: Hash Functions
- Cryptography: Encryption
Complexity:
- Computational Complexity (video)
- Simonson:
- Greedy Algs. II & Intro to NP Completeness (video)
- NP Completeness II & Reductions (video)
- NP Completeness III (Video)
- NP Completeness IV (video)
- Skiena:
- CSE373 2012 - Lecture 23 - Introduction to NP-Completeness (video)
- CSE373 2012 - Lecture 24 - NP-Completeness Proofs (video)
- CSE373 2012 - Lecture 25 - NP-Completeness Challenge (video)
- Complexity: P, NP, NP-completeness, Reductions (video)
- Complexity: Approximation Algorithms (video)
- Complexity: Fixed-Parameter Algorithms (video)
- Peter Norvik discusses near-optimal solutions to traveling salesman problem:
- Jupyter Notebook
- Pages 1048 - 1140 in CLRS if you have it.
Bit manipulation C Programming Tutorial 2-10: Bitwise Operators (video) Binary: Plusses & Minuses (Why We Use Two's Complement) (video) 4 ways to count bits in a byte (video)
-
- Big And Little Endian
- Big Endian Vs Little Endian (video)
- Big And Little Endian Inside/Out (video)
- Very technical talk for kernel devs. Don't worry if most is over your head.
- The first half is enough.
- [ ] LRU cache:
- [ ] [The Magic of LRU Cache (100 Days of Google Dev) (video)](https://www.youtube.com/watch?v=R5ON3iwx78M)
- [ ] [Implementing LRU (video)](https://www.youtube.com/watch?v=bq6N7Ym81iI)
- [ ] [LeetCode - 146 LRU Cache (C++) (video)](https://www.youtube.com/watch?v=8-FZRAjR7qU)
- [ ] CPU cache:
- [ ] [MIT 6.004 L15: The Memory Hierarchy (video)](https://www.youtube.com/watch?v=vjYF_fAZI5E&list=PLrRW1w6CGAcXbMtDFj205vALOGmiRc82-&index=24)
- [ ] [MIT 6.004 L16: Cache Issues (video)](https://www.youtube.com/watch?v=ajgC3-pyGlk&index=25&list=PLrRW1w6CGAcXbMtDFj205vALOGmiRc82-)
Very Basics first:
- How does CPU execute program (video)
- Machine Code Instructions (video)
- threads in C++ (series - 10 videos)
- concurrency in Python (videos):
- Short series on threads
- Python Threads
- Mutex in Python
-
[What Is The Difference Between A Process And A Thread?](https://www.quora.com/What-is-the-difference-between-a-process-and-a-thread
-
Understanding the Python GIL (2010) - reference - [ ] David Beazley - Python Concurrency From the Ground Up: LIVE! - PyCon 2015 - [ ] Keynote David Beazley - Topics of Interest (Python Asyncio)
Give talk on design and testing
-
- Agile Software Testing with James Bach (video)
- Open Lecture by James Bach on Software Testing (video)
- Steve Freeman - Test-Driven Development (that’s not what we meant) (video)
- TDD is dead. Long live testing.
- Is TDD dead? (video)
- Video series (152 videos) - not all are needed (video)
- Test-Driven Web Development with Python
- Dependency injection:
- How to write tests
-
- Quick UML review (video)
- Chapter 6 (Part 1) - Patterns (video)
- Chapter 6 (Part 2) - Abstraction-Occurrence, General Hierarchy, Player-Role, Singleton, Observer, Delegation (video)
- Chapter 6 (Part 3) - Adapter, Facade, Immutable, Read-Only Interface, Proxy (video)
- Series of videos (27 videos)
- Head First Design Patterns
- I know the canonical book is "Design Patterns: Elements of Reusable Object-Oriented Software", but Head First is great for beginners to OO.
- Handy reference: 101 Design Patterns & Tips for Developers
This section will have shorter videos that can you watch pretty quickly to review most of the important concepts. It's nice if you want a refresher often.
- Wrap up
Home Reading (for your own, on your own time, don't do all this in a week otherwise you will be wasting your time since you won't remember any of it by cramming it)
- Series of 2-3 minutes short subject videos (23 videos)
- Series of 2-5 minutes short subject videos - Michael Sambol (18 videos):
- Sedgewick Videos - Algorithms I
- Sedgewick Videos - Algorithms II
Once you've learned your brains out, put those brains to work. Take coding challenges every day, as many as you can.
- LeetCode
- TopCoder
- Project Euler (math-focused)
- Codewars
- HackerRank
- Codility
- InterviewCake
- InterviewBit
- Cracking The Coding Interview Set 2 (videos):
- Ten Tips for a (Slightly) Less Awful Resume
- See Resume prep items in Cracking The Coding Interview and back of Programming Interviews Exposed
Now that you know all the computer science topics above, it's time to practice answering coding problems.
Coding question practice is not about memorizing answers to programming problems.
Why you need to practice doing programming problems:
- problem recognition, and where the right data structures and algorithms fit in
- gathering requirements for the problem
- talking your way through the problem like you will in the interview
- coding on a whiteboard or paper, not a computer
- coming up with time and space complexity for your solutions
- testing your solutions
There is a great intro for methodical, communicative problem solving in an interview. You'll get this from the programming interview books, too, but I found this outstanding:
No whiteboard at home? That's fine, buy one. Or don't if that's really an issue, but just practice on paper and practice whiteboarding skills at school or something. You should really practice on whiteboard though, to mimick the real interview setting. But the main thing you want to practice is to practice under stress, there's nothing like coding in front of a guy who is going to decide whether you get a job or not, and then you're as nervous as you've never been before.
The solution? Practice that. How? Every interview you get the opportunity in doing, do it. Even if it's a company you don't care much about, you will still be practicing coding while someone else is looking at you and your subconscious mind constantly fighting you by making you afraid of being embarassed. Trust me, I had the biggest issues with this, the only way to get over it was to interview dozens and dozens of times, just like speaking in public or anything of the sort. The more you do it, the more you realize the worst case scenario is not nearly as big of a deal as your pessimistic-self anticipates, and in that process you will become less and less nervous each time you attempt something similar.
Supplemental:
- Mathematics for Topcoders
- Dynamic Programming – From Novice to Advanced
- MIT Interview Materials
- Exercises for getting better at a given language
Think of about 20 interview questions you'll get, along the lines of the items below. Have 2-3 answers for each. Have a story, not just data, about something you accomplished.
- Why do you want this job?
- What's a tough problem you've solved?
- Biggest challenges faced?
- Best/worst designs seen?
- Ideas for improving an existing Google product.
- How do you work best, as an individual and as part of a team?
- Which of your skills or experiences would be assets in the role and why?
- What did you most enjoy at [job x / project y]?
- What was the biggest challenge you faced at [job x / project y]?
- What was the hardest bug you faced at [job x / project y]?
- What did you learn at [job x / project y]?
- What would you have done better at [job x / project y]?
- How large is your team?
- What does your dev cycle look like? Do you do waterfall/sprints/agile?
- Are rushes to deadlines common? Or is there flexibility?
- How are decisions made in your team?
- How many meetings do you have per week?
- Do you feel your work environment helps you concentrate?
- What are you working on?
- What do you like about it?
- What is the work life like?
- Programming Pearls
- Grokking Algorithms
- Write Great Code: Volume 1: Understanding the Machine
- Elements of Programming Interviews
- Introduction to Algorithms
- Algorithm Design Manual (Skiena)
- The Unix Programming Environment
- The Linux Command Line: A Complete Introduction
- TCP/IP Illustrated Series
- Head First Design Patterns
- Design Patterns: Elements of Reusable Object-Oriented Software
- Site Reliability Engineering
- UNIX and Linux System Administration Handbook, 4th Edition
- Cracking the Coding Interview, 6th Edition
- Elements of Programming Interviews
- Python Machine Learning
- Data Science from Scratch: First Principles with Python
- Introduction to Machine Learning with Python
- Machine Learning for Software Engineers