DEV Community: Yong Liang

JS Heaps

Yong Liang — Mon, 02 Sep 2019 06:54:36 +0000

/* Heaps is a type of tree.

Binary Heaps is similar to Binary Search Tree, but with different rules.
Each node can have most two child nodes. No order to the left or right,
as long as they are smaller or larger than the parent node.

MaxBinaryHeaps- parent nodes are always larger than child nodes.

MinBinaryHeaps- parent nodes are always smaller than child nodes.

Binary Heaps evens out the left and right and the tree is always compact
rather than one sided.

/*Use array or list to present a heap tree

special rules: 
from a parent node, for any index in an array, the left child is placed in 2*index+1,
the right child is placed in 2*index+2.

to find the parent node from child nodes, use Math.floor((index -1)/2)

much like stack/queue, heap can be implemented with array

Coming from Javascript, Arrays in Java are confusing?

Yong Liang — Fri, 23 Aug 2019 05:35:52 +0000

Coming from Javascript, arrays in Java were confusing to me. Below I would like to discuss how arrays work in Java.

Array Declaration

In Java, an array has to declare with a type. Elements in it has to match the array type as well.

//integer array example, both declarations will work

int [] myArray; 
int myArray [];

//string array example

String [] strArray;
String strArray [];

Give array a size

The size of an array will not change dynamically in Java, so we have to define a size before using it. ArrayList is a better option when we need a dynamic size for a collection of datas.

//using the arrays from the examples above, we can define a size for them

myArray = new int[10];

//we can also perform the declaration and size with one line of code

int [] myArray = new int[10];

Array literal

When we know what elements that an array will have, we can use array literal to declare an array.

//the size of the array is determined by the number of elements were defined

int myArray = new int[]{1,2,3,4,5,6,7,8};

//in newer version of Java, we can skip the new int[]

int myArray = {1,2,3,4,5,6,7,8};

My favorite loop to use to get the array elements

for(int eachNumber : myArray){

 System.out.println(eachNumber);
}

How to Write Unit Tests with JUnit 5 in Java (Eclipse)

Yong Liang — Sat, 17 Aug 2019 22:02:39 +0000

What is JUnit?

JUnit is a Java testing framework. It can be used for both Unit Testing and UI Testing. It is a great tool and fun to use. In this article, I would like to demonstrate how to use this framework in Eclipse IDE for beginners.

Junit 5 comes with Eclipse so all we need to do is add it to our project when we first creating the project.

Steps:

add Junit to the project.
add new file -> create a new class file.
add new file -> create JUnit Test file.
write some methods in the class.
create an object of that class inside the Junit Test file.
use the object to invoke class methods to test inputs and outputs.

//This class has one method which will return a string argument.
public class HelloWorld {

     public String printThis(String str){

               return str;
        }

}

//The JUnit file would look like this

class HelloWord{
//instantiate a HelloWorld object called hello.
   HelloWorld hello = new HelloWorld();

//test method names tends to be descriptive 
   @Test
   void should_return_a_same__passing_string_value(){

//one way to think about constructing a test is use these 3 steps

       //given (the inputs)
       String cake = "chocolate cake";

       //when (the actions)
       String cakeTest = "chocolate cake";

       //then (the results)

       assertEquals(cakeTest, hello.printThis(cake) );
//this will pass the test if both values are equal.
 }
}

These are the steps to perform a most basic unit test.

Tricky Javascript Stuff 01

Yong Liang — Sun, 11 Aug 2019 06:59:41 +0000

1. Javascript has two types of value for empty values - null and undefined. What are the differences for these two?

Undefined -

When the value of a variable is not defined, such that when we create a variable without assigning value, the variable is defined as "undefined". When we check the type with typeOf, the type is also undefined.

Some ways to get undefined:

declare a variable without giving it value
a function returns an empty value
not passing any value to a function's parameter

Javascript has a global variable called undefined and its value and type are shown as undefined.

Null -

Null indicates no value. It is a primitive type and we can assign null to variables. When we check typeOf null it returns as object, however, it's not really an object because we can not add properties to it.

2. == vs === || is the more the better?

The double == comparison operator will not check types, only checks values. It will return true for 8 == "8", even though 8 is a number and "8" is a string.

The tripe === operator will check both type and values. Therefore, 8 === "8" will return false since their types are different.

NaN is a not a number type, along with null and undefined, these three are unique types, and will not equal to other types.

Nan does not even equal to itself. NaN == Nan or NaN === NaN both will return false.

Source: https://www.thatjsdude.com/interview/js2.html#nullVsUndefined

Common Chrome Debug Tools Overview

Yong Liang — Wed, 31 Jul 2019 23:04:50 +0000

Debugger

Debugger allows us to set break points to force the code executions at a certain point. Once the program hits the break point and stops the execution, we can then examine the javascript values.

Console.log()

console.log() method displays a message to the console. The content of the message depends on what we pass to the console.log() method. For example, passing console.log("testing") will write "testing" to the console. We can pass objects, arrays, any type of data to console.log() and check their values.

Console.dir()

The console.dir() method displays all the properties of an object in a list manner and allows us to see the content of the child objects.

Console.table()

The console.table() method displays datas in a table format. The first argument is mandatory, which can be an array or object. The second optional argument specifies the number of columns the table should display.

Remove Duplicates From Arrays in Javascript

Yong Liang — Sat, 27 Jul 2019 16:14:31 +0000

Summary

There are several ways to remove duplicates from arrays in JS. This article will demonstrate a method using loop and indexOf() and another method using Array.from() and Set().

Method #1

create a new empty array
iterate through the original array
use indexOf to check whether the new array already has a same value
if the value is not found in the new array, then push it.

//Objective: remove the duplicate values in array1
let array1 = [1,2,3,3,4,2,5,7,1]

let array2 = []

for(let eachValue of array1){
    if(array2.indexOf(eachValue) === -1){
      array2.push(eachValue)
    }
}

console.log(array2) //returns [ 1, 2, 3, 4, 5, 7 ]

Notice that array.indexOf returns -1 if no value is found. In that case we will push the value into the empty array we have created because it is a unique value.

Method #2

Set is a javascript built-in method, which allows to store unique values.
since set returns collection of unique values in an object type, we need to convert this object back to an array.
Array.from() method will convert the Set() object back to an array. This creates a new, shallow copied array.

//Objective: remove the duplicate values in array1

let array1 = [1,2,3,3,4,2,5,7,1]

array1 = Array.from(new Set(array1))


console.log(array1) //returns [ 1, 2, 3, 4, 5, 7 ]

We can also use the array.filter() and indexOf() to return only unique values.

Solve the Two Sum problem with Javascript

Yong Liang — Thu, 18 Jul 2019 12:13:26 +0000

Objective

Given an array of numbers and a target number, find the sum of two numbers from the array that is equal to the target number. May not sum the same index twice.

Brutal Force Solution

Use a nested for loops to check all possible sums in the array and match the target number as it literates. Time Complexity for this solution is O(n^2).

function twoSum(numArray, numTarget)
{
 const arraySize = numArray.length;

 for(let i = 0; i < arraySize; i++){

     for(let j= i + 1; j < arraySize; j++){

       if(numTarget - numArray[i] === numArray[j]){

          return `The sum of indices ${i} and ${j} equals ${numTarget}` 
        }
     }
  }
 return "target not found."
}

//calling 

twoSum([1,2,3], 5)

//returns 'The sum of indices 1 and 2 equals 5'

twoSum([1,2,3], 6) //returns "target not found"

Use key/value Pairs Solution

Instead of thinking the sum of index1 + index2 = target, we can think of index2 = target - index1, then look for index2 in the key/value object which we will store the array values as keys, and array index as value.

The lookup time in objects or hash tables is O(1) constant time, therefore, this implementation improves the time complexity to O(N).

Pseudo code:

create an empty object
iterate the array with a for loop
let num2 = target - num1 (the num2 is the number we want to lookup for in the object)
on each iteration add the value/pair to the object
if the num2 is in the object, we have found it, return the indexes and the sum

function twoSum(numArray, target){

  const numObject = {} //create an empty object

  for(let eachNum in numArray){

    const otherNum = target - numArray[eachNum]

    if(otherNum in numObject){

      return `${otherNum} + ${numArray[eachNum]} = ${target}`
    }

    numObject[numArray[eachNum]] = eachNum

//adding key/value has to go after the if statement to avoid adding the same index twice.
  }

  return "target not found"
}

twoSum([1,2,3,4,5], 8) //output: '3 + 5 = 8'
twoSum([1,2,3,4,5], 10) //"target not found"

Javascript Built-in sort() method

Yong Liang — Fri, 12 Jul 2019 20:33:17 +0000

How does JS built-in sort() method work?

the sort() method will sort arrays in place and return a sorted array. The default sort order is built upon converting the elements into strings, then comparing their sequences of UTF-16 code units values.

The sort() method accepts a compareFunction(a,b) as argument. In order to sort things propertly, we need to define what the compareFunction does.

Examples

var months = ['March', 'Jan', 'Feb', 'Dec'];
months.sort();
console.log(months);
// expected output: Array ["Dec", "Feb", "Jan", "March"]

var array1 = [1, 30, 4, 21, 100000];
array1.sort();
console.log(array1);
// expected output: Array [1, 100000, 21, 30, 4]

//the results are not sorted correctly.

The default sort() compares elements as strings, so 21 is greater than 10000 because 2 is > 1 for example. In order to fix this we can use the compareFunction.

The compareFunction

These are the rules I found from Mozilla's documentation:

If compareFunction(a, b) is less than 0, sort a to an index lower than b (i.e. a comes first).
If compareFunction(a, b) returns 0, leave a and b unchanged with respect to each other, but sorted with respect to all different elements. Note: the ECMAscript standard does not guarantee this behavior, thus, not all browsers (e.g. Mozilla versions dating back to at least 2003) respect this.
If compareFunction(a, b) is greater than 0, sort b to an index lower than a (i.e. b comes first).
compareFunction(a, b) must always return the same value when given a specific pair of elements a and b as its two arguments. If inconsistent results are returned, then the sort order is undefined.

var numbers = [4, 2, 5, 1, 3];
numbers.sort(function(a, b) {
   return a - b;
 });
 console.log(numbers);

// [1, 2, 3, 4, 5]


//to sort by the length of strings

function lengthCompare(a,b){
    return a.length - b.length 
}

console.log(["grapefruitPlusKiwi", "apple", "pie", "orange", "pineapple", "banananananana"].sort(lengthCompare))

//["pie", "apple", "orange", "pineapple", "banananananana", "grapefruitPlusKiwi"]

source from mozilla

How to Reverse a Given String in Javascript

Yong Liang — Sat, 06 Jul 2019 03:38:39 +0000

Objective

Create a function which takes a string as argument and return a reversed version of that string.

Method 1

1.Convert the string into an array so that we can iterate through each character.

2.Iterate the array backward and push each character into a new array. We can use the built-in reverse() function or write one ourselves.

3.Finally use .join() to convert the array back to a string and return it.

//This solution uses all javascript built-in methods

function reverseString(str){

    let strArray = str.split("") 
    //it's important not to add space on the quotation mark here.

    strArray = strArray.reverse()

    return strArray.join("") //also no space on quotation mark here
}

reverseString("amazon google") //call the function

"elgoog nozama" //the returned string

Write our own reverse method:

function reverseString(str){

    let revArray = [];
    let strArray = str.split("")

    // Looping from the end to the beginning
    for(let i = strArray.length; i >= 0; i--) {

       //push each character into the new array
        revArray.push(strArray[i]); 
    } 

    // Joining the array elements 
    return revArray.join(''); 
}

Instead of using the built-in .split() to converse a string to array, We can also use the for ... of loop. This way we can iterate through each character of a string instead of an array.

function stackReverse(str){
    let strArray = [];

    for(let eachLetter of str){
        strArray.push(eachLetter)
    }

    strArray.reverse();

    return strArray.join("")

}

stackReverse("google amazon") //call the function

"nozama elgoog" //return value

This is my finding for how to reverse a string in javascript, hope you've enjoyed it.

How does Bubble Sort work?

Yong Liang — Thu, 27 Jun 2019 00:02:38 +0000

What is bubble sort?

Bubble sort is an algorithm where the largest value will bubble up to the top of a list, continue sorting this way we will have an ascending sorted array or list. We will use nested loops to compare each current items with the rest of the items in the list.

Understand how to swap two elements using Javascript

//swapping function takes an array, and two indexes

 function swap2(arr, index1, index2){
     let temp = arr[index1]; //let a temp variable to hold index1's value
     arr[index1] = arr[index2]; //replace index1 with index2' value
     arr[index2] = temp;//finally replace index2 with temp, which was index1
 }

In the ES2015 we can do swapping using this syntax

const swap = (arr, index1, index2) => {     
[arr[index1], arr[index2]] = [arr[index2], arr[index1]]
 }

Implement bubble sort using nested array - Javascript

Sudo Code:
1.iterate the array reversely
2.create a counter variable
3.iterate the inner loop to compare each item
4.swap the items if the current item is greater
5.when swap happens, set noSwap to false so that it won't break the loop
6.when noSwap never set to false, loop breaks.

function BubbleSort(arr){
    for(let i = arr.length; i >0; i--){ 
        let noSwap = true; 
        for(let j =0; j < (i-1); j++){ 
            if(arr[j] > arr[j+1]){ 
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j+1]= temp;
                noSwap = false;
            }
        }
        if(noSwap){break;}
    }
    return arr;
}

The time complexity for bubble sort is O(n^2), making it less popular compare to merge sort and other sorting algorithms.

What are Linear and Binary search in Javascript?

Yong Liang — Tue, 18 Jun 2019 00:25:31 +0000

How do Linear Search & Binary Search work?

A linear search checks each items in a collection of data one at a time in order to find the searching item. For example, when we search an item in an array, the worse case is that we have to literate through the whole array, which gives us an O(n) performance. An example of linear search would look like this in Javascript:

//Linear Search 
let arr = [1,4,3,9,5,2,7,8]

//this function accepts an array and an element to be searched
function linearSearchArray(arr, targetElement){

 for(let eachItemIndex in arr){
   if(arr[eachItemIndex] === targetElement){
     return eachItemIndex;
  }
 }
 return -1;
}

linearSearchArray(arr, 9) //will return 3 because 9 has an index of 3 in the array.

Binary Search

A binary search is a little more complicated and only works on a sorted array. Binary search in a nutshell is that we first look at the middle element in a sorted array, then compare it with the item we are searching for, if the middle element is greater than the searching item, then we know that half of the elements in the array are greater than the item we are searching for, therefore we can drop that half of the array and search only the other half. We continue this operation until we find the element we are looking for.

In a worse case, as we shrink the array, eventually there will be only one element left to check, if that isn't the matching element then the element we are looking for is not in the array. Because we drop half of the array each time we check, the size of the array is divided by 2 every time we conduct a comparison. Hence the time complexity of a binary search is O(log n). It is much faster than linear search on average. Here is one way to implement a binary search in Javascript:

//Binary Search 

let arr = [1,4,3,9,5,2,7,8]

//this function takes an array and an element we want to find arguments

function binarySearchArray(arr, target){

//define the positions we will work with
  let startPosition =0, endPosition = arr.length -1, midPosition = 0;

//use a while loop to keep dividing and looking for the target
 while(startPosition <= endPosition){

//define and update the middle position
       midPostion = Math.floor((startPosition + endPosition) /2);

//break the loop when target is equal to the middle element
//otherwise we update either the start or the end position so that half //of the array will be dropped.

       if(target == arr[midPostion]){
           console.log("target found at index:", midPostion);
           return true;
         }
        else if(arr[midPostion] < target){

            startPosition = midPostion +1;
            //console.log("target not yet found");
        }
        else{
            endPosition = midPostion -1;
            //console.log("target not yet found");
        }

    }

    return false;

}

//call the function
binarySearchArray(arr, 9)
//this returns target found at index: 3 true

Stack and Queue in Javascript: Use Array or LinkedList?

Yong Liang — Mon, 10 Jun 2019 23:10:52 +0000

Introduction:

Stack and Queue are collection of datas, similar to arrays or lists, but follow different principles in design. Stack and Queue mainly focus on adding and removing one item at a time to a list. They both are important data structures and have different uses in our applications.

Stack:

Stack - is a concept that creates a collection of data uses
First-in-last-out or last-in-first-out principle. Which means that items that first added to the list will be the last one to be removed.

Let's say I use array.push() 10 times to add 10 items to a new array, when I do array.pop(), the first items to pop is the last item I pushed in. This concept is very useful to implement something like undo/redo functions. when we do an undo, we undo the last action. Website histories is also a good use of a Stack because the last page we visit displays at top of the list.

The most basic Stack should have a method to add and a method to remove items from a list that follows the First-in-last-out principle. In Javascript we can use push to add an item to the end of the list, and pop to remove the item from the end of the list. Another way to do it is to use unshift/shift to add/remove from the beginning of the list.

Keep in mind that when we remove/add anything at the beginning of an array, all elements in it need to re-index. This does not happen when we add/remove items at the end of an array. So push/pop will outperform unshift/shift for Stack implementation. A Stack using array would look like this:

class Stack{
    constructor(){
        stackArray =[]
    }

    push(element){
        this.stackArray.push(element)
    }

    pop(){
        if(this.stackArray.length === 0){
            return "underFlow"
        }
        this.stackArray.pop()
    }
}

In Javascript, as array's length grows, the array doubles its size under hood, automatically and dynamically. This can waste a lot of space in memory for a Stack, because we only add/remove one item at a time with Stack. Due to this, a SinglyLinkedList is more ideal to create a Stack. Optimized for space complexity and Unshift/Shift methods are constant time O(1) (same as push/pop in array) in a SinglyLinkedList.

Queue:

Queue - Unlike Stack, Queue uses a concept of first-in-first-out or last-in-last-out principles. The first item added to a list is the first item to be removed when requests. Similar to how printers work, the first request sent to it is the first page to be printed. Queue is useful for anything like telephone wait line, restaurant wait line etc...

In Javascript, one way to implement a Queue using array is to use push() to add items, and shift() to remove item, as this will satisfy the concept of first-in-first-out principle. However, because shift() remove the first item in an array and all indexes need to shift over, this compromises the time complexity, achieving only O(n) for removing.

Fortunately, we can use a singlyLinkedList again to create a Queue. Both push() and shift() methods are constant time O(1) in singlyLinkedList. This allows our Queue to have a faster performance for adding/removing items, as well as a dynamic length list to save space in memory.