Overview
What is the coding roadmap?
The coding roadmap is a series of projects that are designed to help you learn the foundations of programming.
What the coding roadmap is NOT?
The coding roadmap is NOT a course or a tutorial. It is also NOT a substitute for a college degree or a bootcamp.
Who is the coding roadmap for?
For the most part, this roadmap is designed for beginners or students, but software engineers of all experience levels may find this useful. This is a great resource for you, if:
You are new to programming and want to build a solid foundation around the core concepts of programming.
You are a software engineer and want to brush up on the fundamentals.
You are already in tech and know a bit up programming, and are planning to making a career switch to software engineering.
You are curious about software engineering and want to see if it is a right fit for you.
You are preparing for software engineering interviews.
Watch this to get an overview of this roadmap.
In addition to that, you should know the absolute basics of programming -- primitives, variables, operators, conditionals, loops, functions, objects, etc. Complete Module 0 for a self-assessment.
Books for Data Structures & Algorithms
Computer Science Distilled (Beginner friendly)
Grokking Algorithms (Beginner friendly)
Data Structures and Algorithms in Python (Beginner Friendly)
Data Structures and Algorithms Made Easy (Intermediate)
Introduction to Algorithms (Advanced)
Algorithms 4th Edition (Advanced)
Algorithm Design Manual (Advanced)
Books for Good Coding Habits
Free Resources
While each module has relevant free resources within it, here are some free resources that are generally applicable to all modules.
Paid Resources
Educative.io (10% off via this link)
Suggested Course 1: Learn Python 3 from Scratch
Suggested Course 2: Python 3: From Beginner to Advanced
Suggested Course 3: Data Structures and Algorithms in Python
LeetCode (15% off via this link) **you do not need Premium plan for any of the modules
How to use the coding roadmap?
Each project is designed to be completed in a week or two. Start with Module 0 and work your way through the modules. For each module:
Read the project description and the project requirements to understand what you will need to deliver first.
Review the recommended study topics and use the provided resources to learn those topics.
Solve the self-assessment problems.
Finish on the project.
Modules
Module 0 - The Basics
This module is mostly designed as a self-assessment to see if you understand the very basics of programming. This is required knowledge for you to proceed to the next module. If you find that you lack even the basic knowledge, use the resources in this module to learn the basics and come back to this module again when you feel ready. If you have the basic knowledge, feel free to skip this module.
Resources
Self Assessment
Module 1 - String manipulation and formatting
This is something you do frequently in the real world. Things like input validation, sanitization, conversion or internationalization are common practice.
Project - Case Converter
In programming, there are five common cases: camelCase, snakecase, kebab-case, PascalCase and UPPER_CASE_SNAKE_CASE. For this project, you are to Write a function that takes in a sentence and a desired case as the inputs, and then converts the sentence into the desired case.
Examples:
convert("Hello, World.", "camel") Output: helloWorld convert("Hello, World.", "snake") Output: hello_world convert("Hello, World.", "kebab") Output: hello-world convert("Hello, World.", "pascal") Output: HelloWorld convert("Hello, World.", "uppercasesnake") Output: HELLO_WORLD
Module 2 - Linked Lists
Linked lists don't get enough love, but they are quite handy data structures, especially you are unsure about the size or the capacity ahead of time. Are you the kind that has 100 tabs open in your browser? Well, then you've been using Linked Lists daily. When you press Ctrl + Tab to cycle between those tabs, you are basically making your way through a circular linked list.
Project - Browser History
You have a browser of one tab where you start on the homepage
and you can visit another url
, get back in the history number of steps
or move forward in the history number of steps
.
Implement the BrowserHistory
class:
BrowserHistory(string homepage)
Initializes the object with thehomepage
of the browser.void visit(string url)
Visitsurl
from the current page. It clears up all the forward history.string back(int steps)
Movesteps
back in history. If you can only returnx
steps in the history andsteps > x
, you will return onlyx
steps. Return the currenturl
after moving back in history at moststeps
.string forward(int steps)
Movesteps
forward in history. If you can only forwardx
steps in the history andsteps > x
, you will forward onlyx
steps. Return the currenturl
after forwarding in history at moststeps
.
Examples:
Input: ["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"] [["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]] Output: [null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"] Explanation: BrowserHistory browserHistory = new BrowserHistory("leetcode.com"); browserHistory.visit("google.com"); // You are in "leetcode.com". Visit "google.com" browserHistory.visit("facebook.com"); // You are in "google.com". Visit "facebook.com" browserHistory.visit("youtube.com"); // You are in "facebook.com". Visit "youtube.com" browserHistory.back(1); // You are in "youtube.com", move back to "facebook.com" return "facebook.com" browserHistory.back(1); // You are in "facebook.com", move back to "google.com" return "google.com" browserHistory.forward(1); // You are in "google.com", move forward to "facebook.com" return "facebook.com" browserHistory.visit("linkedin.com"); // You are in "facebook.com". Visit "linkedin.com" browserHistory.forward(2); // You are in "linkedin.com", you cannot move forward any steps. browserHistory.back(2); // You are in "linkedin.com", move back two steps to "facebook.com" then to "google.com". return "google.com" browserHistory.back(7); // You are in "google.com", you can move back only one step to "leetcode.com". return "leetcode.com"
Resources
Self Assessment
Module 3 - Hash tables
Hash table is a very popular data structure in practice. It is a simple concept, but quite powerful when you use it effectively. For example, when you type www.engineeringwithutsav.com on your browser, your browser basically looks at your ISPs routing table, also called the DNS server, for the exact IP address of my web server that hosts the contents of my website. That routing table is basically a giant table with two columns: the domain name, which is the key, and the IP address, which is the value. And that's what a hash table is. It stores a bunch of unique keys that have certain values. You give it a key, and it will give you the value very quickly. In this case, you give it the domain name, and it gives you the IP address so that your browser can fetch the webpage to render. So yeah, you are basically relying on giant distributed hash tables every time you type a domain name on your browser.
Project - Caesar Cipher
A Caesar cipher is a simple method of encoding messages. Caesar ciphers use a substitution method where letters in the alphabet are shifted by some fixed number of spaces to yield an encoding alphabet. A Caesar cipher with a shift of 1 would encode an A as a B, an M as an N, and a Z as an A, and so on. The method is named after Roman leader Julius Caesar, who used it in his private correspondence.
Write a program to encrypt plaintext into ciphertext using the Caesar cipher. Here is the program skeleton:
def build_coder(shift): """ Returns a dict that can apply a Caesar cipher to a letter. The cipher is defined by the shift value. Ignores non-letter characters like punctuation and numbers. shift: -27 < int < 27 returns: dict Example: >>> build_coder(3) {' ': 'c', 'A': 'D', 'C': 'F', 'B': 'E', 'E': 'H', 'D': 'G', 'G': 'J', 'F': 'I', 'I': 'L', 'H': 'K', 'K': 'N', 'J': 'M', 'M': 'P', 'L': 'O', 'O': 'R', 'N': 'Q', 'Q': 'T', 'P': 'S', 'S': 'V', 'R': 'U', 'U': 'X', 'T': 'W', 'W': 'Z', 'V': 'Y', 'Y': 'A', 'X': ' ', 'Z': 'B', 'a': 'd', 'c': 'f', 'b': 'e', 'e': 'h', 'd': 'g', 'g': 'j', 'f': 'i', 'i': 'l', 'h': 'k', 'k': 'n', 'j': 'm', 'm': 'p', 'l': 'o', 'o': 'r', 'n': 'q', 'q': 't', 'p': 's', 's': 'v', 'r': 'u', 'u': 'x', 't': 'w', 'w': 'z', 'v': 'y', 'y': 'a', 'x': ' ', 'z': 'b'} (The order of the key-value pairs may be different.) """ ### YOUR CODE GOES HERE def build_encoder(shift): """ Returns a dict that can be used to encode a plain text. For example, you could encrypt the plain text by calling the following commands >>>encoder = build_encoder(shift) >>>encrypted_text = apply_coder(plain_text, encoder) The cipher is defined by the shift value. Ignores non-letter characters like punctuation and numbers. shift: 0 <= int < 27 returns: dict Example: >>> build_encoder(3) {' ': 'c', 'A': 'D', 'C': 'F', 'B': 'E', 'E': 'H', 'D': 'G', 'G': 'J', 'F': 'I', 'I': 'L', 'H': 'K', 'K': 'N', 'J': 'M', 'M': 'P', 'L': 'O', 'O': 'R', 'N': 'Q', 'Q': 'T', 'P': 'S', 'S': 'V', 'R': 'U', 'U': 'X', 'T': 'W', 'W': 'Z', 'V': 'Y', 'Y': 'A', 'X': ' ', 'Z': 'B', 'a': 'd', 'c': 'f', 'b': 'e', 'e': 'h', 'd': 'g', 'g': 'j', 'f': 'i', 'i': 'l', 'h': 'k', 'k': 'n', 'j': 'm', 'm': 'p', 'l': 'o', 'o': 'r', 'n': 'q', 'q': 't', 'p': 's', 's': 'v', 'r': 'u', 'u': 'x', 't': 'w', 'w': 'z', 'v': 'y', 'y': 'a', 'x': ' ', 'z': 'b'} (The order of the key-value pairs may be different.) HINT : Use build_coder. """ ### YOUR CODE GOES HERE def build_decoder(shift): """ Returns a dict that can be used to decode an encrypted text. For example, you could decrypt an encrypted text by calling the following commands >>>encoder = build_encoder(shift) >>>encrypted_text = apply_coder(plain_text, encoder) >>>decrypted_text = apply_coder(plain_text, decoder) The cipher is defined by the shift value. Ignores non-letter characters like punctuation and numbers. shift: 0 <= int < 27 returns: dict Example: >>> build_decoder(3) {' ': 'x', 'A': 'Y', 'C': ' ', 'B': 'Z', 'E': 'B', 'D': 'A', 'G': 'D', 'F': 'C', 'I': 'F', 'H': 'E', 'K': 'H', 'J': 'G', 'M': 'J', 'L': 'I', 'O': 'L', 'N': 'K', 'Q': 'N', 'P': 'M', 'S': 'P', 'R': 'O', 'U': 'R', 'T': 'Q', 'W': 'T', 'V': 'S', 'Y': 'V', 'X': 'U', 'Z': 'W', 'a': 'y', 'c': ' ', 'b': 'z', 'e': 'b', 'd': 'a', 'g': 'd', 'f': 'c', 'i': 'f', 'h': 'e', 'k': 'h', 'j': 'g', 'm': 'j', 'l': 'i', 'o': 'l', 'n': 'k', 'q': 'n', 'p': 'm', 's': 'p', 'r': 'o', 'u': 'r', 't': 'q', 'w': 't', 'v': 's', 'y': 'v', 'x': 'u', 'z': 'w'} (The order of the key-value pairs may be different.) HINT : Use build_coder. """ ### YOUR CODE GOES HERE def apply_coder(text, coder): """ Applies the coder to the text. Returns the encoded text. text: string coder: dict with mappings of characters to shifted characters returns: text after mapping coder chars to original text Example: >>> apply_coder("Hello, world!", build_encoder(3)) 'Khoor,czruog!' >>> apply_coder("Khoor,czruog!", build_decoder(3)) 'Hello, world!' """ ### YOUR CODE GOES HERE def apply_shift(text, shift): """ Given a text, returns a new text Caesar shifted by the given shift offset. The empty space counts as the 27th letter of the alphabet, so spaces should be replaced by a lowercase letter as appropriate. Otherwise, lower case letters should remain lower case, upper case letters should remain upper case, and all other punctuation should stay as it is. text: string to apply the shift to shift: amount to shift the text returns: text after being shifted by specified amount. Example: >>> apply_shift('This is a test.', 8) 'Apq hq hiham a.' """ ### YOUR CODE GOES HERE
Module 4 - Stacks
Consider your text editor. When you type something, then hit UNDO, you revert your latest action, right? Well, that is utilizing a stack. Your actions are basically added to a stack, which is a LIFO (Last in, First out) data structure, so your last action will always be on the top. And when you hit undo, the stack is simply "popped", undoing your latest action. If you hit undo again, the action you performed previous to that one is reverted since that would have been the second-to-last action you performed. So on and so forth.
Project - Basic Calculator
Given a string s
which represents an expression, evaluate this expression and return its value.
The integer division should truncate toward zero.
You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1]
.
Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval()
.
Examples:
Example 1: Input: s = "3+2*2" Output: 7 Example 2: Input: s = " 3/2 " Output: 1 Example 3: Input: s = " 3+5 / 2 " Output: 5
Module 5 - Queues
Queues are pretty self-explanatory and quite common as well. How many of you tried buying a Playstation 5 when it released in the summer of 2020, and got hit with the dreaded "You have been added to a queue... do not refresh the browser" message? What is happening there? Well, because so many people rushed to buy the product at the same time, the web server reached its capacity and could not handle any more traffic. But instead of just erroring out, the load balancer redirected you to a temporary queue, which is a FIFO (First in, First out) data structure. As traffic improves in the web server, the queue is "dequeued", letting the first person that got put in the queue through to the website, then the second, then third ... just like a queue in the shopping mall.
Project - Circular Queue
Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called "Ring Buffer".
One of the benefits of the circular queue is that we can make use of the spaces in front of the queue. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is a space in front of the queue. But using the circular queue, we can use the space to store new values.
Implementation the MyCircularQueue
class:
MyCircularQueue(k)
Initializes the object with the size of the queue to bek
.int Front()
Gets the front item from the queue. If the queue is empty, return-1
.int Rear()
Gets the last item from the queue. If the queue is empty, return-1
.boolean enQueue(int value)
Inserts an element into the circular queue. Returntrue
if the operation is successful.boolean deQueue()
Deletes an element from the circular queue. Returntrue
if the operation is successful.boolean isEmpty()
Checks whether the circular queue is empty or not.boolean isFull()
Checks whether the circular queue is full or not.
You must solve the problem without using the built-in queue data structure in your programming language.
Examples:
Input ["MyCircularQueue", "enQueue", "enQueue", "enQueue", "enQueue", "Rear", "isFull", "deQueue", "enQueue", "Rear"] [[3], [1], [2], [3], [4], [], [], [], [4], []] Output [null, true, true, true, false, 3, true, true, true, 4] Explanation MyCircularQueue myCircularQueue = new MyCircularQueue(3); myCircularQueue.enQueue(1); // return True myCircularQueue.enQueue(2); // return True myCircularQueue.enQueue(3); // return True myCircularQueue.enQueue(4); // return False myCircularQueue.Rear(); // return 3 myCircularQueue.isFull(); // return True myCircularQueue.deQueue(); // return True myCircularQueue.enQueue(4); // return True myCircularQueue.Rear(); // return 4
Module 6 - Recursion
Recursion is usually the first thing that makes new programmers nervous. And that is expected, because recursion is not a natural thing to happen in real life. It is a very abstract and mathematical concept, and that makes it a bit tricky to grasp at first. So, don't fret it if you end up spending more time on this module. However, in the programming world though, you will see recursive data structures quite frequently. For example, clicking on a folder, then its sub-folder, and then the sub-folder of that folder... this is a recursive action. A folder can have a file or a folder. And for all those sub-folders, the same definition applies -- each one of them can have files or more folders. You get the idea.
Project - Deep Copy
Write a program that can copy all files and folders (including sub-folders) from source location to destination.
Example usage:
python copy.py [SOURCE FOLDER] [DESTINATION FOLDER] will copy everything from source folder to the destination folder
Resources
Self Assessment
Module 7 - Binary Search
If you need to search anything that is ordered, you will most likely use binary search. Have you ever searched a physical dictionary for a definition? How did you do it? You surely did not look page after page and word after word, until you found the word you were looking for. You must has started at the middle of the dictionary to check if the word you are looking for falls on the left half or the right half. If it falls on the left half, you search the left half of the dictionary. And if it falls on the right half, you search the right half of the dictionary. You keep discarding one of the halves until you have landed at the page that has the word you are looking for. Well, this is what binary search is. It is a very efficient search algorithm that discards half of search space at every iteration greatly reducing the time it takes to search for something.
Project - Dictionary Search
Given this word list, write a program that allows you to search for a word. If word is found on this list, it returns the word, if not, it returns the word that is alphabetically closest to it. The search will have be written using binary search.
Examples:
Given the word list: [apple, banana, bingo, cat, curl] Input: bingo Output: bingo Input: banjo Output: bingo Input: cut Output: curl Input: cat Output: cat
Module 8 - Trees
Trees are a very common data structure in the real world. They are very useful for storing data in a hierarchical manner. For example, you might have a tree that represents a company structure. Each node in the tree has a name, and each node can have a list of employees. And each employee can have a list of subordinates. But not just that, trees are the foundations of storage systems like SQL server and a critical part of searching. For example, when you search for something on YouTube, it auto-completes your word or sentence for you, right? Under the covers, it is basically walking through a special kind of tree called a Trie to produce those suggestions.
Project - Trie
A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.
Implement the Trie class:
Trie()
Initializes the trie object.void insert(String word)
Inserts the stringword
into the trie.boolean search(String word)
Returnstrue
if the stringword
is in the trie (i.e., was inserted before), andfalse
otherwise.boolean startsWith(String prefix)
Returnstrue
if there is a previously inserted stringword
that has the prefixprefix
, andfalse
otherwise.
Examples:
Input ["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]] Output [null, null, true, false, true, null, true] Explanation Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // return True trie.search("app"); // return False trie.startsWith("app"); // return True trie.insert("app"); trie.search("app"); // return True
Resources
Self Assessment
Module 9 - Graphs
Graphs are everywhere -- social networks, recommendation systems, maps, machine learning, you name it, graphs are lurking behind the scenes. Graphs sound intense because they are often spoken about in very mathematical lingo. For example, "There is an undirected weighted graph made up of X edges and Y vertices, which may or may not have disjoint components. How can we find the shortest path from vertex A to vertex B?" As a beginner software engineer, this may be overwhelming. But don't worry, in reality, this is basically like saying, "We have the map of the United states, that has a bunch of states with multiple roads connecting them and we can drive on those roads on either direction. In addition to that, some of states, like Alaska or Hawaii, may not be accessible by roads at all. Given that information, what do you think is the shortest way to drive from New York to California?" Not that bad now, eh? This is basically how maps work. Think of graphs as "less structured trees". In fact, a tree is a special type of a graph -- a connected, acyclic and typically undirected graph.
But on occasion, graphs are also a bit sneaky, in that they appear even at places where you'd think they don't belong. For example, consider a spelling checker. You know the one that underlines misspelled words with those squiggly red lines? Well, one of the ways you can build something like that, is by modeling dictionary words as a graph and then using an algorithm called Edit Distance or Levenstein Distance to figure out whether a word could be misspelled. Modeling non-graph-like structures as graphs can be a bit tricky and takes some practice.
Project - ThoughtWorks Trains Problem
The local commuter railroad services a number of towns in Kiwiland. Because of monetary concerns, all of the tracks are 'one-way.' That is, a route from Kaitaia to Invercargill does not imply the existence of a route from Invercargill to Kaitaia. In fact, even if both of these routes do happen to exist, they are distinct and are not necessarily the same distance!
The purpose of this problem is to help the railroad provide its customers with information about the routes. In particular, you will compute the distance along a certain route, the number of different routes between two towns, and the shortest route between two towns.
Input
The input is a directed graph where a node represents a town and an edge represents a route between two towns. The weighting of the edge represents the distance between the two towns. A given route will never appear more than once, and for a given route, the starting and ending town will not be the same town.
Consider this graph as an example input: AB5, BC4, CD8, DC8, DE6, AD5, CE2, EB3, AE7
This is the input graph, where the towns are named using the first few letters of the alphabet from A to D. A route between two towns (A to B) with a distance of 5 is represented as AB5.
Output
You program is expected to produce the following 10 pieces of information as output about the input graph:
1. The distance of the route A-B-C.
2. The distance of the route A-D.
3. The distance of the route A-D-C.
4. The distance of the route A-E-B-C-D.
5. The distance of the route A-E-D.
**For 1 through 5, if no such route exists, output 'NO SUCH ROUTE'. Otherwise, follow the route as given; do not make any extra stops! For example, the first problem means to start at city A, then travel directly to city B (a distance of 5), then directly to city C (a distance of 4).
6. The number of trips starting at C and ending at C with a maximum of 3 stops. In the sample data below, there are two such trips: C-D-C (2 stops). and C-E-B-C (3 stops).
7. The number of trips starting at A and ending at C with exactly 4 stops. In the sample data below, there are three such trips: A to C (via B,C,D); A to C (via D,C,D); and A to C (via D,E,B).
8. The length of the shortest route (in terms of distance to travel) from A to C.
9. The length of the shortest route (in terms of distance to travel) from B to B.
10. The number of different routes from C to C with a distance of less than 30. In the sample data, the trips are: CDC, CEBC, CEBCDC, CDCEBC, CDEBC, CEBCEBC, CEBCEBCEBC.
Example:
Input: AB5, BC4, CD8, DC8, DE6, AD5, CE2, EB3, AE7 Outputs: Output #1: 9 Output #2: 5 Output #3: 13 Output #4: 22 Output #5: NO SUCH ROUTE Output #6: 2 Output #7: 3 Output #8: 9 Output #9: 9 Output #10: 7
Resources
Self Assessment
Module - Final Project
The final project is open-ended. I encourage you to try to come up with your own ideas and build something interesting using all or most of the topics you have learn from module 0 through 9. You can even use the code from the previous projects as a starting point.
Good luck!