Efficient Design
Series:Acing The Interview
Hello and welcome to the second post in my series, Acing the Interview! If you've already been following along, welcome back! Throughout this series, we'll be discussing topics like behavioral and technical questions, as well as design patterns, algorithms, and data structures. We will also cover areas such as mock interviews, how to discuss your projects, and what to expect during the day of the interview. If you are just joining us, I would highly recommend going back to the first post of this series on Behavioral Questions and reading through it all to be prepared for your interview.
Today, we'll continue on to the next topic of discussion, once again summarizing some examples from Cracking the Coding Interview 1 with some of my own experiences and insight. If you have the time though, I would highly recommend purchasing the book and reading it through to be prepared for your next interview. We have a lot of information to cover so let's get started with our next topic: Efficient Design.
"Knowledge has to be improved, challenged, and increased constantly, or it vanishes." -Peter Drucker
There are 4 main topics that I've included into the category of Efficient Design. These areas include:
Big O Notation
The big O notation is a fairly straight forward concept, which describes the time (run-time) and space (memory storage) complexity of your code using algebraic terms. This notation is used to describe the worst-case performance of your algorithms and determines if that algorithm will scale well with a larger data set. For example, when looking at a typical example of O(n2), which is typically pronounced as "Big O squared", we can understand that an algorithm will run in quadratic time, where the runtime gets slower as the data input grows. It is one of the most fundamental tools for computer scientists as it helps to analyze the cost of an algorithm. Due to its ability to determine cost, it is also a good practice for software engineers to understand this concept as well.
The most important aspect to remember about big O notation is to not over-think it. The reason that we look at the worst-case scenario with this notation is because it is O(mn) (a.k.a. exponentially) easier to do so then looking at the best-case and/or average-case of the function...see what I did there😉. If a function takes the same amount of time and space to execute, regardless of the size of the input, then it's time and space complexity is O(1). If the time/space to execute is proportional to the size of the input, then its big O notation is O(n), where n is the size of the input. If you are working with nested loops, where each loop has the same input, then you're looking at an O(n2) complexity, which runs in quadratic time. With this big O notation, as the input for the function grows, the runtime will get slower.
This might seem complex at first but, with a little bit of patience and practice, you will quickly realize that it's no more difficult than looking at a couple lines of code, identifying the time and space consuming statements, and determining how they interact with each other. From there, it's just a matter of writing down a couple of numbers and letters in the right format.
Data Structures
A data structure is a named location that can be used to store, organize, and retrieve data in a particular way so that it can be used effectively. One such example of a data structure is the array, which allows us to store a list of items having the same data-type. Other types include, but are not limited to, stack, queue, and binary tree, which all allow us to store a list of items having the same data-type. The major difference between these 4 data structures is in their implementation of how they store, organize, and retrieve data.
For example, a stack is a linear data structure, where elements are only allowed to be inserted and deleted from one side of the list, called the top. When an insertion occurs, it's called a push operation, and the pop operation is when a deletion occurs. For these types of data structures, the order of insertion and deletion is LIFO (Last In First Out), much like how you might typically add or remove dinner plates from the cabinet.
| 4 | 11 | TOP |
| 3 | 4 | |
| 2 | 6 | |
| 1 | 15 | |
| 0 | 8 |
On the other hand, a binary tree is a finite set of one or more nodes, where one node is designated as the root node, and the remaining nodes are separated into sets, called the subtree of the root. Each node must have a parent node, and may have no more than 2 child nodes. Also, each node contains a value and the references to its children.
Each of these data structures have use cases where their big O notation will be better than the rest, and its up to you to know when that may be. With a little bit of research and practice though, you will be able to spot these use cases quickly and implement the ideal data structure into your algorithms.
Algorithms
An algorithm is simply a collection of steps used to solve a particular problem. While there are many different types of algorithms currently in existence, they all tend to follow one of three different directions:
- Brute Force
- Greedy
- Hash Table
With a brute force algorithm, you detail out all possible solutions and check them for validity. For example, to get the highest product of 3 numbers in an array, grab every set of 3 numbers, multiply them, and keep track of the max. This will give you the correct answer after forcing each possible solution. This type of algorithm can be applied to most questions and is a great and helpful way to start the problem. Understandably though, it is usually not the most efficient, which leads us to the greedy algorithm.
With this algorithm, you keep track of the best answer you've seen so far, in one pass through the input. The tricky part to working with this solution is identifying what values you need to keep updated at each step in order to have the final answer when you reach the end of the input. This leads us to the last type of algorithm, hash table.
When it comes down to it, this will be the most common way for you to solve interview questions. The solution to these questions will often be a "counts" hash, mapping items to how many times they appear in the input array. Using something like a hash table, hash map, dictionary, etc. on the problem will almost always be the solution. This approach spends space (increases space complexity) in order to save time (decreases time complexity) but is typically an acceptable trade-off for a company. You could impress the interviewer by noting this in your solution and starting a discussion with them on which is more important for the company.
Design Patterns
When you combine data structures and algorithms in your solution and apply it to a common problem, you will likely find a design pattern that exists to solve that particular issue. A design pattern is a solution for a commonly occurring problem that exists when designing software. These patterns are almost always "evolved" and built upon over time instead of being "discovered" in a single instance.
It's important to note that design patterns are simply guidelines to follow for a particular solution and will not force any specific type of implementation. These patterns should also not be blindly applied to your code base and only when needed to make maintainable, extensible, and reusable objects. The code implementation is always your responsibility as the developer.
There are three different types of design patterns to cover, including:
- Creational
- Structural
- Behavioral
Creational design patterns makes the creation process more adaptable and dynamic by replacing the direct instantiation of an object with constructors. These patterns can provide a lot of flexibility for the developer when looking at which objects are created, how they are created, and how they are also initialized. The structural design pattern provides us with solutions to bring together different parts of a system in a flexible and extensible fashion. With this type of pattern, you can guarantee that when one part of the system changes, the rest of the application does not need to change along with it. Lastly, we have the behavioral design pattern. These patterns take an action that is used by an object or class and abstracts it out to reduce complexity and increase efficiency. With the action abstracted, we can change the algorithm used, the objects affected, or the behavior, while still retaining the same basic interface for classes or objects that use that action.
This topic might seem like a complex and scary one to learn, but I promise you that is only due to the sheer amount of data structures, algorithms, and design patterns that currently exist in the programming world. By breaking these items down into smaller chunks to study and learn, the process will become a lot more easier for you to work through. I can't promise that it will be a quick topic to study or one that everyone will pick up on right away, but, with some patience and consistent practice, you will be pulling these topics up in conversation without even realizing it.
As mentioned previously, there are numerous sources to help you master each and every one of these topics. One such resource is the Cracking the Coding Interview 1 book by Gayle Laakmann McDowell. This book has a tremendous amount of information on topics such as the big O notation, data structures, core algorithms, strategies to tackle algorithm questions, as well as 189 programming interview questions with hints and solutions for each. This book was a vital resource for me as I went through the preparation for my interviews and might be vital to you as well. McDowell does an excellent job of giving insight into the interview process of major tech companies, as well as giving detailed walkthroughs of each interview questions so that you don't only know that answer, but you understand why that is the correct answer. If there is only one resource that you take away from this entire blog post, I would highly recommend it to be that book.
If you enjoyed the post, be sure to follow me so that you don't miss the rest of this series, where I dive deeper into preparing for the interview, and what to expect the day of, so that you too can Ace the Interview! The links to my social media accounts can be found on my contact page. Please feel free to share any of your own experiences with the interviewing process, general questions and comments, or even other topics you would like me to write about. If this series of posts help you land that dream job of yours, be sure to let me know as well. Thank you and I look forward to hearing from you!👋