To watch the youtube video explaining this topic, click here.
Docker is a tool for containerizing projects so that any required dependencies (libraries) can be installed in isolation within the Docker container and doesn't have to be installed on the host computer.
This is good practice because it:
In this blogpost we'll look at Dockerizing a simple project.
Your computer must have Docker installed to use it, of course. Docker installation varies depending on your operating system, so google for a guide.
This previous tutorial shows how to install Docker on older versions of Ubuntu linux.
On newer versions, of Ubuntu Linux, you can install docker using the following command:
And test it with:
Setting Up A Test Project
The best projects to Dockerize are backend servers, so let's take a very basic Hello World server.
This repository has the bare minimum code required to run a Node.js server.
If you have node/npm installed locally, then you can try running this project locally.
And go to localhost:3000 in your browser to ensure the server gives a response.
(If you don't have node/npm installed, then don't worry because we'll be dockerizing the project in the next section to not need to have them installed locally.)
Dockerizing The Project
To dockerize the project, we must add a Docker file to our project.
There are a few things we need to specify in our Dockerfile:
Open the Dockerfile and paste the following code inside of it:
Additionally, we're going to specify a Docker Ignore file, which works similarly to a Git Ignore file; it will specify files in our project folder that we don't need copied into the Docker container. (It's good practice to make the Docker container as small as possible.) For example, we don't need to copy our local node_modules folder since we want to rebuild it inside the container, anyway.
Create the Docker Ignore file:
Open .dockerignore and add the files/folders we don't need copied over into it:
Now our codebase is Dockerized. How do we run the server locally? First we need to build a Docker image for our project, and then we'll run that image.
To build the Docker image:
We can see the image we just built in our list of docker images.
To run the Docker image we just built:
Note that the internal Docker container is using port 3000, but we're specifying our local computer to connect to the Docker container on our computer's port 8000. (This is just for clarity, feel free to use the same ports.)
We can now see our server running on port 8000 on our computer, without needing Node or NPM installed. Check at localhost:8000 in your browser.
And that's it. The next steps would be to commit the Dockerfile (and docker ignore file) to our project's repository and update our README for the new deployment steps.
Dockerization of a project is pretty simple and has many benefits. It's useful when working with multiple people and setting up CI/CD. All it takes to Dockerize a project is creating a Dockerfile and using a few new commands to work locally.
The next blogpost is going to be on using docker compose, which helps create more complex local systems.
We'll also be doing a tutorial on CircleCI, and Docker will help with our CI steps.
Like this content and want more? Feel free to look around and find another blog post that interests you. You can also contact me through one of the various social media channels.
To watch the video explaining this topic, please click here.
Backtracking is a technique when using recursion (DFS). The trick is:
Basically, because DFS is deterministic and goes in a "depth-first" order, at each level we can edit information, which keeps the "state" of our system the way we need it to for the next level's recursive calls, and then we can undo the change we made for whenever we go back up to the previous level.
A good analogy of this is a kitchen. Pretend we have a kitchen that only one person is going to use at a time.
Similarly, using backtracking in DFS means we can have shared variable without having to create a new one for each recursive call. This saves time and memory.
[Leetcode Medium] Word Search (Boggle Problem)
Given a 2D board of tiles (letters) and a word, check if the word exists in the board.
We'll try each tile as the beginning of our traversal, and what we'll recursively do is:
The "backtracking" part of this solution is that we're changing shared state (step 2), making recursive calls, and then undoing our change for when we go back up to previous levels.
Here's pseudocode for our solution to the boggle problem:
Full Code (C++)
The full C++ code, which corresponds to the "Word Search" problem on Leetcode, is as follows:
To watch the youtube video that goes over this topic, click here.
A Trie is a tree data structure that stores sequences in a way such that overlapping elements (in the same position) can share the same node.
For example, "apple" and "apply" are two distinct sequences of characters, but they both share the initial sequence "appl".
A Trie is implemented as a tree. Each node of the tree holds:
Trie's Underlying Data Model
As the picture above shows, a Trie is represented as a tree of nodes. However, unlike a binary trees where each node can just have a left and right pointer, you have to decide how many pointers each Trie node is going to have.
For example, a Trie that holds characters only containing the lowercase English alphabet will need exactly 26 pointers to other nodes. Or maybe our Trie holds phone numbers, in which case we expect only digits and each node holds 10 pointers (one for each digit).
We could hardcode each pointer if we know exactly what our Trie is going to hold.
We can clean this up by using an array (which still requires knowing the mapping. Ex. next maps to the character 'a').
A more flexible approach (but potentially less efficient) is using a hash map, which means your Trie can scale to as many nodes as required without needing to know exactly how many ahead of time.
Now we can handle unexpected character inputs like punctuation (! ? &) or special characters.
We initialize our Trie with an empty root TrieNode, and from that rootnode we add/update nodes as necessary with methods designed to traverse and edit TrieNodes.
Trie Operations (with Pseudocode)
As with most tree data structures, traversing nodes is best done with recursion or iteration. Most of the operations we'll see utilize iteration, but recursion is also fine.
Initializing the Trie
Assuming we have our TrieNode structure set up, we start by initializing an empty node to be the root of our tree.
If we want to insert a sequence into our Trie, we iteratively traverse the Trie for each element in the sequence. If the node doesn't exist for a certain element in the Trie, then we create it. At the last element of the sequence, we mark the node as endOfSequence=true to indicate that node ends a sequence.
To check if a sequence was inserted into our Trie, we iteratively traverse the Trie. If we ever find that one of the elements in the sequence doesn't have a node for it in the Trie, we return false. If we get to the end of the sequence and the node in Trie doesn't have endOfSequence==true then we return false. (This can happen in cases where we inserted longer sequences. Ex. Insert "antler" but check if our Trie contains "ant".)
To check if there's any sequence in our Trie that starts with a sequence, we can iteratively traverse the Trie and make sure each element of the sequence has a node in the Trie. For example, check if any sequences begin with "ant".
(This is very similar to the Contains operation so code is omitted in this blog post. See the full code on github to see how it's implemented.)
The time and space complexity for all of these operations are O(number of elements in the sequence). Tries are very efficient.
To see full Trie code, see the code I wrote on github that creates a Trie class.
When To Use Tries
Tries are really good data structures if you need to:
To test your knowledge, Leetcode has a problem on implementing the methods of a Trie.
Hi, I'm srcmake. I play video games and develop software.
Pro-tip: Click the "DIRECTORY" button in the menu to find a list of blog posts.
License: All code and instructions are provided under the MIT License.