DEV Community: Jordan Long

twoSum

Jordan Long — Tue, 22 Dec 2020 06:28:45 +0000

The twoSum problem is an extremely popular interview problem and have had it come up in every algorithm meetup I have been to and have even actually had it as a mock interview question before. It's very common so if you are like me and are preparing for technical interviews, I would recommend mastering it.

First I'll break down the problem. Basically, you are given an array of integers, and a target number. Let's say the array is [5, 6, 3, 2, 11, -1, 2, 7] and our target is 16. We want to return the two numbers that add up to our target. In this case it would be [5, 11]. There are so many ways to accomplish this but I'll go through two. One being the "brute force" way which isn't the most optimal, and the other solution being a more optimal solution.

The brute force solution requires us to loop over our array using two pointers. Our first pointer will start at the 0 index, and our second array traversal pointer will start at 1 ahead of our first pointer. We then add a conditional to add up the value of our first pointer and the value of our second pointer. If those two pointers equal each other, we return the two pointers. If none of the values in our array add up to the target sum then what do we do? In an interview setting that would be considered an edge case, something you should ask the the person interviewing you for right off the bat. In this case, if we don't find two sums that sum up to the target we will return an empty array.

Let's break it down step by step, we start our first pointer traversal at 0. Inside of our loop we create a variable called current that we will use to keep track of the current number of our traversal. We then start our second traversal of the array starting our second pointer at i + 1. So if we had an array [1, 2, 3] the pointer i starts at index 0 (1) and j starts at index 1 (2). Then we create a variable to keep track of our second current iterator (secondCurrent). Literally all that is left here is a conditional to check if our current + secondCurrent is equal to our target and if it is, return both pointers return[current, secondCurrent]. As for the end, don't forget the edge case of returning an empty array if no integers add up to the target, this is very important.

Now, why is this a naive solution? Well we can optimize our code to make it run faster. The time complexity of the algorithm above is quadratic ( O(n2) ) which isn't the best solution. Unfamiliar with quadratic time complexity? Quadratic time complexity represents an algorithm whose performance is directly proportional to the squared size of the input data set (think of Linear, but squared). Within our programs, this time complexity will occur whenever we nest over multiple iterations within the data sets.

In an interview setting, after submitting that solution your interviewer will ask you if you can optimize your solution to make it more efficient, and you will say yes and this is how. By initializing an empty object (or hash table or whatever you prefer to call it) to store values in. Here is what the optimized solution looks like:

The difference here code wise is we set our currentNum variable similarly to how we did in the naive solution but then things get different. We calculate the difference of our target and our currentNum. Then say if our difference is in our nums object, then we return our currentNum, difference. If the difference isn't in our nums object then we take our currentNum and store it into our hash table. (nums[currentNum] = true ). Then, if no two integers add up to the target we of course return our empty array at the end.

We were able to optimize our time complexity to linear time (O(n)) where n is the size of the input. Informally, this means that the running time increases at most linearly with the size of the input. Linear time is the best possible time complexity in situations where the algorithm has to sequentially read its entire input in the worst case scenario.

Search feature using React Hooks

Jordan Long — Fri, 18 Dec 2020 18:59:20 +0000

The other night I found myself in a zoom meeting spectating a mock frontend interview coding challenge done by an engineer with a junior developer. I wasn't the one doing the challenge unfortunately but I got some inspiration to do the challenge myself. I won't say exactly what the challenge was as I don't want to step on any toes but for my solution I wanted to take the main idea of the challenge and add a twist or stretch goal. One feature that you can find on almost every single site or app is some sort of search feature. As popular as they are and for juniors they may kind of feel daunting, they really aren't too bad. Here's how I implemented mine.

As I started out on my own challenge of building this, my first task was to fetch fake user info from an api. The idea for my version (remember I'm twisting someone else's challenge idea) was to use the fake data from the api to render out a twitter feed. You would have just a basic list of boxed tweets that included a users picture, first and last name, their @name, and tweet content like a sentence or two. Using react hooks for the first time I knew I had to store the users in state for sure. In the useEffect hook (which can be kind of compared to componentDidMount() in class components) is where the fetch took place. Using the response I got back from the fetch I set the user state to the response data. Here is a snippet of the fetch:

The response back from the fetch call was an array of user objects. I knew in order to display the data for the tweet feed I had to iterate over the array of objects, and put the users pictures, and their first and last names, as well as their @names in the correct elements. Using .map() I plucked out the information needed and was one step closer to rendering.

After finishing the iteration and rendering the data as well as minimal CSS, here is what the tweet feed looked like.

At this point in time, I was done with my original goal of having the tweet feed, so then I wanted to implement the stretch goal which was to add a search feature to filter the tweets by username. In order to do this part, I knew I need an input box to search in, as well as to make that a controlled input and store the contents in state. Using the useState() hook in React I set the default state of the input to an empty string. Here is how you declare state using the useState hook, as well as creating the input field and making it controlled.

A quick rundown on how this works is you set the value of the input box to be an empty string (const [input, setInput] = useState(""), ) then in the input tags onChange event handler, you update the state with whatever value is being typed into the input box.

Now in order to make sure whatever is typed filters the tweet feed, we use JavaScripts .filter() method to get the job done. If you are unfamiliar with the .filter() method I'll post a link to it at the end. Since we already have all of our user information stored in our state already, it makes this part a whole lot easer. I used a helper function to filter the all of the users who's username matched with the value in the input field. Here is the helper function:

The last step to ensure our search feature is to call our helper function where we were originally were mapping over our users array. This is the function where it all comes together.

The end result looks like this!

Just like that, you've got yourself a dummy twitter feed and the ability to search and filter the results by username. Some topics I didn't go as deep in detail above were .filter(), and React hooks in general. Below are some resources to help you out on that front. I hope this helps!

JavaScripts .filter() method

React Hooks!

Big O notation

Jordan Long — Sat, 12 Dec 2020 04:29:47 +0000

If you haven't heard of big O notation before it may seem like an intimidating concept. You do a simple google search just to look up the definition just to see what the heck it is and are even more intimidated. You see phrases like "run time analysis", or "time and space complexity" and are even more intimidated than you were before looking it up. As intense as it may seem after taking time to learn the ins and outs it really isn't as bad as it sounds.

Big O notation is a symbolism used in complexity theory, mathematics, and computer science. In mathematics it describes the limiting behavior of a function when the argument tends towards a particular value or infinity. In computer science (which is what we are concerned with) big O notation is a formula used to calculate how much time and space our algorithm takes as the size of the input grows.

In this article, I will go over the most common RUNTIME complexities that you will come across in your journey. I will have to write a part two as to how and why to compute these different complexities but for now this is a good start. I will say when you are computing complexities especially in an interview setting you will always judge your computation off of the worst case scenario. You want to do it off of worst case because you're not expecting your algorithm to run in the best or even average cases. It allows you to make analytical statements such as, “well, in the worst case scenario, my algorithm will scale this quickly and why”. Here are the most common complexities you will have to know and understand.

1) Constant time - O(1)

Constant time describes algorithms that take the same amount of time no matter how big or small the input grows. If an input with two or even three elements takes the same amount of time to run as an input that has one hundred elements, that algorithm runs in constant time. If you had an array say
let array = [1, 2, 3, 4, 5] and you were instructed to get the first element no matter what, (array[0]) that is a basic example of constant time complexity. Here is a picture:

2) Linear time - O(n)

Linear runtime describes an algorithm that the time to execute is directly proportional to the size of the input. One non code example to compare to linear time is reading a book. Where n (the size of the input) is the number of pages. Here is a code example of linear runtime.

)

3) Logarithmic time - O(log (n))

One of the more complicated or "mathy" terms to understand when pertaining to big O notation. Logarithmic time complexity takes place if the time it takes to run the algorithm is proportional to the logarithm of the input size n. If you are familiar with binary search, then you're familiar with implementing a logarithmic algorithm. Here is an example:

4) Quadratic time - O(n^)

Quadratic time complexity if the time to execution it is proportional to the square of the input size. If any solution you have that involves nested loops or iterations that typically falls in the category of quadratic time. If you were in an interview setting I would recommend not solving the problem using quadratic time unless you know how to optimize it. Here is an example:

These are the four most common time complexities you will encounter, ranking these four from best to worst would be constant, logarithmic, linear, quadratic. Here is a picture showing how these algorithms perform as the size of the input grows: