Forem: Daniel Zaltsman

Breadth-first search implementation

Daniel Zaltsman — Sun, 26 Jul 2020 04:03:57 +0000

Hello there! If you've somehow stumbled this post, I'm assuming you're trying to understand how the breadth-first search algorithm works, and how to use it to solve problems!

In my other post about the differences between depth-first search and breadth-first search, we talked about cases where we would use the two appropriately. In this post I'll explain how breadth-first search and then implement a way traverse a graph with it.

A major difference between the two is the data structure we use. DFS uses stacks(in case of recursion the call stack) and BFS uses queues.

We'll traverse a tree using BFS and I'll describe each step.

var levelOrder = function(root) {
    // If root is null return an empty array
    if(!root) return []

    const queue = [root] // initialize the queue with root
    const levels = [] // declare output array

    while(queue.length !== 0){
       const queueLength = queue.length // 
       const currLevel = [] // Declare this level

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

           const current = queue.shift()

           if(current.left){
               queue.push(current.left)
           }
           if(current.right){
               queue.push(current.right)
           }

           currLevel.push(current.val)
       }

       levels.push(currLevel)
   }
    return levels
}

We start by checking if root is null. We then initalize our queue and push root into it, since we know that we will visit it first.

Now we go into our while loop, which will keep going until our queue is empty. Then we get the length prior to dequeueing, and loop through to exhaust all options and only to include nodes at currLevel. In our for loop, we add the left and right node for the current level and the push it into currLevel, and after the level is finished we push it into the output array.

This repeats until we get to the last level and eventually the function returns an array of arrays, each one containing the nodes of each level of the tree.

Binary Search

Daniel Zaltsman — Sat, 18 Jul 2020 23:27:49 +0000

Today I'll be going over binary search, a search algorithm that finds the position of a target value in a sorted array.

It works by repeatedly halving the portion from the list that could contain the item until you land on the intended target. We start from the middle of the list and depending on the condition, we manipulate the range to eliminate a half of the list.

Let's take a look at a classic binary search problem: Find an element position in a sorted array. We have the target element and we want to return the index/position of it.

const binarySearch = (arr,target) => {

    let left = 0
    let right = arr.length - 1
    let boundary_index = -1

    while(left <= right){
        let mid = left + Math.trunc((right - left) / 2);
        if(arr[mid] === target){
            return mid
        }
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1
}

The way we implement binary search is by first creating the range in which the element could reasonably be. In this while loop, we are constantly searching the middle element of the array and checking for three things:

1: Is the current element the target? If it is, we return the index.

2: Is the current element smaller than the target? If it is, we know that everything to the left of this element cannot be the target. Therefore, we make the left boundary of the range mid + 1.

Is the current element larger than the target? If it is, we know that everything to the right of this element cannot be the target. Therefore, we make the right boundary of the range mid - 1.

We can assume these things because the array is sorted in ascending order. The values become larger as we go to the right of the list. If we never find the index, we return -1.

Reversing a string

Daniel Zaltsman — Sat, 11 Jul 2020 23:58:23 +0000

Here comes the next challenge: Reversing a string.

Description: Write a function that reverses a string. The input string is given as an array of characters char[]. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
You may assume all the characters consist of printable ascii characters.

Simple enough! Here was my first answer when I attempted it a few months ago.


return s.reverse()

Cheeky. But let's come up with our own solution.

So we cannot allocate memory to a new array, and we have to modify the array in-place. The first thing I do is look for a pattern. When reversing a string, the last letter is first, first is last, second to last is second, second is second to last, etc. This will be repeated until we hit the middle. It may be different odd/even length words, but we can account for that. Let's implement that solution!

var reverseString = function(s) {

for(let i = 0; i < s.length/2 ; i++){
        let prev = s[i]
        s[i] = s[s.length - 1 - i]
        s[s.length - 1 - i] = prev
    }
}

Let's break down this solution. On each character, we will save the current character, change the current character in the array to the character on the opposite side of the array, and then use the saved character to change the character on the further end.

In this solution, we only need one pointer, prev. The iterator variable i will increment until it hits the middle of the word. For odd numbered words the reversing will stop before it hits the one letter in the middle and for even numbered words it will continue until it reverses the last pair in the middle of the word.

Fizzbuzz

Daniel Zaltsman — Mon, 06 Jul 2020 02:56:13 +0000

Fizzbuzz is a test that was devised to filter out 99.5% of candidates who are very weak programmers. It also shows what style of programming people use, as this question can be handled a many number of ways.

Here is the problem: Write a program that outputs the string representation of numbers from 1 to n. But for multiples of three it should output “Fizz” instead of the number and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”.

Before I tackled this question, I thought more about scalability than just immediately answering the problem. I had thought if I hashed the keys and the values, I would be able to add more keys if it was needed. Here is my original solution:

var fizzBuzz = function(n) {


    let result = []
    let fizzObject = {
        3: 'Fizz',
        5: 'Buzz',
        // 7: 'Jazz'
    } 
    let numArray = [3,5]

    for(let i = 1; i < n + 1; i++){
        let result_str = ''
        numArray.map((key) => {
            if(i % key === 0){
               result_str += fizzObject[key]
               }            
        })        
        if(!result_str){
            result_str = i.toString()
        }
        result.push(result_str)
    }    
    return result
};

Notice the commented out "7" key and value "Jazz". If I wanted to extend this solution, I can do it easily! However, it is very slow. So I tested out my other solution to see how fast, albeit naive, it is:

var fizzBuzz = function(n) {
    let result = [];
    for (i = 1; i <= n; i++) {
        if (i % 3 == 0 && i % 5 == 0) result.push("FizzBuzz");
        else if (i % 3 == 0) result.push("Fizz");
        else if (i % 5 == 0) result.push("Buzz");
        else result.push(i + "");
    }
    return result;
};

This solution is much faster, but it may become messy depending on how many lines of code you need to add to account for new modifications.

Valid Anagram

Daniel Zaltsman — Mon, 29 Jun 2020 00:48:56 +0000

Here we have a new leetcode problem:
Given two strings s and t , write a function to determine if t is an anagram of s.

Let's go over the definition of an anagram: a word, phrase, or sentence formed from another by rearranging its letters:
“Angel” is an anagram of “glean.”

So for a word to an anagram of another, they must use the same letters and also the same amount of letters.

One solution is to compare both strings by turning them into arrays, sorting them, and comparing them one by one. However, this is very slow. The worst case scenario is the time complexity being O(n^2).

Here's my solution:

const isAnagram = (s, t) => {
    if(!s || !t){
       return null
       }
    if(s.length !== t.length){
       return false 
       }

    let obj = {}

    for(let i = 0; i < s.length; i++){
        if(obj[s[i]]){
           obj[s[i]]++
           }
        else{
            obj[s[i]] = 1
        }
    }

    for(let i = 0; i < t.length; i++){
        if(!obj[t[i]]){
           return false
           }
        if(obj[t[i]] === 0){
           return false
           }
        if(obj[t[i]]){
           obj[t[i]]--
           }
    }
    return true
};

Step 1: Take all the letters from the first word and put them into a hash table, the keys being each letter, and the value being how many occurrences of each letter.

Step 2: Run through the second word and run each letter from the second word to the keys of the hash table with three conditions placed in it. The first case tests to see whether the letter is in the object at all, and if it isn't would disqualify it from being an anagram. The second case checks to see if the value of the letter is greater than 0. If it is, that means there is an extra letter occurrence, which means it is not an anagram. The last condition tests to see if it the letter exists in the hash table. To account for that letter, we lowered the value for that letter in the hashtable. Therefore, the case where there are no more letters in the word we are comparing, and all values in the hashmap are 0 is the case where it is a valid anagram.

This solution is O(n) + O(m). I've also put a condition before the main comparison starts to check if the lengths are equal.

Reverse a Linked List

Daniel Zaltsman — Fri, 19 Jun 2020 03:32:13 +0000

This will be my first post of many as I navigate through leetcode, sharing and explaining my solutions!

This one, however, is more of a utility question. Basically you know it or you don't.

If you don't know what a linked list is, the short explanation is a linear data structure that contains a head, which contains information, and a reference to the next object. If you want to read more on linked lists, check out my posts on data structures!

Reversing a linked list

This portion is for those who are already aware of what linked lists and how they're implemented. The question is simple enough: Reverse a singly linked list.

I know what you're thinking: WHAT?! BUT HOW?!

That's what I thought. The key is pointer variables. I'll show you the code first and explain how it works.

var reverseList = function(head) {
    let prev = null
    let current = head
    let next = head

    while(current !== null){
        next = current.next
        current.next = prev
        prev = current
        current = next
    }
    return prev
};

This may be a bit helpful, but let's dive into it.
As you can see, we have three variables: prev, current, and next outside of a while loop.

Prev is set to null, current is set to the head of the linked list as well as next.

While current does not equal null, next becomes the node after the current one. The reference to the next node now becomes prev, which is null. prev now becomes current, which is the head. And current becomes the next node.

If we were using 1->2->3->4->5 as our linked list, next moved on from 1 to 2, the reference or arrow from 1 goes to null, prev becomes 1, and current becomes 2 along with next.

Do you see the pattern?

What should happen next is: next becomes 3, the reference or arrow from 2 now points to 1, prev becomes 2, and current becomes 3. This continues until current becomes null. Here's a nifty gif to help visualize this:

Error handling in javascript

Daniel Zaltsman — Sun, 14 Jun 2020 22:28:19 +0000

Errors in your code are inevitable. Controlling the flow and error handling are important parts of debugging and making your program run smoothly.

In this post, we'll cover throw, try/catch, and finally.

Throw

The throw statement throws a user-defined exception. Execution of the current function will stop (the statements after throw won't be executed), and control will be passed to the first catch block in the call stack. If no catch block exists among caller functions, the program will terminate.

If you know what your value shouldn't be, you can add a throw statement to your function and catch unapproved values before they continue.

let num = 12

if(num === 12){
  throw "I don't like this value"
}

//expected output: Uncaught I don't like this value

You may throw any expression, not just expressions of a specific type. The following code throws several exceptions of varying type: strings, numbers, booleans and objects.

Try...Catch

The try...catch statement marks a block of statements to try, and specifies one or more responses should an exception be thrown. If an exception is thrown, the try...catch statement catches it.

The try...catch statement consists of a try block, which contains one or more statements, and a catch block, containing statements that specify what to do if an exception is thrown in the try block.

let json = '{ "age": 30 }';

try {

  let user = JSON.parse(json); 
  if (!user.name) {
    throw new SyntaxError("Incomplete data: no name");
  }

  console.log( user.name );

} catch(e) {
  console.log( "JSON Error: " + e ); 
}

When we obtain our JSON object, we find there is no name property. Now we throw our new Syntax error, which means that our catch block will run and log the error in the console. If there was a name in the JSON, it would log the name.

Finally

The finally block contains statements to be executed after the try and catch blocks execute. Additionally, the finally block executes before the code that follows the try…catch…finally statement.

It is also important to note that the finally block will execute whether or not an exception is thrown. If an exception is thrown, however, the statements in the finally block execute even if no catch block handles the exception that was thrown.

try {

  let user = JSON.parse(json); 
  if (!user.name) {
    throw new SyntaxError("Incomplete data: no name");
  }

  console.log( user.name );

} catch(e) {
  console.log( "JSON Error: " + e ); 
} finally {
  console.log("This will always run, even when there's no exception")
}

Text formatting in Javascript

Daniel Zaltsman — Mon, 08 Jun 2020 01:04:04 +0000

At some point, you may need to transform/manipulate strings to output them in the way that you want/need. You can write custom methods, but I think there's something here for you. I present to you several javascript methods for text formatting!

concat()

Combines the text of two strings and returns a new string.

let string1 = 'Hello'
let string2 = 'world!'
let string3 = string1.concat(' ', string2)
console.log(string3)
// expected output: 'Hello world!'

split()

Splits a String object into an array of strings by separating the string into substrings.

let string1 = 'I!am!saying!hello!to!the!world'

string1.split('!')
// expected output:['I','am','saying','hello','to','the','world']

toLowerCase(),toUpperCase()

Return the string in all lowercase or all uppercase, respectively.

let string = "Hello World!"

let upperString = string.toUpperCase()
let lowerString = string.toLowerCase()

console.log(upperString)
// expected output: HELLO WORLD!
console.log(lowerString)
// expected output: hello world!

slice()

Extracts a section of a string and returns a new string.

let string = "Hello World!"

console.log(string.slice(0))
//expected output: Hello World!
console.log(string.slice(5))
//expected output: World!
console.log(string.slice(-1))
//expected output: !

match(), matchAll(), replace(), replaceAll(), search()

Work with regular expressions.

const paragraph = 'The quick brown fox jumps over the lazy dog. It barked.';
const regex = /[A-Z]/g;
const found = paragraph.match(regex);

console.log(found);
// expected output: Array ["T", "I"]

const p = 'The quick brown fox jumps over the lazy dog. If the dog reacted, was it really lazy?';

const regex = /dog/gi;

console.log(p.replace(regex, 'ferret'));
// expected output: "The quick brown fox jumps over the lazy ferret. If the ferret reacted, was it really lazy?"

console.log(p.replace('dog', 'monkey'));
// expected output: "The quick brown fox jumps over the lazy monkey. If the dog reacted, was it really lazy?"

trim()

Trims whitespace from the beginning and end of the string.

const greeting = '   Hello world!   ';

console.log(greeting);
// expected output: "   Hello world!   ";

console.log(greeting.trim());
// expected output: "Hello world!";

Spread operator

Daniel Zaltsman — Mon, 01 Jun 2020 03:29:16 +0000

If you're looking to conveniently make a shallow copy of objects in javascript(meaning one level deep), my recommendation is to use the spread operator.

From MDN: Spread syntax allows an iterable such as an array expression or string to be expanded in places where zero or more arguments (for function calls) or elements (for array literals) are expected, or an object expression to be expanded in places where zero or more key-value pairs (for object literals) are expected.

It looks like this:

let array = [1,2,3]
let arrayCopy = [...array]
console.log(arrayCopy)
// expected output: [ 1, 2, 3 ]

Spread syntax effectively goes one level deep while copying an array. Therefore, it may be unsuitable for copying multidimensional arrays,

We can take the content for objects and copy them as well, like so:

let obj = {id: 234}
let objCopy = {...obj}
console.log(objCopy)
// expected output: { id: 234 }

Another way to use the spread operator is to pass it into a function call:


let func = (x,y,z) => {
  console.log(`${x} + ${y} + ${z} = `,x+y+z)
}
let array = [1,2,3]
func(...array)
// expected output: 1 + 2 + 3 =  6

We can also concatenate arrays easily:

let arr1 = ["a","b","c"];
let arr2 = ["d","e","f"]
let arr3 = [...arr1,...arr2]
console.log(arr3)
// expected output: ["a","b","c","d","e","f"]

So there you have, an easy and effective way to take and manipulate the contents of an object. For deeper copies, I suggest using well known js libraries such as lodash.

React Hooks: useEffect()

Daniel Zaltsman — Fri, 22 May 2020 23:46:58 +0000

In my last post, I covered useState() and its usefulness in a functional component. In the same vein of imitating class component functionality, we have useEffect() to perform side effects in function components. In class components, we put side effects in componentDidMount and componentDidUpdate.

Here is a short example of useEffect():

function Example() {
  const [count, setCount] = useState(0);

  useEffect(() => {
    document.title = `You clicked ${count} times`;
  });
}

In useEffect() you have three parts: code that runs when useEffect() is called(which is on every render), the cleanup effect(runs when the component unmounts), and a parameter that you can pass into useEffect() which tells that useEffect() function to run only when that parameter changes. So if I put in a state variable, the effect may run when that variable changes. But if that component re-renders with the same value, it will not fire the effect.

In the example above, the effect will fire every time the component is re-rendered. However, if we placed the count as a second parameter and on a re-render it hadn't changed, the effect will not fire. The current example makes more sense since this is probably something you want to display at all times this component is mounted. You can even have multiple useEffect functions with these second parameters and separate your tasks based on what is being changed on a re-render.

Here's another example:

useEffect(() => {
  document.title = `You clicked ${count} times`;
}, [count]);

This is the useEffect with a second parameter placed in it. This will only fire if count changes.

Lastly, using the effect cleanup helps avoiding duplicating your code in componentDidUpdate and componentWillUnmount.

function FriendStatus(props) {
  // ...
  useEffect(() => {
    // ...
    ChatAPI.subscribeToFriendStatus(props.friend.id, handleStatusChange);
    return () => {
      ChatAPI.unsubscribeFromFriendStatus(props.friend.id, handleStatusChange);
    };
  });

The return statement is the cleanup: this effect runs when the component unmounts. In this case, it is unsubscribing from a friend's status.

React Hooks: useState()

Daniel Zaltsman — Mon, 18 May 2020 01:54:09 +0000

In a recent post on React hooks, I advocated their usage and explained how they could make your functional components flexible, extendable, and reusable. I would like to bring your attention to one of my favorite hooks: useState().

In some cases, you need to bring some state logic into a function component. Instead of rewriting it as a class component, you can hook into React state and lifecycle features. Implementing it is easy!

import React from 'react';
import {useState} from 'react'

function App() {

  const [importantThing, setImportantThing] = useState('initial value')

  return (
    <div >
      {importantThing}
    </div>
  );
}

export default App;

After importing useState from React, we see two values in an array being declared, and an initial value being set. The array is there to destructure the variables in useState, where the first value references the variable that lives in the state, and the second value is the reference to the function that changes the variable.

You can also set the variable to be an object, like so:

const [fruits, setFruits] = useState([{ apple: 'Granny Smith' }]);

React Hooks

Daniel Zaltsman — Mon, 11 May 2020 01:34:16 +0000

If you've been using functional components in your react project that contain a lot of logic and realized too late you need state, React Hooks is here to help!

In the early history of React, creating classes was a built-in method in React and at the time Javascript didn't have a way to natively build classes, until ES6. After ES6, React embraced classes in Javascript and made it so you can use native Javascript classes to create your components.

There were early problems with this, involving the complex nature of javascript classes like inheritance and the "this" keyword. In every class, because of ES6 standard, you had to remember to pass "props" to your super inside of your constructor method before you were able to use the "this" keyword.

On top of that, autobinding had to be done manually as opposed to the earlier "React.createClass()" method. For every method, you had to remember to bind each method to the object.

This quickly became a nuisance. Shortly after, thankfully, class fields were introduced which solved the problem of calling super. Additionally, using arrow functions solved the problem of autobinding.

This leads us to a question: why use function components?

Syntax friendly for javascript users

A function component is just a function. Easy to read and understand, there's no need to get confused with React syntax. It also inherently solved our previous issues with "super(props)" and the "this" keyword.

Lifecycle methods

Lifecycle methods are ways that classes manage application state. But with React Hooks, you can simplify the way your components maintain their internal state data, a la useEffect(). componentDidUpdate and componentDidMount can be reduced to one useEffect function. This was a problem since this logic is duplicated amongst those two methods, but with useEffect it is synchronized and only needs to be written once.

Sharing non-visual logic

React couples UI to a component, and the only way way to share logic between them was to use complicated patterns like Higher-order components and Render props. But React Hooks have an answer to that: custom hooks.

You can create custom hooks that are decoupled from any UI. As stated in the React documentation: "Unlike a React component, a custom Hook doesn’t need to have a specific signature. We can decide what it takes as arguments, and what, if anything, it should return. In other words, it’s just like a normal function. Its name should always start with use so that you can tell at a glance that the rules of Hooks apply to it...Custom Hooks are a mechanism to reuse stateful logic (such as setting up a subscription and remembering the current value), but every time you use a custom Hook, all state and effects inside of it are fully isolated."

Having hooks can make your future code simpler and highly reusable, so get out there and start experimenting with hooks!