Data structures, Design Patterns & Algorithms

📄 Table of contents

  • Module Pattern / Revealing module Pattern
  • Factory Pattern
  • Observer Pattern
  • Singleton Pattern

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ ✦ ✦ ✦ ▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬

There goes an old adage Algorithms + Data Structures = Programs, and that equation still holds true in today’s era.

Time Complexity is often measured in terms of :

  • Big Oh (O) : worst case running time
  • Big Omega (Ω) : best case running time
  • Big Theta (Θ) : both best and worst case running time

The time complexity of an algorithm is the total amount of time required by an algorithm to complete its execution. The lesser the time complexity, the faster the execution.

Understanding Time Complexity with Simple Examples

Imagine a classroom of 100 students in which you gave your pen to one person. Now, you want that pen. Here are some ways to find the pen and what the O order is.

O(n^2):

  • also called quadratic complexity.
  • You go and ask the first person of the class, if he has the pen. Also, you ask this person about other 99 people in the classroom if they have that pen and so on,
    This is what we call O(n^2).

O(n):

  • also called linear complexity.
  • Going and asking each student individually is O(N).

O(log n): Now I divide the class into two groups, then ask: “Is it on the left side, or the right side of the classroom?” Then I take that group and divide it into two and ask again, and so on. Repeat the process till you are left with one student who has your pen. This is what you mean by O(log n).

Algorithm that has running time O(log n) is slight faster than O(n). Commonly, algorithm divides the problem into sub problems with the same size. Example: binary search algorithm, binary conversion algorithm.

I might need to do the O(n^2) search if only one student knows on which student the pen is hidden.

I’d use the O(n) if one student had the pen and only they knew it.

I’d use the O(log n) search if all the students knew, but would only tell me if I guessed the right side.

Exponential O(2^n)

Exponential (base 2) running time means that the calculations performed by an algorithm double every time as the input grows. Examples:

  • Power Set: finding all the subsets on a set.
  • Fibonacci.

Linearithmic O(nlogn)

This running time is often found in “divide & conquer algorithms” which divide the problem into sub problems recursively and then merge them in n time.

Linearithmic algorithms are capable of good performance with very large data sets. Some examples of linearithmic algorithms are:

  • Heap sort
  • Merge sort
  • Quick sort

Constant O(1)

A constant-time algorithm is one that takes the same amount of time, regardless of its input. Examples:

  • Given two numbers, report the sum.
  • Given key-value hash table, return value for key.
  • Given a list of numbers, report the result of adding the first element to itself 1,000,000 times.

O(n!) — Factorial Time

It’s the slowest of them all.

Big O examples covered in this post

Must Read @ https://www.geeksforgeeks.org/analysis-of-algorithms-set-4-analysis-of-loops/?ref=rp

◉ Searching Algorithms

Linear search and binary search are algorithms for finding a value in an array, not sorting the array.

This algorithm is a very simple algorithm. Here, a sequential search is made throughout every element in the data structure one by one. If the match is found, it is returned otherwise searching process continues until the end of the data structure.

For Binary Search to work, the array should be sorted first.

This is a fast searching algorithm of the runtime complexity of O(log N).

Note: An O(log N) algorithm is considered as highly efficient because the ratio of the number of operations to the size of the input decreases and tends to zero when N increases. (N is the input size in units of bits needed to represent the input)

◉ Sorting (BIHMQ)

  • Bubble Sort — O(N²)
  • Insertion Sort — O(N²)
  • Heap Sort — O(N log n)
  • Merge Sort — O(N log n)
  • Quick Sort — O(N log n)

This is a highly efficient algorithm that uses the time complexity of O(n log n) for the worst case and n² for the average case. This is based on the partitioning array of data into smaller arrays.

  • The large array is separated into two arrays, one is holding larger values than a specific value and the other one is holding smaller values than the specific value. (there is a special name for the specific value called ‘pivot’)
  • After separating the large array then calls subarray itself recursively twice to sort.

courtesy: www.techiedelight.com

The pivot value divides the array into two parts. And recursively, we find the pivot for each sub-lists until all lists contain only one element.

This algorithm is easier than quicksort but better for smaller data sets. This is based on the comparison of adjacent elements of the array and swapped if they are not in order. This is not effective for larger data sets because of the time complexity of both average and worst cases is O(n²) where n is the number of items.

Though bubble sort was a much easier algorithm, this is NOT suitable for larger data sets.

Bubble Sort
INSERTION SORT
MERGE SORT
QUICK SORT

Conclusion

Each of these algorithms comes with their own strengths and weaknesses.

A bubble sort algorithm might be easier to understand, but it is the most INefficient of the four algorithms in this post. If we give it an array of 10 elements, then at worse it will compare every element with every other element in the list, resulting in a maximum of 100 (10*10) loops.

Insertion sort uses two loops. And since these loops are placed one inside the other, the time complexity will be of the form 0(n^2) where n is the number of elements in the array. A silver lining, this algorithm will perform better than bubble sort if the array elements require less sorting.

Merge sort uses recursion, which improves the efficiency of the sorting process by a huge margin. Merge sort requires the algorithm to go through every element of the array at least once. But with each recursive call, we only operate on half of the elements. So even if the number of elements increases to twice the original size, the algorithm will only require us to call one more recursion.

Quick Sort is the most efficient algorithm of the four in this post. Similar to merge sort, this algorithm also requires at least one go through the entire array. But any increase in the array’s size will not lead to any kind of increase in operations. Doubling the array size will only cause in one extra level of operation of the algorithm.

Why Design Patterns?

A design pattern is a term used in software engineering for a general reusable solution to a commonly occurring problem in software design.

There were 23 design patterns introduced in the original book Design Patterns: Elements Of Reusable Object-Oriented Software written by Erich Gamma, Richard Helm, Ralph Johnson andJohn Vlissides — the famous Gang of Four (GoF).

Revealing module pattern is a design pattern, which let you organise your javascript code in modules, and gives better code structure.It gives you power to create public / private variables / methods(using closure), and avoids polluting global scope(If you know how to avoid that).

How it works:

It uses IIFE(Immediately invoked function expression: (function(){ })();) to wrap your module function, thus creating a local scope for all your variables and methods.

(function () {
// declare private variables and/or functions
return {
// declare public variables and/or functions}
})();
  • Modules should be Immediately-Invoked-Function-Expressions (IIFE) to allow for private scopes — that is, a closure that protect variables and methods.
  • it should return an object instead of a function. This is what it looks like:
var people = (function(){
var name = "anil kumar"; //local variable
function sayName(){
alert(name);
};
return{
sayYourName: sayName
}
})();
alert(people.sayYourName());

The Observer Pattern is a software design pattern in which an object, called the subject, maintains a list of its dependents, called observers, and notifies them automatically of any state changes.

The Connect Method in Redux uses the Observer Pattern.

In Redux, it is possible for components to listen (or connect) to any part of the state tree. When the state changes, the components will update. This is an excellent example of the Observer Pattern.

The observers are the components, and the subject is the state tree.

export default connect()(App);  #connect() is an inbuilt HOF.

“In software engineering, the Singleton Pattern is a design pattern that restricts the instantiation of a class to only one instance that is globally available.

In broader terms, the Singleton restricts clients from creating multiple objects, after the first object created, it will return instances of itself i.e., A Singleton only allows for a single instantiation, but many instances of the same object.

One example is using an office printer. If there are ten people in an office, and they all use one printer, ten computers share one printer (instance). By sharing one printer, they share the same resources.

The create method is private because we do not want the client to access this, however, notice that the getInstance method is public. Each officer worker can generate a printer instance by interacting with the getInstance method, like so:

var officePrinter = printer.getInstance();

In AngularJS, Singletons are prevalent, the most notable being services, factories, and providers. Since they maintain state and provides resource accessing, creating two instances defeats the point of a shared service/factory/provider.

Race conditions occur in multi-threaded applications when more than one thread tries to access the same resource. Singletons are susceptible to race conditions, such that if no instance were initialized first, two threads could then create two objects instead of returning and instance. This defeats the purpose of a singleton. Therefore, developers must be privy to synchronization when implementing singletons in multithreaded applications.

It is also useful when you need that instance to be accessible in different parts of the application, usually for logging functionality, communication with external systems, database access, etc.Ja

The State Tree (in Redux) uses a pattern known as the Singleton Pattern.

In Factory pattern, we create object without exposing the creation logic to the client and refer to newly created object using a common interface.

Factory Pattern template

What is a Data Structure?

Simply put, a data structure is a container that stores data in a specific layout. This “layout” allows a data structure to be efficient in some operations and inefficient in others. Your goal is to understand data structures so that you can pick the data structure that’s most optimal for the problem at hand.

Why do we need Data Structures?

As data structures are used to store data in an organized form, and since data is the most crucial entity in computer science, the true worth of data structures is clear.

No matter what problem are you solving, in one way or another you have to deal with data — whether it’s an employee’s salary, stock prices, a grocery list, or even a simple telephone directory.

Based on different scenarios, data needs to be stored in a specific format. We have a handful of data structures that cover our need to store data in different formats.

8 Commonly used Data Structures

Let’s first list the most commonly used data structures, and then we’ll cover them one by one:

  1. Arrays
  2. Stacks
  3. Queues
  4. Linked Lists
  5. Trees
  6. Graphs
  7. Tries (they are effectively trees, but it’s still good to call them out separately).
  8. Hash Tables

Arrays

An array is the simplest and most widely used data structure. Other data structures like stacks and queues are derived from arrays.

Here’s an image of a simple array of size 4, containing elements (1, 2, 3 and 4).

Each data element is assigned a positive numerical value called the Index, which corresponds to the position of that item in the array. The majority of languages define the starting index of the array as 0.

The following are the two types of arrays:

  • One-dimensional arrays (as shown above)
  • Multi-dimensional arrays (arrays within arrays)

Basic Operations on Arrays

  • Insert — Inserts an element at given index
  • Get — Returns the element at given index
  • Delete — Deletes an element at given index
  • Size — Get the total number of elements in array

Commonly asked Array interview questions

  • Find the second minimum element of an array
  • First non-repeating integers in an array
  • Merge two sorted arrays
  • Rearrange positive and negative values in an array

Stacks (LIFO)

We are all familiar with the famous Undo option, which is present in almost every application. Ever wondered how it works? The idea: you store the previous states of your work (which are limited to a specific number) in the memory in such an order that the last one appears first. This can’t be done just by using arrays. That is where the Stack comes in handy.

A real-life example of Stack could be a pile of books placed in a vertical order. In order to get the book that’s somewhere in the middle, you will need to remove all the books placed on top of it. This is how the LIFO (Last In First Out) method works.

Here’s an image of stack containing three data elements (1, 2 and 3), where 3 is at the top and will be removed first:

Basic operations of stack:

  • Push — Inserts an element at the top
  • Pop — Returns the top element after removing from the stack
  • isEmpty — Returns true if the stack is empty
  • Top — Returns the top element without removing from the stack

Commonly asked Stack interview questions

  • Evaluate postfix expression using a stack
  • Sort values in a stack
  • Check balanced parentheses in an expression

Queues

Similar to Stack, Queue is another linear data structure that stores the element in a sequential manner. The only significant difference between Stack and Queue is that instead of using the LIFO method, Queue implements the FIFO method, which is short for First in First Out.

A perfect real-life example of Queue: a line of people waiting at a ticket booth. If a new person comes, they will join the line from the end, not from the start — and the person standing at the front will be the first to get the ticket and hence leave the line.

Here’s an image of Queue containing four data elements (1, 2, 3 and 4), where 1 is at the top and will be removed first:

Basic operations of Queue

  • Enqueue() — Inserts element to the end of the queue
  • Dequeue() — Removes an element from the start of the queue
  • isEmpty() — Returns true if queue is empty
  • Top() — Returns the first element of the queue

Commonly asked Queue interview questions

  • Implement stack using a queue
  • Reverse first k elements of a queue
  • Generate binary numbers from 1 to n using a queue

Linked List

A linked list is another important linear data structure which might look similar to arrays at first but differs in memory allocation, internal structure and how basic operations of insertion and deletion are carried out.

A linked list is like a chain of nodes, where each node contains information like data and a pointer to the succeeding node in the chain. There’s a head pointer, which points to the first element of the linked list, and if the list is empty then it simply points to null or nothing.

Linked lists are used to implement file systems, hash tables, and adjacency lists.

Here’s a visual representation of the internal structure of a linked list:

Following are the types of linked lists:

  • Singly Linked List (Unidirectional)
  • Doubly Linked List (Bi-directional)

Basic operations of Linked List:

  • InsertAtEnd — Inserts given element at the end of the linked list
  • InsertAtHead — Inserts given element at the start/head of the linked list
  • Delete — Deletes given element from the linked list
  • DeleteAtHead — Deletes first element of the linked list
  • Search — Returns the given element from a linked list
  • isEmpty — Returns true if the linked list is empty

Commonly asked Linked List interview questions

  • Reverse a linked list
  • Detect loop in a linked list
  • Return Nth node from the end in a linked list
  • Remove duplicates from a linked list

Graphs

A graph is a set of nodes that are connected to each other in the form of a network. Nodes are also called vertices. A pair(x,y) is called an edge, which indicates that vertex x is connected to vertex y. An edge may contain weight/cost, showing how much cost is required to traverse from vertex x to y.

Types of Graphs:

  • Undirected Graph
  • Directed Graph

In a programming language, graphs can be represented using two forms:

  • Adjacency Matrix
  • Adjacency List

Common graph traversing algorithms:

  • Breadth First Search
  • Depth First Search

Commonly asked Graph interview questions

  • Implement Breadth and Depth First Search
  • Check if a graph is a tree or not
  • Count number of edges in a graph
  • Find the shortest path between two vertices

Trees

A tree is a hierarchical data structure consisting of vertices (nodes) and edges that connect them. Trees are similar to graphs, but the key point that differentiates a tree from the graph is that a cycle cannot exist in a tree.

Trees are extensively used in Artificial Intelligence and complex algorithms to provide an efficient storage mechanism for problem-solving.

Here’s an image of a simple tree, and basic terminologies used in tree data structure:

The following are the types of trees:

  • N-ary Tree
  • Balanced Tree
  • Binary Tree
  • Binary Search Tree
  • AVL Tree
  • Red Black Tree
  • 2–3 Tree

Out of the above, Binary Tree and Binary Search Tree are the most commonly used trees.

Commonly asked Tree interview questions

  • Find the height of a binary tree
  • Find kth maximum value in a binary search tree
  • Find nodes at “k” distance from the root
  • Find ancestors of a given node in a binary tree

Trie

Trie, which is also known as “Prefix Trees”, is a tree-like data structure which proves to be quite efficient for solving problems related to strings. It provides fast retrieval, and is mostly used for searching words in a dictionary, providing auto suggestions in a search engine, and even for IP routing.

Here’s an illustration of how three words “top”, “thus”, and “their” are stored in Trie:

The words are stored in the top to the bottom manner where green colored nodes “p”, “s” and “r” indicates the end of “top”, “thus”, and “their” respectively.

Commonly asked Trie interview questions:

  • Count total number of words in Trie
  • Print all words stored in Trie
  • Sort elements of an array using Trie
  • Form words from a dictionary using Trie
  • Build a T9 dictionary

Hash Table

Hashing is a process used to uniquely identify objects and store each object at some pre-calculated unique index called its “key.” So, the object is stored in the form of a “key-value” pair, and the collection of such items is called a “dictionary.” Each object can be searched using that key. There are different data structures based on hashing, but the most commonly used data structure is the hash table.

Hash tables are generally implemented using arrays.

The performance of hashing data structure depends upon these three factors:

  • Hash Function
  • Size of the Hash Table
  • Collision Handling Method

Here’s an illustration of how the hash is mapped in an array. The index of this array is calculated through a Hash Function.

Commonly asked Hashing interview questions

  • Find symmetric pairs in an array
  • Trace complete path of a journey
  • Find if an array is a subset of another array
  • Check if given arrays are disjoint

The above are the top eight data structures that you should definitely know before walking into a coding interview.

References:

https://medium.com/@amejiarosario/8-time-complexity-examples-that-every-programmer-should-know-171bd21e5ba

https://www.geeksforgeeks.org/understanding-time-complexity-simple-examples/

Experience with Front-end Technologies and MERN / MEAN Stack. Working on all Major UI Frameworks like React, Angular.