DEV Community: Samantha Diaz

Singly vs. Doubly Linked Lists

Samantha Diaz — Thu, 28 Jul 2022 15:28:34 +0000

This blog briefly compares Singly Linked Lists and Doubly Linked Lists in JavaScript.

What Are Lists?

Lists are a data structure used to keep order of an object. Unlike an array, a list is not an actual data type in JavaScript and does not give its items an index. Instead, lists are created from Objects and use nodes to point to the previous or next node to keep order, depending on the list type.

Singly Linked Lists

To create a singly linked list, first create a class to represent a node, or the items you are collecting in the list. This class represents the blueprint for each item to be added to the list.

In the below example, I am using Color to act as the node class. Each color will have a name and a .next property to reference the next color in the list. The .next property will default to null when the color is created.

class Color {
    constructor(name){
        this.name = name;
        this.next = null;
    }
}

While we could use this Color class to create new colors, we'll let our list take care of that in the next example.

The Rainbow class is used to maintain our ordered list. The push method is defined inside the class and is used to create and add items at the end of the list.

class Rainbow {
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    push(name){
        let newColor = new Color(name);
        if(this.length === 0) {
            this.head = newColor;
            this.tail = this.head;
        } else {
            this.tail.next = newColor;
            this.tail = newColor;
        }
        this.length++;
        return this;
    }

let list = new Rainbow()
list.push("Red")
list.push("Orange")
list.push("Yellow")

console.log(list)
// Rainbow {
//     head: Color { name: 'Red', next: Color { name: 'Orange', next: [Color] } },
//     tail: Color { name: 'Yellow', next: null },
//     length: 3
//   }

Note that Singly Linked Lists only flow one way - from the head (Red) to the tail (Yellow).

This can become an issue if you care about time when trying to access the last item in a Singly Linked List, as you must iterate through each item to find the .next item until you reach the last value. For small lists this may not be a problem, but the larger the list grows, the more time it takes to iterate to the last item, giving a Big O of linear time (O(n)).

class Rainbow {

    ...

    get(index){ 
        if(index < 0 || index >= this.length) return null;
        let counter = 0;
        let color = this.head;
        while (counter !== index) {
            color = color.next;
            counter++;
        }
        return color;
    }
}

list.get(1) // this is index of 1, so the 2nd item, Orange
// Color { name: 'Orange', next: Color { name: 'Yellow', next: null } }

Doubly Linked Lists

Doubly Linked Lists are almost identical to a Singly Linked Lists, however they have an additional property called prev that represents the previous item in the list. This gives us access to move either forward or backwards through the list.

class Color {
    constructor(name){
        this.name = name;
        this.next = null;
        this.prev = null;
    }
}

class Rainbow {
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    push(name){
        let newColor = new Color(name);
        if(this.length === 0) {
            this.head = newColor;
            this.tail= newColor;
        } else {
            this.tail.next = newColor;
            newColor.prev = this.tail;
            this.tail = newColor;
        }
        this.length++;
        return this;
    }
    get(index){
        if(index < 0 || index >= this.length) return null;
        let count, color;
        if (index <= this.length/2){
            count = 0
            color = this.head;
            while (count != index){
                color = color.next;
                count++;
            }
            console.log("Moved Forward")
        } else {
            count = this.length - 1;
            color = this.tail;
            while (count != index){
                color = color.prev;
                count--;
            }
            console.log("Moved Backward")
        }
        return color;
    }
}

let list = new Rainbow()
list.push("Red")
list.push("Orange")
list.push("Yellow")

console.log(list)
// Rainbow {
//     head: <ref *1> Color {
//       name: 'Red',
//       next: Color { name: 'Orange', next: [Color], prev: [Circular *1] },
//       prev: null
//     },
//     tail: <ref *2> Color {
//       name: 'Yellow',
//       next: null,
//       prev: Color { name: 'Orange', next: [Circular *2], prev: [Color] }
//     },
//     length: 3
//   }

list.get(0)
// "Moved Forward"
// <ref *2> Color {
//   name: 'Red',
//   next: <ref *1> Color {
//     name: 'Orange',
//     next: Color { name: 'Yellow', next: null, prev: [Circular *1] },
//     prev: [Circular *2]
//   },
//   prev: null
// }

list.get(2)
// "Moved Backward"
// <ref *1> Color {
//   name: 'Yellow',
//   next: null,
//   prev: <ref *2> Color {
//     name: 'Orange',
//     next: [Circular *1],
//     prev: Color { name: 'Red', next: [Circular *2], prev: null }
//   }
// }

Difference Between Singly & Doubly Linked Lists

In short, the main difference is that Singly Linked Lists can only move in one direction, which can be unfavorable if you need to access items in the end of the list. Doubly Linked Lists track an extra property called .prev that allows us to travel in reverse. While time is shorten when accessing with Doubly Linked List, it requires us to store an additional variable in memory.

JavaScript's Object Overview

Samantha Diaz — Thu, 28 Jul 2022 00:52:49 +0000

This is an overview on how to create a basic object class in JavaScript.

JS Objects

JavaScript is not an object-oriented programming language. However, you can create 'objects' in JavaScript that behave similar to other OO languages.

Per the MDN Document, an object is a collection of properties.

JavaScript uses objects as a data type that provides a framework for how a particular item should behave. An instance method is used to define a specific instance's characteristics.

Syntax

    class Dog {
        constructor(name, breed, age, owner){
            this.name = name;
            this.breed = breed;
            this.age = age;
            this.owner = owner;
        }
    }

The Constructor Method

Every class uses the constructor method to instantiate a new instance of the object. In my example above, we pass in a name, breed, age, and owner when we create a new Dog object. We set this instance of Dog to be equal to the variables passed in. The keyword this refers to that particular instance of Dog.

Note that the above is just the method for creation; no instance of Dog has yet been created.

To better understand the object's properties versus the arguments given, you could alternatively set up your constructor per the below. Note that dogName, dogBreed, ... are the arguments passed in, and .name, breed are the properties each Dog instance will obtain.

    class Dog {
        constructor(dogName, dogBreed, dogAge, dogOwner){
            this.name = dogName;
            this.breed = dogBreed;
            this.age = dogAge;
            this.owner = dogOwner;
        }
    }

Create an Object

Create a new object with the new keyword, followed by the class name. I prefer to store a new object in a variable so we can use it later to modify.

dog1 = new Dog("Fluffy", "Golden Retriever", "4", "Jane Smith") 
// Dog {name: 'Fluffy', breed: 'Golden Retriever', age: '4', owner: 'Jane Smith'}

Retrieve an Object's Data

With our variable, dog1, we can access that variable's data by calling their properties.

dog1.name
// 'Fluffy'

dog1.breed
// 'Golden Retriever'

dog1.age
// '4'

Give an Object Behavior with Instance Methods

An instance method takes action on that particular Dog instance it is called on.

In the example below, the method named bark gives each instance of Dog the ability to "woof" when called. Similarly, the ageUp method increases that specific dog's age by 1 and returns its new age.

    class Dog {
        constructor(name, breed, age, owner){
          ...
        }

       bark(){
           return `${this.name} the dog says woof!`;
       }
       ageUp(){
           this.age += 1;
           return this.age;
       }
    }

dog1.bark()
// "Fluffy the dog says woof!"

dog1.ageUp()
// 5

Solve a Frequency Counter Problem in JavaScript with an Empty Object

Samantha Diaz — Fri, 15 Jul 2022 20:37:53 +0000

Creating an empty object in JavaScript can help to solve technical interview problems that ask you to find a value's frequency in an array.

Create an Empty Object

To create an empty object, set a variable equal to hashes. Note that unlike arrays, there is no order in an object and it uses key/value pairings instead of indexes.

let myObject = {};

Create Keys from an Array

Given an array, you can iterate and assign the array's values as the object's keys.

Code:

for (let i = 0; i < array.length; i++){ // A
   let key = array[i];                  // B
   if (myObject[key]){                  // C
        myObject[key] += 1;             // D
   } else {                             // E
        myObject[key] = 1;              // F
   }
}

Pseudocode:

A) Iterate through the array
B) Grab the value of each item in the array and set it to variable key
C) If key exists as a key in myObject...
- D) ... increment it by 1
E) If not (key doesn't exist in myObject)...
- F) ... create key in myObject and set it equal to 1

Refactored Code using Conditional (ternary) operator:

for (let i = 0; i < array.length; i++){
   let key = array[i];
   if myObject[key] ? myObject[key] += 1 : myObject[key] = 1
}

How to Access a Value in an Object

To access a key's value in an object is the same as accessing an index in an array:

myObject[value];

Solve a Frequency Counter Problem

Suppose you are solving to find the only number in an array that does not repeat. Assume there is only ever 1 answer.

To solve, you could:

A) Create an empty object
B) Iterate through the array to capture the array's values
C) Set the values as keys and increment on each occurrence of the array
D) Return the key in the hash with a count of 1 to find the non-repeating number

function findUniqueNumber(array) {  
  let myObject = {};                                          // A

  for (let i = 0; i < array.length; i++){                     // B
      let num = array[i];
      myObject[num] ? myObject[num] +=1 : myObject[num] = 1   // C
  }

  for (let key in myObject){
       if (myObject[key] === 1) return key;                   // D
  }
}

findUniqueNumber( [4, 6, 5, 17, 3, 5, 17, 88, 4, 88, 3] )     // 6

Big O of using an Object

Using brute force gives a Big O of quadratic O(n^2) because it requires two nested loops. As n inputs grows, it requires 2 sets of iterations to grab the first number and the next number to compare and repeats through the array's length.

By creating an object, we can reduce Big O to linear O(n). Here, we iterate twice through the array but on independent loops (2n can be simplified to n). So generally speaking, performance is only dependent on the size of the input array.

Swap Array Elements with JavaScript's ES6

Samantha Diaz — Tue, 12 Jul 2022 15:20:55 +0000

If you are solving a problem and it requires you to swap elements in an array, you might create a function like this:

function swap(array, a, b){
    let temp = array[a];
    array[a] = array[b];
    array[b] = temp;
}

Code Breakdown

We define a function called swap, and pass in arguments for an array, variable a, and variable b. These represent the values we want to swap.
Next, we declare a temporary variable, temp, and set that equal to the value of a in the array. We need to hold this value in a variable to refer to it later.
Then, we set the value of a in array to the value of b in array.
Finally, we set the value of b in array to the value of our temp variable. Notice that we can't set it to the value of a in array as we have already changed that to equal b's value.

BUT - with ES6, there's a simpler way!

const swap = (array, a, b) => {
    [array[a], array[b]] = [array[b], array[a]];
};

This uses Destructuring Assignment to separate the elements of the array into values that can be reassigned.

Code Breakdown

To make the code more compact, we declare the function using an arrow function named swap from ES6.
This function takes the same arguments: array, a, b
Instead of requiring the temp variable, we can simply assign the array's value of a and b to the respective opposite value on the right side of the equal sign.

Difference Between 'for...in' and 'for...of' Loop s

Samantha Diaz — Fri, 08 Jul 2022 17:27:51 +0000

This blog summarizes when to use 'for...in' and 'for...of' loops in JavaScript.

Difference

The 'for...in' loop is used for objects. The 'for...of' loop is used on data structures like arrays and strings.

It is possible to use a for in loop with arrays and strings. However, per JavaScript's MDN, the for of loop is preferred for strings and arrays as it returns the index as a number, whereas the for in loop will return the index as a string.

How to remember?

Think about for in loops as being inside an object. Since objects have no order, every item is associated inside it, all together. It's like a purse containing all your items - no order, everything is just inside.

Since arrays and strings have order, think about for of loops as in every item of an array or string. If you were reading a book (array) with chapters (indexes), you would say you're currently "reading chapter 3 of 30 in the book". So, think of it as 'for X index OF an array'.

For...in

For...in loops iterate through an object.

From the MDN Web Doc:

for (const variable in object) {
  statement
}

Examples

const object = { a: 1, b: 2, c: 3 };

for (const property in object) {
  console.log(`${property}: ${object[property]}`);
}

// "a: 1"
// "b: 2"
// "c: 3"

const obj = { a: 1, b: 2, c: 3 };
for (var i in obj) {
  console.log(i);
}

// "a"
// "b"
// "c"

For...of

For...of loops iterate over an array or string.

From the MDN Web Doc:

for (variable of iterable) {
  statement
}

Examples

const array1 = ['a', 'b', 'c'];

for (const element of array1) {
  console.log(element);
}

// "a"
// "b"
// "c"

const string = 'boo';

for (const value of string) {
  console.log(value);
}
// "b"
// "o"
// "o"

Algorithms - Two Pointers Pattern

Samantha Diaz — Mon, 27 Jun 2022 22:41:50 +0000

This covers the Two Pointer Pattern algorithm for technical interviews in JavaScript.

When to Use the Two Pointer Pattern

The Two Pointer Pattern is helpful when you need to perform a search to find a pair of numbers that meet a certain condition within a sorted data set.

For example, you can use this method to solve to find the first two numbers in an array that sums to a desired value.

The Two Pointer Pattern only works if your data set is sorted. Be sure to ask your interviewer if the data set is already sorted or if it can be.

How to Use the Two Pointer Pattern

Let's assume you are solving to find the first set of numbers that sum to zero in a sorted array.

Instead of using brute force and nested loops to check the 1st item with the 2nd, then the 1st item with the 3rd and so on, you can set up pointers in the first (left) and last (right) position of the array to compare.

Move the pointers based on the sum of the values:

If the sum of the pointers are greater than the solve for 0, it means the highest number is too large, so move the last pointer (right) down 1 position.
If the sum of the pointers are less than the solve for 0, it means your smallest number is too small, so move the first pointer (left) up 1 position.

Repeat this logic until the pointers meet or you solve for the desired sum.

Hasn't clicked yet?

If the biggest number (right pointer) is paired with the smallest number (left pointer) and their sum is greater than the desired value, then no other number paired with the right pointer will result in the desired sum as it will continue to be too high. So, move the right pointer one position over towards the center, keep the left pointer the same, and run through the iteration again.

The same idea applies if the sum of the pointers is too small - you move the left pointer over one spot towards the center. If the sum of smallest number (left pointer) and largest number (right pointer) is less than the sum, then there is no number remaining in the array that can be paired with the smallest number to meet your desired sum - since even paired with the highest number is too low.

Visual Examples

In this example, we solve for the first pair that sums to 0. Notice that the data set is sorted from smallest to largest.

If you take the first number at index 0 (-3) and the last number at index 6 (3), you'll find the answer in one iteration - the sum equals zero!

What if you are solving for the first pair that sums to 2? This completes in 3 iterations.

Here's another example, solving for sum of 10. Completes in 5 iterations:

Last example, solving for sum of 30. Here, the solution is not found and it uses the max amount of iterations, 4:

How to Code Two Pointer Solution

Example: return an array of the first pair that sums to zero.

function zeroSum(arr) {
   let left = 0;
   let right = arr.length - 0;

   while(left < right){
      let sum = arr[left] + arr[right];
      if (sum === 0){
         return [[arr[left], arr[right]];
      } else if (sum > 0){
         right --;
      } else {
         left ++;
      }
   }
}

Explain the Code Line by Line

function zeroSum(arr) {
  ...
}

Declare the JavaScript function, passing in arr as a parameter for a data set.

   let left = 0;
   let right = arr.length - 0;

Here we declare our pointer's initial index.
The left pointer will always start at 0, since an array's index starts at 0.
The right pointer starts at the last index in our array, which we find by getting the array length and subtracting by 1 to get it's index.

   while(left < right){
     ...
   }

We set our loop to run only while our left pointer is less than our right pointer. Otherwise we'd duplicate iterations if our left pointer is greater than or equal to the right pointer.

      let sum = arr[left] + arr[right];

We declare sum inside the while loop so that the respective pointers update on each iteration.
The sum equals the value at the left pointer's index plus the value at the right pointer's index.

      if (sum === 0){
         return [[arr[left], arr[right]];
      } else if (sum > 0){
         right --;
      } else {
         left ++;
      }

The if statement sets the pointers based on our condition.
First, if the sum equals 0, then return the values in an array itself. This return will exit the while loop on the first iteration that matches our criteria.
If sum is greater than 0, then the numbers are too large. Decrease the right pointer one space to the left.
Else (if sum is less than 0), then the numbers are too small. Increase the left pointer one space to the right.

Big O of the Two Pointer Pattern

Using brute force with nested loops gives a time complexity of O(n^2) as you have to loop through each item in the array to grab the 1st number, then loop again through each item to check it against the 2nd.

Using the Two Pointer Pattern reduces the time complexity to be more favorable at O(n). This pattern will at most only iterate the length of the array minus 1, since we compare in pairs.

Space to solve this problem will be constant at O(1).

Before You Begin The Technical Interview ...

Samantha Diaz — Thu, 23 Jun 2022 15:53:09 +0000

These are tips on how to begin the technical interview before you start to code.

Understand the Problem

It seems obvious - but make sure you understand the problem you are asked to solve for. Ask your interviewer any questions to clarify the problem.

I find it helpful to summarize the problem back to the interviewer to make sure I can explain it in my own words. This helps to confirm that my interpretation of the problem is correct. Nothing's worse than wasting time solving a problem that wasn't even asked!

Ask About Inputs

Ask what assumptions can be made about the inputs or arguments. If the problem says it accepts an array, will that array be sorted or unsorted? If it accepts a string, will it vary in length and characters? Will the user always provide 2 arguments, what if they only give 1?

Ask About Edge Cases

Edge cases are the most extreme inputs that can be used in the problem. If the problem accepts a string as data type, what happens if the user inputs a number, or array? What if the problem accepts an array, but the user provides an empty array? These are questions to ask the interviewer to further clarify the problem, but to also give you more understanding on what you need to return.

What Should Be Returned From Your Solution?

Your solution needs to return something - make sure you fully understand what. Should it return a value, or index of a data set? What data type should be returned, a string or integer? Is the problem asking to return the count of duplicates or does it want the pair values themselves?

Here, you can also think about what to return based on particular inputs. If the input is empty, or null, what should your solution return?

Time to code, but first... Write Pseudocode!

Writing pseudocode is helpful because it allows you to quickly organize your thoughts before spending time writing perfect, working code. If you draft your solution in comments, this gives you time to think about the Big O of your solution incase you want to try a different approach. It also gives you space to see if there's anything that can be quickly refactored.

One thing to note - make sure you tell your interviewer that you are writing pseudocode! While this may seem obvious to you, it may not be to your interviewer and they may think this is what you consider real code to be. Don't leave any room for interpretations and tell the interviewer this is only used to draft your ideas, and that you will live code shortly after.

Stuck on Part of the Problem? Code What You Can!

After you've pseudo-coded and drafted your ideas, start where you can. If you can confidently solve for part of the problem, do it! Maybe you only know how to code the return value - that's ok! You have a limited time to solve for the problem, and it's better to show for something than to get stuck on one small area of the solution and not present anything.

Above Anything Else - Think Out-loud!

The interviewer wants to understand your thought process - so narrate it! Sure, you can code in silence and let your solution speak for itself, but being quiet doesn't allow you to show off your extensive knowledge. You're trying to impress them for the job, after-all.

For example, you know that array indexes start at 0 and that's why you started your loop at i = 0, but make it known and say it out-loud! This also highlights your communication skills to the interviewer.

Don't Forget to Refactor!

While this last part typically comes when you're done with the coding challenge, talk with you interviewer on what could be refactored. If you have the time - code it. If not, quickly explain where your mind is headed next and where you'd look to improve your code.

Lastly - Be Confident and Trust Yourself!

If you've landed a technical interview, you're doing something right. Push out negative thoughts or self-doubt. You've studied, you've practiced, and you're going to do great so long as you keep a positive mind set.

It's ok if you can't fully solve the problem - just show what you can. The interviewer will appreciate how communicative you are by asking questions and narrating your thought process. They'll think you have strong attention to detail if you ask about edge cases. And they'll see you as a problem solver if you're able to use Google to supplement your solution. These are still valuable traits to display even if you get stuck on the solution. Code what you know and you'll do fine!

Quick Summary on Big O Notation

Samantha Diaz — Tue, 21 Jun 2022 15:14:21 +0000

This blog gives a short summary on Big O Notation, specifically for technical interviews.

What is Big O Notation?

The "O" in Big O Notation (that's "O'" the letter, not a zero) comes from the German word "Ordnung" which means the order of approximation. Big O is used to estimate the performance of code based on its time and space complexity. It's a way to compare performance and runtime in the event inputs were to grow indefinitely - or, to the biggest number you can think of.

Big O Results

The ideal solution will have the smallest, or less steep, Big O as possible. The most common Big O results are:

Constant, O(1) - operations, un-ordered data structures like object manipulation, variable assignments, inserting/deleting at the end of an ordered data structure
Linear, O(n) - loops & iterations, anytime you need to search or step through an ordered data structured, inserting/deleting at beginning of an ordered data structure
Log, O(log n) - recursion functions, searching algorithms
Quadratic, O(n^2) - nested loops & iterations

Calculating Big O

To calculate Big O, count the number of operations in your code snippet and count as many times as the code runs. This means that if you are looping (or iterating), the code would perform the operation n amount of times. If you use a nested loop, this means the operation runs n * n number of times - so this would be quadratic O(n^2). If you add a number then multiply it by something, you are performing 2 mathematical operations and hence would be a constant O(2).

Simplifying Big O

Big O should be simplified to its lowest form. For example, if your code has 5 mathematical operations and involves an 2 iterations, this can be simplified to O(5 + 2n) -> O(n). The idea behind this is that a huge number will still be a huge number if multiplied by 2 and added 5.

A Trick to Reduce Big O with Arrays

When dealing with manipulating arrays, order matters. If you add (.unshift) or remove (.shift) to the beginning of an array, you are shifting every item in the array and hence every item needs to be re-indexed. This creates a linear Big O, O(n). Instead, add (.push) or remove (.pop) from the end of the array, so that the other indexes in the array remain unchanged. This gives a more ideal Big O: constant O(1).