Posts

Z-Function Algorithm: Substring Search

Agenda: Quick Intro Input Output Complexity Algo Logic C++ Code Real-Life use cases Practice Problem Conclusion Sources for further reading Quick Intro The Z-function is a powerful string-matching algorithm used for pattern matching and searching within a given string. Its primary purpose is to find all occurrences of a specified pattern in the text. Definition: Given a string s of length n, the Z-function produces an array Z where Z[i] represents the length of the longest substring starting from s[i] that is also a prefix of s. Input Text(T): The input to the Z-function algorithm is a single string T of length n . Output Z-Array(z): The output of the Z-function algorithm is an array Z of length n where each element Z[i] represents the length of the longest substring starting from the position i in T that matches a prefix of T . Complexity Time: O(n) Space: O(n) Where, n ---> length of input Text....
Post a Comment
Read more

KMP Algorithm: Pattern Searching in Text

Agenda: Quick Intro Input Output Complexity Algo Logic Code Real-Life Use Cases Conclusion Sources for further reading 1. Quick Intro The Knuth-Morris-Pratt (KMP) algorithm is a classic string-searching algorithm used to find occurrences of a "pattern" string within a "text" string.  It was devised by Donald Knuth , James H. Morris , and Vaughan Pratt , hence the name KMP .  The key feature of the KMP algorithm is its ability to perform the search efficiently by avoiding unnecessary comparisons . 2. Input The KMP algorithm takes two inputs: Text (T) : The string in which we are searching for a pattern. Pattern (P) : The string we are searching for within the text. 3. Output Indices (I): Starting indices of all occurrences of the pattern in the text. If the pattern is not found, it returns an empty list. 4. Complexity Time Complexity :  O(n + m)   n ---> Length of the text. m ---> Length of the pattern. Sp...
Post a Comment
Read more

Morris Traversal: Space Efficient Way to Traverse Binary Trees | Threaded BT

Agenda: Quick Intro Why? Understanding Morris Traversal: The Threaded Binary Tree Advantages Drawbacks Implementation in Python Time & Space Complexity Conclusion Quick Intro Morris Traversal is a clever tree traversal algorithm that allows us to traverse a binary tree in CONSTANT SPACE . (i.e. without recursion or an explicit stack). Why? When dealing with binary trees, traditional traversal methods like In-order, Pre-order, and post-order often require additional space proportional to the height of the tree, primarily for the recursion stack. This space complexity can be a limitation in memory-constrained environments . Understanding Morris Traversal: The Threaded Binary Tree Named after its inventor, Joseph M. Morris, this traversal technique leverages the concept of threading the binary tree . Threading the binary tree means it uses threads or links pointing to ancestor node...
Post a Comment
Read more

Moore's Voting Algorithm

Agenda: What is Moore's Voting Algorithm? Analogy Logic Why it works? Code
Post a Comment
Read more

Breaking Norms: The Strategic Art of Database Denormalization

 Agenda: Introduction What is Denormalization? Benefits When to use? Read-Heavy Systems Reporting and Analytics Real time data Requirements Denormalization Techniques Materialized Views Redundant Columns Aggregated Tables Challenges and Consideration Conclusion
Post a Comment
Read more

Decoding Database Scaling: Federation vs Sharding

Image
 Agenda: Understanding Federation Federation in precise and simple possible terms with good example Advantages of Federation Disadvantages of federation The Essence of Sharding Disadvantages of Sharding Federation vs Sharding Key Differences Choosing the Right Path In the dynamic landscape of data management, the quest for efficient and scalable database solutions is perpetual. Two prominent strategies that often stand out in this pursuit are Federation and Sharding. Both approaches address the challenges of handling large volumes of data and maintaining optimal performance, yet they differ significantly in their implementations and implications. In this blog post, we'll delve into the intricacies of Federation and Sharding, exploring their strengths, weaknesses, and applications. [1] Understanding Federation Federation (or functional partitioning) splits up databases by function. Federation is like having separate but independent databases, each responsible for specific types of d...
Post a Comment
Read more

Consistent Hashing (Balancing Act in Distributed Systems)

Image
Agenda: Introduction What is Consistent Hashing? Why it is needed? How Consistent Hashing Works Hash Ring Hash Function Data Retrieval Advantages of Consistent Hashing Real-World Applications Challenges and Considerations Conclusion
Post a Comment
Read more