DEV Community: Jack Cole

How to Solve a Coding Challenge

Jack Cole — Sun, 22 Nov 2020 04:58:05 +0000

Recently I've been doing LeetCode's weekly contests and I recommend anyone wanting to practice for interviews do them as well. The contests are great because they mimic the environment of a real interview. You are given a set amount of time (often 90 minutes) to solve several problems that increase in difficulty. The tests do a good job of imitating a high pressure environment rather than practicing problems in a lax setting.

After repeatedly taking these contests I feel that I've nailed down a method that works for me for solving problems and wanted to share. Anyway lets jump into how I solve each problem.

Take the time to read the problem 2-3 times until I'm confident I understand it. If I have a few confusions I continue to the next step anyway which is...
Examine the test cases and make sure I understand why the test inputs lead to the test outputs.
If you're given the expected time complexity you can narrow down approaches they want you to use. For example, if they want you to do an O(log n) search you can first try a binary search.
At this point I think about how I'm going to approach the problem while looking at the provided code as well as the provided constraints.
Always try to think of edge cases that could cause problems before you code as well as while you are coding

Thanks for reading! I'd love to hear what works for you when you're solving a coding problem and how what you think I should do differently.

Creating a Coding Interview Study Guide in Ruby

Jack Cole — Sun, 15 Nov 2020 07:33:14 +0000

As a follow up to my previous post, I'm going to be creating a study guide on various computer science concepts that would be helpful for coding interviews. All of the code for this will be done in ruby. If I previously posted about a topic I'll be sure to link to it.

You're going to need to know iteration and recursion, arrays and matrices, linked lists, queues, stacks, heaps, sets, hash maps, trees, binary search, graphs, traversals like breadth-first search and depth-first search, tries, and sorting algorithms (particularly merge sort and quick sort). Also knowing some dynamic programming concepts could be helpful such as memoization and divide and conqueror.

The file with all of the code examples can be found here. I'll be continuously updating and refactoring the code. Hopefully this is helpful to anyone else reading this. If I miss anything be sure to let me know and I'll update it.

Creating a Coding Interview Study Guide in Javascript

Jack Cole — Sun, 08 Nov 2020 07:43:38 +0000

In this post I'm going to be compiling all of the computer science concepts I've learned to create a study guide on most of the general technical skills you would need to know. If there's anything I missed please let me know and I'll be sure to add it to the list. All of the code for this is going to be in Javascript. If I previously posted about a topic I'll be sure to link to it. Here we go.

The file with all of the code examples can be found here. I'll be continuously updating this file in the future and plan on posting a similar cheatsheet with all of the code implemented in Ruby.

Learning How to Divide and Conqueror

Jack Cole — Sun, 01 Nov 2020 03:14:16 +0000

Last week I discussed the concept of memoization. This week I wanted to continue discussing concepts needed for dynamic programming and focus on using the method of divide and conqueror.

What Is Divide and Conqueror

Divide and conqueror is an algorithm paradigm based on multi branch recursion. More specifically you take the initial problem and breaking it down into sub-problems until the sub-problems are simple enough to effectively solve. The solutions of the sub-problems are then combined to form the solution of the original problem.

Divide and conqueror is often used to solve problems such as sorting and multiplying large numbers. To show an example I'll show the implementation of merge sort and quick sort. Since I've previously covered these in a post on sorting algorithms this time I've coded them in Ruby!

Remember that these methods are going to be following the following three steps.

Divide the problem into sub-problems
Conqueror the sub-problems
Merge the results of the sub-problems into the final solution

In my implementation I use two functions to clearly illustrate the process of dividing and conqueror. The first method divides the input into smaller arrays that can easily be sorted. The next methods then sorts the smaller arrays and then combines the sorted numbers to return the solution.

In the implementation of quick sort these concepts are also applied in a single method.

Thanks for reading! The code for this lesson can be found here.

Learning Memoization in Javascript Part 2

Jack Cole — Sun, 25 Oct 2020 03:53:29 +0000

After doing some research on how to implement memoization in a function with multiple arguments I realized this is a pretty unusual situation that will rarely occur...

In my last post I went over implementing memoization in javascript using the fibonacci sequence as an example. However, in that example our function only utilized a single argument. But how do we memoize when a function needs to track multiple arguments?

Implementation

In my example I'm going to use a nested map object. The map will have multiple dimensions and store the fibonacci data in the dimension that matches the specific method call. Remember, this is just an example displaying how we would go about doing this.

Also going on a short tangent, notice how I use map objects instead of a regular hash. Javascript has a map object, learn to use it! You can read more about that here.

Thanks for reading! I know that this is a pretty niche situation but memoization is a good skill to know and could come in handy in the future! The code for this post and my last post can be found here.

Learning Memoization

Jack Cole — Sun, 18 Oct 2020 06:08:56 +0000

In this post I'll be discussing what memoization is as well as when to use it.

What is Memoization?

Memoization at its core is the process of greatly decreasing the run time of expensive recursive or iterative function. More specifically, memoization stores and reuses precomputed values while passing them through recursive calls to improve the speed of your algorithms.

Why Use Memoization?

A great example of how and why to use memoization can be seen when creating a function to create the Fibonacci sequence.

If you're not familiar, the Fibonacci sequence starts with 0 and 1, all further values are calculated by adding the previous two values. 0 + 1 = 1, 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, etc.

This function is often made recursively like so.

When calling this function on small numbers it is relatively quick, but when we call it on large numbers the runtime will drastically increase. This is due to each call of fibonacci() doing the same amount of work, regardless of it was already run or not. The function is repeatedly doing the same calculations over and over again!

How to use Memoization?

Instead of doing wasting time by doing the same work over and over again let's instead store the result of the work in case we need to use it again. In this case we can use a simple hash map to track what numbers have been computed and what results we got from the computations.

Our main function contains our map that stores computed values as well as another function. This inner function checks if our hash contains the result of the called number, otherwise it does the fibonacci function from the original example. By doing this method we avoid any unnecessary work.

Conclusion

Hopefully you now understand the basics of memoization. However, in this example we only really scratched the surface. Memoization gets much more complicated when the function needs to handle multiple arguments or store objects passed as arguments. In my next post I'll go over some more complicated scenarios and how to deal with them.

Thanks for reading! The code used in this post can be found here.

Learning Heap Sort in Javascript

Jack Cole — Sat, 10 Oct 2020 01:12:29 +0000

In this week's post I'll be going over how to do a heap sort using javascript. In a past post I've discussed heaps as a data structure. Since this sort utilizes a heap I recommend checking out that first.

Now onto the heap sort. Heap sort works similarly to selection sort in that they both find the maximum element and place it at the end.

Helper Methods

Due the the comparing we're going to be doing between elements it's a good idea to have a method that can easily swap the location of elements. We can easily do this using some fancy ES6 syntax.

We're also going to need a method that turns an array into a max heap. Remember that this means that each node will be greater value than it's children.

The Sort

The function works by taking the input array and turning it into a max heap. From here we swap the location of the root node and the last node, and then we reduce the size of the heap by one, effectively removing the largest value. We then repeat this process until there are no more values in the heap.

Heap sort has a runtime of O(nlogn). This means that a good situation to use a heap sort is when you're want a consistently timed sort (in games) but don't necessarily need the quickest solution every time. Heap sort will always have a O(nlogn) whereas a quick sort is often faster but can potentially be very slow.

Thanks for reading! The code for this post can be found here.

Sorting Algorithms in Javascript Part 2

Jack Cole — Sun, 04 Oct 2020 04:44:47 +0000

It's been a couple of weeks since I wrote my last post on sorting algorithms and I think it's finally time to revisit the topic. In this post I'll be covering additional sorting algorithms that are more uncommon than the ones I covered in my first post.

In this article I'm going to cover:

Selection Sort
Bucket Sort
Counting Sort

Helper Methods

Just like in my first post, we're going to be doing a lot of swapping of elements. It makes sense to create some helper methods that can be used in our sorting methods.

Selection Sort

Selection sort works by dividing the input array into a sorted and unsorted list. The sorted list begins empty and while the unsorted begins as the initial array. We continuously loop through the array to find the smallest element and add that element to the sorted list. This repeats until the entire array is sorted.

Runtime: O(n^2) to O(n^2)

Bucket Sort

Bucket sort works by distributing the elements of the input array into different sections or buckets. The elements are then sorted with a different sorting method, most commonly selection sort. Bucket sort is much faster than solely using selection sort due to the strategic placement of elements into buckets at the cost of additional memory use.

Runtime: O(n+k) to O(n^2)

Counting Sort

Counting sort is unique in that it doesn't do any comparing between it's elements. Instead counting sort counts the number of elements having distinct key values. From there it uses arithmetic to calculate the position of each element. The main caveat of counting sort is that we need to know the min and max elements in the input array.

Runtime: O(n)

Thanks for readying! I intent to also cover heap sorting in a future post but wanted to cover heap data structures before getting to that.

The code for this lesson can be found here.

Learning Regex in Javascript Part 2

Jack Cole — Sat, 26 Sep 2020 00:12:59 +0000

In this post I'll be be wrapping up my first post on regex. In a similar fashion to my last post, I'll be sure to provide examples that show the inputs and outputs. Let's jump into it!

Some Shortcuts

There are a ton of characters you can use in your regex to create unique specifications in your queries. I'll list a bunch below.

. gets any character that's not a line break
\s gets a white space
\S gets a non-white space
\d gets a digit
\D gets a non-digit

Only the Start or End

If you want to find a character at the beginning or end of your string, you can use ^ or $.

The Caret (^)

^ also has a second use. When used inside of brackets, ^ indicates that you want anything except what's in the brackets.

Quantifiers

Quantifiers specify how many of the specified characters we want.

? means zero or one
* means zero or more
+ means one or more
{} specifies the exact quantity

Special Characters

Finally, if you want to capture any special characters you need to precede them with a \.

Learning Regex in Javascript Part 1

Jack Cole — Sun, 20 Sep 2020 01:28:20 +0000

Today I'll be discussing the intimidating regex. Regex, or regular expressions are a sequence of characters that are used to define a search pattern. The search pattern is most often used in string searches to find or replace certain sections of a string.

Making a Regex Object

In javascript there are two different methods to create a regex. The first is using the constructor provided by javascript, new RegExp(). Here's a quick example.

The other way is by creating a literal. Here's an example.

Regex Methods

Javascript has four helpful methods that can be used with regex objects.

match
test
replace

Match is called on a string and takes an input of a regex object. It returns an array with any characters that matched the regex.

Test takes an input of a string and returns a boolean that indicates if the string had any matches with the regex.

Replace is used on a string, takes a regex object and a string as input and returns the new string with any sections that matched the regex replaced by the specified string.

Brackets, Hyphens

If you use brackets around your regex you'll look for a single character. If you use a hyphen you'll look for anything in that range.

Flags

Flags can be added to to the end of a regex to change what is returned. In javascript the usable flags are,

i, ignore case
g, global match (find all)
m, multi line

Thanks for reading! Next week I'll continue to go through more complex uses of regex. The code for this lesson can be found here.

Learning Heaps in Javascript

Jack Cole — Sat, 12 Sep 2020 21:26:24 +0000

In this weeks article I'll be discussing heaps. We'll go over how to implement a heap in javascript, but first let's go over what a heap is.

What is a heap?

A heap is an almost complete tree like data structure that satisfies the heaps property.

Let's dissect this definition. First, we need to know what a complete tree is. A complete tree is a tree data structure where every node is filled except for the last level.

Next we need to know what properties a heap can have. Heaps are often structures in one of two ways. As a min heap, or as a max heap. A min heap is a heap where the parent node is greater than it's children. A max heap is a heap where the parent node is less than it's children. Furthermore, heaps can be classified as a binary heap if each node only has two children. Below is an example of a non-complete binary min heap.

Why use a heap?

The main use for a heap is a priority queue. A priority queue is a normal queue where each element has an additional value that indicates the priority it should exit the queue. Heaps are a perfect fit for priority queues because they support insert, delete, and extract max/min methods in O(logn) time.

Implementation of a heap

Now that we've got through all of that let's learn how to go about implementing a heap. Due to heaps being a tree like structure you would think that implementing one would be similar to implementing a tree. However, due to the ordered structure of a heap we actually are going to be storing our heap in an array.

We are able to store our heap in an array compactly because we don't need to use any pointers. We are instead able to locate the parent and children through arithmetic using the indicies of the array.

Let's start with the heap class. All we need to do is create an empty array. For this implementation we'll be making a minHeap.

From here we'll need a few helper methods that we'll use for our main functionality. First we'll need a method to swap the location of two elements in our heap given their indexes. This can cleanly be done in one line using ES6 syntax, nice!

Next we'll need a method that takes an element and moves it up the tree until it is placed into the right location. We'll pass the method the index of the element we want to move. We'll then continuously loop, each time comparing current element with its parent. If the parent is greater than the current element, we'll swap their locations and repeat the process until the element is in the correct location.

Notice how we are able to locate the parent note with a basic equation.

Similar to the moveUp method, we'll need a method to move an element down the tree. This method will be of a similar structure except we'll be comparing the parent to both of its children.

Now that we have our helper methods we can easily implement the main functions of our heap. First, we need a method to insert elements into our heap. All we need to do is push our element to the end of our heap then move it up.

Next, we need a method to remove elements from the heap. This method is going to be a two in one. It defaults the argument to null so that when nothing is passed in we remove the last element from the heap. Otherwise, the method removes the specified node.

Thanks for reading! As usual, the code from this post can be found here.

Learning Tries in Javascript

Jack Cole — Sun, 06 Sep 2020 00:12:16 +0000

In this weeks article I'm going to be discussing Tries. A Trie is a data structure thats main purpose is retrieval. Tries are most often used to store and retrieve strings in O(L) time, where L is the length of the string. A common use of a Trie data structure is to do prefix searching, such as an autocomplete form.

As you can see in the example above, each node contains a letter. Each chain of nodes will result in a string. In theory we could use a trie to store every word in the dictionary, but that would use an incredible amount of memory. For this reason Tries are often replaced by other data structures when a prefix search isn't necessary.

Tries have two main functions:

Insert
Search

But before we dive into those, let's first start with implementing the overall structure.

We need to create two classes, a node class and our tree class. Each node will contain a value, which is the letter it represents, a boolean representing if it's the last letter in a word, and an object for holding the nodes children. The Trie will only need the root, which is initialized as an empty node.

For our insert method we need to traverse through our tree. So to start we initialize a node variable representing the node we are currently on, and set it to the root. For each character in the passed in word, we see if our current node is holding the character as a child, if it isn't we add it as a child. We then change our current node to that character and repeat until we've gone through the word. After our traversal we set the last node's status to show it is the last character of a word.

Our search method is similar to our insert method in that we are doing another traversal. However, all we do in the loop is check if each letter is present in the word. If all of the characters are there and the last character's status shows it's the last character of a word then we return true, otherwise we return false.

Thanks for reading! You can find the code for this post here.