DEV Community: Karthikeyan

Data structures in daily programming!

Karthikeyan — Sat, 14 Mar 2020 16:43:27 +0000

While I studying in computer science graduation there was a separate subject called data structures. But I don't understand what is it till last week.

I wanted to explain the way I needed while at my college. I wanted to explain the real-world example first and how can we use it in software development.

What is data structures?

Official

In computer science, a data structure is a data organization, management, and storage format that enables efficient access and modification. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.

I understand this explanation is not feasible. Let me explain in layman terms.

Layman term

In real-world, imagine you have some items like eggs, vegetables, vessels, etc., And you need to store all the items. How would you do it? It's not possible to store all the items in the same storage. If you do means eggs will break. So, you need to come up with an efficient solution that the items can be easily retrieved whenever you need and also you can add a certain item easily. How would you do it?

This is where the data structures come to the game. So now you are using different storage structure for different items that the items can be added/removed/accessed from the data storage efficiently.

How can we use it in daily programming?

Good question! In javascript, there are two data structures we are using array and objects both are good in their purposes. In some cases, you might be needed to insert the value in front of the array instead of to the last. In this case, inserting value to the front is very costlier (we'll discuss it later). So array won't be helpful in this case but there are other data structures will be helpful eg: Linked List. Inserting a value to the front is constant time in the linked list.

We'll discuss more on different data structures and how to implement in daily development in upcoming blogs.

Simple right?

Type of data structures:

Singly Linked List
Doubly Linked List
Stacks
Queues
Binary Search Trees
Tree Traversal
Binary Heaps
Hash Tables (Javascript Objects)
Graphs
Graph Traversal

I'll write a separate blog post for each data structures. Hope you understand what is data structures and why we are using it. Please comment on your feedback about my blogs.

Thanks!

Recursion in daily programming!

Karthikeyan — Sat, 07 Mar 2020 13:58:16 +0000

We may use recursion in daily programming without knowing.
I will explain what recursion is and where can we use it. Keep reading!

What is recursion?

In layman terms, when we doing the same task repeatedly we can call it a recursive task. In programming terms, when a function calls a function itself to do the task and it's going iteratively to complete. It's called recursion.

Still confused?

Okay, take one example.

function findCorrectObject(arr, id) {
   if(arr[arr.length].id === id) {
     return arr[arr.legth];
   } else if(arr.length === 0) {
     return "Not found!";
   } else {
     arr.pop();
     findCorrectObject(arr, id);
   }
}
findCorrectObject([{id: "3434343", title: "title 1"}, {id: "45454565", title: "title 2"}], "3434343");

In this example, we finding the correct element from the array. As you see we called the same function with the required params. This is recursion. It'll run till it finds the correct object or the till the array will empty.

Simple right?

Where we can use it?

In javascript, recursion taking a huge place. In so many scenarios we can use the recursion. Example: JSON.parse / JSON.stringify

If you look inside the code of __deep() in lodash library it uses the same recursion. I'm telling deep cloning means in javascript if assign an object to a variable it'll shallow copy it'll not a deep copy. This means when you changed the new object created with the existing one it'll also change the existing one.

We can use recursion to solve that problem.

Here is the code for deep copy of an object! Don't get fear about huge code. I'll explain what it actually will do. Read the code carefully!

function clone(item) {
  if (!item) {
    return item;
  } // null, undefined values check

  var types = [Number, String, Boolean],
    result;

  // normalizing primitives if someone did new String('aaa'), or new Number('444');
  types.forEach(function(type) {
    if (item instanceof type) {
      result = type(item); // Yeah, we used recursion here! To find the exact primitive
    }
  });

  // If the result is still undefined. The item should be an Object or Array
  if (typeof result == "undefined") { 
    if (Object.prototype.toString.call(item) === "[object Array]") {
      result = [];
      // If the item is array, we call the same function to deep clone each values. Yes it is recursion.
      item.forEach(function(child, index, array) {
        result[index] = clone(child);
      });
    } else if (typeof item == "object") {
      // testing that this is DOM
      if (item.nodeType && typeof item.cloneNode == "function") {
        result = item.cloneNode(true);
      } else if (!item.prototype) {
        // check that this is a literal
        if (item instanceof Date) {
          result = new Date(item);
        } else {
          // it is an object literal
          result = {};
          for (var i in item) {
            result[i] = clone(item[i]);
          }
        }
      } else {
        // depending what you would like here,
        // just keep the reference, or create new object
        if (false && item.constructor) {
          // would not advice to do that, reason? Read below
          result = new item.constructor();
        } else {
          result = item;
        }
      }
    } else {
      result = item;
    }
  }

  return result;
}

var copy = clone({
  one: {
    "one-one": new String("hello"),
    "one-two": ["one", "two", true, "four"]
  },
  two: document.createElement("div"),
  three: [
    {
      name: "three-one",
      number: new Number("100"),
      obj: new (function() {
        this.name = "Object test";
      })()
    }
  ]
});

Another Example

If you think the previous example is too much, here I took one famous problem to explain recursion.

function calculateFactorial(num) {
  if(num === 1) return 1;
  return num * calculateFactorial(num - 1);
}

calculateFactorial(5);

In this function, the calculateFactorial will call a total of 5 times to complete the problem. Whenever the calculateFactorial(num - 1) function call it'll create the separate function stack and the previous function will wait till the current function resolves. Likewise, the new function will be called in runtime until it returns 1.

I recently used recursion in my project. I currently working with reactJS. So it'll better if explain the real-life scenario. We had one problem, the user need to select the children of the parent in the dropdown. And the children might have another child. Likewise the data will grove. I used this library to solve the particular problem.

I immensely used recursion inside. Because each object might have another set of object and I need to go through all the phases until I reach the final object without another child.

Recursion solving so many problems that loops cannot solve. And also the code will be cleaner and optimized.

Thanks for reading!!

Problem Solving Patterns

Karthikeyan — Mon, 02 Mar 2020 19:24:39 +0000

When talking about the patterns, there will not the best problem-solving patterns it does not exist. Instead, look at all the patterns and choose whichever is best.

Today I pass through some good problem-solving patterns. I would like to share with you all.

1. Frequency Counter

This will not calculate the frequency. This will collect the frequencies of value. It will use Objects/Sets of key and values to store the values. This can often avoid the need for nested loops or O(N^2) operations with arrays/strings.

Let's take an example:

Write a function called sameValues, which accepts two arrays. The function should return true if every value in the array has its corresponding value squared in the second array. The frequency of values must be the same.

Sample input/outputs:

sameValues([1,2,3], [4,1,9]) // true
sameValues([1,2,3], [1,9]) // false
sameValues([1,2,1], [4,4,1]) // false (must be same frequency)

Here is the problem the squarred value not only should be in second array. Instead it should be in same frequency/occurence

Standard Solution:

function same(arr1, arr2){
    if(arr1.length !== arr2.length){
        return false;
    }
    for(let i = 0; i < arr1.length; i++){
        let correctIndex = arr2.indexOf(arr1[i] ** 2) // Loop inside a loop
        if(correctIndex === -1) {
            return false;
        }
        arr2.splice(correctIndex,1)
    }
    return true
}

// Time Complexity => O(N^2)

Optimized solution

function same(arr1, arr2){
    if(arr1.length !== arr2.length){ // If array 1 is not equal to array 2 return false
        return false;
    }
    // Initialize the freqeuncyCounter for both values
    let frequencyCounter1 = {}
    let frequencyCounter2 = {}

    // Get array elements one by one and add 1 to it if already exists or else initiate it. 
    for(let val of arr1){
        frequencyCounter1[val] = (frequencyCounter1[val] || 0) + 1
    }

    // Same applicable to array 2
    for(let val of arr2){
        frequencyCounter2[val] = (frequencyCounter2[val] || 0) + 1        
    }

    // Now the important part, we checked each key in frequencyCounter1
    // Squaring the value and check if it exists in frequencyCounter2
    // If not return false
    // And also check the passed key having the same frequency if not return false.
    // If it pass through all the conditions return true.
    for(let key in frequencyCounter1){
        if(!(key ** 2 in frequencyCounter2)){
            return false
        }
        if(frequencyCounter2[key ** 2] !== frequencyCounter1[key]){
            return false
        }
    }
    return true
}

// Time Complexity => O(n)

In this problem, we removed the loop inside the loop instead we created the separate loops and store the values in the object.

2. Multiple Pointers

Creating pointers or values that correspond to an index or position and move towards the beginning, end or middle based on a certain condition

Very efficient for solving problems with minimal space complexity as well

Example:

Write a function called sumZero which accepts a sorted array of integers. The function should find the first pair where the sum is 0. Return an array that includes both values that sum to zero or undefined if a pair does not exist

Sample Inputs/Outputs

sumZero([-3,-2,-1,0,1,2,3]) // [-3,3] 
sumZero([-2,0,1,3]) // undefined
sumZero([1,2,3]) // undefined

Standard Solution:

function sumZero(arr){
    for(let i = 0; i < arr.length; i++){
        for(let j = i+1; j < arr.length; j++){ // Loop inside a loop
            if(arr[i] + arr[j] === 0){
                return [arr[i], arr[j]];
            }
        }
    }
}
// Time Complexity => O(n^2)

Optimized Solution:

function sumZero(arr){
    let left = 0; // Initialize the first pointer with 0th index
    let right = arr.length - 1; // Second pointer to the end of the array
    while(left < right){ // Iterate till the two pointer become same
        let sum = arr[left] + arr[right]; 
        if(sum === 0){ // If sum zero found the values return it.
            return [arr[left], arr[right]];
        } else if(sum > 0){ // Means the right pointer value will not match anymore so we need to decrease our array order. 
            right--;
        } else { // the left pointer value not be found in right pointer value
            left++;
        }
    }
}

3. Sliding Window

This pattern involves creating a window which can either be an array or number from one position to another
All the way from beginning to end it's sliding one another. First, it'll solve the first set of values and then go to the next set. Will continue till the end.
Depending on a certain condition, the window either increases or closes (and a new window is created)
Very useful for keeping track of a subset of data in an array/string etc.

Example:

Write a function called maxSubarraySum which accepts an array of integers and a number called n. The function should calculate the maximum sum of n consecutive elements in the array.

Sample Inputs:
maxSubarraySum([1,2,5,2,8,1,5],2) // 10
maxSubarraySum([1,2,5,2,8,1,5],4) // 17
maxSubarraySum([4,2,1,6],1) // 6
maxSubarraySum([4,2,1,6,2],4) // 13
maxSubarraySum([],4) // null

Standard Solution

function maxSubarraySum(arr, num) {
  if ( num > arr.length){
    return null;
  }
  var max = -Infinity;
  for (let i = 0; i < arr.length - num + 1; i ++){
    temp = 0;
    for (let j = 0; j < num; j++){
      temp += arr[i + j];
    }
    if (temp > max) {
      max = temp;
    }
  }
  return max;
}

Optimized solution

function maxSubarraySum(arr, num){
  let maxSum = 0;
  let tempSum = 0;
  if (arr.length < num) return null;
  for (let i = 0; i < num; i++) { // Initiated out first slide with num numbers
    maxSum += arr[i]; // Store the sum on num array values in maxSum
  }
  tempSum = maxSum; // Initiate the tempSum with maxSum value
  for (let i = num; i < arr.length; i++) { // Iterate from where you left before
    tempSum = tempSum - arr[i - num] + arr[i]; // don't need to iterate again the num numbers of next slide instead sub the earlier starting value and add next first value.
    maxSum = Math.max(maxSum, tempSum); // Calculate the maximum of two values and asign to maxSum
  }
  return maxSum;
}

Best Problem-Solving Approaches

Karthikeyan — Sun, 01 Mar 2020 17:55:28 +0000

Hello developers,

In this post, we're going to discuss the problem-solving Approaches and how to come up with the optimum approaches for a problem. I recommend you to refer to this post before you are solving any problem. Whatever I'm discussing will help you in the longer run. Hope you will enjoy!

Outcomes!

Will discuss, about what an algorithm is?
Will discuss, how to devise a plan to solve any problem?
Will compare and contrast problem-solving patterns including frequency counters, two-pointer problems and divide and conquer

Algorithm

A process or set of steps to accomplish a certain task. (in simple terms)

The algorithm will help you to solve a smaller to bigger problem. It's a good practice to write an efficient algorithm all the time. So, we need to practice accordingly.

How do we improve our algorithmic skill?

To improve our skill we need to follow some rules before proceeding any problem.

We need to plan before solving anything (like plan what data structures to use, what programming technique is suitable for this problem)
Master common problem-solving patterns (will discuss in this post)

Checklist for problem-solving

Understand the problem (observe the expectations)
Explore concrete examples (play around with the sample inputs)
Break it down into pieces.
Solve and simplify.
Look back and refactor the code.

Understand the problem

Restructure the whole problem in your own words.
Gather the information about the inputs of the problem.
Gather the information about the expected outputs for the problem.
Think about the output and ask yourself is it possible to produce the output with given inputs? and analyse, is the information given to you enough?

Example: Write a function which takes two numbers and returns their sum.
First I will write in my own words as I understood the problem. After that, I'll analyze the given inputs and possible outputs for the same problem.

Explore examples(Test cases)

Explore examples means you don't need to come up with the working examples for this problem. Instead, come up with examples of inputs, possible outputs and try to understand the problem better.

Start with simple examples (write it down the simple example inputs)
Progress with more complex examples (write some bigger user stories).
Explore examples with empty values
Explore examples with invalid values.

Break It Down

Let's break the complex bigger problem into smaller steps to accomplish. write down the steps. This will also help to write better code. Because you already know the steps so you'll easily break it down into multiple functions for each subproblem and the code will also readable and maintainable.

Simplify the problem

Find the more difficult part of the problem you are trying to solve.
Forgot about that part temporarily and concentrate on other parts.
After completing all the solvable parts go to the complicated part.

Refactoring the code

while refactoring the code try to convert it to more readable and performant. Comment the code well.
Checklist for refactoring the code:

Can you check the result?
Can you derive the result differently?
Can you understand it at a glance?
Can you use the result or method for some other problem?
Can you improve the performance of your solution?
Can you think of other ways to refactor?
How have other people solved this problem?

I won't say this is the best approach. The best approach doesn't exist. If you have any thoughts feel free to comment below.

Let's master the common problem-solving patterns in the next blog.

Thanks!

Analyzing the performance of Javascript Methods

Karthikeyan — Sun, 01 Mar 2020 13:21:50 +0000

Let's discuss the performance of Javascript built-in methods.

Things we are going to discuss in this blog:

Understand how objects and arrays work, through the lens of Big O.
Understand why adding elements to the start is slow.
Compare and contrast the runtime for arrays and objects, as well as built-in methods

Objects

Objects are unordered key-value pairs. Means these object values not indexed like arrays. You giving a key name and key-value, it's stored that's it it will not be indexed.

Where can we use Objects?

When you don't need to order the elements with the index value.
When you want to access/insert/remove the elements fastly.

When you accessing the elements means you don't need to search through all the elements of the objects like arrays unless you already know what the exact key name!

What is the Big O of objects?

Insertion => O(1) - Ex: obj["name"] = "John";
Removal => O(1)
Searching => O(n) - Ex: Object.keys(obj);
Access => O(1) - Ex: obj["name"];

When you don't want to order elements Objects are well performant.

Big O Object Methods

Object.keys - O(N)
Object.values - O(N)
Object.entries - O(N)
hasOwnProperty - O(1)

Arrays

Arrays are ordered list. By default, arrays will order the elements with ascending order when inserting anything.

Ex: let values = [true, {}, [], 2, "awesome"];

Where can we use Arrays?

When you want to list elements in the order.
When you want fast access/insertion and removal (with some limitations)

What is the Big O of arrays?

Inserting
- The performance of the arrays depends on how you inserting the value.
- If you insert at the end of the array. The Big O is O(1). Since it's not changing the order of the array. Ex: [3, 4].push(2)
- If you insert at the beginning of the array. The Big O is O(n). Since it's changing the order of the whole array. Changing the order of the whole array means you can say I'm just inserting the value in arr[0]. But what really happens is the previous value stored in arr[0] will move arr[1] similar to all the values. Ex: [1, 3, 4].shift(2)
Removal
Same as inserting.
Remove the end of the array value is O(1). Ex: [3,4].pop()
Remove the beginning value is costliest O(n). Ex: [3,4].unShift()
Searching
Searching an element is O(n). Since we should loop through all the elements of the array to search a particular. No matter we found the element at the beginning or middle. Cumulatively we can consider it as an O(n). Ex: [2,3,4].find(value => value === 3)
Accessing
Accessing an element is O(n). You should know the exact index value of the element to access. Ex: arr[3]

The basic array operations we are using daily still there are so many operations we not covering those in this blog.

concat - O(N)
slice - O(N)
splice - O(N)
sort - O(N * log N)
forEach/map/filter/reduce/etc. - O(N)

Inserting at the beginning is not as easy as we might think! There are more efficient data structures for that! We'll discuss in coming articles.

Thanks for reading. See you in the next blog soon.

Brief Intro to Big O

Karthikeyan — Sat, 29 Feb 2020 17:20:14 +0000

Hello Devs,

Previously I have written a dev blog on why data structures are needed in frontend development. If you didn't read yet feel free to check it out

In this blog, we are going to discuss what Big O is and where we can use it?

First, we will start with the official definition.

What is Big O?

Big O Notation is the language we use to describe the complexity of an algorithm. In other words, Big O Notation is the language we use for talking about how long an algorithm takes to run. It is how we compare the efficiency of different approaches to a problem. With Big O Notation we express the runtime in terms of — how quickly it grows relative to the input, as the input gets larger.

How Big O calculates the performance without using a computer?

This is where Big O comes to the game. Imagine you need to solve a problem and you have 2 solutions. You need to select the optimized code.

Example

Code: 1

Code: 2

How will you choose which is efficient code?

Within the system?
Based on lines of code?
Using any tool?

Calculating Performance!

When comes to calculating performance we need to consider two things.

Time Complexity
Space Complexity

Time Complexity (Faster Processing)

Can we use timers(in Javascript) to calculate which is faster?

Why not? We'll try!

First output is => Time Elapsed: 0.9381299999998882 seconds.
Second output is => Time Elapsed: 0.9610100000000093 seconds.

The output is differing for each run right? The output solely depends on the hardware. So we can't take this is as the final decision. We need something more.

Counting Operations...

Now, we'll do the optimization based on counting how many operations are making for each run.

Analyze the first program and count how many operations are making at each run. But in the second program counting is a bit hard since the operation is based on input.

Big O calculation will be based on input.
Big O will calculate the worst-case scenario.

Since the operation is based on input. I think we can use Big O to calculate performance.

Let's back to Big O again!

It allows us to talk formally about how the runtime of an algorithm grows as the inputs grow

We have some types in Big O

It could be linear O(n). (Which means the runtime grows based on the input)
It could be quadratic O(n**2).
It could be constant O(1). (Which means the runtime will be constant at any time).

You can see whatever the O(1) is the more efficient solution and followed by O(n!) is the less efficient solution.

Example for O(n)

function addUpTo(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) { // Since the loop is based on input
    total += i;
  }
  return total;
}

Even though we have two loops in the function. We can consider this as an O(n) solution.

function countUpAndDown(n) {
  console.log("Going up!");
  for (let i = 0; i < n; i++) {
    console.log(i);
  }
  console.log("At the top!\nGoing down...");
  for (let j = n - 1; j >= 0; j--) {
    console.log(j);
  }
  console.log("Back down. Bye!");
}

// Loop inside a loop will be considered as O(n**2)

function printAllPairs(n) {
  for (var i = 0; i < n; i++) {
    for (var j = 0; j < n; j++) {
      console.log(i, j);
    }
  }
}

Shorthands for Big O

O(2n) => O(n)
O(300) => O(1)
O(50n*2) => O(n*2)
O(n + 10) => O(n)
O(10n*2 + 20) => O(n*2)
O(n*2 + 5n + 8 ) => O(n*2) (Choose the maximum one always)

I think this is enough for time complexity.

Space Complexity

Space complexity mainly focused on memory space optimization. It will calculate how much space needed for running that program. It will also rate the efficiency based on the calculations. Very similar to time complexity.

In javascript, the space complexity is based on the below rules.

Most primitives (booleans, numbers, undefined, null) are constant space
Strings require O(n) space (where n is the string length)
Reference types are generally O( n), where n is the length (for arrays) or the number of keys (for objects)

Example 1:
This one is O(1) space complexity

function sum(arr) {
  let total = 0;
  for (let i = 0; i < arr.length; i++) {
    total += arr[i]; // Replacing the already declared variable
  }
  return total;
}

Example 2:
This one is O(n) space complexity

function double(arr) {
  let newArr = []; // Will not be a constant space
  for (let i = 0; i < arr.length; i++) {
    newArr.push(2 * arr[i]); // Pushing values to array dynamically
  }
  return newArr;
}

Finally, we came to a conclusion.

To analyze the performance of an algorithm, we use Big O Notation
Big O Notation can give us a high-level understanding of the time or space complexity of an algorithm
Big O Notation doesn't care about precision, only about general trends (linear? quadratic? constant?)
The time or space complexity (as measured by Big O) depends only on the algorithm, not the hardware used to run the algorithm
Big O Notation is everywhere, so get lots of practice!

Thanks for reading. See you in the next blog soon.

Why data structures and algorithms are important for frontend?

Karthikeyan — Fri, 28 Feb 2020 17:21:46 +0000

So in this blog, we are going to discuss why data structures are important.

Yeah, I'm currently learning data structures and algorithm properly. So I decided to write a blog on this topic to improve my journal and understanding.

Myself a frontend developer as like everyone I thought frontend developer don't need to learn how to write efficient code. But after realizing my mistake I thought I should give a shot to learn DS and Algo. Because the important part of writing efficient code is using perfect data structures and choosing which algorithm.

So Now can discuss, why it even matters in frontend development?

In the old frontend, development peoples are built sites that are statically rendered the HTML from the backend. But now the frontend development is more evolved than before everything is rendered in frontend(browser) and the backend is calling only for data pulling.

You may ask like this why I need to code efficiently? Still, I'm solving most of the business problems with my current knowledge.

If you think you don't need it means you didn't involve in the complex tasks.

If you have only 10 list items in your list view page. Yes, you don't need to code efficiently because in the worst case also the site will run smoothly.

But imagine you need to display 50 list items per page and each item having many more interactions and you need to implement a very good UX to the whole page. Yes, you definitely should know algorithms practice to write efficient code.

As a front end developer, I have faced so many performance issues because of re-rendering and other things. For solving those problems we should be strong DS and Algo.

filter vs find

One of the examples for finding particular data is a filter and find. So what is the difference between them?. the filter will do filter the whole list item and returns the expected items as an array. But find will search the list items and returns an expected item when it's found out and then stop the process. This is a major difference. Likewise, there are so many things to know to write efficient code.

So, it's always better to know what DS, Algo and how can we use it to write efficient code.

It's really fun!

And more than everything if you are the one who loves code and solving problems and here warm welcome. It's really more fun than anything.

Improving skills definitely

Solving problems will definitely help you to think logically and efficiently you can learn any technologies at any time but those thinking and logical skills will come by more practice. More practice will give more feed to your brain.

Coming in interviews also!

This is for sure! Most of the top tech companies will ask their questions from DS and Algo from the first round itself.

I lined so many blogs related to how to write efficient code in frontend development. So, don't forget to follow me in this community.

If you find any mistakes in this blog, feel free to point out in the comment section.