Posts

Showing posts from October, 2021

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...

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/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); String result = value == -1 ? "There is no max voted element" : "The max voted element is " + value; System.out.println(result); } } Output The max voted element is 3

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 Output Does abcxabcdabcdabcyhave pattern: abcdabcy? true Using DFA (Deterministic Finite State Machine) Does abcxabcdabcdabcyhave pattern: abcdabcy? true