DEV Community: BebopVinh

A Developer Boy Sorts Out a Messy Line

BebopVinh — Mon, 09 Dec 2019 03:46:53 +0000

Header image: Photo by Roman Arkhipov on Unsplash

Preface

This post will cover the New Year Chaos HackerRank challenge covering arrays. It will also apply the bubble sort algorithm, which I've talked about previously here.

Note: Too lazy to read? Here are the goods on PythonTutor

The Problem

People are waiting in line, each individual is represented by an integer at an index. If everyone is honest, each individual would be at the index that is 1 less than their value i.e. first person is at 0, second at 1, etc...

If the line gets messy, and say person 7 is at index 0, and 4 is at index 6, we need to figure out how many "swaps" need to happen minimally to restore order.

Obviously, we can't just look at a number and place them into a new array at an index that is one less of the value. The problem is asking for the amount of swaps, not a sorted array.

The Caveat

If a person needs to swap more than twice, the line is declared "Too chaotic". This will be our secondary break mechanism.

The Core

Bubble sort at the core, missing ways to keep tracking of total amount of bribes and if an element has been swapped more than twice or not.

function minimumBribes(q) {
    //add variables to keep track of bribes
    while (k > 0) {
        let noSwap = true
        for (let i = 0; i < k; i++) {
            //add ways to keep track of how many times an element is swapped
            //reset this count if no swap happens when moving on to the next 
            element
            let j = i + 1
            if (q[i] > q[j]) {
                noSwap = false
                swapValues(q, i, j)
            }
        }
        if (noSwap) break
        k--
    }
    //return the total swaps here.
}

function swapValues(array, i, j) {
    [array[i], array[j]] = [array[j], array[i]]
}

Now with the added counters and logic to break if things are "Too chaotic":

function minimumBribes(q) {
    let k = q.length
    let totalBribes = 0
    //currentSwaps will keep track of how many times an element has been swapped
    let currentSwaps
    //noSwap is the standard flag to break the loop if array is already sorted
    let noSwap
    while (k > 0) {
        //assumes initial values
        currentSwaps = 0
        noSwap = true
        for (let i = 0; i < k; i++) {
            let j = i + 1
            if (q[i] > q[j]) {
                /*if an element at `i` is already swapped twice, we know this 
                crazy line is "Too chaotic". Break out and save our sanity. */
                if (currentSwaps == 2) {
                    console.log("Too chaotic")
                    return
                }
                /* if that's not the case, we swap and increment both counters
                 by 1, also set the noSwap flag to false,
                 so next iteration can happen to check if array is sorted */
                noSwap = false
                swapValues(q, i, j)
                ++currentSwaps
                ++totalBribes
            //if no swap happens, we reset currentSwaps for the next new element
            } else {
                currentSwaps = 0
            }
        }
        if (noSwap) break
        k--
    }
    console.log(totalBribes)
}
function swapValues(array, i, j) {
    [array[i], array[j]] = [array[j], array[i]]
}

Hope this makes sense. Let me know if I screw up somewhere, happy to revise.

BONUS: First attempt at the problem

function minimumBribes(q) {
    let bribes = 0
    for (let i = 0; i < q.length; i++) {
        //if the element at index i is greater than it's current index + 3, we 
        //know it'll be "Too chaotic" to fix
        if (q[i] > i + 3) {
            console.log("Too chaotic")
            return
        //else, add to bribes the difference between the the current element's 
        value and the next index value (i.e. element 7 at index 3)
        } else if (q[i] > i + 1) {
            bribes += q[i] - (i + 1)
        //sometimes, the current element is is smaller than it's index (i.e. 
        element 4 at index 6)
        } else if (q[i] > q[i + 1]) {
            bribes++
        }
    }
    return console.log(bribes)
}

This passed the initial 3 test cases, but failed all the others and gave me a big headache!

A Developer Boy and His Bubble Sort

BebopVinh — Mon, 09 Dec 2019 03:46:29 +0000

Header image: Photo by Braedon McLeod on Unsplash

First Impression

I've learned about bubble sort recently. To my surprise, my initial impression of the term is not how the algorithm is at all. I thought it has to do with separating elements into bubbled zones so you'd know what to expect when looking into each zone.

Nope.

Break Down

It's called bubble sort because the largest element will "bubble" to the top (end). It can also be referred to as "sinking sort". Both names is not very intuitive to me, but what draws me in is how it works.

The basics of this algorithm is that it will go through an array n amount of times. Where n represents the array size. It will look at each element (current) and the element one index ahead (next). If the current is larger than the next, it will swap them. Regardless of the swap, it increment the current and next indices by 1 until it reaches the end.

In the next iteration, it will only look at the beginning through one element less than the last. For example:

Your array size is 5
First iteration will be index 0-4
Swaps happens
Second iteration will be index 0-3
Swaps don't happen because it is all sorted, this also gets flagged
Loops break and algorithm ends by returning the sorted array

Note: Swapping could also happen in the second, third, fourth iteration, etc... Then, the algorithm would keep going.

Here it is in action:

via visualgo.net

There's an advance logic added in what is shown. The algorithm will stop iterating if, after one run through, no swaps are made. This means that the array is already sorted, so we don't need to waste more runtime iterating the full n amount.

Why?

Bubble Sort is good for

small data set
semi-sorted arrays
O(N) run time best case, O(N^2) worst case

The Components

We will need a helper function to swap two elements of an array:

function swapValues(array, i, j) {
    [array[i], array[j]] = [array[j], array[i]]
}

Here, we're reassigning the elements at index i and j in one line. You can also do it with 3 lines:

function swapValues(array, i, j) {
    let temp = array[i]
    array[i] = array[j]
    array[j] = temp
}

Next, we need two loops--nested. The outer loop will repeat the iteration n amount of times. The inner will look at each element and the one ahead of it. We will use a while outer and for inner here.
Note: Two for loops are fine, too

function bubbleSort(array) {
    let k = array.length

    while (k > 0) {
        for (let i = 0; i < k; i++) {
            //elements gets compared in here
        }

        //decrement k at the end for next iteration
        k--
    }
    return array
}

Execution

Add logic to compare two adjacent elements:

function bubbleSort(array) {
    let k = array.length

    while (k > 0) {
        for (let i = 0; i < k; i++) {
            //elements gets compared in here
            let j = i + 1
            if (array[i] > array[j]) {
                swapValues(array, i, j)
            }
            //add logic to break if no swaps happened
        }
        //decrement k at the end for next iteration
        k--
    }
    return array
}

If current element at i is greater than the next at j, we swap them. Now we add logic to break the loop if no swaps happened (AKA array is finish sorting before k runs out):

function bubbleSort(array) {
    let k = array.length

    while (k > 0) {
        //declare a noSwap boolean flag, assume true
        let noSwap = true
        for (let i = 0; i < k; i++) {
            //elements gets compared in here
            let j = i + 1
            if (array[i] > array[j]) {
                //if a swap happens, this iteration is flagged false, and next iteration needs to run through to check if array is sorted
                noSwap = false
                swapValues(array, i, j)
            }
            //add logic to break if no swaps happened
            //if the for loop completed with no swapping, the array is sorted
            if (noSwap) break
        }
        //decrement k at the end for next iteration
        k--
    }
    return array
}

That is the core of a bubble sort algorithm. You could also implement the swapValues logic directly as well, without a helper function.

Next up: Applying this algorithm to a HackerRank challenge!

LeetCode #122: The Valleys and Peaks Approach

BebopVinh — Sun, 10 Nov 2019 10:41:14 +0000

SPOILER: This post will go over this problem 122. Best Time to Buy and Sell Stock II

Two months ago, a cohort mate and I decided to tackle this problem. Our first impression was that it shouldn't be too hard. We were in over our heads.
Here's my best initial solution, which didn't work at all:



def max_profit(prices)
    start = prices.shift
    last = prices.length - 1
    #default case which returns 0 if prices only decreases over time
    if prices.all? {|n| n < start}
        return 0
    end  
    min, max = start, 0  
    prices.each do |n|
        if n < start
            min = n
        elsif n > max
            max = n
        end
    end
end

It must have been at least 2 hours, and we were both frustrated. I caved and looked at the "Solution" tab and went for the shortest, cleanest chunk of code I saw:



def max_profit(prices)
    i = 1
    profit = 0
    while i < prices.length
        if (prices[i] > prices[i-1])
            profit += prices[i] - prices[i - 1]
        end
        i += 1
    end
    profit
end

It's a clean while loop. But, it wasn't very intuitive to me. The problem is not asking to report the days where it's best to buy and sell stock, so this solution works. All it does is go through all the numbers in the array, then anytime it goes from a lower to a higher number, it counts that as profit. The way the problem is phrased, this solution is just not the first thing I would think of.

This week, a few other cohort mates decided to give this problem a try. And, I decided to look at another approach in the "Solution" tab. This time, dealing with valleys and peaks:



def max_profit(prices)
    i, max = 0, 0
    valley = prices.first
    peak = prices.first
    last = prices.length - 1

    while i < last
        while (i < last && prices[i] >= prices[i + 1])
            i+= 1
        end
        valley = prices[i]
        while (i < last && prices[i] <= prices[i + 1])
            i += 1
        end
        peak = prices[i]
        max += peak - valley
    end
    max
end

Here's my crappy chart with annotation to try and explain this solution:

At first glance, I thought this was O( N^2 ) in time-complexity, because there are loops nested in a loop. But, a closer look will show that the counter is incremented via the nested loop. The outer loop picks up from where the second inner loop while (i < last && prices[i] <= prices[i + 1]) ends. That means the whole thing traverse throug the array only once. So, it's O(N) for time-complexity.

This solution makes more sense. The outer loop makes sure the pointer/counter keeps going until the end of the graph. The first inner loop looks for a valley (a number right before the price starts increasing). The second inner loop will start afterwards. This one looks for a peak (a number right before the price starts decreasing). Once it has this, it adds the difference to the max profit. The loop ends at the tail of the array.

Here's the second iteration through the graph:

After this, the outer loop will restart at index 4. It will find a valley at index 5, but no peak. Therefore, there's nothing else added to the profit.

First Time with React Hooks

BebopVinh — Mon, 28 Oct 2019 01:16:23 +0000

I keep hearing about how React Hooks is the direction where Facebook wants the React library to go. So, I wanted to take an existing project of mine and convert a Class component to a Functional component that uses the useState React Hook. Let's take a look at the Class component.

The Class Component Version

import React, { Component } from 'react'

export class RecipesInput extends Component {

   state = {
      recipe: ""
   }

   handleChange = event => {
      this.setState({ [event.target.name]: event.target.value })
   }

   handleSubmit = event => {
      event.preventDefault()
      this.props.fetchRecipes(this.state)
   }


   render() {
      return (
         <div>
            <h2>Recipes Search Bar</h2>
            <form onSubmit={this.handleSubmit}>
               <input name="recipe" type="text" value={this.state.recipe} onChange={this.handleChange}/>
               <input type="submit" value="Search!"/>
            </form>
         </div>
      )
   }
}

export default RecipesInput

Standard stuff. It's a form that takes a user's input, store the changes in the local state, then submit the state upon onSubmit. Let's change it up.

//class
import React, { Component } from 'react'
export class RecipesInput extends Component {

   state = {
      recipe: ""
   }
...

//functional
import React, { useState } from "react"
export default function RecipesInput(props) {
    const [recipe, setRecipe] = useState("")

...

I don't import {Component}. Removed the local state. I import {useState}, a React Hook. Then call this hook according to the official doc. I have a dispatch action being passed down to this component from the parent container component. We'll comeback to this.

The biggest change is obviously the hook. On the left side, you declare the name of the state, then the name of the method to modify it. On the right side, you call the Hook you want to use, then feed it the initialState(An empty string in this case).

//class

   handleChange = event => {
      this.setState({ [event.target.name]: event.target.value })
   }

   render() {
      return (
         <div>
            <h2>Recipes Search Bar</h2>
            <form onSubmit={this.handleSubmit}>
               <input name="recipe" type="text" value={this.state.recipe} onChange={this.handleChange}/>
               <input type="submit" value="Search!"/>
            </form>
         </div>
      )
   }



//functional
    return (
        <div>
            <h2>Recipes Search Bar</h2>
            <form onSubmit={handleSubmit}>
                <input
                    name="recipe"
                    type="text"
                    value={recipe}
                    onChange={event => {
                        setRecipe(event.target.value)
                    }}
                />
                <input type="submit" value="Search!" />
            </form>
        </div>
    )

render() turns into return(). There's no longer any mention of this. The biggest change here is the onChange for the text input.

Instead of using handleChange and this.setState to update the local state upon the input's change, we can just call the hook we set up with setRecipe. Then, we feed it the updated value, which we're grabbing from the input bar itself.

The last part is to modify the handleSubmit. All we have to do is remove this.

const handleSubmit = event => {
   event.preventDefault()
   props.fetchRecipes(recipe)
}

Final Product

import React, { useState } from "react"

export default function RecipesInput(props) {
    const [recipe, setRecipe] = useState("")

    const handleSubmit = event => {
        event.preventDefault()
        props.fetchRecipes(recipe)
    }

    return (
        <div>
            <h2>Recipes Search Bar</h2>
            <form onSubmit={handleSubmit}>
                <input
                    name="recipe"
                    type="text"
                    value={recipe}
                    onChange={event => {
                        setRecipe(event.target.value)
                    }}
                />
                <input type="submit" value="Search!" />
            </form>
        </div>
    )
}

React Hook Test Link

My Take on Async JavaScript Promises with Concurrency Limit

BebopVinh — Mon, 21 Oct 2019 03:36:19 +0000

In a recent interview, I was asked to go under the hood of a Promise and explain how it would work with a concurrency limit. Having only focused on how Async/Await made everything so much easier to read and write, I blanked out. While I did my best to attempt at it, I couldn't explain it well enough to pass the tech interview.

Disclaimer: Below is my first impression and attempt at comprehending what a Promise and Concurrency really are. I still have much to go on and am really open to any corrections/advice to this post. Sources linked below.

Promise?

Okay, a Promise is an object to be fulfilled at a later time provided by the Web API. It can be resolved or rejected. If resolved, a .then chain can be run on the result. If rejected, a .catch will handle the errors. Both .then and .catch takes a callback functions and let you manage your Promise however you like.
Paraphrase: As best explained by Kyle Simpson, getting a Promise is like going to a burger-joint and ordering a burger. You don't get a burger instantly, as they have to make-to-order. Instead, you get a receipt, which then lets you exchange it for the burger you order once it is ready.

The structure of a promise is like this (as shown by Beau):

   //structure of a Promise
   let myPromise = new Promise(function(resolve, reject) {
      if (conditions are met) {
         resolve('Done!')
      } else {
         reject('Something went wrong!')
      }
   })
   //chaining a `then` when resolved
   .then(result => {return result})
   //chaining a `catch` when rejected
   .catch(error => console.log(error))

There's other things regarding Promises that I won't go over. Such as try/catch which basically lets you wrap your Async operations in a try block and it will call catch if anything inside the block goes wrong.

There's also Async/Await, which is like syntactic sugar for writing async functions and make them read like synchronous things. Check out the video by Brad Traversy below, it makes life simpler! I wasn't allowed to use this, though.

Concurrency Limit

My best take on these two words is how many Promises can run or should be running at a given time interval. Given a limit (say 10 Promises at a time) and an array of Promises (say 100 elements), the solution function should run 10 Promises in parallel and queue up the next Promise should one of them complete. This repeats until all the Promises are resolved.

In comes Promise.all(), which is a Prototype method that returns a super ultimate Promise (I'm making this up) once all the Promises are resolved.

Here's my stab at this after reading and watching some materials. I did even worse in the interview.
Warning: Broken code below!

const limit = 10
let promiseBatches = []
let promiseArray = [] //realistically would be filled with Promises to be resolved
function promiseBatch(promiseArray, limit) {
   let batch = []
   i = 0
   //run 10 promises while there are still 10 promises
   while i < limit && promise.Array.length > 0 {
      let promise = promiseArray.shift()
      i ++
      batch.push(promise.resolve())
   }
   //adds batch to big batches array for Promise.all()
   promiseBatches.concat(batch)

   //recursive until promiseArray is empty, else return Promise.all() of the batches
   if promiseArray.length > 0 {
      promiseBatch(promiseArray, limit)
   } else {
      return Promise.all(promiseBatches)
   }
}

I'm pretty sure I'm still wrong. Any thoughts?

Sources

Promises explained by Beau from FreeCodeCamp

Event Loop by Philip Roberts

Advanced Async and Concurrency Patterns by Kyle Simpson

Async/Await by Brad Traversy