DEV Community: Brad Goldsmith

And the job search is on

Brad Goldsmith — Sat, 23 Sep 2023 20:33:02 +0000

I'm writing this because honestly I'm not sure how else to express how I feel. I'm currently looking for a job and have been processing the past few weeks in my own way. This is just a way for me to personally get some closure on a situation that I never thought would happen to me. It has nothing to do with tech or dev just a story about what happened to me a few weeks back.

So on September 8th I got an invitation to a call for 12:00pm and it was roughly 11:45am. I hopped on the call and should've known from the get go something was wrong as it was a service that we don't use at work. Myself and 20 plus other talented employees, from web application developers, to managers, to migration assistants, to hr employees just to name a few, were all laid off. During this call we were kicked out of our company slack, emails, and all other web services. I personally have never felt like more of a criminal in my life, and to be bluntly I've gotten arrested before. A mass layoff where all of our microphones were muted and no one was able to ask any questions. Medical benefits ending at midnight, so gotta immediately get a prescription filled, a two week severance, and not even a true explanation of what happened.

Just over two weeks now and I guess all I can say and I still have no closure and never will. I joined the company three months prior and left a relatively great job based on what the CEO and others sold to me. In the end the decision to job hop was mine and mine alone and I completely understand that but upper management always spoke of transparency and there wasn't any signs or warnings. In fact prior to that 12pm call we were all told to put in our holiday PTO and I had just finished up a project after working till 10pm the night before, and for what?

This was my first layoff from a company and truly the first time I felt disposable in my programming career. In the 5 almost 6 years I always felt like I had job security until now. I have never left a job without having one and have never looked for a job without currently being employed. This is just a really odd situation for me right now. It gets so much worse because CEOs and companies don't realize what they truly are doing to people. So yea I'm losing out on a vacation that I had planned, tickets, accommodations, but that's not the real kicker. I have a new home build set to be completed at the end of October and now without steady income obtaining a mortgage is 100% in jeopardy.

I'm not saying that I'm special in compared to the other people who got were let go as well but during the interview process I felt like I got to know the upper management and we had a 1 on 1 conversations and I explained to them I'm building a home. In the end I left a good paycheck to pursue something that I thought had potential. I took a huge risk on this company and I have no one to blame but myself.

So now that that is done I'm applying everywhere to find my next role. Probably going to have to take a 20-30k pay cut but at this point I just want some stability back in my life. The thing that bothers me the most about this entire situation is that during my interview process I asked about stock options because I thought this company was a startup and multiple times from HR and from the CEO himself I was told options are not available because we are done with our rounds of funding. Turns out that wasn't the case and the reason we were all laid off was a money issue.

That's about all I have to say here but I'm gonna continue writing about the application process and how it's going. I feel like writing things like this is good for me and keeps my spirits up. Thanks so much for taking the time to read this and have a wonderful day and weekend.

Data Structures and Algorithms - Sliding Window Pattern

Brad Goldsmith — Mon, 23 May 2022 13:37:44 +0000

So this one here is a pretty cool pattern to recognize and be able to implement. Anytime you have a problem where it involves sub arrays you should always considering using this pattern. First off anytime you can use a sliding window you can also brute force it with multiple for loops and conditionals. So in a situation where you want to get something done you are more than welcomed to brute force all you'd like, however in most interviews or tech problems you would fail based on quadratic or exponential time complexity. When working with smaller sets you'd never realize just how long these take. Let's look at this first type of problem where we want to return the longest substring without repeating characters. I've seen this problem on LeetCode and I believe HackerRank, and I'm guessing there are many versions of this question out there. It's a classic sliding window problem. So lets look at this generic problem where we try to find the max consecutive sum of an array of numbers. This method will take in an array, and number which is consecutive elements in the array. Lets say we have the following array:
[10,22,32,13,5,9] and our number passed in looking for consecutive elements is 3.

By using the brute force method we can do 2 for loops and we'd come up with the following arrays to add up and get a total and then compare:

[10,22,32]
[22,32,13]
[32,13,5]
[13,5,9]

And this approach will 100% work but it is definitely not an efficient way of solving this problem. If we look at the first two arrays what are the differences? Well in the first array we start with 10 and in the second array we end with 13, that means the 22 and 32 happen to be in both arrays and since they are why would we want to add them up again? So in this case take our first sum which is 64 we'd subtract the first element (10) and add the next element (13) which would look like: 64 - 10 + 13, which would give us 67 which would be a new max value. This is the idea of the sliding window. We start with an initial window and then "slide" it over.

So to make this work the first thing we'll have to do is get the very first sum of the subarray and in this case a simple for loop will work just fine. I like to make a tempSum variable too so that I can use the Math.max() method and compare our maxSum to the tempSum (next window element) and see if we need to adjust out new total. Now all we need to do is start a second loop starting at our consecutive number passed in and we now get our new tempSum which would be tempSum - arr[i - num] + arr[i] and if it's larger than the maxSum we'll store it. So as you can see we never create new arrays we just use basic arithmetic to get the new sum and compare. So here is my final function for it:

function maxSubarraySum(arr, num) {
    if(num > arr.length) return null;
    let maxSum = 0;
    let tempSum = 0;
    for(let i = 0; i < num; i++) {
        maxSum += arr[i];
    }
    tempSum = maxSum;
    for(let i = num; i < arr.length; i++) {
        tempSum = tempSum - arr[i - num] + arr[i];
        maxSum = Math.max(maxSum, tempSum);
    }

    return maxSum;
}

So the first thing that you should always do with any type of coding problem is account for the edge case(s) which I do in the first line. And there is the pattern!!!!!!!

Data Structures and Algorithms - Radix Sort

Brad Goldsmith — Mon, 23 May 2022 00:29:08 +0000

The previous two intermediate sorting algorithms that I "learned" were comparison sorts. We compared values and swapped them, at the most basic level. And now that I think about it this is the case for the elementary sorts as well. The one thing to remember is the best time complexity that we can achieve with these comparison sorts is logarithmic, which is not horrible but we'd like to do even better, and this is where Radix Sort comes in. One thing to note is Radix Sort and other non comparison sorts will not guarantee a better time complexity than the other sorting algorithms, just in specific cases they are much more efficient. Radix Sort is a special sorting algorithm that works on lists of numbers, usually binary. We could actually convert a list of strings to integers and then use the Radix Sort but at that point you'd be better off selecting a different type. The way that this algorithm works is by exploiting the fact that the information about the size of a number is encoded in the number of digits. What exactly does that mean though?

Well if a number has more digits its a larger number. 300 has 3 digits (3,0,0) where 95, has two digits (9,5) so we can safely assume based on digits that 300 is larger than 95 and also because we just know that lol. The way this works (and this is for base 10 numbers, no decimals, for now) is we have 10 "buckets" 0-9, and we place numbers in each bucket based on their last (right most) digit. We do not sort in within the bucket rather just place them there. We then place them back into a list based on their bucket order, so even though 9 is smaller than 1000, 1000 would be first based on it's right most digit is 0. The process is then repeated based now on the second digit from the right. Any number that does not have a second digit from the right, say 9 would be put in the 0 bucket since its second digit from right is 0. We continue to repeat this process until we have hit the largest most value. The number of times we repeat this process is by the number of the largest digit number.

. Here is an example that kinda shows you what is going on.

To implement Radix Sort we have to write a few helper functions, just as we did before, wether that be pivot, swap, merge, etc... One helper function we'll need to write is a method that returns the digit in the number at a give place. so lets say we have getDigit(number, place) we'd expect the following results:

getDigit(93824, 0);  //4
getDigit(93824, 1);  //2
getDigit(93824, 2);  //8
getDigit(93824, 3);  //3
getDigit(93824, 4);  //9

Hint hint for this one there is no reason to reinvent the wheel. Stackoverflow has many solutions and here is one of them:

function getDigit(number, place) {
    return Math.floor(Math.abs(number) / Math.pow(10, place)) % 10;
}

The next helper method we'll need to create is how many digits are in the numbers. Why? Well because the largest one will be how we determine just how many times to sort into buckets / reorder. We'll call this digitCount(number) and we'll get some more great code from Stackoverflow and get:

function digitCount(number) {
    if(number === 0) return 1;
    return Math.floor(Math.log10(Math.abs(number))) + 1;
}

Our final method to create is one that given an array of numbers return the largest digitCount in that array, and as you can see we'll use our previously defined method. By using Math.max(num1, num2) we can compare and return our max value. Here we go:

function mostDigits(numbers) {
    let maxDigits = 0;
    for(let i = 0; i < numbers.length; i++) {
        maxDigits = Math.max(maxDigits, digitCount(numbers[i]));
    }
    return maxDigits;
}

For the actual Radix Sort we'll need to:

Find the largest digits (mostDigits())
Start a loop from 0 until the return of the previous step
create buckets for each digit, which is an array with 10 sub arrays each starting empty.
place each number in the proper corresponding bucket based on whichever "digit" we are comparing (we'll be using 'getDigit()` here).
Replace our array (reorder) with the values from the buckets from 0 -> 9
return a list (all sorted woot woot!!!!) Radix Sort.

Data Structures and Algorithms - Quick Sort

Brad Goldsmith — Sun, 22 May 2022 13:40:29 +0000

The next intermediate sorting algorithm we'll discuss is Quick Sort. The general idea of Quick Sort is to choose a "pivot" point for comparison, and this can be any item in the array. Then what we do is compare the other values to that and smaller ones get placed to the left and larger ones you guessed it get placed to the right. Once completed we can now assume that our pivot point is in the right place of the array. So we break down our initial array into 2 arrays based on their values being larger or smaller than our selected pivot value. Then in these newly formed arrays we select a new "pivot" point and we repeat the process. As you guessed it since we are repeating over and over again the best way to do this would be to use recursion, and again completely understanding this one gets very tough very fast. It is much harder to conceptualize it than Merge Sort (in my opinion). Ideally you should use the same pivot index in each call, I like to use the first or last element of the array however you can use any. Here is a quick visualization of how this algorithm works.

.

Similarly to MergeSort we'll need to create a helper function so that we can do the comparisons with out pivot value and the array that is passed in. This pivot helper should accept three values, an array, a start index, and and an end index. Well then grab the pivot point from the start of the array, and again you can choose any point I'll just use the beginning for consistencies (ideally you'd choose the median value, however you might not know it so this will work, in fact any position will work). We will then loop through the array from the start to end index and compare our pivot value (index of 0) to the next value. If that value is greater we need to swap those 2 values and increase the pivot index, which for use will be 0 by 1. At the end of this function we'll return the pivot index.

So after watching videos over and over again and reading many different posts about Quick Sort I can 100% say that I just don't understand it. I can 100% talk about it and how it works but if anyone ever asked me to implement it from scratch I'd be in some serious trouble. I feel like with Merge Sort I could rebuild it based on just being able to talk about it where with this algorithm, I just cannot break it down to a point where it makes sense to me. So for you it might but I got nothing. I'm gonna keep trying and if I somehow manage a breakthrough with this I will definitely come back and revisit this post. But my interview with the big "G" is happening Wednesday and I cannot take time that I don't have to try and learn this particular concept better. QuickSort

Data Structures and Algorithms - Merge Sort

Brad Goldsmith — Sun, 22 May 2022 12:27:20 +0000

The first three elementary algorithms that I recently wrote about are not good for large data sets. They are good to know for certain scenarios but for lets say an array of 100,000 it would take 1000x longer (not sure about this factor but feel free to create an array with 100,000 values and do it on bubble sort and then compare to this when it's done). The idea behind this particular sort is:

splitting up
merging
sorting

Merge sort takes the fact that array with 0 or 1 elements are always sorted. It works by the divide and conquer approach. We break up our array into smaller array and continue that until we have arrays of 0 or 1 elements and then we merge them back together, and you probably guessed it but this can be done either iteratively or recursively. The recursive solution is definitely the "better" route to go however if you do not fully understand recursion (I may or may not lol) then iterative is probably better. Here is a photo that will more or less show you how it works:

So as you can see we continue to split up the arrays in halves until they are single elements and then once down to those single elements we compare them and build them up into smaller arrays, then compare two of those arrays (first elements, since they are sorted) and so on and so forth.

An easy way to start the implementation of merge sort is to create a helper function that takes in two sorted arrays and merge them. Remember these arrays can be length of 1 or 2 or 3 as long as they are sorted. This will be used over and over again until finally a fully sorted array is returned. In this function we'll need a counter for each array and an array to push values into, and then a while loop to continue to loop over until all values have been accounted for. So after this all we'll have to do is break down the initial input array into halves and then halves again until they have single lengths. This type of divide and conquer pattern can and will be used when doing breadth and depth first searches. If we want to find a value or a sorted array that is one million in length we break it down in halves each time and eventually we will land on our value that we are looking for. Extremely faster than iterating over every value and seeing if that value is the one we are looking for.

To break the initial array into halves we'll use recursion. So the plan is to split the array in half by using slice, which returns a copy so does not modify the original array. So once we have the "left" side we'll continue to call our function recursively until we have a base case which in our case is a length of one or less than one. Now when we have our base case arrays we'll call on our helper function to merge these two sorted arrays. Merge Sort. So I added (and please let it be known I just found this solution online) a fully iterative solution in case recursion does not make sense to you. The easiest way to visualize the recursion process in my opinion is to either write it down or and so you can truly see whats going on is in google developer console you can add your own code snippets in the Source tab. You can then write your JS code there (or copy paste mine) and add break points and watch the actual call stack and how it takes place. Listen I am not an expert in recursion and I'm trying to add it in my code where I can daily but you'll need to have a fundamental understanding of it before you can move on to more advance topics such and tree traversals. The final thing I'll say about this is how efficient this particular algorithm is. Well the time complexity is n log n which is not the best however it's 100% acceptable. The space complexity is solely big O(n) since we are not creating new arrays we are solely modifying them. So congrats on your first efficient / intermediate sorting algorithm.

Data Structures and Algorithms - Elementary Sorting Algorithms

Brad Goldsmith — Fri, 20 May 2022 18:40:04 +0000

When talking sorting, and javascript there is a very real chance you have use the Javascript array.sort() method. Since it has a built in sorting method what is the point of learning others? Well after going over data structures it is safe to assume that you should not always be using arrays, and if you are I highly suggest at least learning some others. The problem with the default sorting method for javascript is that it sorts by comparing sequences of UTF-16 which [1,2,10,4,15] would return [1,10,15,2,4]. Keep in mind that it does provide a callback method in which you can tell it how you want to do the sorting (a-b, a.length - b.length, etc....), and with this callback method you can 100% get which results you need. But since we are on a journey of learning it's time to learn some other ways to manually sort data. We'll start with from what I've been told are the most basic and a lot of people consider them elementary algorithms but again knowing these other ways to solve problems is the first step in growing the knowledge that you'll need it the development career path. These three sorting algorithms are Bubble Sort, Selection Sort, and Insertion Sort.

Bubble sort by default is probably the most elementary sorting algorithm and probably the least efficient algorithm out there but it's also generally the first one that is taught because of how easy it is to visualize and understand. The way that bubble sort works is through two loops. You compare the first element of the array with the second element and if the first element is greater than (if you are sorting smallest to greatest), you would swap them. You continue this until you are at the end of the array. And with each iteration of the loop, 1 item is guaranteed to be "sorted". Please be aware that more can be however you will still need to loop over every index of the array. Once you do you will have a fully sorted array. Remember with each pass you make you loop through the length minus 1, as we know the final element is sorted each iteration.

Remember that loops within loops are extremely inefficient since their time complexities is factorial which is just about as worse as you can do. So if that is the case why even learn these elementary algorithms? Well first off it's good to have a knowledge of how to sort an array or structure if you need. So even being the most basic and horribly inefficient, it will still give you a solution to a problem. On a side note

The one use case in which Bubble Sort excels in is if you have an almost fully sorted array, and have one catch. Create a variable and during each pass set the variable to false. If a swap takes place make it true and at the end of the pass if it is false, return because we know we'd have a fully sorted array. Keep in mind you can set it to true to start call it something different and do the same if it is false. I don't have that coded in my files but feel free to add it in yours. Bubble Sort.

Selection sort is similar to bubble sort as its considered an elementary sorting algorithm, and as a high level overview what it does is the "reverse" of bubble sort (places high items sorted first), and it places smaller values in their sorted positions first. We are moving from the beginning to end but the sorted data is accumulated at the beginning instead of the end. We accomplish this by looping through the array and keeping track of the smallest value. After the first pass we swap the smallest value with the first position, and then on the second pass would be second position swap and so on and so forth. Remember for each pass we'll store the smallest value as the first item in that particular iteration.

As with Bubble Sort the time complexity in the worse case scenario is factorial which is extremely undesirable, again though when you are first starting out with any type of problem solving ( and this doesn't necessarily have to be related to development/programming ), getting to the finish line or a solution is the first step. If you cannot even finish a problem you don't really have room to say I don't need to know this since it's horribly inefficient. Horribly inefficient is still horrible but in the end it will give a solution so again, important enough to have an understanding of. Selection Sort

Insertion sort is definitely a little more complicated that Bubble and Selection. In an insertion sort we build up the sort by creating a larger left portion (of the array) which is always sorted. In this sorting algorithm we'll start with the second item in the array instead of the first and compare the two. If they need to be swapped we swap them otherwise we now move to the third position and then go back to the 2nd and 1st for comparisons. We insert the values if they are in the wrong position. So once we hit the last item in the array and then it goes down the array and it is either inserted or left alone, we'll have a fully sorted array. Insertion Sort.

Data Structures and Algorithms - Graphs

Brad Goldsmith — Thu, 19 May 2022 17:40:50 +0000

Graphs are extremely useful in todays world. They are used in social networks (modeling users), recommendation engines (Netflix), advertisements targeting you, well the list just goes on. So what are they? The most basic definition of a graph would be that they are a collection of nodes or values and connections between said nodes/values. Not all nodes have to be connected to one another. Some terminology in graphs that we need to know are:

Vertex / Vertices - the node(s) that make up a graph
Edges - the connection between vertices
Undirected graph - no direction to the edges (2 way connection /edges, example would be facebook friends - each other see each others content)
Directed graph - specific direction of edges / connections between vertices (usually represented by arrows, instagram - followers only being able to see the followed content but not vice versa if they are both not following)
Weighted Graph - edges having a value
Unweighted Graph - edges containing no values ***3/4 can be used with 5/6 and vice versa so you can have for example a weighted directed graph or an unweighted undirected graph and all the possible combinations.
Connected g=Graph - all nodes are reachable somehow (100% of nodes can be traversed and values can be stored)
Disconnected Graph - when at least one node is not connected to the Graph. this sounds confusing but it's something that i read about and I'm not really sure of a use case or when it would be encountered but I feel like it's worth mentioning.
Cyclical graph - any 3+ nodes are interconnected so that they can be traversed infinitely. This is important to know when traversing because if it is cyclical and you do not account for it you could end up in an infinite loop.
Acyclic Graph - 3 or more nodes are not interconnected in a way in a which an infinite traversal is possible.

So as far as creating a Graph what do we need? Well we need a way to store the Vertices (nodes) as well as their edges, and we must remember they can have multiple edges and these edges can be weighted, uni or bidirectional. I know that's a lot lol. Two of the most well known and most popular ways of storing graphs and their data are:

Adjacency Matrix - A matrix is a 2 dimensional structure generally implemented with nested arrays and store information in rows and columns. Undirected graphs will show up in a matrix in a symmetrical pattern vs non symmetrical for directed
Adjacency List - use an array or list to store the edges of a vertex. If the vertices values are not numbers we can use a hash table to store the relevant data. Pros and cons of the two are that an Adjacency list can take up less space and it is faster to iterate over all of the edges however it can be slower to look up a specific edge. Opposites are true of an adjacency list as it takes up more space and is slower to iterate over all edges however it is generally faster to look up a specific edge.

When talking about traversing a graph all it means is visiting every vertex in a graph. We do this by visiting two older methods that we created before and that is breadth first search (BFS) and depth first search (DFS). Just remember that every tree is a graph but not every graph is a tree. In a graph there is also no root so how do you start your traversal? We would just specify a starting point or our "root". In a DFS for graphs you'd pick a node and then determine how we want to traverse. I'd suggest by lowest value and go all the way down those nodes edges and then onto the siblings. And repeat. In a BFS for graphs you'd select the "root" to start with and then a child and then those child siblings before going "down" (and remember when I say down it doesn't necessarily mean in that direction). Graph, and here is my graph class which honestly I had a relatively easier time writing traversing functions than adding / removing. I don't know why but for me it was hard to visualize a graph without looking at vertices and edges. I'll have to continue on this one for sure.

Data Structures and Algorithms - Binary Heaps

Brad Goldsmith — Mon, 16 May 2022 23:55:51 +0000

Heaps data structures that are another form of trees. They are a special form of heaps and there are many types of heaps as well. We'll be talking about MaxBinaryHeap and MinBinaryHeap which similarly to a BST each parent can have a max of 2 children. The caveat for Max and Min heaps is that in a MaxBinaryHeaps, parent nodes are always larger than child nodes and you guessed it, in MinBinaryHeaps, parent nodes are always smaller than child nodes. Unlike a BST there is no order to left and right, the only principles that they follow (min/max) are what we just wrote about (parents smaller / larger than children). A binary heap is as compact as possible and all of the children of each node are as full as they can be and the left children are filled out before the right. One thing to mention here is that Binary Heaps are used to implement Priority Queues. So it would be a queue first in first out however depending on the priority/importance would determine when that node would be dequeued. They can also be used with graph traversal algorithms.

A heap can be represented as an array with some basic math. Think about it. You store indexed values and we know that the left is always filled out first so we can create some logic to find which values are children and parents. For any index of an array, which we'll call n, the left child is stored at 2n+1 and the right child is stored at 2n+2. With this logic we could build out a heap using a standard array, isn't that cool? We can also reverse this to get parent nodes from children. For a child at index n, its parent index would be floor((n-1)/2) and we'd have to add the floor method as there are not going to be decimal indices. Working with an array when we insert values, we push them onto then end and then we travel down the array until it reaches the point where it needs to "live".

When dealing with min/maxHeaps you generally have a method to extract either the min or max value which would be the root node. The way you do it remove the root node (shift()) and then replace the node with the very last element of the array. Then through a process known as "bubble-down" you would check the continue to check children nodes and if the new root is small than the child you swap until it is in its proper position. Again you'd want to start with the left side since we know in a heap the left children are filled out first. So the bubble down process is, well its just hard to grasp. I highly recommend watching some videos on it and console logging a whole bunch so you can see how it works. I still cannot quite explain it and when I say I barely understand it I think that might be the understatement of the day for sure.

We talked about priority queues just a bit at the beginning and I'll go over them very briefly. They are a data structure where each element has a priority and elements with a higher priority are served before elements with lower priorities. So this legitimately sounds like what we just did and the higher numbers in the maxBinaryHeap are actually the priorities. Thing about all values just being added to heap or end of the array. A newly high priority "case" would be added and whenever the next item was dequeued, you would swap the values and then bubble down to sit it at its proper spot. I am not 100% sure that was properly explained but I think you can get the idea. I never said I was a great writer and or teacher I'm just trying to get some knowledge to stick with me.

MaxBinaryHeap
MinBinaryHeap
Priority Queue

I feel like out of everything I've studied and "learned" thus far this one didn't stick near as much as the others. I feel like I may have rushed it and now definitely plan to revisit this very soon. But for now I keep on trucking and continue my journey.

Data Structures and Algorithms - Binary Search Trees

Brad Goldsmith — Sun, 15 May 2022 11:51:48 +0000

A tree is a data structure that consists of nodes in a parent / child relationships, and these nodes are connected via an edge (can be called branches too). Each node can point to multiple other nodes and when you draw it out it has a "tree" like structure except it generally goes from top to bottom where a tree would grow upwards. Trees are nonlinear so unlike a linked list you encounter branches, and their nodes are generally going to be strings and numbers but they can also be other data types as well. A BST node can only point to children, and not siblings, so each node is moving away from the root, the top node of the tree. Some other terminology would be siblings with are nodes that have the same parent ally a leaf which is a node with no children.

The most common example of a tree is the HTML DOM. Opening up a website and inspecting element you can just console the children and nodes and is kinda fun to play around with. Trees are also used in machine learning, which I'd love to get into one day but that's gonna be another day or week or month. One thing that you would probably encounter daily and not realize it, is your projects and whatever text editor you use (should be VS Code), the folder structure is in a tree like structure.

A binary search tree has special conditions that other trees do not and that is a node can have a maximum of 2 children, and that is the binary part. They are also kept in a specific order, and are generally used to store data for comparisons, whether it be number or strings (the 2 most common). So whatever value is on the root, smaller items go to the left and larger items/values are stored to the right, and this continues as you go to children. Because data is sorted in binary search trees, searching through them is very efficient. It is very similar to the divide and conquer method but it's already done for us. I'll be visiting a few algorithms after I have the data structure portion "done". Compare and then right or left based on smaller or larger and repeat. One thing we never talked about are duplicate values. Comparing less than or equal too is great and all but what happens when the values are the same? An easy way to handle it would be to just return false or undefined but then again you could add a frequency value on that specific node, but that really is up to the programmer to make that decision. I'm not really sure what I'd do as I've never created one in a real world scenario but I like the idea of a counter, I feel like if the data was entered it should be stored somehow.

I thought about breaking this next section up but have decided to throw it in here. I'm going to be working through tree traversals here, which basically is an algorithm to visit every node on a tree. It is also, from what I've been gathering, a very common problem on coding interviews. Unliked a linked list there are many ways to traverse a tree where with a linked list there is a limited amount (1 or 2 depending on singly or doubly linked list). The easiest way to do this is through recursion, which in my dumb terms is basically calling the same method over and over again until it completes the task (potential for infinite loops...). Let me also say I barely understand the concept of recursion so I probably need to be revisiting recursion on a weekly if not daily basis. I do implement recursive functions in my code base when I can. Even though recursion may be a better and more efficient way of doing it, you can always write these methods iteratively as well. Two ways of traversing trees are:

Breadth First Search (BFS) - working across the tree, which is basically a horizontal traverse, going one row/level at a time (sibling nodes before children).
Depth First Search (DFS) - going down a tree then back up. But with the DFS there are multiple orders in which you can go, which I'll talk about.

Binary Search Tree. So now that we have done traversals we have to discuss when to use BFS vs DFS and then talk about the multiple ways in which a DFS can be done. We'll talk first just BFS vs DFS. If you have a tree that is a max width capacity (each parent has its maximum of 2 children BST!!!!!!!), we will have to store tons of data in our Queue and that would take up a bunch of memory, where in DFS we are not storing nodes across the siblings rather than individual left and right nodes. Time would be equal on both but in this scenario a DFS would take up less space (memory). If a tree is very much like a linked list (which it can be), then the BFS is more convenient since we are adding/removing from the queue at each node visit and in this scenario, the DFS would take up more more space. I think generally speaking you will see trees that are more flushed out, or tree like, vs list like, but again this is speculation by me since I have never actually used one outside of creating HTML elements and I didn't realize it was one until I started learning about this subject.

One thing I totally forgot to mention is that during my learning process I am focusing on 2 main sources.

Algo Expert Crash course on data structures, and doing as many of their problems as I can.
JS Algorithms and Data Structures Masterclass I'm also watching misc YouTube videos here and there to try and get some extra explanation when I do not fully understand what is going on. So quite a bit of what I am writing out here is word for word at times from all of these sources. I am not taking any credit for this, I just feel like for myself if I type/write it out and try to explain it in my own words I retain it a bit better. I will also say that I'm going to revisit these courses and these posts over and over again to really try and make sure all of this information sticks, since the goal is to learn and not just memorize.

Data Structures and Algorithms - Hash Tables

Brad Goldsmith — Fri, 13 May 2022 20:06:18 +0000

Hash tables, or hash maps, are used to store key value pairs and are available by default in many languages. In Javascript, they are the Javascript Object and Maps (objects have some limitations but are still considered hash tables). Remember in a JS array the keys or index are alway integers and they count up from 0. With the hash table you can store strings, integers, and even other data types as these keys, and in a hash table these keys do not have to be ordered. As far as insertion, deletion, and search, hash tables are extremely fast generally having a constant time. They do this because under the hood the hash map is a dynamic array of linked lists, and since it's an array we can access the index at a constant time. We'll talk about some scenarios later on where collision occurs which would drastically increase the time but again for now let's think of it all as constant.

Computers don't know how to read string or other data type indices, only integers, so what we must do is create a hash function or a function that converts these non readable values to some type of fixed size digit. There are many existing famous hash functions out there that are readily available. One thing to note is that a converted key to a hash number needs to be within the length of the array. If we have an array of length 100, the hash number could not be 654 or we'd have to add 554 new slots and that just doesn't make any sense, especially knowing we need consecutive memory slots. One way to be sure your hashed item is within the proper fixed size, you would use the Modulus % operator and take the newly hashed value % arr.length it would then always fit within the constraints that we have described. I guess in a sense a hashing function is an extremely valuable algorithm, and outside of these hash tables / maps, hash functions are used widely in security, authentication, and cryptography in programming just to name a few.

Things to not with hashing is that we cannot work backwards. If you do not have the original key you will not be able to get it from the hash. So what makes a good hash function? It must be fast, it should distribute indices uniformly, and it must be always yield the same output with the same input, otherwise how would you be able to find the value? Hash Function. Here is a cool JS hash function that can be used. However if you look at the bottom you'll see its not really IE compatible but at this point who cares, you should not be using IE!!!!!!!

When hashing you could run into collision in where multiple inputs will output the same hashed value. Now whenever collision occurs it will increase the time complexity and at worse case scenario, which you remember is how you want to describe it, would be big O of N which means it would be a linear value as N increases it would take that much more time. So how to deal with these collisions. We'll first off with better hashing algorithms and larger hash tables we can reduce the number of collisions. Two ways of dealing with them are:

Separate chaining - storing the same indices into an actual data structure such as an array or linked list.
Linear probing - when a collision occurs we search to find the next empty slot, which would not increase the time complexity for our insert, delete, and search. The caveat here is that you'll never be able to fill more items than the length of the array.

Here is my basic implementation of a Hash Table. Hash Table. I went with about as basic as a hash function as possible, and for collision I went with the separate chaining approach. One thing to note here is that I did not account for duplicate keys. In many languages that have Hash Maps by default, will override a value if the same key value pair is passed in. I think it would've been easy enough to implement but at this point I just wanted to build something out so I had knowledge of it. And in the end it's nothing but an extra conditional or two and I think at this point I'm fine with this.

Data Structures and Algorithms - Stacks and Queues

Brad Goldsmith — Thu, 12 May 2022 19:04:37 +0000

Stacks and Queues are both array like data structures. I'm going over these togethers since while learning them I learned them together so it makes sense. The biggest differences between them is that the Stack follows LIFO (last in first out) and the Queue follows FIFO (first in first out) principles. What exactly does that mean? Think of a stack as students turning in papers in a pile (or stack) and when a teacher starts grading they will start from the top and work their way to the bottom (LIFO). And then think of queue as you are in line at a grocery store. The first person in line checks out first and then the next person and the next and so on and so forth. As a rule of thumb stacks are typically implemented with a dynamic array or a singly linked list where queues are typically implemented with a linked list (singly or doubly). They both have the same time and space complexities as well for push / pop (stacks), enqueuing / dequeuing (queues) and searching for an element, the first part being in constant time.

Coming from a restaurant and bar background I am very familiar with the FIFO principle, and that was my lame joke and relatable item for the week. So one thing I learned about Stacks and implementing them as arrays is you can do this 2 separate ways. You can use push and pop array methods which would put everything at the end of the array and take it from the end (LIFO) principle as well as you can use the shift and unshift methods which would do the exact same thing except continue to add / remove from the beginning of the array. That being said doing it this way would drastically reduce performance since doing anything at the beginning of the array basically doubles memory as a new array has to be created.

I'm going to implement the Stack with a singly linked list and by doing so we'll be adding / removing from the head which gives us a constant space time complexity. We could do this with a doubly linked list as well and do it at either the head or the tail but that doesn't make a whole lot of sense since we just learned that by default you'll be using up twice the memory allocation and I just don't see a need for that. Stack

Queues exist every in programming. Uploading photos is generally done one at a time, background tasks and another really good example is your printer. As it adds all of the pages to the printer (queue) it'll print the first ones added first, page one, page two and so on... We can one hundred percent build a queue with an array using the predefined methods but remember the memory allocation and efficiency of adding and then removing from the beginning of an array. And we can do it in reverse order and add to the end and remove from the beginning of the array if we really wanted too but again performance issues. Now we'll go ahead and build out a Queue from scratch using again a singly linked list by adding to the end and removing from the beginning which would give us a constant space time complexity (what we are going for). Queue. If we wanted to add to beginning and remove from the end a doubly linked list would make most sense to use. I'm trying my best to learn as much as I can as quickly as I can because at the end of the month I have an interview with google for an entry level role. Wish me luck!!!!!!!

Data Structures and Algorithms - Doubly Linked List

Brad Goldsmith — Thu, 12 May 2022 14:47:50 +0000

I believe this will be very brief as a doubly linked list is basically the same thing as a singly linked list with the exception that each node will not only have next pointer but a previous pointer as well. In that manner a doubly linked list may traverse bidirectionally as well as start at either the tail or the head. So for the pop() method you could just start from the tail and then traverse one down and set it's next value to null. So much more efficient than having to traverse it all the way up. This does add a little complexity however when adding / removing a node since we have to account for the dual connecting nodes. And by default a DLL uses more memory than a SLL however it does have more flexibility as you can see here. So which one is right to use? I guess that would depend on each individual situation and if memory is something to be accounted for, which it should, then in that case the SLL would probably be the way to go.

I was very curious about memory allocation and a couple of other small nuances and stumbled across this page: DLL vs SLL . According to them the memory difference is 4bytes (SLL) vs 8bytes(DLL) so what I gather there is that other pointer literally doubles the memory allocation. Good to know and there are some other cool comparisons if you'd like to check them out.

So as per this "series" here is a link to my github repo where I created the Doubly Linked List class. Doubly Linked List. I'm sure there are many other ways of implementing these methods and there are probably some that I have left off so feel free to comment on it. Again sorry for the short content but as you can see the Doubly Linked List is extremely similar to a Singly Linked List so this is all I have.