DEV Community: Donny

Array Method in JavaScript: Reduce

Donny — Mon, 30 Nov 2020 20:36:14 +0000

Let’s review one of my favorite advanced array methods in JavaScript: Reduce.

What Does Reduce Do?

Imagine taking a bunch of ingredients from a recipe and tossing them one by one into a pot. Apply heat to that pot. After the pot cooks for a bit, you’ll be left with a marvelous stew.

That’s basically what happens in the reduce method. We take a bunch of items (elements of an array). Throw them into a pot (an accumulator) and apply heat (logic) . Finally, we are left with our result--a yummy dish.

Let’s take a simple example:

We start with our dish’s ingredients: an array of 4 integers. Let’s call our array “ourIngredients.”


const ourIngredients = [ 1, 2, 3, 4]

Our recipe calls for us to take our ingredients, add them all together and come out with a total. So given our ingredients: 1, 2, 3, 4; we’re hoping to use our reduce recipe to end up with 10 (1 + 2 + 3 + 4).

So let’s set it up.

We’ll need a variable “stove” to be assigned to the cooking instructions.


const ourIngredients = [ 1, 2, 3, 4]

const stove

The stove will need a pot, then need to take each “ingredient” in turn:


const ourIngredients = [ 1, 2, 3, 4] 

const stove = ( pot, ingredient ) =>

Now we have to tell the stove what to do with the pot and the ingredient. In our case, we just want to add each ingredient to the pot in order to get our cumulative total:


const ourIngredients = [ 1, 2, 3, 4] 

const stove = ( pot, ingredient ) => pot + ingredient

Let’s put it all together. All that remains is to “call” our stove on the list of ingredients. The magic word we’ll use is “reduce”: (We’ll console.log our result)


const ourIngredients = [ 1, 2, 3, 4] 
// In techno talk, we have:
// 1) declared an arrow function and named it ‘stove’
// 2) passed in 2 parameters: ‘pot’ and ‘ingredient’ 
       // (pot, ingredient)
// 3)  told pot to just keep adding the given ingredient
//    to the pot:   pot + ingredient

const stove = ( pot, ingredient ) => pot + ingredient

//take the ingredients, call the reduce method
// and pass in our instructions (stove)
console.log(ourIngredients.reduce(stove));  // 10

That is the basic. Now let’s get a little fancier.

Our current example assumes we’re starting with an empty pot, that is, at 0. But what if our pot already had something in it--let’s say an integer “5” was already in the pot before we started cooking. In that case, we would expect to get 15 at the end of our session (10 + 5)

Let’s see how to add something to the pot before cooking with “ourIngredients:”


const ourIngredients = [ 1, 2, 3, 4] 

const stove = ( pot, ingredient ) => pot + ingredient

//But there is a 5 already in the pot:
console.log(ourIngredients.reduce(stove, 5));  // 15

Before I leave you for today, let’s ratchet it up a couple of notches with a more challenging example. This next example comes up from time to time in coding challenges:

Say we’re given an array of names:

const names = [ ‘Desmond’, ‘Orlando’, ‘Leticia’, ‘Desmond’, ‘Shane’, ‘Desmond’,  ‘Madison’, ‘Leticia’]

We need to find out how many times each name occurs and end up with a object like this:

const names = [ ‘Desmond’, ‘Orlando’, ‘Leticia’, ‘Desmond]

// convert the array into an object and count
// the occurrence of each element:
{

‘Desmond’: 3,
  ‘Orlando’: 1,
  ‘Shane’: 1,
  ‘Madison’: 1,
  ‘Leticia’: 2
}

Let’s do it by first setting up our stove. We know we’ll need a pot and an ingredient as parameters. When it’s all done, we’ll want to pop the pot off the stove by using a “return” statement:


const stove = ( pot, ingredient) => {



return pot

}

Now comes the logic. If the ingredient is already in the pot, all we have to do is increment its count (Its count is the ingredient’s value)


const stove = ( pot, ingredient) => {

if (pot[ ingredient ]) {
  pot[ ingredient ]++
}

return pot

}

Else, we know the ingredient is not in the pot, so we can set its value or count to 1:


const stove = ( pot, ingredient) => {

if (pot[ ingredient ]) {
  pot[ ingredient ]++
} else {
  pot[ ingredient ] = 1
}

return pot

}

Now let’s bring it all together!

let’s take our “names” array, call our magic “reduce” method and tell it to use our stove method:


//almost done…..
names.reduce(stove)

Oops! Almost done. We forgot two things. Firstly, we want to console.log the results:


// REALLY almost done…..
console.log(names.reduce(stove))

AND, we need to tell our reduce method that there was something already in the pot when we began cooking. What was that? An empty object, {} !!!! We’ll need that empty object to hold the transformed array:


// Now we’re done.  Notice the empty array after “stove”
console.log(names.reduce(stove), {} )

And there you are: a primer to the “reduce” method in JavaScript. Have a look at the MDN with the full treatise on “reduce” there are some even wilder things you can do with it!

Here’s the link to the MDN article on “reduce”

Keep on cooking up your dreams with code!

Namaste!

Interview Prep: Implementing A Binary Tree

Donny — Wed, 25 Nov 2020 20:14:46 +0000

Welcome back to interview prep. This week, we’ll build on last week’s intro to tree data structures and we’ll actually implement or build a binary tree in Java.

If you’ve never heard of the tree data structure, check out last week’s article to get up to speed:

Read about the Basics Here

Our Problem

We’re given a picture of a tree data structure the looks like this:

We are asked to code this tree out in Java.

Left and Right

We’ll just need a bit of additional terminology to accomplish our task. Note that each parent has 2 children. We can say that one child is on the “left” side of the parent and one is on the “right” side.

For example, in our image of a tree above, we see that the root is the node containing the value “1”. Its left child is “2” and its right child is “3”.

To simplify our language, instead of referring to the child nodes, we can refer just to the edges (lines) that lead from the parent to the child. Thus, we can say node 1’s right edge (or just “right) leads to node 3. Node 1’s left edge (or just “left”) leads to node 2.

With that knowledge, let’s begin to code

Let’s start by declaring a BinaryTree class and a main class:


public class BinaryTree{

    public static void main(String[] args) {

    }
}

Then we’ll need a private field to hold our entry point to our tree. That entry point is called the “root”. Let’s declare that field as a TreeNode type (we’ll write the TreeNode class next).


public class BinaryTree{

    private TreeNode root;

    public static void main(String[] args) {

    }
}

We’ve declared our root note as a TreeNode class type, so we better write that TreeNode class.

TreeNode is the class that will produce all the individual nodes we need to construct our binary tree.

We’ll have to supply each TreeNode with three items: 1) a left edge (we’ll just call it “left”); 2) a right edge (named “right”) and a variable we’ll call “variable” to store the node’s data. We’ll assume our binary tree can only contain integers as data for simplicity’s sake.


public class BinaryTree{

    private TreeNode root;

    private class TreeNode{
        private TreeNode left;  // left edge
        private TreeNode right; // right edge
        private int data;    //  here is where the data goes
    }

    public static void main(String[] args) {

    }
}

Let’s add a constructor method below our field declarations in our TreeNode class. This constructor will just take as a parameter the data we want to insert into the node we’re creating.


public class BinaryTree{

    private TreeNode root;

    private class TreeNode{
        private TreeNode left;  // left edge
        private TreeNode right; // right edge
        private int data;    //  here is where the data goes

        public TreeNode(int data) {
             this.data = data;
        }
    }

    public static void main(String[] args) {

    }
}

We’re ready now to create our tree. Below the TreeNode class, still within our BinaryTree class, let’s make a createBinaryTree method and within that method, let’s create a few nodes. We’ll create those nodes by creating instances of our TreeNode class:


public class BinaryTree{

    private TreeNode root;

    private class TreeNode{
        private TreeNode left;  // left edge
        private TreeNode right; // right edge
        private int data;    //  here is where the data goes

        public TreeNode(int data) {
             this.data = data;
        }
    }

   public void createBinaryTree() {

       TreeNode first = newTreeNode(1);
     //I’m create a TreeNode and calling it “first”
           // then I’m assigning the integer “1” as its value

    // Below: create more TreeNodes:
     TreeNode first = newTreeNode(2);
     TreeNode first = newTreeNode(3);
     TreeNode first = newTreeNode(4);
     TreeNode first = newTreeNode(5);
     TreeNode first = newTreeNode(6);
     TreeNode first = newTreeNode(7);

   }

    public static void main(String[] args) {

    }
}

Let’s start organizing these nodes we’ve just created.
We have a field we already declared as “root”. By looking at the diagram of our tree(scroll to the top of this article to see it) we see we want the “1” node as the root. We also see from the diagram that the root node’s “left” edge will have the 2 node. Root’s right edge will have the 3 node. Let’s code that. (For simplicity’s sake, I’ll just show the createBinaryTree method here instead of the whole class)


public void createBinaryTree() {

       TreeNode first = newTreeNode(1);
     //I’m create a TreeNode and calling it “first”
           // then I’m assigning the integer “1” as its value

    // Below: create more TreeNodes:
     TreeNode first = newTreeNode(2);
     TreeNode first = newTreeNode(3);
     TreeNode first = newTreeNode(4);
     TreeNode first = newTreeNode(5);
     TreeNode first = newTreeNode(6);
     TreeNode first = newTreeNode(7);

     // we want our root to be assigned to “first”
     root = first;

     //we know root’s left edge is the 2 node:
     first.left = second;
   // root’s right edge is the 3 node:
   first.right = third;

   }

Let’s finish it up. We see from our original diagram that the 2 node’s (AKA second) left edge points to the 4 node. It’s right edge points to the 5 node.

It’s similar for our 3 node (AKA third): third’s left is 6. Third’s right is 7:

public void createBinaryTree() {

       TreeNode first = newTreeNode(1);
     //I’m create a TreeNode and calling it “first”
           // then I’m assigning the integer “1” as its value

    // Below: create more TreeNodes:
     TreeNode first = newTreeNode(2);
     TreeNode first = newTreeNode(3);
     TreeNode first = newTreeNode(4);
     TreeNode first = newTreeNode(5);
     TreeNode first = newTreeNode(6);
     TreeNode first = newTreeNode(7);


     root = first;


     first.left = second;

   first.right = third;

   //second’s left node is 4
   second.left = fourth;

   //second’s right node is 5
   second.right = fifth;

   //Last two nodes to place:
   third.left = sixth;
   third.right = seventh;

   }

And there is your binary tree implementation in Java. Admittedly, this is a simple implementation and there are fancier ways of doing this. For example, you could start with an array of data and then implement the tree using that array. However, as my dance teacher told me, “You have to learn the basic step first before you try any variations.”

By the way, if you look at our original diagram one last time, what if your interviewer asks you, “Ok, but what do the nodes containing the values 4, 5, 6, 7 point to?” Be sure to use the technical word to answer this question. So instead of saying, “Well, they point to ‘zip’”, you can say, “They point to null.”

Enjoy the adventure,

and keep coding out your dreams!

Namaste!

Interview Prep: Binary and General Trees

Donny — Wed, 18 Nov 2020 23:08:18 +0000

In your study of data structures, perhaps you’ve only gotten to the linear structures, e.g. stacks, queues, linked lists. Think of these as one dimensional like a street-- you can only go up or down that street. Now let’s consider a multi-dimensional data structure: trees. A tree has one main trunk, but it can have branches. And those branches can have their own branches, like this:

So what does a tree look like as a data structure?

First, let’s remember from our linear data structures that those structures consisted of nodes of data. Each node pointed to the next node:

In trees, the difference is that each node can point to more than one node:

In the above image, we have 4 nodes: A, B, C and D.

The A node is called the root, because all other nodes branch off from A. We can even say, “A is the parent of B, C and D. B, C, and D are the children of A

Siblings

Let’s learn some more terminology with this tree below:

Above, we see node A is the root and B, C , D are A’s children. However, because B, C, D are on the same level (“Same level” means you can draw a horizontal line connecting the lengths of B, C, D) these nodes are also siblings of each other.

Ancestors and Descendants

See the tree below:

In the image above, we see three nodes: A, B and E circled in pink. Just like in a family tree diagram, E’s “parent” or ancestor is B. But the “family line” extends further back to A. A is also an ancestor of E.

We can also look at it in the opposite direction with the nodes circled in blue highlighting nodes D, G, H, and I. D has two “children” or descendants: G and H. However, D’s “family line” extends further through H to I. I is also a descendant of D.

Leaves

Here’s another tree:

Sometimes nodes don’t have children. In that case, these child-less nodes are called leaves (think of a leaf on a tree blowing around in the wind untethered by any branches beyond it). A leaf can also be called external (Think of the leaf blowing in the wind as a conduit to the outside world; no further branches are blocking it.

If leafs can be termed external, what would we call those nodes who do have at least 1 child? Yep, those nodes are internal.

Path and Path Length

Given a tree where we select two different nodes of that tree, a path is the set of edges from one node to the other. The path length is the number of edges in that path:

In the above diagram, we want to get from the root, A, to H. You see the path was traced out for us in blue. Each of those arrows that point from a parent node to a child node is called an edge. We see it took 3 edges to get from A to H.

Node Level and Node Depth

Let’s describe a way to tell how deep down a given node is nested:

In the image above, we define the root level to be “0”. Each succeeding level increases by 1. The terms “level” and “depth” are used interchangeably.

For example, we see that Node C is at a depth (or level) of 1. Node H is at a depth of 3.

Another related concept is the height of a tree:

In this example, we can determine the height of a tree by just counting levels--the trick is that we have to start with “0”. So node A is at a height of 0; B, C, and D are at a height of 1. E, F, and G are at a height of 2 and finally node H is at a height of 3. Our tree’s height is then 3.

Degree

Look at this example:

First of all its height is 2. Can you tell?

Then, we look at the maximum number of possible children for every node in the tree. We see that the maximum number is 3.

We can say that our tree has a height of 2 and a degree of 3.

Types of Trees

The last thing we’ll look at today are types of trees.

You can have a tree where each node has any number of children from 0 to n. The number of children each node has can be different from parent node to parent node. In this case, we have a general tree

On the other hand, we can have a tree where every parent has at most n children. The most popular version of this kind of tree is where n = 2. In this case we have a binary tree.

Here’s an example of a binary tree:

Notice how we have the root at node 1. Then each child or descendant of node 1 has at either 0, 1 or 2 children.

So there you have most of the basic terminology to be able to work with trees. Most of our work going forward will be with binary trees--as my tutor told me, binary trees represent about 95% of the work with trees.

More to come!

Keep coding out your dreams!

Namaste!

Interview Prep: Bit Manipulation: Part III

Donny — Thu, 12 Nov 2020 04:07:48 +0000

Welcome back to more work on Bit Manipulation in preparation for that big job interview you’re going for.

We’ll be pushing forward based on what we’ve talked about in my last 2 articles on bit manipulation. If this subject is new to you, go ahead and read at least the first one here:

Article I
Bitwise Manipulation Part 1

Bitwise Manipulation Part 2

Today, we’ll look at some more interview questions that can be solved by using bit manipulation. But before we do that, we’ll just need to learn one more way of manipulating bits in addition to the ones we’ve already covered in my previous articles.

Left and Right Shift Operator in Java

The Java API gives us a left shift operator ( << ) as well as a right shift operator( >> )

Let’s see how they work:

Let’s make up a base two integer. The letters above the number are just a way to identify each component of the integer. Let's set our integer to the variable “a”:

          A   B   C   D   E   F  
a =       1   0   1   0   1   1

Now let’s say we want to right shift this number by two places. We would write:

               a >> 2

So let’s take our “hand”, place it just to the left of column “A” and shove the whole integer over to the right by 2 places. But remember, any number that gets shoved to the right of column “F” just disappears!

So here’s what we get after right shifting by 2

( a > > 2)

 A   B   C   D   E   F  
         1   0   1   0

That’s all there is to right shifting.

Now let’s retrieve our original number:

          A   B   C   D   E   F 
a =       1   0   1    0  1   1

Let’s now shift the integer contained in variable “a” 2 places in the opposite direction to the left. We’ll write it like this:

               a << 2

So again we’ll take our “hand” and place it this time just to the right of column “F” and shove the whole integer two places over to the left:

                  A   B   C   D   E   F  
          a =     1   0    1   0   1   1

But this gives us empty bits in columns “E” and “F” as seen above. We’ll have to fill those columns in with zeros to get our final result below:

             A   B    C   D    E   F  
     a =     1   0    1   0    1   1    0   0

And Now for Some Cool Tricks You Can Use In Your Interview:

Right shift ( > >) is the same as dividing by 2

Let’s take a decimal number , 10. Let’s convert to to base 2:
11000

We’ll right shift binary 11000 by 1 place:

1100

Binary 1100 is decimal 12 which is half of decimal 24.

You can keep shifting one place to the right and keep on halving our number to check it out!

Set the 2 to the nth bit of integer X

This is a good one.

We’re given an binary integer, say it’s 1010;

A B C D
1 0 1 0

We’re also told our “n” is 2. That means we have to set (put a one) in column B. Why column B? In short, column B is the 2 to the “n” column. Our “n” was given as “2”. Column B is our 2 to the 2nd column:

Column D is the 2 to the 0th column or the “ones” column
Column C is the 2 to the 1st column or the “twos” column
Column B is the 2 to the 2nd column or the “fours” column

The way we’ll set our column B is by using this simple formula:

        x | ( 1 << n)

Let’s work it out. First let’s start with what’s inside the parens on the right side of the bitwise “OR” operator ( | ): 1 << n

We want to shift the integer “1” to the left by n places. We were given n as “2”. Let’s do it:

              1    //original integer

          1 0 0   // shift the original 
                     over to the left by 
                     2 places

Now let compare our x, 1010, to 100 using bitwise OR ( | )

      A   B   C  D
      1   0   1   0
      0   1   0   0
      _____________
      1   1   1   0      // 1010 | 0100

After applying bitwise OR, we see that in our result ( 1 1 1 0 ), in column B is now set as the problem required.

These are just two of the very fun things you can do with bit manipulation. I hope it’s whetted your appetite for more. Using base 2 and bit manipulation allows for a fine tuning of our integers that would be clunky in base ten.

Keep on coding out your dreams!

Namaste

Interview Prep: More on Bit Manipulation

Donny — Tue, 03 Nov 2020 01:37:33 +0000

Welcome back again to another episode of Interview Prep. We’ve been playing around with Bit Manipulation lately. If you didn’t catch my first article the gives the basics, give it a quick read-through now as we’ll be continuing on from where it left off:

Bitwise Manipulation, Part I

As a quick overview, remember that “bit manipulation” means we’re working in base-2 instead of base-10. The reason why we care is that working in base-2 gives us a finer level of control over our data. Think of bit manipulation as working with a nail file instead of a hammer.

So now that you know some basic operations of bit manipulation from my first article, let’s use those operations to do some cool stuff and also to help us answer some possible interview questions.

Clear the Least Significant Bit that is Set

The question you might get goes like this:

“Clear the least significant set bit in a given
sequence of bits”

First, let’s define the terms. What do they mean by “significant” bit?

Simple. Look at this sequence of bits:

                                          X
1010001110000001000000010000111100000101010

Now put your finger on the screen (go ahead, I won’t tell!) on the extreme right side of the sequence(Marked with an “X”). Now move your finger along the sequence to the left.

You are now moving your finger from the least significant bit toward the more significant bits.

<<---<<<<---<<<<<go to the left to get more significant

                                          X
1010001110000001000000010000111100000101010
Y

In our example, the bit marked with an “X” is the least significant and “Y” is the most significant bit. The degree
of “significance” increases as we move our finger along the bit sequence from right to left.

Now back to our original question. Let’s take a fresh bit sequence:

We are being asked to create an algorithm that clears the least significant set bit.

If we put our finger on the extreme right side of the sequence( cell E3), we move our finger to the left along the sequence and there move from least “significant” bit to more significant bit. The first set bit we come to is the “1” in cell D1 marked in red. This is the bit we need to clear and turn into a zero.

In our algorithm, we have two basic tasks to perform: 1) find the least significant set bit and then “clear” it, meaning set it to zero.

Now comes the cool part. The easy way we can find and clear the least significant bit is to use bit manipulation. And here’s the formula that works every time for this problem:

 x & ( x - 1)

Let’s just work out the above formula!

We were given “x” :

Now let’s type in x-1 on line 5:

Lastly, let’s find out what the expression x & (x-1) resolves to:

Just to review our “&” operation:

In Column A: “1” on line 3 and “1” on line 5 resolve to “1” on line 8.

Column B: 0 and 0 resolve to 0

Column C: 1 and 1 resolve to 1

Column D: 1 and 0 resolve to 0

Column E: 0 and 1 resolve to 0

Remember we wanted to find and clear the least significant bit in line 3, the bit marked in red. And that’s what we did! In line 8, we see Cell D8 marked in blue where the cell was cleared.

Our secret formula: x & ( x-1) cleared the least significant bit.

One More

Let’s look at one more problem. Given a sequence of

bits(we’ll start with the same one we’ve been using)

We’re asked to write an algorithm that sets the least significant cleared bit.

In the image above, we’re given the sequence on line 3.
The least significant cleared bit is in cell E3. We want our algorithm to choose this cell and set it so that we’re left with the bit sequence on line 8.

How do we do it?

Simple! We’ll use another magic bit manipulation formula. This time, it’s:

          x | (x + 1)

Let’s do it!

We already have “x”, so let’s fill in (x + 1) on line 5 below and then let’s check to see that it resolves to our desired result on line 8:

We see that we successfully found the least significant cleared bit in our given sequence (Cell E3) and set it in our result in Cell E8 (in red) on line 8. Voilà!

Those are just a couple of tricks. There are more, so I hope that whets your appetite and increases your appreciation for bit manipulation. This way of looking at numbers allows us to make some subtle changes in our values that would otherwise not be possible.

Keep coding out your dreams!

Interview Prep: Bitwise Manipulation

Donny — Thu, 29 Oct 2020 01:22:11 +0000

Welcome back to interview prep. Today we’ll tackle a new subject to help you get ready for that big technical interview: bitwise manipulation.

First the punchline to get you motivated: what is it and why do I need to know this?

In bitwise manipulation, we’re looking at numbers not from a base-10 perspective but from a base-2 perspective. For example, the number “10” in base-10 would be expressed as “1010” in base-2.

Why is this important?

For now, I’m afraid you’ll have to take it on faith that by examining numbers in this bitwise, base-2 way, we can make subtle manipulations to those numbers which makes solving certain algorithms really easy. If we tried to use base-10 for those certain algorithms, it would be a bloody mess!

Are we Onboard re: base 2 and what a bit is?

You can skip this section if you already know about base 2 and bits, otherwise read on.

Take a regular base-10 number like 156. You know from elementary school show how to read this number since you learned about place value.

Let me make a slight alteration to the image above. Let us use a more computer science-like expression for the values of the 3 columns. Instead of “100s” we’ll call it “10 to the power of 2” or 10^2. Instead of “10s”, it’s 10 to the power of 1: 10^1. Lastly the “1s” column is 10 to the power of 0: 10^0 (Remember any number to the power of 0a power calculates to “1”

I bet you got it. So here’s a quick check. Can you figure out what “10101” in base-2 works out to be in base-10?

Right! It’s 21. Starting from the right of the number, we have 1*2^4 + 0* 2^3 + 1* 2^2 + 0* 2^1 + 1 * 2^0 = 21

Let’s Learn Some Terminology

Now that we know what base 2 is, we can start using more fancy computer science terms.

Let’s just look at at base two number: 11100

Think of each number, the 1 or the 0, occupying a separate cell in a spreadsheet. In the illustration below, I’ve given each column a letter to identify it:

The fancy word for each cell of the spreadsheet is: byte

In each cell or byte, the only two numbers we can put in them is 1 or 0.

If we put a 1 in the cell, that cell or byte is said to be set or on.

In contrast, if there is a 0 stored
in the byte, that byte is said to be clear or off.

That means in our example above, we see that columns A, B and C contain bytes that are “set” or “on”, while columns D and E contain bytes that are “clear” or “off”.*

Fun aside: the bytes are represented to us humans as the integer 1 or the integer 0. However, the computer does not “see” these symbols. Just recognizes intensity of light. This means the byte containing the “1” is seen by the computer as a brighter light. The “0” is seen by the computer as a dimmer light.

Let’s Start Manipulating Those Bits!

So finally we know enough to start making some bit-wise waves!

Let’s learn some basic operations of bits:

Bitwise NOT ( ~ )

Bitwise AND ( & )

Bitwise OR ( | )

Bitwise XOR ( ^ )

Let’s take them one at a time:

Bitwise NOT

Bitwise NOT ( ~ ) is easy. If the bit is set (1) then bitwise NOT, the tilde sign ( ~ ) clears it (turns it into 0).

If the bit is clear (0) the tilde sign ( ~ ) will clear it.

So given the base two number 11100. If we apply bitwise NOT we’ll get 00011:

~(11100) = 00011

Bitwise AND

Do not confuse the regular AND symbol that you already know (&&) with BITWISE AND (&). Bitwise AND is represented by only one ampersand in the Java language. We use that bitwise AND when we’re working on the level of bits only.

Think of bitwise AND like multiplication. When we take two base-two numbers OF EQUAL LENGTH and apply bitwise AND we’ll find the result by multiplying the column of one number with the corresponding column of the second number:

Starting in column A. Multiply 1 in column 3 by 1 right below it in cell A5 and we get 1 in cell A7 as the result.

Column B: 1 x 0 gives us zero
Column C: 1 x 1 gives us 1
Column D: 0 x 1 gives us zero
Column E: 0 x 0 gives us zero

Bitwise OR ( | )

Again, notice bitwise OR is represented by only ONE pipe symbol. It is different from the normal OR ( ||) with two pipe symbols that you’re used to using in the Java language.

You can think of bitwise OR as like addition. You’ll be adding each column individually:

This time in Col A we add 1 and 1 and get technically 10 in base two, but we’ll chop of the zero and call it one.

In Col B: 0 + 1 gives us 1

In Col C: 1 + 1 gives us 1

In Col D: 1 + 1 gives us 1

In Col E 0 + 0 gives us 0

And now comes my favorite:

Bitwise XOR ( ^ )

XOR is pronounced EX-OR and also as ZOR (As in Zoro, the famous swordsman!)
For this one, all you have to remember is that in each column, if one number contains a “1”, the other number must contain a “0” in order to result in a “1”. If both bytes are set, or if both bytes are clear, then we’ll get “0”

Let’s see it in action:

In column A, 1 and 1 return 0

Col B: 1 and 0 return 1

Col C: 1 and 1 return 0

Col D: 1 and 0 return 1

Col E: 0 and 0 return 0

Now that you know some of the basic bit manipulations, we can begin to solve some bit manipulation algorithms which is where the beauty of bits come into play. We’ll be able to “fine tune” and make subtle distinctions between integers using base 2 and bit manipulation as opposed to using base 10 to try to accomplish the same thing. Think of the difference in your code the same as the difference between rose pedals (base 2) vs. a mess (base 10)!

See you next time for more!

And in the meantime:

Keep coding out your dreams!

Namaste!

Interview Prep: Remove the Nth Node From the End Of A Singly Linked List

Donny — Thu, 22 Oct 2020 01:24:38 +0000

Welcome back to interview prep. In this series, we are examining common technical interview questions in the realm of data structures and algorithms.

If you’ve never heard of singly linked lists before, then you should read my basic article on linked lists first. Otherwise, let’s push on!

Linked Lists Part I

Linked Lists part II

So here’s our problem for today: Given a singly linked list, remove the nth node from the end of the list.

Let’s understand the question.

We’re given the linked list below as well as the integer “4”

As we can see above, our linked list consists of node containing integers from 0 to 9. The head node (H) is at 0 and the tail node (T) is at 9.

Now let’s remove the nth node from the list. We were given n = 4, so we’ll remove the 4th node from the end.
If we count the nodes backwards beginning from the tail node, or “9”, the 4th node from the end is “6”. Let’s remove it. Now our node will look like the list in blue below:

How Do We Do This?

First, let’s understand conceptually how we approach this question.

Our first problem is finding the 4th node from the end of the list. In our code, we cannot traverse a singly linked list backwards. The only way we may traverse our list is starting at the head and moving in one direction until we reach “null” after the tail.

Think of a singly linked list as a one-way street.

But not to worry, we have a plan!

First, let’s set two pointers at the head of our list. We’ll call those two pointers “first” (F) and “second” (S)

Now let’s advance our “second” pointer “n” number of places. Our “n” is 4, so let’s advance “S” by 4 places:

So now our pointers are 4 places apart from each other.
Next step is to start advancing each pointer by 1. Let’s do this together in our heads:

Advance S to 5; advance F to 1
Advance S to 6; advance F to 2
Advance S to 7; advance F to 3

and so on….

We’ll have to stop advancing pointers when S gets to null. At that moment, our points will look like this:

Look at that! Our “S” pointer ended at “null” while our
“F” pointer ended at “6”. We notice that “6” is the 4th node from the end of the list--exactly the node we needed to find!

Now that we’ve found the node we need to remove, we’ll get rid of it by resetting the node before it, “5”, to point at “7”.

Let’s Code It Up!

Now you have a conceptual understanding of how we’ll solve this algorithm. Let’s code it up!

Remember, the only things we can “see” of a linked list are the head, and tail. Also, we can only traverse the linked list starting at the head and moving towards the tail.

In our function, removeNthNodeFromEnd, we’ll use “head” and “n” as parameters.


const removeNthNodeFromEnd = ( head, n ) => {


}

Now let’s set our first pointer, variable “first”, and our
second pointer, variable “second”, to “head”.

We’ll also need a counter variable( set counter to “1”) to keep track of the number of places we traverse in the list:


const removeNthNodeFromEnd = ( head, n ) => {
  let first = head
  let second = head
  let counter = 1

}

To get the “second” pointer to traverse 4 places on our list, we’ll use a “while” loop


const removeNthNodeFromEnd = ( head, n ) => {
  let first = head
  let second = head
  let counter = 1

  while( counter <= n ) {
     second = second.next
     counter ++
   }

}

We’re getting there! We now have “second” set four places ahead of “first”.

Next step is to start both pointers traversing the list--each moving one node at a time in step with each other. When “second” finally gets to the end of the list and gets to “null”, we want to stop the traversing of “first”.

But wait! We have a little edge case to deal with. What if, after advancing “second” by “n” places, “second” points to “null”? It would look like this:

We see that “S” is at “null” and the node we need to remove at “F” is actually the head node. We cannot just remove the head node like we could any middle node. If we remove the head node, we must reset the head node to the next node. In our example, the new head node would be “1”. Let’s take care of that edge case:


const removeNthNodeFromEnd = ( head, n ) => {
  let first = head
  let second = head
  let counter = 1

  while( counter <= n ) {
     second = second.next
     counter ++
   }

   //edge case if second points to “null”:
 if ( second === null ) {
 // update value of the head node 
 head.value = head.next value

 //update the pointer of the head node:
 head.next = head.next.next

// and we’re done.  Let’s just exit the function
return head
   }



}

Now that the edge case is out of the way, let’s have each pointer traverse the list. However, we want to stop the traversal when “second” gets to the last node before “null”.
That means “first” will land on the node before the one we really want to eliminate.

Our pointers will look like this:

Why do we do this? Well, think of the links between the nodes as little tied knots in a string. If we really traversed to the “6”, the one we want to eliminate, and then “untied” its knot to “7” we would have lost the reference to the “7”. Think of the “7” then being unlinked to the rest of the list, it would just “float” away.
The way we need to get rid of the “6” is via it’s immediate previous neighbor -- the “5”

What we’ll do now that “first” is pointing at “5” is we’ll “retie” the 5’s “next” knot to 7. Visualize this. You’ll see how nothing gets untied in the process. Once we “tie” the 5 to the 7, now we can safely untie the 6 from the 7. The six can then just float off into computer infinity.

Let’s do it. I’ll write the code to advance both pointers so long as “second” IS NOT null:


const removeNthNodeFromEnd = ( head, n ) => {
  let first = head
  let second = head
  let counter = 1

  while( counter <= n ) {
     second = second.next
     counter ++
   }

   //edge case if second points to “null”:
 if ( second === null ) {
 // update value of the head node 
 head.value = head.next value

 //update the pointer of the head node:
 head.next = head.next.next

// and we’re done.  Let’s just exit the function
return head
   }

       // now we advance each pointer. Let’s
       // keep going so long as second IS NOT null
       while ( second. next !== null ) {

           second = second.next
           first = first. next
       }


}

We’re down to our last line of code now!

We just have to do that “retying” explained above. So we got our first pointer at 5, the node before the 6--the node we want to get rid of. We know we just have to “retie” the 5 to the node after 6, or 7.

How do we “re-tie” our 5 to the 7?

We just do:

      first.next = first.next.next

On the right side of the expression, “first” is set to “5”. That means first.next would be “6” and first.next.next is “7”. I’m saying, “Set 7 to be the next node after “first” or “5”.

See the final code below


const removeNthNodeFromEnd = ( head, n ) => {
  let first = head
  let second = head
  let counter = 1

  while( counter <= n ) {
     second = second.next
     counter ++
   }

   //edge case if second points to “null”:
 if ( second === null ) {
 // update value of the head node 
 head.value = head.next value

 //update the pointer of the head node:
 head.next = head.next.next

// and we’re done.  Let’s just exit the function
return head
   }

       // now we advance each pointer. Let’s
       // keep going so long as second IS NOT null
       while ( second. next !== null ) {

           second = second.next
           first = first. next
       }

      first.next = first.next.next

     // does the interviewer want us to return something?
}

I would ask the interviewer what, if anything, they want us to return. Maybe the head? Maybe “n”? Maybe just the string “I did it! Yay!”

Space and Time Complexity

We are just traversing a list one time. There is no nested looping, so we have O(n) time complexity

We are not creating any new data structures with our algorithm. All our operations are done in place on the one list so our space complexity is a cool O(1)

And there you have it. A fun, relatively easy algorithm to remove a node “n” places from the end of a singly linked list.

Happy coding and best wishes with your interviews!

What About These Fat Arrow Functions?

Donny — Fri, 16 Oct 2020 00:48:13 +0000

When I first started learning JavaScript a couple years ago, I was taught to write the classic arrow expressions:

function myMessage( ) {
   console.log(“Hello, World!”)
}

Then I started using the new-fangled arrow function ES2015 way of
writing the same thing:


const myMessage = ( ) => {
   console.log(“Hello, World!”)
}

The new syntax seems cool to me, but then I found out there were some important differences between the new and the old syntax. Sometimes those differences made arrow functions really amazing and other times, they caused unforeseen problems.

First, let’s go over some basics:

Omitting Parentheses.

Normally, we use parentheses to define the parameters our arrow function:


const addTwoNumbers = ( x, y ) => {
   return x + y
}

Above, we’ve put parentheses around our two parameters, x and y.

We also must use parentheses if we have zero parameters:


const mySecretMessage = ( ) => {
   console.log(“This is fun”)
}

However, if we have just one parameter, we can optionally omit the parenthesis:


const sayMyName = (string) => {
   console.log (string)
}

// we could have eliminated the parenthesis since there
// is only one parameter in our arrow function. 

// Let’s rewrite it:

const sayMyName = string => {
   console.log (string)
}

To summarize: you can only omit parentheses around the parameters of an arrow function if you have one parameter. If you have zero, two, three or more parameters, you must use parentheses.

Omit the Curly Braces

When we have just one statement in our function body, we can simplify the statement by vomiting the curly braces:

This function with only one statement in the function body:


//Example A

const addTwoNumbers = ( x, y ) => {
   return x + y
}

Becomes this:

//Example B

const addTwoNumbers = ( x, y ) =>   return x + y
}

Cool! In the re-written statement, we 1) removed the curly braces, 2) removed the keyword “return” and 3) put the function body statement on the same line as the function definition.
Note the use of a couple of new vocabulary words. in Example A above, when we use the return keyword it is known as an explicit return. In contract, when we omit the return keyword as in Example B, it is called an implicit return.

***An Outlier Occassion Where Parentheses Are A Must:

If you’re going to return an object literal, then you must wrap that object in parentheses:


const greetings = name =>({ message: `Hello, ${ name }!`})

//now call “greetings”

greetings(‘Timmy’)    // -> { message: Hello, Timmy! }

If we don’t wrap the object literal in parentheses, then JavaScript will confuse the curly braces with those that define the function body.

The Famous “This”

The “this” keyword is a well-known bugaboo for many a JavaScript programmer. And to make it more fun, the “this” keyword acts differently in a classic function call vs. an arrow function call.

Let’s look at how “this” works in a method of an object.

See the method below:

const car = {
  model: 'Fiesta',
  manufacturer: 'Ford',
  fullName: function() {
    return `${this.manufacturer} ${this.model}`
  }
}

Above you see the object “car”. Look at the key “fullName”. The value corresponding to “fullName” is a classic anonymous function.

In this case, when we call the fullName function like this:

car.fullName( )

because we’re using a classic function, JavaScript knows to look for the meaning of “this” in the object it’s being called in. In our case, the “this” is being called in the object named “car”. Good, now JS will know how to parse the literals “this.manufacturer” and “this.model”. We just said the “this” must refer to the “car” object, so we we have “manufacturer” and a “model” property in our “car” object? Yes, we do! So JS can return:

car.fullName( )  // returns: “Ford Fiesta”

Now let see what would happen if we turn our car.fullName method into an arrow function like this:

const car = {
  model: 'Fiesta',
  manufacturer: 'Ford',
  fullName: () => {
    return `${this.manufacturer} ${this.model}`
  }
}

What happens now when we try to call “car.fullName( )” ?
The difference lies in the fact how the arrow function will interpret the “this” keyword. We already saw how the classic function knew that “this” referred to the object itself and therefore all the object’s key/value pairs were made available to that function.

However, our arrow function interprets the “this” keyword differently.

Our arrow function will only look for a meaning of “this” in its lexical scope meaning the context where that function is executed.

In other words, this is the only thing our arrow function “sees”:

fullName: ( ) => {
  return `${ this.manufacturer} ${ this.model }`

Our arrow function only sees the parts of the object that directly concern its own execution. It does not see the “model” property nor does it see the “manufacturer” property.

Therefore, when our fat arrow method function tries to interpret “this.manufacturer” and “this.model” it finds no references to anything like that. Both values will be returned as undefined.

car.fullName(  )  // “undefined undefined”

The upshot of all “this” is: when constructing a method in an object, you have to use the classic function keyword.

Interview Prep: Reverse Linked List Algorithm

Donny — Thu, 08 Oct 2020 01:11:58 +0000

Welcome back to Interview Prep. Today we’ll look at a very popular interview question regarding linked lists.

If you already know the basics of linked lists, read on. If not, try starting with my “linked list basics” articles:

LINKED LISTS ARTICLES BASICS:
Linked Lists Basics Part I

Linked Lists Basics Part II

What’s the Question?

We’re given a linked linked list liked this:

This is a linked list with 5 nodes. Each node contains an integer 1-5. In this list, 1 points to 2. 2 points to 3. 3 points to 4, 4 points to 5. 1 is the “head” of the list and 5 is the “tail” of the list

Now, we want to reverse the links of the list so that it looks like one in green below

You see that in the picture above, our green linked list has been reversed. 5 is now the head and points to 4. 4 now points to 3 and so on. 0 is now the tail.

How to do it?

Well, you might guess that to reverse our original list it will involve each node’s “next” property. Yes, that’s right. The tricky part is that when we reverse a node’s “next” property and have it point to its previous node, we’ll lose reference to the former next node. Here’s what I mean:

Let’s just take another linked list. This time with just 3 nodes: 1, 2 and 3. We want to take 2’s “next” property and point it at “1”. Below I’ve circled in pink the arrow representing the “next” property we want to reverse

In the second line of the image above, I’ve 2’s “next” property to the previous member: “1”. However, as you can see, now there is no arrow pointing to “3”. “3” is now lost to our linked list.

So how do we avoid losing references when reversing a linked list?

Use Pointers

To illustrate what we’ll be doing, I’m going to use a picture and start in the middle of the list. It will be easier to visualize that way. (Yes, when we get to the real code we’ll start with the head of the list. Also for now, don’t worry about edge cases.)

Let’s go back to our original white linked list with 5 nodes:

You’ll notice I’ve added pointers in blue. P2, currently at node with the value of 3 is the main event!. We want to reverse its “next” property(represented as an arrow in our diagram). In order not to lose any references while we manipulate the “next” properties, we’ll set one more pointer: P1, which is currently at the node with the value of 2.

There are just 4 steps to solve this problem:

We still just one more pointer, a “P3” to point to the node after our “P2 node”.

We’ll set p3 to p2.next:

Set P2. next to its predecessor, “1”

Above, you’ll see in pink that I’ve reversed P2’s “next” property . P2 now points to P1, like we wanted.

So now what? How do we keep traversing the linked list?

We’ll have to keep moving the pointers. In fact there are just two more steps to go to finish the main logic!

Set P1 to P2:

Above, you’ll see I’ve shifted P1 to its new location

Last step: now set P2 to P3:

There you have one iteration of our traversal of our linked list.

Before we go to the code, however, I want to show you how P3 gets shifted:

We just did one complete iteration in steps 1-4 above. We’re now ready to start our second iteration. Let’s go back to just step one. In step one, we set P3 to P2.next like so:

You’ll remember we had already shifted P2 to P3’s position in step #4 above. Therefore, we can set a new P3 to the shifted P2’s next property.

Now to the Code

Just a reminder before we start coding.

That P2 pointer is our “star” pointer and our code will be constructed to accommodate it.

2)In our original linked list with 5 nodes, do you know what comes before “1” and after “5”. Yes, that right, NOTHING or “null”:

Also, since we’re not always sure how long our linked list will be, let’s use a “while” loop. We’ll keep looping until our “star” pointer, P2, runs off the list and gets to “null”
A minor point is, “what should this list return?” This is a good question to ask your interviewer. Maybe they don’t want anything returned! For now, let’s just return P1 ‘cause we can!

Ok, let’s code:

// Declare our function and pass it our linked list’s head // 
// node

const reverseLinkedList = head => {
      // our p2 is the star pointer.  Let’s 
set it to the head
     let p2 = head
    // p1 comes BEFORE P2.  But if p2 is the head,
   //  what can come before the head?  Must be “null”
    let p1 = null

  // Here’s our while loop.  We’ll keep looping 
 // so long as P2, our star, doesn’t fall off the linked list
// and get to “null”
    while ( p2 !== null) {
        let p3 = p2.next   //step 1
        p2.next = p1       //step 2
        p1 = p2              //step 3
        p2 = p3              //step 4
    }
    return p1          //This imaginary interviewer wanted
                               // me to return P1.  Go figure!
}

I should start adding a discussion of space and time complexity.

In this algorithm we have a time complexity of O(n) since we’re just traversing the list one time.

Space complexity is a cool O(1) since we’re doing all our operations in place. We’re not creating a new linked list or other object, for example, which would have taken up more space in memory.

And there you have a solution to a popular linked list interview question. Now you can knock ‘em dead!

Have fun and
Keep coding out your dreams!

Namaste!

Donny

Interview Prep: Stacks: Part II

Donny — Wed, 30 Sep 2020 22:46:32 +0000

Welcome (back) to interview prep. Over these past 3 weeks, we did a quick run-through of the first basic linear data structure which we’ll need knowledge of for technical interviews: linked lists. Here are the links to my two posts:

Linked List Part I
Linked List Part II

Now we’re on the 2nd basic linear data structure: stacks. If you have not already read Part I of stacks or don’t have previous knowledge of the subject, you can read about the basics of stacks in my post here:

Stacks Part I

In this post, now that we know the basics of stack, let’s look at a common algorithm problem involving stacks: Balance the Curly Braces, Brackets and Parens.

This question goes like this:

Given a string consisting of opening and closing curly braces, brackets and parens, determine if they “balance”, that is: does each opening brace, bracket and paren have a “mate” that closes it? If the symbols “balance” return the boolean “true”, if not, return boolean “false.”

Here’s a string of symbols I’ve drawn. Notice how each opening symbol has a “mate.” The algorithm testing this string would return the boolean “true.” So you can see it better, I’ve shown matching pairs by color:

By contrast, here’s a string of symbols that does NOT balanced:

Note how the last coral-colored closing paren on the right end of the string does not have a “mate” and will therefore be evaluated as boolean “false.”

So now let’s design an algorithm in JavaScript to solve this problem.

Let’s draw it out first:

We’ll use a stack data structure, of course. Let’s iterate through the string. When we come upon an opening symbol we’ll simply add it to our stack. Let’s take our balanced stack from the first illustration above. The first five symbols in the string are opening symbols, so we’ll just add them to our stack one at a time like this:

Now on our next iteration of our original string, we come to a closing bracket at position 6. We have to look (peek) at the top of the stack and see if we find its mate--and sure enough we do! That means we can “pop” that opening bracket on the top of our stack:

Here’s what our stack looks like now with the top blue opening bracket removed:

Next stop on our iteration through our original string is position 7, a green-colored closing paren. Is its mate, an opening paren, on the top of the stack? Yes, it is! That means we can pop off that opening paren from the top of our stack. Let’s pop it off and here’s what our stack looks like now:

I won’t go through the rest of the iteration as I’m sure you get the idea!

Let’s Code ‘em Up in JS

/*
 Let's make a helper 'peek' function
that we can use to find the element
on the stack
*/
function peek(stack) {
  return stack[stack.length - 1]
}


function isBalanced(str) {
  let OPENING = "({["
  let CLOSING = ")}]"
  // see FOOTNOTE 1 below:

  // make an empty stack from an array:
  let stack = []

  // iterate through every letter of the string
  for (let i = 0; i < str.length; i++) {

      //store each symbol we visit in the string as variable "letter"
      let letter = str.charAt(i)

      //if the letter we're visiting is part of the OPENING string, 
        // we want to push it onto the stack
      if (OPENING.includes(letter)) {
          stack.push(letter)

        // otherwise, the letter must be a closing symbol...let's see   
          // if it's mate is on top of the stack:
      } else if (CLOSING.includes(letter)) {

          // OOPS!  Before we check for a match, let's check to see that
            // the stack is not empty.  If the stack is empty, there cannot
            //  be a match.  We'll have to return "false"
          if (stack.length === 0) {
              return false

            //  Ok, the stack has something in it, let's check for a match
          } else {
              // grab the symbol on the top of our stack using our 'peek' method
                 // and assign it to variable 'top'
              let top = peek(stack)
               // our top symbol can be found in our OPENING variable
                 //  get the index of our top symbol in the Opening Variable
                 //  and compare it to the index of the letter we're visiting in our CLOSING variable.  
                 //  if the two indicies are THE SAME, we know we have a match and we can pop the top
                 //  item off.
              if (OPENING.indexOf(top) === CLOSING.indexOf(letter)) {
                  stack.pop()
                  // otherwise, we return false, we know we're not balanced
              } else {
                  return false
              }
          }
      }
  }
  //lastly before we end, let's make a final check.  If we really have a balanced
    //  string, it means everything has matched up and all the opening symbols from
    //  the stack have been removed and our stack should be empty
    //  stack.length === 0 will return the final boolean value.
  return stack.length === 0
}


/*
  FOOTNOTE 1
  Regarding these two statements:   
  let OPENING = "({["
  let CLOSING = ")}]"

  variable OPENING contains a string of all possible opening symbols. 
  variable CLOSING contains a string of all possible closing symbols.   

  Notice how the index of opening symbol "("  or [0] in OPENING, is exactly the same index
  as its mate, the symbol ")" or [0] in CLOSING.  

  Index of the opening symbol "{" or [1] in OPENING, is exactly the same index
  as its mate, the symbol "}" or [1] in CLOSING.  

  And so on.  This little correspondence will make it easier for us
  to match up opening and closing symbols--we'll use indicies.
*/

And there you have it! One of the common algorithms asked in coding interviews solved!

Keep studying and keep applying for that amazing job you seek!

Interview Prep: Data Structures:Stacks

Donny — Fri, 25 Sep 2020 21:16:04 +0000

Are you like me and getting reading for a technical interview? As one technical interviewer said to me, “Technical interviews are getting harder. Used to be years ago we just asked you to reverse a string. Now you have to be good at data structures and algorithms.*

I’ve previously written a two part article one common data structure: linked lists

Here are the links:

Linked Lists Part 1
Linked Lists Part 2

Today we’ll look at the next data structure that flows from linked lists and common arrays: the stack.

What is a Stack?

The easiest way to think of a stack is to visualize a stack of pancakes on a plate. When the chef wants to add another pancake to the stack, that new pancake can only be added to the top of the stack. Later, when the chef is ready to serve those pancakes, they can only take the pancakes from the top of the stack.

In other words, whatever goes on the pancake stack first, will go off last. The pancake stack operates under
a system of FILO (First in, last out).

Let’s make a couple of other observations about our pancake stack before we start coding.

The only pancake you can actually “see” or peek at is the topmost pancake in the stack.
The only way we can access our pancake stack is via the topmost pancake again! We can remove that topmost pancake which will reveal the one below it, then remove that newly revealed pancake and get the one below it and so one until we reach our sticky plate.
The pancakes in our stack will know which order they go in since each pancake will “point” to the one below it.
The two other things we can do is know how many pancakes are in the stack and state whether there are any pancakes left on the plate, i.e. (isEmpty?).

Getting to the Code

Similar to how we set up the Linked Lists, we’ll need two classes for our stack:

1) a class named “Node” that will create the nodes of information that will go into our stack. The nodes are our pancakes!

2) We’ll also need a “Stack” class where we’ll write our methods we’ll need to manipulate our stacks.

Here’s our skeleton so far:

// class “node” to create the nodes, or “pancakes” that
// will go into our stack:

class StackNode {
  constructor( data, next){
     this.data = data
     this.next = next
  }
}

// Here’s our class where we’ll keep the methods we need
// to manipulate our stack.
// To start each new stack, we’ll begin with a “blank slate”
//  so we’ll set both the “top” (top pancake) and the length
//  of the stack to “null”.

class LinkedStack {
  constructor() {
    this.top = null
    this.size = null
  }
  // methods for our stack will go here
}

Let’s start adding threw easy methods to get us going. We want a method to find out if the stack is empty (isEmpty), get the current length of the stack (getLength) and peek at the top pancake (peek).

for isEmpty all we have to do is see if there is a “top”. We can do this by returning the boolean value to the expression this.top === null

for getLength, we’ll just return the size property which we already initiated in the constructor.

For peek, our constructor provided us with a "top" property, so we just have to return the data in that property to be able to peek.

Let's look at our code now after having added the isEmpty(),getLength() and peek() methods:

class StackNode {
  constructor( data, next){
     this.data = data
     this.next = next
  }
}

class LinkedStack {
  constructor() {
    this.top = null
    this.size = null
  }

  isEmpty(){
    return this.top === null
  }

  getLength() {
     return this.size
  }

  peek() {
    return this.top.data
  }

}

Ok, that much is done! Now let’s look at this picture to figure out what two methods will form the meat and potatoes of our stack implementation. Let’s look at the picture below:

Starting at the left of the picture above, we see an empty stack. To add a node, we need a “push” method. To remove a node, we’ll need a “pop” method (Does this remind you of regular arrays in JavaScript?)

Let’s do one method at a time:

push()

To code out the “push” method, here’s what we’ll need to do:

The method will take a value as a parameter. This value is the data for the new node that is about to be pushed on the stack
Inside the body of the method, we’ll create a new node with the help of our “stack” class and pass that new node our parameter.
Now we want to set our new node’s “next” property to the current top node. In other words, we want our new node to point to the current top.
We’ll reset the top of the stack to our new node.
Add one to our size property to account for the additional node we just pushed on the stack.

push(value) {    //pass in the value for the new node
  let node = new StackNode(value)    // create a new node
 node.next = this.top   // Our new node will point to the  
                                   //  current top node
 this.top = node          // our new node is now set as the top  
                                   //node     
 this.size ++               // increment size by one                           
}

On to our next method: pop()

pop()

For pop, we want to remove the top node. Here’s how we'll accomplish that:

First let save the top node to a variable because we’ll want to return what we popped at the end of the function.
Take the current top and set it to the node below it.
Decrement size by one to account for the node we just popped.
Return the data that was held in the node we popped.

Here's the code for pop():

pop(){
  let poppedNode = this.top   // save the 
                          //node we’ll pop to          
                          // a variable

 this.top = this.top.next    // set the top 
                           //node to be the 
                           // one below it

 return poppedNode.data    // return the data
                        // that was contained
                        // in the poppedNode. 
}

Now let’s put the methods we must wrote back in our LinkedStack class:

class StackNode {
  constructor( data, next){
     this.data = data
     this.next = next
  }
}

class LinkedStack {
  constructor() {
    this.top = null
    this.size = null
  }

  isEmpty(){
    return this.top === null
  }


  getLength() {
     return this.size
  }






  push(value) {    

    let node = new StackNode(value)   
    node.next = this.top                               
    this.top = node                                           
    this.size ++                                         
 }    

  pop(){
    let poppedNode = this.top                                                   
    this.top = this.top.next                                                         
    return poppedNode.data                                            
  }

}

And there you have your basis stack data structure implementation. Next time, let’s have a look at a common algorithm asked in relation to stacks.

In the meantime,

Keep coding out your dreams!

Namaste,

Donny

*One interviewer gave me a standard to achieve: be able to do the problems of medium-difficulty on Leet Code. The problems of high-difficulty are rarely asked. He also noted that, if LeetCode is too hard, you could start with Hacker Rank which tends to be a bit easier than LeetCode.

Interview Prep: Singly Linked Lists--Part 2

Donny — Sat, 19 Sep 2020 21:50:47 +0000

Onward with interview prep. If you are unfamiliar with singly linked lists, please read Part 1 as this post will continue from where we left off:

Linked Lists Part 1

First a quick review:
Note: When I refer to “linked lists,” I am referring to singly linked lists. (There are also doubly linked lists, but we’ll keep them for another time)
Linked lists are like arrays: they are “list-like” objects. The difference is that linked lists do not have indices like arrays. Linked lists have a beginning point( usually called a “head” and an ending point (usually called a “tail”). If you want to access a given element of the list (also called a “node”), you just have to traverse the linked list starting always at the head.

Imagine you are standing on one bank of a river and you want to cross it. There are a series of big rocks that form a bridge across the river. You can now step from one side of the river (the head) across to the other side of the river (the tail). Oh yes, that rock bridge is one-way only!

Ok, that was the review. Now let’s talk about a common algorithm you might be asked in interviews involving linked lists:

Find the Median of the Linked List

We’re given a linked list as pictured above. Our linked list has 5 nodes. Its first node, or head, contains the integer “5”. This node points to “4”. “4” points to “7” and so on. The last node, “10”, points to “null”. Our task is to find out what the median point of the node is.

The brute force way might be to just traverse the list and keep a counter so we can find out how long the list is. When we hit “null” we know we’ve reached the end of the list. Now just divide the counter by 2 and then floor the result if we get a decimal. We can then traverse a second time by “result’s” number of times to find the median.

But let’s impress the interviewer instead. Let’s show him a really sophisticated way of doing this. We’ll use the “Tortoise and Hare” approach attributed to Robert W. Floyd. Let's put both the tortoise and the hare at the head of the linked list. The hare can traverse the list two times as fast as the tortoise. In other words, the tortoise will always only be able to cover half the ground as the hare.

Let’s now let them both start traversing our linked list. The hare will finish first, of course. He will have to stop at the tail of the linked list. But once the hare has reached the end of the linked list, we know the tortoise will have only traversed half as much as the hare. What? “Half as much” means half the length of the link or the middle point!

Now we’ve found the median and we’ve done it so efficiently. Instead of all that counting and extra time traversing twice in our brute force method, we’ve only traversed the list once using “pointers” (the hare and the tortoise).

Have a look at a picture:

Got it here

Ok, now let’s code it up in JavaScript:

First, let’s recreate our two classes from Part I: First, we'll make a Node class to create individual nodes and second: a SinglyLinkedList class where we’ll put all our methods.

class Node {
 constructor(val) {
   this.val = val
   this.next = next
 }
}

class SinglyLinkedList {
 constructor() {
   this.length = 0
   this.head = null
   this.tail = null
 }
}

Now let’s create the shell of our new findMiddleElement method. We’ll set the variables “tortoise” and “hare” each to the head of the linked list as that is where they will start their "run."

class Node {
 constructor(val) {
   this.val = val
   this.next = next
 }
}

class SinglyLinkedList {
  constructor() {
   this.length = 0
   this.head = null
   this.tail = null
  }
  findMiddleElement() {
   let tortoise = this.head
   let hare = this.head         
  }
}

The first thing we should do is find out if the list really exists ( Testing for this edge case will show your interviewer that you’re really on your toes!)

One easy way to do this is just check to see if there is a head. If there is no head to the list, then there is no list and we can just return “undefined”. (Ask your interviewer what you should return in this case. Maybe they want something else returned, like “-1” or “Oops!”.

class Node {
 constructor(val) {
   this.val = val
   this.next = next
 }
}

class SinglyLinkedList {
 constructor() {
   this.length = 0
   this.head = null
   this.tail = null
 }
 findMiddleElement() {


   let tortoise = this.head
   let hare = this.head         
   if(!this.head) {
    return undefined
  }
}

Next comes the “meat” of our logic. We want our tortoise and hare to start moving along the linked list. However, we don’t know how long our list is, so we should use a “while” loop.

We’ll let our “while” loop run until the hare gets to the end of the list. How will we know when the hare has completed his run? There are two possibilities:

1). If there is an odd number of nodes he'll be at the end of the list when he gets to the very last node We’ll know he’s at the last node when the next node is “null”. For example: in a list that has 7 nodes, he’ll start at node #1, and then moving 2 nodes at a time, he’ll go from node 1 to node 3 to node 5 to node 7. At node 7, the next node is null, he’ll have to stop there. This means our condition for the “while” loop will be “keep going as long as the hare’s “next” node is not “null” (hare.next !== null)

Now consider if there is an even number of nodes. For example, if there are 8 nodes and our hare starts at node 1, he’ll go node 1 to node 3 to node 5 to node 7. At node 7 when he then jumps 2 nodes, he’ll go off the list and be in “null” land. So we want him to keep going as long as he’s NOT in “null” land ( hare !== null)

Now let’s put in the shell of our “while” loop. We’ll combine our two conditions with an “&&” logical operator.

class Node {
 constructor(val) {
   this.val = val
   this.next = next
 }
}

class SinglyLinkedList {
 constructor() {
   this.length = 0
   this.head = null
   this.tail = null
 }
  findMiddleElement() {
   let tortoise = this.head
   let hare = this.head    

   if(!this.head) {
    return undefined
   }

   while ( hare !== null && hare.next !== null) {
   }
  }
}

The next part is easy. In the body of the “while” statement we want to let our heroes go! We’ll use “dot next” (.next) to tell each hero to move to the next node. That means the tortoise can go (.next), but the hare has to go twice as fast (.next.next). Like this:

class Node {
 constructor(val) {
   this.val = val
   this.next = next
 }
}

class SinglyLinkedList {
  constructor() {
   this.length = 0
   this.head = null
   this.tail = null
  }
  findMiddleElement() {
   let tortoise = this.head
   let hare = this.head 
   if(!this.head) {
    return undefined
  }

  while ( hare !== null && hare.next !== null) {
    tortoise = tortoise.next
    hare = hare.next.next
  }
 }
}

And lastly, we’ll retrieve our prize. Once the while loop has run its course, our hare will be sitting at the end of the linked list while our tortoise will be at the median point. Let’s get tortoise’s data value in our final return statement to complete the algorithm:

class Node {
 constructor(val) {
   this.val = val
   this.next = next
 }
}

class SinglyLinkedList {
 constructor() {
   this.length = 0
   this.head = null
   this.tail = null
 }
 findMiddleElement() {
   let tortoise = this.head
   let hare = this.head     
   if(!this.head) {
    return undefined
  }

   while ( hare !== null && hare.next !== null) {
    tortoise = tortoise.next
    hare = hare.next.next
   }

   return hare.val
 }

}

This tortoise and the hare approach is useful in other kinds of problems, too. Keep this approach on your back burner whenever you’re looking at linked lists or any kind of cycles where you’re trying to find the end, middle point or where something intersects with something else.

Happy interviewing and best wishes!