00:00:11.980
Hello everyone! We're going to go ahead and get started because this talk, when I practice, hits right at 40 minutes, and I want to make sure that you don't miss out on any content. So, if you are here for "Fun, Friendly Computer Science," you're in the right place. This talk is going to be your computer science quick hits.
00:00:31.670
We're going to cover seven computer science topics in about 35 minutes. Since we don't have much time, I am mainly focusing on fundamental and introductory object-oriented concepts. There's a whole world of computer science out there, but I cannot fit it into 40 minutes. If you have familiarity with loops, arrays, and classes, you'll have no problem following along. This is a beginner-level talk.
00:01:04.100
My name is Mercedes Bernard, my pronouns are she and her, and I am an engineering manager and senior software engineer with a consulting firm in Chicago called Tandem. My background is in traditional computer science. I have a bachelor's degree in it from DePaul University, but the longer I am in this industry, the more I realize that I don’t need to know all of that, or at least not to the depth that they teach it.
00:01:20.420
If you came into software from a non-traditional career path—whether you went to a code school, taught yourself, or jumped around and tried a lot of different careers—you may have never had the opportunity to learn these items. But you'll still be interviewed on them.
00:01:31.340
If you are more of a front-end engineer, be aware that tech interviews can be broken. Many interviewers don't know how to interview properly. Even though you might be doing lots of CSS, you might still get asked to implement a linked list, which raises the question: why would you ever need to do that? My goal with this talk is to show you that the topics that show up in interviews and that are sometimes used for gatekeeping aren't intimidating and aren't truly that important.
00:01:50.180
You probably know most of what I'm going to cover today; you just don't have the right vocabulary to express it. The important takeaway is that you can get by without ever learning this in depth. You will walk away from this talk with a high-level understanding of a range of concepts, including some helpful metaphors for explaining them and code samples that you can refer to later if you want to explore further.
00:02:11.120
If you're thinking, "Oh, this is beginner stuff; I know all of this and don't need it," I guarantee you there's still something in here that you can take away to help explain these concepts to the people you mentor. If you are someone who likes visual aids and would prefer to have the slides up close—especially because there will be code samples—you can find the slides posted online to follow along.
00:03:06.370
There will also be code samples in this talk, available on my GitHub. If you do pull those down, be sure to check out the commits I made; I did a very good job with them. Each commit corresponds to a concept and has a great commit message. There's test coverage, so you can view unit tests for some concepts; often, the tests illustrate what I'm trying to explain better than my explanations. All the code is runnable, allowing you a working UI to play with if you learn more by doing than by reading.
00:03:24.490
If you are here, I assume you write Ruby code, but I also have repositories for JavaScript and Python if you are more familiar with those languages or just want to see how they compare. Alright, let’s get started! So, do we have anyone here who is really good in the kitchen? Who likes to cook or bake? Awesome! Don’t call me out if I get this wrong because I’m terrible at it.
00:04:00.130
But if you’re good at cooking, there’s this concept called cooking with ratios. Cooking with ratios is where you don’t memorize a recipe but instead memorize the ratios of the ingredients. You can then change the proportion of your ingredients based on how much of a dish you want to make. Big O notation measures the relative complexity of a function or algorithm, usually in terms of running time.
00:04:39.580
However, we can discuss any computing resource—stack depth, CPU, memory usage, etc. For our examples, we will focus on running time. Big O is also language, hardware, and time agnostic; if I upgrade my laptop and my code runs faster on it than on yours, it doesn't change the relative complexity of the code. It is measured in proportion to the input size and analyzed in a worst-case scenario.
00:05:33.520
When someone provides a sorting algorithm, they want to know the Big O notation in the worst-case scenario, not when the collection you handed them is almost sorted. I'm going to break down some of the Big O complexities. The first is O(1), which represents a constant running time. No matter how your input size changes, it always takes the same amount of time to run.
00:06:30.880
For example, if I'm making cupcakes, which follow a 4-3-2-1 ratio—4 eggs, 3 cups of flour, and so on—if we are combining butter and sugar, we would beat them with an electric mixer for three minutes. It doesn't matter if I'm using two cups of butter or four cups of butter; it consistently takes three minutes. So, that's O(1). The next most common complexity is O(n), indicating that the running time increases directly with the input size, signifying linear complexity.
00:07:38.490
If the recipe states that with each egg added, you beat it for one minute, then for four eggs, it takes four minutes, and for eight eggs, it takes eight minutes—a linear increase. Now, moving to O(n²), if I want to combine flour, milk, and butter very slowly to avoid chunky flour, that may take longer. Generally speaking, whenever you see a nested loop, it is likely O(n²). If we have O(n³), it becomes worse in performance.
00:08:58.000
Let’s say I’m making cupcakes to celebrate Fibonacci’s birthday; calculating Fibonacci numbers is O(2^n) and represents exponential growth. At first, increases in input size do not yield significant increases in running time, but as you increase the size, running time can increase steeply. The converse of exponential growth is logarithmic growth, O(log n), which approaches constant time as input size increases.
00:10:36.630
Divide and conquer algorithms usually exhibit logarithmic time behavior. A common example is binary search. Logarithmic growth is evident when you repeatedly divide a dataset into two halves until the entire dataset is narrowed down.
00:11:53.960
Now, why do you use Big O notation? It comes up often in interviews and is a helpful mechanism to have a shared language with other programmers to compare the performance of two different approaches to the same coding problem. However, if you don’t remember what O(n) or exponential growth is, that’s okay. Walking away with a general understanding that the more you nest loops, the worse the performance gets is beneficial.
00:12:30.290
Next, we’ll discuss set theory. Venn diagrams are a great way to view set theory. A set is a data structure similar to an array but is characterized as an unordered collection with no duplicates. Set operations are more interesting because they allow for mathematical computations. The first operation is called Union, which is the combination of two sets. This can be represented as X ∪ Y.
00:14:18.950
It encompasses everything that exists in set X or in set Y. The converse is intersection, which is X ∩ Y, in which we consider only the elements that exist in both sets. The set difference, expressed as X - Y, encompasses the elements in set X but not in set Y. Moreover, mathematicians and computer scientists love to complicate things; therefore, the relative complement has its own notation, Y ackslash X, which represents everything in Y excluding those in X.
00:15:24.600
Lastly, we have symmetric difference, represented as X Δ Y. This denotes the items that exist in either set X or set Y but excludes those within their intersection. Why do you use Venn diagrams? If you have ever utilized relational databases to write SQL, you engage with set theory through inner joins and other operations.
00:16:11.820
From a feature implementation standpoint, consider website filters as an application of set theory. If you're purchasing shoes and can select sizes like six and six-and-a-half, that falls under union operations, whereas choosing shoes in different colors may represent an intersection.
00:17:29.580
Next, let’s talk about recursion. Russian nesting dolls serve as a great metaphor because they relate to size—inside each doll, there’s another doll, which you can keep opening until you reach the smallest one. Recursion is when a function calls itself, either directly or indirectly. The function that does the calling is called the recursive function.
00:18:54.540
When writing a recursive function, it's critical to avoid infinite loops or stack overflow exceptions. You need a base case, which is a finite, discrete value that signals when the recursion should stop. In our nesting dolls example, the smallest doll serves as the base case. When programming a recursive function, return one upon reaching the smallest doll and increment as you return back up the stack.
00:20:17.320
You can achieve anything iteratively or recursively, but recursion is sometimes hard to read and understand. It works best for solving problems with nested hierarchies. When structuring a mega menu or rendering file systems, recursion is often very useful. Now let’s delve into the four principles of object-oriented programming.
00:21:48.490
If ever asked about the four principles of object-oriented programming in an interview, you can confidently answer them. The first principle is encapsulation. For instance, we can illustrate this with horses; they have four main gates: walk, trot, canter, and gallop. When coding, you wouldn't want to detail every step of a horse's movement. Instead, you would have methods that encapsulate the state of the horse's legs.
00:23:36.870
Encapsulation hides an object's state from any other object, allowing you to create a public interface through methods to alter an object's state safely. The next principle is abstraction, which extends encapsulation. Abstraction refers to hiding the internal implementation details of a class while providing a limited interface for interaction.
00:24:44.210
The third principle is inheritance. For example, consider a scenario where all plants require sunlight, soil, and water. In a programming context, if we create a class for plants with information on their care, we might use inheritance to share methods that output this information.
00:25:58.550
A child class can inherit method properties from a parent class, illustrating a plant's care instructions. Lastly, the fourth principle is polymorphism. This is where different classes might implement the same method in different ways. For instance, in crafting fabric, you might have knitting, weaving, and crocheting, all of which can have similar method names but they are implemented differently.
00:27:50.910
Regardless of the implementation, you can still initiate the fabric creation method in a consistent manner, demonstrating true polymorphism. We've successfully covered a lot of content, and while I had to cut out a section on data structures, you can find the slides along with all code samples on my website.
