Table of Contents |
---|
...
Algorithms-Specific Informational Websites (not programming challenge websites)
Nick Parlante - Pointers, Binary Trees, etc.
Very good explanations
OK explanations
...
Interview Prep sites
rec'd by Choketsu
Codility
Rec'd by Toptal
rec'd by Choketsu
via Tom A.
Non-Interview-Prep Challenge sites
...
Someone who works with machine learning explaining how Kaggle is a simplification of real ML work:
Jason B Hill's Project Euler solutions
Rec'd by Toptal, Chris Uga
rec'd by Choketsu
How to get started training at the USACO Gateway:
What is it like to attend the USACO training camp?
It's only a week
New people just get 3 hours of lab/lecture in the morning
The top guys do a contest every day. Sometimes the contest goes until after lunch, otherwise they just review after lunch. (Seems like 5 hrs/day)
Then everyone has fun for the rest of the day
If one is stuck on a particular section, is it worthwhile to keep on trying to solve the given problem, or should one move on to other sources in preparation for programming contests?
Richard Peng, one of the most successful Canadian IOI competitors of all time, on the USACO training pages:
"USACO training was put together before the major IOI escalation (Finland/Korea/Wisconsin). A lot of the techniques described on it are no longer useful on *OI and a lot of the 'hot' topics over the past few years are not covered. Also, a lot of the bottle necks on training are quite meaningless, and they typically cause a lot of frustration and time waste on the scale of months."
Topics
Linked Lists
...
Algorithms
Testing recognition / basic understanding
What does "BFS" stand for?
Acronym used in IK
Give an example of an O(X) algorithm. ← See 'The Pragmatic Programmer' for examples.
Give an example of an O(1) algorithm.
Give an example of an O(lg(n)) algorithm.
"Binary search of a sorted list, traversing a binary tree, and finding the first set bit in a machine word(?)."
Give an example of an O(n) algorithm.
Exhaustive searches, finding the maximum value in an array, and generating checksums.
Give an example of an O(m * n) algorithm.
"This commonly occurs in simple sorting algorithms, such as bubble sort, where the outer loop scans each element in the array in turn, and the inner loop works out where to place that element in the sorted result."
Give an example of an O(n*lg(n)) algorithm.
Quicksort
Give an example of an O(n^2) algorithm.
Give an example of an O(n^3) algorithm.
Give an example of an O(2^n) algorithm.
Give an example of an O(n!) algorithm.
"Whenever algorithms start looking at the permutations of things, their running times may get out of hand. (...) Examples include algorithms for many of the acknowledged 'hard' problems–the traveling salesman problem, optimally packing things into a container, partitioning a set of numbers so that each set has the same total, and so on. Often, heuristics are used to reduce the running times of these types of algorithms in particular problem domains."
Arrays and other Ad-hoc problems
Concurrency
Dynamic Programming
Graphs and other Data Structures
Group coding mocks
Group mocks on Concurrency
Group mocks on Object Modeling
Group mocks on Scalable Systems
Linked Lists, Stacks, and Queues
Object Modeling
Orientation + Behavioral
Recursion
Scalable Systems
Sorting
Strings
Trees
Done - K-ary tree
Used in IK
BST
Used in IK
System Design
Step-by-step process
Ask clarifying questions. (Source)
Constrain the problem to make it solvable within the hour.
Share what you know about the system with the interviewer.
If you’re not familiar with the system, they can fill you in.
Metrics
Specify some key metrics to help your high-level decision-making.
Example: the number of users, the amount of data
You don’t necessarily have to go into the details of scaling at this point.
Design the system at a high level.
At an early stage, it’s OK to have a few simple components; later on you can get more complex.
Example:
Design Spotify: “A mobile app connects to a load balancer which connects to multiple webservers, which connect to the database.”
Outline your database design.
After laying out your components, design your database.
Split out databases appropriate for different types of data.
In general, try to explain why you’re doing something upfront rather than waiting for your interviewer to ask you.
Learning resources
Alex Xu
https://www.designgurus.io/ - Grokking the System Design Interview (online course)
https://drive.google.com/file/d/1U7EchvgzCjTtF5JzGVVCFgjXC-qw7lIG/view?pli=1 ← They send you a link to this ebook when you sign up for their newsletter.
NeetCode system design courses - https://neetcode.io/courses
https://www.algoexpert.io/systems/product
Negative review: https://www.reddit.com/r/cscareerquestions/comments/s0e54f/warning_systems_expert_by_the_algoexpert_guy_is/
“modules are very light on information, and you'd have a better time just reading the wikipedia page on those topics.”
“topics aren't well explained and it's just an extremely high level overview of what they are”
Udemy: https://www.udemy.com/courses/search/?src=ukw&q=system+design
https://www.amazon.com/Scalability-Startup-Engineers-Artur-Ejsmont/dp/0071843655
...