DEV Community: samuel zih

Design Add and Search Words Data Structure

samuel zih — Tue, 19 Nov 2024 03:41:22 +0000

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

WordDictionary() Initializes the object.
void addWord(word) Adds word to the data structure, it can be matched later.
bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

The code:

_note: _

in the walkthrough image below i use .a or .b or.c just to distinct the first a or b or c. This is not the same as a word starting with '.' as seen in the problem description. if we are to search a word that started with '.' ,the first letter of that word can be any letter present in the children of the root as described in the problem statement.

The Walkthrough:

for better image quality follow this link on page 3:

https://www.canva.com/design/DAGW0KnXStQ/ATe3pYzBeDOMFzS-ZfBLVA/edit?utm_content=DAGW0KnXStQ&utm_campaign=designshare&utm_medium=link2&utm_source=sharebutton

Binary Tree Maximum Path Sum

samuel zih — Tue, 19 Nov 2024 02:14:53 +0000

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node's values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

for this problem I have provided the code and the visual walkthrough of how the algorithm performs.

Example:

The Code:

Visual Walkthrough

for a better quality image follow this link the image is on page 2:

https://www.canva.com/design/DAGW0KnXStQ/ATe3pYzBeDOMFzS-ZfBLVA/edit?utm_content=DAGW0KnXStQ&utm_campaign=designshare&utm_medium=link2&utm_source=sharebutton

Combination Sum Leetcode Problem

samuel zih — Sat, 16 Nov 2024 07:37:58 +0000

This is a simple solution code and walkthrough of the leetcode problem combination sum

I have found that solutions to the combination sum problem are often very difficult to test. By this, I mean that walking through an example can be challenging due to the many recursive calls involved. To address this, I decided to create a walkthrough using a simple example. This solution combines both iteration and recursion, making the walkthrough process much easier to follow compared to solutions that rely on double recursion. Additionally, the example is short and simple enough for curious minds to easily follow and cement their understanding of the underlying functionality of the code. For this walkthrough, I have used the example of candidates = [2, 3, 4] and target = 6.

Below is an image of my handwritten walkthrough. I encourage you to review the solution and try to understand my reasoning for each step as presented in the image. The walkthrough progresses from left to right.

Maybe you can put the code on your laptop and the image of the walkthrough on your phone or tablet to better follow both code and walkthrough for the same example or other examples.

I find that:

An example with an array length of 3 is usually ideal.

A target value big enough for the elements in the array to easily make up the target is best for walkthrough purposes.

2.
Anything larger than an array length of 3 makes the process of walking through the code unnecessarily tedious, which defeats the purpose of the test.

The elements in the array must also be of a sizeable value. For example: Do not use candidates like [1, 3, 4] with a target of 6.

Here, the value 1 is very small, and including it unnecessarily increases the number of recursive calls.

For instance, we already know that a possible combination for a target of 6 is 1, 1, 1, 1, 1, 1. To find that particular solution, the code would make six recursive calls, and each of those 6 recursive calls will possibly lead to other recursive calls if the condition to find other combinations, after we meet the condition which found the combination [1, 1, 1, 1, 1, 1], and return, is not met. Now imagine doing the same for other combinations like [1, 1, 1, 3] and so on. It’s easy to see how this would quickly become exhausting.

In summary:

The condition for this test is:
The elements in the array must be of a sizeable value.
The target must be appropriate, not too small or too large.
Simply put, if you cannot handwrite the possible combinations of a target from your example candidate array to get your proposed target, then you should not use it to test.

After this, try and also see if you could do the same.

For now, I have decided to upload this version. If God permits, I will rewrite it in proper handwriting with a more polished and formatted presentation in the future.

Code:

Walkthrough Solution

Typed version:

for better image quality of the solution follow this link:

https://www.canva.com/design/DAGW0KnXStQ/ATe3pYzBeDOMFzS-ZfBLVA/edit?utm_content=DAGW0KnXStQ&utm_campaign=designshare&utm_medium=link2&utm_source=sharebutton

Typed version of this solution:

https://www.canva.com/design/DAGZTNrbtP8/HCuH-1dKACCc3TmVpCL0ow/edit?utm_content=DAGZTNrbtP8&utm_campaign=designshare&utm_medium=link2&utm_source=sharebutton

Hope this helps ; byeeee 😁

Building a Binary Tree from Preorder and Inorder Traversal: An In-Depth Guide

samuel zih — Mon, 23 Sep 2024 02:54:14 +0000

In this blog post, we’ll walk through a solution to the well-known problem: constructing a binary tree from its preorder and inorder traversal arrays. We'll not only explain the logic behind the algorithm but also show how the recursive process works step-by-step. Along the way, we’ll delve into the concepts that govern the solution and break it down for easy understanding.

Problem Statement
You are given two arrays representing the preorder and inorder traversal of a binary tree. Your task is to construct the binary tree from these arrays.

Preorder traversal: Visit the root node first, then recursively visit the left subtree, followed by the right subtree.
(Root → Left → Right)

Inorder traversal: Recursively visit the left subtree first, then visit the root, and finally, visit the right subtree.
(Left → Root → Right)

example:

Key Concepts
To understand how to solve this problem, we need to grasp the structure of binary trees and how their preorder and inorder traversals work:

Preorder Traversal gives us the root of the tree first.
Inorder Traversal provides us the relative positioning of the left and right subtrees concerning the root.

From this, we can break down the problem recursively:

The first element of the preorder array is the root of the tree.
The inorder array splits into two parts: the left part consists of elements belonging to the left subtree, and the right part consists of elements in the right subtree.
Using the root node, we can recursively build the left and right subtrees.

The Recursive DFS Algorithm
Let’s break down the recursive process. We’ll use the following recursive function to build the tree:

Walkthrough: Constructing the Left Subtree
Let's start by building the leftmost branch of the tree for the example preorder and inorder arrays.

Initial Call:
Preorder: [10, 6, 4, 2, 8, 14, 12, 13, 16]
Inorder: [2, 4, 6, 8, 10, 12, 13, 14, 16]

From the preorder array, the first element is 10, which is the root of the tree. The inorder array splits around 10:

Left subtree: [2, 4, 6, 8]
Right subtree: [12, 13, 14, 16]

First Recursive Call (Left Subtree of 10):
Preorder: [6, 4, 2, 8]
Inorder: [2, 4, 6, 8]
Here, 6 is the next root (first element of the preorder), and the inorder array splits into:

Left subtree: [2, 4]
Right subtree: [8]
Second Recursive Call (Left Subtree of 6):
Preorder: [4, 2]
Inorder: [2, 4]
Now, 4 becomes the next root, and the inorder array splits again:

Left subtree: [2]
Right subtree:
Third Recursive Call (Left Subtree of 4):
Preorder: [2]
Inorder: [2]
Finally, 2 is the root of this subtree, and since there are no more elements in the preorder or inorder arrays, we reach the base case and return None for both the left and right children of 2.

Walkthrough: Constructing the Right Subtree
Now, let's switch to building the rightmost branch, which starts from the root's right subtree.

Preorder: [10, 6, 4, 2, 8, 14, 12, 13, 16]
Inorder: [2, 4, 6, 8, 10, 12, 13, 14, 16]

Initial Call (Right Subtree of 10):
Preorder: [14, 12, 13, 16]
Inorder: [12, 13, 14, 16]
The next root is 14, and the inorder array splits around 14:

Left subtree: [12, 13]
Right subtree: [16]
First Recursive Call (Left Subtree of 14):
Preorder: [12, 13]
Inorder: [12, 13]
Here, 12 is the next root, and the inorder array splits into:

Left subtree: []
Right subtree: [13]
Second Recursive Call (Right Subtree of 12):
Preorder: [13]
Inorder: [13]

Finally, 13 is the root of this subtree, and since there are no more elements in the preorder or inorder arrays, we reach the base case and return None for both the left and right children of 13.

At this point, we’ve completed the rightmost branch of the tree:

Completing the Tree
Now, we can merge the left and right branches to form the full tree:

Code Explanation
Let’s go over the code section by section:

1. Base Case:

This checks whether either the preorder or inorder arrays are empty. If so, we’ve reached a leaf node and return None.

2. Root Node Construction:

The first element of the preorder array is always the root of the current subtree. We create a new TreeNode with this value.

3. Find Root Index in Inorder Array:

To split the left and right subtrees, we need to find where the root value appears in the inorder array. The elements to the left of this index form the left subtree, and the elements to the right form the right subtree.

Recursively Build Left and Right Subtrees:

Abstract Reasoning for root.left:

root.left =
self.buildTree(
preorder so : rootval on left and we take the right element after the rootval to the inorderindex of the rootval;,
inorder so : root_val is on the right and we take element from the start of the inorder array up until the inorderindex of rootval)

Explanation:

In the preorder traversal, the first element is always the root. After that, the elements belonging to the left subtree will come before those of the right subtree.

The code preorder[1:root_index_in_inorder+1] is extracting the portion of the preorder array that corresponds to the left subtree.
This range is from the second element (right after the root) up to the position determined by root_index_in_inorder + 1.
This index is the length of the left subtree as indicated by the inorder traversal.

In the inorder traversal, elements to the left of root_index_in_inorder are part of the left subtree.
inorder[:root_index_in_inorder] correctly captures all elements from the start of the inorder array up until the root value, indicating the left subtree.

Abstract Reasoning for root.right:

root.right =
self.buildTree(
preorder so : rootval on left and we take the right element after the rootval to the inorderindex of the rootval;,
inorder so : root_val is on the left and we take element from inorderindex of rootval in inorder till the end of the array)

Explanation:

In the preorder traversal, after the left subtree has been accounted for, the remaining elements belong to the right subtree.

The code preorder[root_index_in_inorder+1:] captures the elements of the preorder array that belong to the right subtree.

This starts after the left subtree and extends to the rest of the array.
In the inorder traversal, elements to the right of root_index_in_inorder belong to the right subtree.

inorder[root_index_in_inorder+1:] correctly slices the inorder array starting from just after the root and extending to the end, representing the right subtree.

Conclusion
Constructing a binary tree from preorder and inorder arrays is a classic recursive problem. By understanding how these two traversals work and breaking the problem down recursively, we can effectively rebuild the entire tree. I hope this walkthrough clarified the recursive process, and the detailed breakdown of both the leftmost and rightmost branches gives you a better understanding of how the algorithm works in practice.

Feel free to experiment with other examples to deepen your understanding of this elegant solution!

Design a Ticket Booking Site

samuel zih — Thu, 29 Aug 2024 15:52:34 +0000

Design a Ticket Booking Site

When developing distributed systems, it’s essential to design with a clear focus on several critical goals: supporting resource sharing, ensuring transparency in distribution, maintaining openness, achieving scalability, and avoiding common pitfalls that could compromise system performance. These goals are particularly important in high-demand applications like a Ticket Booking Web Application, where users expect seamless experiences despite varying loads and complex operations.

In this case study, I will explore how I addressed these design goals in the development of a ticket booking platform. The system not only supports the basic functionalities of viewing and booking events but also meets stringent non-functional requirements like high availability, low latency, and scalability under extreme conditions. Through a combination of innovative solutions and industry best practices, I ensured the application could handle millions of users during peak times, maintain consistent data, and deliver fast search results, all while safeguarding against the challenges inherent in distributed system design.

** Functional requirements:**

Users should be able to view events
Users should be able to search for events
Users should be able to book tickets to events

Below the line (out of scope for our discussion)):

Users should be able to view their booked events
Admins or event coordinators should be able to add events
Popular events should have dynamic pricing

*Non-Functional requirements: *

The system should prioritize availability for searching & viewing events, but should prioritize consistency for booking events (no double booking)
The system should be scalable and able to handle high throughput in the form of popular events (10 million users, one event)
The system should have low latency search (< 500ms)
The system is read heavy, and thus needs to be able to support high read throughput (100:1)

Below the line (out of scope for our discussion):

1.The system should protect user data and adhere to GDPR

The system should be fault tolerant 3.The system should provide secure transactions for purchases
The system should be well tested and easy to deploy (CI/CD pipelines)
The system should have regular backups

The functional requirements refers to what Users should be able to do.Non-functional requirements define the system's quality and how it should function.Our application has clients who communicate with our servers through API gateways to perform operations like search, event CRUD, booking, and Stripe payment. Our servers also interact with our database. Let's take one of the functional components: Search. In our initial design, to search for anything, we would have to traverse the entire table in our database to find it. The execution time of this type of search is directly proportional to the number of items in our table, leading to delays. In the above diagram

** A better solution would be to query a search engine like Elasticsearch**, which builds an inverted index to make searching documents by term much faster. For example, if we have a popular search query, we can tokenize that string or set of strings, create terms from them, and map those terms in a hashmap of sorts to the documents or queries where they appear. For instance, "Westlife": [event1, event2 …] or "playoffs": [event3, event4 …]. This approach makes searching for any term and retrieving results super fast.

Now the issue arises: how do we send data to our database and Elasticsearch while ensuring that the data remains consistent, available, and fault-tolerant at all times? One approach is to send the data synchronously to the two databases simultaneously, but the problem with this is that if one system fails completely, we can no longer persist data, or worse, even if we do persist our data, we may end up with inconsistent data. A better approach is to use Change Data Capture (CDC), which captures changes in our primary data store and puts them onto a stream to be consumed asynchronously. For this, we use Debezium as a CDC and Kafka as a streaming service.
Kafka itself operates on a consensus-based algorithm, KRaft. The leader appends incoming log changes (AppendEntries RPCs) with new log entries to its followers (state machine). Kafka takes this data into a log and appends it to the primary database and to Elasticsearch. This ensures that in the case of failovers, the data entries are still available in the log to be consumed, maintaining data consistency and availability at all times.

With CDC and streaming, we also need to account for edge cases. For instance, if we have a surge of requests for a big event, we need to protect our servers. This can be managed by implementing data batching:instead of sending individual requests to elastic search for each change we accumulate a batch of changes and send them in a single bulk request. This reduces the number of HTTP requests and minimizing the network overhead and improves throughput., filtering, deduplication: the consumer can filter out unnecessary changes or deduplicate events before they are batched, rate limiting, or throttling the consumer service also manages how fats data is sent to elasticsearch to avoid overwhelming the cluster.

This search solution has successfully met our requirement of avoiding low-latency search, ensuring super-fast search performance.

We can further improve search performance by deploying a Content Delivery Network (CDN) between our client and API gateway. This CDN caches API endpoints and results for a short time, delivering them to users during network surges in the same geographical location. This is particularly useful during high-traffic periods, such as Black Friday sales or popular events. In cases where many users are searching for the same exact term, the CDN can return cached results immediately, significantly speeding up the search process. However, this approach is only effective if the users' searches are geographically close to where the surge occurs.

A downside to this approach is that it becomes less useful as the permutations of search queries increase. Additionally, if our system evolves to provide personalized recommendations, a CDN may not suffice. This is because, with a CDN, every user making the same API call receives the exact same result, which would not be appropriate for a recommendation system.

Let's take another part of our system: scalability during surges for popular events and the ways we can handle ticket purchases. For really popular events, tickets could go stale quickly. One approach is to find a way to hold tickets for some time, especially when they have been reserved, we use a ticket lock for this. When new users want to view the remaining tickets, we will fetch the tickets from our database, compare them to our ticket lock, remove the ones present in our ticket lock, and then send the remaining as available tickets. If the time of a ticket in the ticket lock expires, it is removed from the ticket lock, and the next time a ticket is viewed, it will be present as available. We can also create a WebSocket or Server-Sent Events (SSE) to inform users in real-time about the available tickets left, tickets booked, and the number remaining, all in real-time.

To protect our server and better balance the workloads on our servers and database during big occasions like Black Friday or, in our case, big events, we know that in such scenarios, our servers can easily be bombarded with requests, which can lead to catastrophe. To prevent this, we can set up a choke point between our API gateway and server. We use a queue like Redis sorted sets, where API requests are held and executed periodically. The requests are held, and let's say 100 are sent to our database at a time, and so forth. This helps reduce the write load on the database, thereby reducing the need for replication to handle this situation. Of course, this choke point should be admin-enabled for special occasions like big events; otherwise, it will just delay requests on a normal day.

Since reads are greater than writes, we can reduce the read load on our database by caching certain operations that rarely change, especially since event names, venues, and performers rarely change. It makes sense to cache reads on these in a Redis store and ensure the cache is invalidated or updated on changes to the event name, venue, or performer. By doing this, we significantly reduce the load on our database while making reads on event names, venues, and performers incredibly fast. These are the techniques and design patterns I take into account as a software developer when designing systems, especially distributed systems, to ensure openness, scalability, resiliency, fault tolerance, and high availability of resources.

In summary, designing a robust and scalable Ticket Booking Web Application involves addressing both functional and non-functional requirements through thoughtful architectural decisions. By integrating Elasticsearch, we achieve low-latency search capabilities, enabling rapid retrieval of event data even under heavy loads. The use of Change Data Capture (CDC) with Kafka ensures that our data remains consistent and available, even in the face of system failures, by capturing and streaming changes asynchronously to both the primary database and Elasticsearch.
To further enhance performance during high-traffic periods, such as major events or sales, deploying a Content Delivery Network (CDN) allows us to cache API responses, delivering them quickly to geographically proximate users. This approach significantly reduces server load and improves response times during surges.
For ticket booking, implementing ticket locks prevents double bookings by temporarily reserving tickets and updating availability in real-time. Additionally, by introducing server-side queuing, we can manage write operations more efficiently, preventing server overload during peak times. Caching frequently accessed data, like event details, in a Redis store further reduces the strain on our database, ensuring fast read operations.
These strategies collectively contribute to a system that is not only scalable and resilient but also capable of delivering a seamless and efficient user experience, even in the face of high demand and complex data requirements.