Posts

Capacity Estimation

Image
 References: Ref1 , Ref2 , Ref3 Approx/Actual Estimation 1 Million / day = 12 / sec 1 Million / day = 700 / min 1 Million / day = 4200 / hrs Power of 2s Round of into power of 2 and 10s 50 -> 64 500 -> 512 1 day -> 86400 sec -> 100000 Million/Billion/Trillion 1 Million = 10^6 1 Billion = 10^9 1 Trillion = 10^12 Storage 1 Byte = 8 bits 1 KB = 1024 Bytes 1 MB = 1024 KB 1 GB = 1024 MB

Implement Thread Pool

 Reference: JavaCodeGreek

OSI Model | Open Systems Interconnection Model

All ( Application Layer)  People ( Presentation Layer)  Seem ( Session Layer)  To ( Transport Layer)  Need ( Network Layer)  Data ( Data Link Layer)  Processing ( Physical Layer) GreeksForGreeks reference Additional References Switch:   Facilitate network communication within local network.  Connect devices (Computer, printer, application server etc).  Maintain a table to MAC address and Port Work with Data link layer Router: Work with network layer Connect two networks or (connect network to internet) Maintain logical address Assign private IP address to the devices of local network Maintain pool o private IP address Router use  Dynamic Host Configuration Protocol (DHCP) to automatically provides an Internet Protocol (IP) host with its IP address and other related configuration information such as the subnet mask and default gateway. Public IP of router is used to connect to the internet and private IP of router is used to communicate to inside local network All computers in p

Data Structures and Algorithms | Program list

  Reference

Time Complexity Java Collection

  Stackoverflow

ArrayList vs LinkedList

  StackOverflow

Types of network protocols

Ref1 Transmission Control Protocol (TCP) Internet Protocol (IP):  User Datagram Protocol (UDP):  Post office Protocol (POP):  Simple mail transport Protocol (SMTP):  File Transfer Protocol (FTP):  Hypertext Transfer Protocol (HTTP):  Hypertext Transfer Protocol Secure (HTTPS):  Telnet:  Gopher:  Some other popular protocols act as co-functioning protocols associated with these primary protocols for core functioning. These are:  ARP (Address Resolution Protocol)  DHCP (Dynamic Host Configuration Protocol)  IMAP4 (Internet Message Access Protocol)  SIP (Session Initiation Protocol)  RTP (Real-Time Transport Protocol)  Secure Real Time Transport Protocol (SRTP): The  Secure Real-time Transport Protocol  (SRTP) is a profile for Real-time Transport Protocol (RTP) intended to provide encryption, message authentication and integrity, and replay attack protection to the RTP data in both unicast and multicast applications. RLP (Resource Location Protocol)  RAP (Route Access Protocol)  L2TP (Lay

Monolithic vs Microservice architecture difference

  What Is Monolithic Architecture? A  monolithic  application is built on a single code base with a variable number of modules. The number of modules depends on the complexity of the business and its technical features. The whole application—and dependencies, when applicable—are built on a single system with a single executable binary for deployment. A monolithic architecture has distinct advantages and disadvantages that should be evaluated when deciding when selecting the optimal type of architecture for the application. Monolithic architecture pros: Fewer cross-cutting concerns: The majority of applications typically have a large number of cross-cutting concerns. Running them all on a monolithic architecture facilitates hooking up components. Less operational overheads: Avoids the additional costs stemming from microservices such as interservice communication, service discovery and registration, load balancing, decentralized data management or distributed logging, for example. Comp

Majority Elements in an Array | Moore's Voting Algorithm | Element appears more than Array.length/2

class MostVotedElement { public static int boyerMooreMaxVoting(int[] array) { int maxVotedElement = array[0]; int count = 1; for(int i = 0; i < array.length; i++) { count = (maxVotedElement == array[i]) ? ++count : --count; // If count is 0 then assign current element as maxVotedElement if(count == 0) { maxVotedElement = array[i]; count = 1; } } // Re-validate maxVotedElement count = 0; for(int element : array) { if(maxVotedElement == element) { count++; } } return count > array.length/2 ? count : -1; // it will find count if element's // frequency is more than array.length/2. 2 Can be any number 3, 4 etc } public static void main(String args[]){ int[] array = new int[] {2, 3, 4, 3, 3}; int value = boyerMooreMaxVoting(array);

Substring search algorithms

Given text and pattern, find out appearance of pattern in given text.  1. Knuth–Morris–Pratt(KMP) Pattern Matching , Explanation Video 2. Boyer-Moore: Example Video1 , Video2 3. Rabin-Karp: Example Video 1 Related Questions: Boyer Moore maximum voting algorithm : Explanation Video1 Approach 1: Use brute force algorithm where we can count frequency of each element. Time complexity: O(N^2) & Space complexity: 1 Approach 2: Sort the array in NLogN time and count element occurrences in O(N) time. Approach 3: Use frequency table of elements. Time complexity: 1 & Space complexity: O(N^2) Approach 4: Use HashMap where element as key and count as value Approach 5: Boyer Moore maximum voting algorithm: Code , Time Complexity: O(N) & Space complexity: 1

Knuth–Morris–Pratt(KMP) Pattern Matching

/** * Do pattern matching using KMP algorithm * * Runtime complexity - O(m + n) where m is length of text and n is length of pattern * Space complexity - O(n) */ class SubstringSearch { /** * Slow method of pattern matching */ public boolean hasSubstring(char[] text, char[] pattern){ int i=0; int j=0; int k = 0; while(i < text.length && j < pattern.length){ if(text[i] == pattern[j]){ i++; j++; }else{ j=0; k++; i = k; } } if(j == pattern.length){ return true; } return false; } /** * Compute temporary array to maintain size of suffix which is same as prefix * Time/space complexity is O(size of pattern) */ private int[] computeTemporaryArray(char pattern[]){ int [] lps = new int[pattern.length]; int index =0;

Negative Weights

Image
 

edge-weighted Direct Acyclic Graphs (DAGs)

Image
 

Shorted paths algorithms

Image
  Shorted Path Properties Dijkstra's algorithm ( Java code ) edge-weighted Direct Acyclic Graphs (DAGs) Negative Weights Shortest paths summary Dijkstra’s algorithm. ・Nearly linear-time when weights are nonnegative. ・Generalization encompasses DFS, BFS, and Prim.  Acyclic edge-weighted digraphs. ・Arise in applications. ・Faster than Dijkstra’s algorithm. ・Negative weights are no problem.  Negative weights and negative cycles. ・Arise in applications. ・If no negative cycles, can find shortest paths via Bellman-Ford. ・If negative cycles, can find one via Bellman-Ford.  Shortest-paths is a broadly useful problem-solving model.

Dijkstra's algorithm Java implementation

/** Single-source shortest paths API */ class DijkstraSingleSourceShortestPath { // Source private final int s; // distTo[v] is length of shortest known path from s to v. private final double[] distTo; // edgeTo[w] is last edge on shortest known path from s to w private final DirectedEdge[] edgeTo; private IndexMinPQ pq; public DijkstraSingleSourceShortestPath(EdgeWeightedDigraph G, int s) { // shortest paths from s in graph G this.s = s; this.distTo = new double[G.V()]; this.edgeTo = new DirectedEdge[G.V()]; pq = new IndexMinPQ (G.V()); for (int v = 0; v < G.V(); v++) distTo[v] = Double.POSITIVE_INFINITY; distTo[s] = 0.0; pq.insert(s, 0.0); while (!pq.isEmpty()) { // relax vertices in order of distance from s int v = pq.delMin(); for (DirectedEdge e : G.adj(v)) relax(e); } } /** length of shortest p

Prim's minimum spanning tree algorithm: lazy implementation

import java.util.Queue; import java.util.ArrayDeque; import java.util.PriorityQueue; import java.util.Set; import java.util.HashSet; import java.util.List; import java.util.ArrayList; class PrimMinimumSpanningTreeLazy { private boolean[] visited; // MST vertices private Queue mst; // MST edges private Queue pq; // PriorityQueue of edges private double weight; public PrimMinimumSpanningTreeLazy(EdgeWeightedGraph G) { this.visited = new boolean[G.V()]; this.mst = new ArrayDeque<>(); this.pq = new PriorityQueue<>(); // assume G is connected visit(G, 0); while (!pq.isEmpty() && mst.size() < G.V()-1) { // repeatedly delete the min weight edge e = v–w from PQ Edge edge = pq.poll(); // greedily add edges to MST int v = edge.either(), w = edge.other(v); // ignore if both endpoints in T if(visi

Kruskal's algorithm: Java implementation

import java.util.Queue; import java.util.ArrayDeque; import java.util.PriorityQueue; import java.util.Set; import java.util.HashSet; import java.util.List; import java.util.ArrayList; class KruskalMinimumSpanningTree { private Queue mst = new ArrayDeque (); private double weight; public KruskalMinimumSpanningTree(EdgeWeightedGraph G) { // build priority queue Queue pq = new PriorityQueue (); for (Edge e : G.edges()) { pq.add(e); } UnionFind uf = new UnionFind(G.V()); while (!pq.isEmpty() && mst.size() < G.V()-1) { Edge e = pq.poll(); // greedily add edges to MST int v = e.either(), w = e.other(v); if (!uf.isConnected(v, w)) { // Check that edge v–w does not create cycle // merge sets uf.union(v, w); // add edge to MST mst.add(e); // add weight in total weight count

Minimum spanning tree

Image
  Greedy MST algorithm: efficient implementations 1. Kruskal's algorithm ( Code ) 2. Prim's algorithm (1.   lazy implementation , 2.  ) 3. Borüvka's algorithm