To watch the youtube video explaining this topic, please click here.
Given a signed 32-bit integer, reverse its digits. If there's an overflow after reversing, then return 0. (Problem on Leetcode.)
String Solution (without Handling Overflow)
An easy solution would be to convert the integer to its string representation -> reverse that string -> convert the string back to an integer.
In the case of a negative number, we can make the number positive for the string conversion, then make it negative again before returning the final answer.
This is a pretty clean algorithm, but if you run it in Leetcode you'll likely find that your answer is wrong for some solutions. That's because this algorithm is susceptible to integer overflows.
An Integer's Bit Representation
Let's understand how an integer is represented. A 32-bit integer is literally 32 bits (0 or 1) put together in binary format.
The maximum number we can create using 32 bits is by using 32 1's, which equals 4,294,967,295.
So an unsigned 32-bit integer's maximum value is 4,294,967,295, and the range of numbers you can represent using 32 bits would be [0, 4,294,967,295].
However, a signed integer means we want to be able to include negatives numbers. The easiest way to think about this is that we want to take the maximum value for a 32-bit integer and split it in half, and allow half of the value to count toward negative numbers and the other half to count toward positive numbers.
4,294,967,295 / 2 = 2,147,483,647.5
So the range of a signed integer will be [-2,147,483,648, 2,147,483,647].
String Solution (Handling The Overflow with a 64-Bit Integer)
Looking back at out problem of reversing a signed 32-bit integer, if we tried to reverse 2,147,483,647 then we would get 7,463,847,412 which is definitely an overflow, since it goes over the maximum value a signed integer can be. The problem asks us to return 0 if we overflow.
One easy way to do this is to use a 64-bit (signed) integer to store the reversed value. The range for a 64-bit integer is [-9,223,372,036,854,775,808, 9,223,372,036,854,775,807], which will comfortably fit any flipped 32-bit integer.
The only difference in our code is now we work with 64-bit integers, use string_to_long, and have a couple of new if statements to check if we overflowed after reversing.
The time complexity of this solution is O(number of digits). However, this O(N) involves converting the integer to a string, reversing the string, and then converting back to a number. Those are expensive operations.
Mathematical Solution (With 64-Bit Integer)
The string solution works but has expensive operations converting integers to strings and vice-versa. We can optimize by directly using math to convert the number to its reversed form.
Basically, we go through each digit from right to left and make that the digit of our reversed number.
This solution is still O(number of digits) but the operations (modulus and divide) are less expensive.
Mathematical Solution (Only Use 32-Bit Integers)
The truth is in a real interview, if you're asked this question, the interviewer isn't going to let you use a 64-bit integer. It's basically cheating. We can't just throw more hardware (in this case, bits) at all of our problems, and we need to stay within the confines of the types we have. This is especially true for low level programming.
We can eliminate the use of 64-bit integers by, at each step, checking if we're going to overflow if we were to add the next digit.
The time complexity is still O(number of digits), but we added three if-statements at each step, so the code is going to perform slightly worse.
To watch the youtube video explaining this topic, please click here.
Introduction - N-Queens
N-Queens is an interesting problem. It requires knowing the Backtracking algorithm to solve efficiently, and also requires a fair bit of code compared to standard algorithm questions.
In this blogpost, we'll solve the N-Queens problem. If this is your first time seeing Backtracking, please look at the previous tutorial on Backtracking on an easier problem. Additionally, our solution will show "good object oriented code" since we'll utilize a class structure to solve this (as opposed to pure code inside of functions).
Given a number n, return all valid nxn chessboards that have n queens placed on them such that no Queens are attacking each other. (Problem on Leetcode.)
We're going to create an nxn chessboard and we continually try to place Queens on it (and if the board ends up valid with n queens on it, then we add it to our solution set), but we're going to be smart about how we place the Queens. Specifically, we're going not going to place Queens on a spots that are already being attacked.
Let's represent the chessboard as a matrix of integers. -1 means a Queen is on a cell, otherwise the number represents the number of Queens that are attacking that cell.
The flow is to try adding Queens on a valid cell -> update the board to mark the positions she attacks, and then try adding more queens. Whenever we reach the end of a board (no more Queens can be added or we're at the final cell), we add the board if possible, and then we backtrack by removing the previous Queen we added and try placing a new Queen somewhere else.
In our case of backtracking, our shared state is the chess board, and we recursively place Queens (and update the board) and then remove that Queen (and update the board).
In addition, some optimizations we'll take advantage of are:
The C++ code that solves this problem is:
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.
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.