DEV Community: Andrew Williams

Algorithm Practice: Reverse Words in a String

Andrew Williams — Mon, 08 Feb 2021 04:39:42 +0000

The Grind Continues

Another week, another coding challenge! Since I've been prepping for job interviews, I decided to peruse Glassdoor for common yet challenging coding questions. One of the most frequent ones to appear was the classic 'Reverse String', which I found had a couple of variations.

While it's frequently said, the same advice echoed by coders from years past still rings true: practice builds confidence. Even after just a couple of weeks of challenging myself, I can already see improvements in my approach to problem-solving. This problem was listed as a 'medium' difficulty on both sites I solved it on, and it was super encouraging to discover a working answer in less time than some of my previous challenges!

The Problem: Reverse Words in a String

Similar to the last problem I blogged about, the prompt for this challenge is pretty simple: given an input of a string, return the string in reverse. This doesn't mean to just return everything backward, but rather return every word in the string in reverse order:

Input String = "I code because I'm cool"
Output String = "cool I'm because code I"

It should be noted that these strings can contain leading or trailing spaces with multiple spaces between the words. Despite these added spaces, the returned string should only have single spaces separating words with no leading or trailing spaces (basically we return normal sentences, just reversed).

My Initial Solution

After I first read the prompt, I knew I was going to need a way to store each word from the inputted string. I also knew I could use some trusty JavaScript methods to help meet the sentence requirements put in place by the prompt. After about 15-20 minutes of brainstorming, I got a working solution:

function(string) {
   let s = string.trim().split(' ')
   let reverseArray = []
   let i = s.length

   while(i > 0){
      reverseArray.push(s[i-1])
      i--
   }

   return reverseArray.filter(x => x).join(" ")
}

Breaking it down, the first thing I did was use two JavaScript methods: trim() and split(). The trim() method removes the white spaces on both sides of a string, immediately eliminating unnecessary blanks on the input. This method is followed by the split() method, which takes our string and creates and returns an array populated by substrings. I included a space (' ') as a separator, making each word an element in the returned array. It should be noted that if our sentence contains extra spaces between words, then some of those spaces will find their way into the array:

string = "I have many spaces"
s = [ 'I', 'have', '', '', 'many', 'spaces' ]

I also defined two other variables: reverseArray, which is equal to an empty array, and i, which is equal to the length of our s array. Given its obvious name, reverseArray will eventually store our words contained in the s array, just in reverse order. The i variable exists to be used in the condition of the function's loop.

I decided to use a while loop for the purpose of inserting each element from s into the reverseArray. Since i is equal to the length of s, the program can start inserting each element starting with the last and finishing with the first. Whenever an element is pushed into reverseArray, we get the correct index value by subtracting 1. After an element is inserted, we decrease the value of i by 1 until we hit 0 and the loop breaks. We now have an array with our elements in the required order:

reverseArray = [ 'spaces', 'many', '', '', 'have', 'I' ]

A lot happens in the final return step. First, the program uses the filter() method to make a new array with values that pass the defined tests. In the case of this algorithm, filter() is used to add just truthy values to the new array. Since empty strings ('') are known as falsy values in JavaScript, the filter disregards them. Finally, the join() method is used to combine each array element into a string, using a space as a separator between each word:

reverseArray.filter(x => x) = [ 'spaces', 'many', 'have', 'I' ]

Output (using join()) = "spaces many have I"

And just like that, the algorithm has returned our string meeting the requirements of the prompt. I completed this solution on LeetCode and I was pretty happy with the runtime and memory usage:

Same Problem, Different Requirements

After completing the previous challenge, I discovered a new version of the same problem with slightly different requirements. In this version, the algorithm had to return a string with the same number of whitespace as the original. This means that all whitespace leading, trailing, or in between words needed to be accounted for. Special characters are also allowed in this version (unlike the problem on LeetCode). Furthermore, it could not use either split() or reverse() to help in the process.

I'll be honest, this one took a little longer to crack. After slowly walking through the logic, it finally clicked and the answer came pretty quickly:

function reverseWordsUpdate(string) {
  let words = [];
  let currentWord = '';
  let stringLength = string.length + 1;

  for(var i = 0; i < stringLength; i++){         
     if(string[i] !== " " && i !== string.length){       
        currentWord += string[i];
     } else if(i === string.length){         
        words.unshift(currentWord);
     } else {
      words.unshift(currentWord);
      words.unshift(" ");
      currentWord = '';
     }
  } 

  return words.join("");
}

Similar to the previous solution, we start with a variable equal to an empty array. But then we have a variable called currentWord equal to an empty string. This variable comes into play later in the for loop (so stay tuned!). Finally, the variable stringLength is equal to its namesake, the length of the string input plus 1. We add 1 for looping purposes:

string = "Coding is the best!"
stringLength = 20

Then we enter the for loop, where one of the conditions is to increment the i variable until it's equal to the stringLength. You probably see now why we added 1 to the string's length: it ensures the loop iterates through each character in the string.

The loop contains several conditional statements. The first if statement checks to see if the character in the string isn't just whitespace and that it's not the last character in the string. If parameters return true, we add that character to the value of currentWord. Now you see the purpose of using currentWord: it allows the function to construct words from each character that isn't a whitespace. This is what it looks like as the loop executes:

i = 0 (currentWord = "C")
i = 1 (currentWord = "Co")
i = 2 (currentWord = "Cod")
i = 3 (currentWord = "Codi")
i = 4 (currentWord = "Codin")
i = 5 (currentWord = "Coding")

But what about when we hit the first whitespace? The first if statement will evaluate false and the program proceeds to the else if that follows. This statement checks to see if i is the last value in the string. If it is, this means we've hit the end of our string (or found the last word) and the program passes it into the words array using the unshift() method (why unshift? Keep reading!). But in this instance, since we are not at the end, this statement evaluates as false too.

The function then hits the final else statement, whose purpose is to take the completed string in currentWord and insert it into the words array. Now unlike my first solution, I decided to use the unshift() method as opposed to shift(). I realized that I could cut out the step of creating another reversed array by simply putting each new value in front of the previous one! After adding the word, the function also adds whitespace to the array and resets the value of currentWord back to an empty string, allowing the next word to be constructed:

words.unshift(currentWord) = [ 'Coding' ]
words.unshift(" ") = [ ' ', 'Coding' ]

Eventually the loop will run its course and the words array will be equal to [ 'best!', ' ', 'the', ' ', 'is', ' ', 'Coding' ]. Finally, just like in my previous answer, the join() method is used to create a string. Unlike my previous join(), I use an empty string ("") as a separator since the words array already contains a specific number of spaces that need to be returned:

Output = "best! the is Coding"

Conclusion

My biggest takeaway from the 'Reverse String' challenge is to search for different variations of the same problem in order to test your coding ability. It's easy to complete a challenge and memorize the code for solving it, but such rigidity hampers the process of thinking critically. It's possible a technical interviewer will take a classic problem and put a unique spin on it, especially when other companies frequently use the same questions. In these cases, it's important to be flexible and walk-through how the logic of the algorithm will change given the new requirements. You've only truly solved a problem when you understand how each part works, not by memorizing an algorithm's structure.

Trust me, I've been guilty of taking the memorization route and it came back to bite me when I was forced to be flexible. If anything I'm taking this practice time as an opportunity to focus on the how and why of the algorithm. I've found that when I do this I can often discover a solution or the next step of the process if I'm stuck. That being said, I'm still a work in progress and I've definitely run into some problems where I've had to wave the white flag. But the important thing I keep telling myself is to understand how the code works, and that's the best advice I can offer to anyone practicing algorithms.

Algorithm Practice: Two Sum

Andrew Williams — Wed, 03 Feb 2021 05:05:14 +0000

Why Algorithms?

By definition, in software development, Algorithms are computer procedures designed to accomplish a specific task. Each algorithm consists of a number of steps the computer takes in order to produce a result. The ultimate goal in using algorithms is to find a result or solution in the most efficient way possible.

Creating and studying algorithms is an essential part of being a software engineer. Sure, you may not run into a situation where you have to fulfill the requirements present in many of your study questions, but the techniques you learn will prove beneficial when performing technical analysis. You may find part of an algorithm you studied makes your application run more efficiently or returns the results your end-user needs.

Regardless of how you use them, algorithms are a great problem-solving tool, and for that reason, I have made it a personal goal to practice algorithm development. For however long it takes, I will be working my way through a series of coding challenges, each designed to test my knowledge (or lack of knowledge) on certain software concepts. I will be using this blog as an outlet to discuss what went well and what didn't go so well with each challenge. If you yourself are a new software developer or are exploring the possibility of becoming one, I hope these posts can be encouraging and motivating for you in your own personal journey!

The Problem: Two Sum

The prompt for this challenge is pretty straightforward: write a function, taking in a non-empty array of integers and a target value, that returns a new array with two values from our input array whose sum equals the target value. Below is an example of what we would expect our function to do:

Array = [8, 1, 7, 5, -9, -11, 3]
Target Value = 10

Output = [7, 3] or [3, 7]

If no two numbers in the array sum up to the target value, we simply return an empty array. It should also be noted that the function cannot add an integer to itself (ex. 5 + 5) and that it should be assumed that there is at most one pair of numbers summing up to the target value.

My Initial Solution

While this problem is classified as "easy" on the platform I'm using, I did find it challenging at first since I had little experience with these kinds of questions. After about 30-35 minutes I finally came up with a solution that cleared all the tests:

function twoSum(array, targetSum) {
    let finalArray = []
    let newArray = array

    for(i=0; i < array.length; i++){
        let targetValue = array[i]
        newArray.splice(i,1)

        newArray.map(value => {
            if (targetValue + value === targetSum){
                finalArray.push(targetValue)
                finalArray.push(value)
            }
        })

        if (finalArray.length === 0){
            newArray.splice(i, 0, targetValue)
        } else {
            return finalArray;
        }
    }
    return finalArray
}

Breaking down the code, I first defined two arrays, one set to an empty array and another set to the array that was passed into the function. I then initiate a for loop that is set to run the length of the array. Within the for loop, I define another variable equal to a value in the array where i is the index number. This variable's value will change each time the loop increments. I then took my newArray and spliced out the value that the index of i.

After removing this value, I then map through newArray to check and see if any other value added with the targetValue equals the targetSum. If these two values return the correct sum, I then push each value into the finalArray.

Once the map is complete, I run another conditional that checks the length of our finalArray. If the length is equal to zero, then the target value is inserted back into newArray at the index value of i, continuing the loop's run. If the length is greater than zero, it indicates there are values present and the program returns finalArray. The last return line after this conditional exists to return the empty array if the loop has cycled all the way through and failed to have found a pair of integers.

Refining My Approach

While this algorithm does pass the challenge presented in the prompt, it is a mess on more levels than one. In fact, I was so happy I simply cleared the tests I submitted this problem without taking time to refactor my work. After a few days I finally decided to take a look, and oh boy was it rough!

For starters, I defined a couple of redundant variables, the most obvious example being newArray at the very beginning. The code becomes cluttered with a large number of variables and it becomes increasingly difficult for someone reading the code to figure out what the function is actually doing. For refactoring purposes, I knew I needed to cut out the redundancy.

I had the right approach incorporating a for loop, but somehow made the puzzling decision to incorporate map. Sure, map can be used to iterate over an array and examine each value, but the purpose is to return a new array. Instead of map, I should have used a second for loop, which would have accomplished same goal of iteration without the need to return a value.

Finally, I made the task of returning a final array more difficult than it needed to be. Instead of a complicated exercise in creating an empty array, pushing the correct values into that array, and checking to see if there are any values in the array, I could have just returned an array with the values inside:

return [value1, value2]

I would have to set my code up differently, but this is definitely the preferred way of doing things.

Coding an Alternative Solution

After reviewing these issues, researching big-O notation, and getting advice from some other developers, I submitted a second solution:

function twoSum(array, targetSum) {
   array.sort((a,b) => a - b);
   let leftIndex = 0
   let rightIndex = array.length-1

   while(leftIndex < rightIndex){
    const currentSum = array[leftIndex] + array[rightIndex]

    if(currentSum === targetSum){
       return [array[leftIndex], array[rightIndex]]
    } else if (currentSum < targetSum){
            leftIndex++
    } else if (currentSum > targetSum){
            rightIndex--
    }
   }
   return [];
}

In this version, the first thing I did was sort the integers in the array from smallest to largest. I then created two variables to represent the first and last index of the array. Then I initiated a while loop, which runs continuously until either the leftIndex is greater than or equal to the rightIndex or a return statement is executed.

Within the loop, I created another variable, currentSum, responsible for holding the sum of the left index value and the right index value. Armed with this variable, I created a conditional that checks to see if this value is equal to the targetSum. If it is, the function returns an array with both index values. The other statements check to see if the currentSum is either greater than or less than the targetSum, adjusting the value of either index in order to change the currentSum. If every value in the array has been evaluated and no pairs have produced the targetSum, the algorithm returns an empty array.

This approach works thanks to numeric ordering and the use of left and right "pointers". Let's use the array I defined earlier and pass it into this algorithm. Below would be our initial values before entering the loop:

Target Value = 10
Sorted Array = [-11, -9, 1, 3, 5, 7, 8]
leftIndex = 0
rightIndex = 6

Once we entered the loop, we sum -11 and 8, which results in -3. Since -3 is less than 10, the first else if statement is executed and leftIndex value is increased by one, which is the index for -9 in the array. Over time the function adjusts the position of each index accordingly until a pair is summed equal to the targetSum. In the case of the example above, this would occur when the leftIndex equals 3 and the rightIndex equals 5.

Conclusion

It feels so good to go back, even with the easier problems, and nail down how and why an algorithm is working. Being able to learn from your mistakes and make your code run more efficiently gives you that confidence boost to tackle another coding challenge. Hopefully, when my future self looks back, I can recognize these small accomplishments as stepping stones of knowledge that helped make me a more well-rounded developer!

New Year, Same Me (with New Goals)

Andrew Williams — Fri, 01 Jan 2021 23:38:53 +0000

Well, it's January 1st once again, and you know what that means: New Year's resolutions are in full swing. People hit the gym, promise to follow their new monthly budgets, and generally look at the yearly reset as a time for personal betterment. But while the future looks bright and people are motivated, we also know that the excitement is short-lived for many. In fact, a quick Google search produced an article from Forbes that found nearly 80% of people's resolutions ultimately end in failure. Numbers like that make you wonder if all this talk of self-improvement is more of a fantasy than an attainable reality.

You may also be wondering why I've decided to open an article talking about New Year's goals on such a depressing note. The reason why is simple: you have to be real about the process. I too am guilty when it comes to creating a list of resolutions only to find myself back in old habits less than a month later. The ultimate problem I have faced, along with countless others, is losing motivation somewhere partway through the process. It has only been through many failed attempts in establishing goals, as well as through reading and listening to other people like Chou Codes, that I came to the realization that motivation only gets you so far.

Take exercise as an example, one of the most common New Year's resolutions. It starts with you feeling or looking out of shape (a common occurrence around the holidays) and realizing that you probably need to make some healthy changes. So you do some research, watch a few YouTube videos, and listen to motivational speakers yell about what it means to be a winner. After absorbing all this content and getting pumped up, you feel like you could hit the gym for 2 hours every day, and so you do! But after a few days or weeks go by, another feeling begins to set in: I'm doing a lot of work, feeling exhausted all the time, and not seeing the results I want. Before you know it, your time at the gym steadily decreases while you start spending more time doing the same unhealthy things you were doing before.

This is just a general example, but I'm sure you can point to a time in your life when you experienced a similar loss of motivation. The excitement of making a lifestyle change just doesn't last forever for a majority of people, and it's the reason why so many always ask the question of "how do I get motivated again"? I'm going to argue that discipline, not motivation, is the best long term strategy for reaching any sort of long term goal you have. This isn't to say there's no place for motivation, most personal journeys start with at least a spark of motivation. The important thing is to balance this excitement with a realistic outlook on how you hope to achieve your goal, hence discipline.

How Will I Stay Disciplined in the New Year?

Okay, so it probably feels like I've been talking the talk up to this point. It's definitely easier to say or write what improvements you need to make in your life than it is to actually make a change. I remember when I first started my coding journey at Flatiron School that I had grand ambitions of when I wanted to complete my work, and before I knew it I was months past my targeted end goal. I was programming like crazy in the beginning, spending 5-6 hours a day knocking out lessons and finishing labs, reaching and completing my first project within a couple of months. But hitting that early highpoint faded pretty quickly as more challenging work followed, and lacking a structured schedule took a toll on my ability to maintain the same pace. I found myself taking more days off from coding during this period than I had before, slowing my overall progress.

Having better discipline and habits would've gone a long way in helping me reach my goal of graduation sooner, and leading up to this new year I've already put considerable time and energy into making sure I can find success for my goals. My strategy is as follows:

1. Set a Schedule

This seems pretty straightforward and basic, but the craziness of life and especially the beast that was 2020 definitely create obstacles that make things difficult. While it may not be 100% foolproof, having a plan or schedule for how you will spend your day and week is crucial to keeping you on the path that brings you closer to your goals. For example, since my time at Flatiron School is almost at an end, I will need to have a plan for job searching once I've graduated. Thankfully, I've already taken the time to create a job search schedule for myself that consists of carving out 1-2 hours of time each day for various activities that improve my chances of finding a job. If something comes up and I can't meet my goal for a certain day, I simply shift my schedule and accomplish the day's original goal the next day.

2. Plan Small and Work Your Way Up

One of the best ways to build discipline is by establishing daily habits. These habits don't require a whole lot of motivation but do demand you set aside the time to complete them. If you've planned your schedule correctly these habits will be on it. For me, I am making a daily habit of completing at least one AlgoExpert coding challenge to help keep my problem-solving skills sharp. One challenge a day might not seem like much, but it allows me to gauge what I am able to handle going forward; this way I don't make the mistake of overwhelming myself with too many tasks. I instead give myself the opportunity to gradually increase my workload in tandem with my confidence and ability.

3. Practice Accountability

It always feels easier to get things done when other people have your back. That's why I made the decision to hold a weekly FaceTime session with my good friend from home to keep up with our weekly tasks. While my friend doesn't program himself, having the opportunity to share where we are at in our work allows up to encourage each other and follow up to see if we are staying on schedule. This part can be a little intimidating, especially if you don't have many close friends you would feel comfortable sharing your struggles and challenges. But even if it's just a family member or a classmate, have someone in the loop on what you are doing and that can be a positive source for you moving forward.

4. Plan to Balance Work and Life

The biggest mistake I made when starting my Flatiron lessons was thinking I'd have plenty of time to code while still being able to spend an equal amount of time with my son. Yep, I found out quickly that focusing too much on work left me drained and discouraged, especially when I would come home from working a 9 hour day only to code for the next 4-5 hours. This point of balancing your life and your work could fall under the schedule section, but I wanted to give it a spot of its own since I think it's a point people forget too often when pursuing any sort of goal. I have intentionally given myself plenty of time on my schedule to spend with my family for the purpose of bonding and growing closer together. You are allowed to have a life outside of your work, and you shouldn't think that happiness will only come from reaching your goals! Be smart, set that time aside for yourself and others.

This is Just a Start

While I have a student blog over on GitHub, one of my smaller goals was branching out and starting a post-graduation blog on a separate site. And that's just what this first article is: one small step moving towards my ultimate goal of finding a job in software and tech. It's going to be a long journey, certainly with many ups and downs, but I'm hoping this blog can be just one example of discipline I develop not just for my professional career but for my personal life as well. If you're interested in seeing how this personal journey turns out, stick with me these coming weeks as I look to build towards my goals with small bits of discipline. I hope at the very least you can be encouraged in reading this to know that you can make intentional changes that result in continual personal progress.