Rabin-Karp algorithm

Process and Thread

Inner Class

Topological sort is a way to sort a Directed Acyclic Graph (DAG) in the order based on all edge directions. For example, a graph below could be ordered in a way.

Minimum Spanning Tree of a graph has the following properties:

1. It has V-1 edges, and all Vertices are connected;
2. Add One edge could lead to a cycle in the tree;
3. The total weight of the MST is less than any other tree of the graph;

Shortest Path is a problem that people encounter almost every day. The basic problem statement is: Give a set of vertices and there distance or any measure (a graph), find the shortest path from one source to a target. There might be some variants, for example, to find the minimum cost along a path, but the basic principle and generate approach is the same.

MapReduce is a programming model for processing big data sets by parallel, distributed algorithm on a cluster. There are a few key words in the above description:

1. Big data sets: that means it is not possible processed by a single machine/host;
2. Parallel/distributed: that means a cluster of machine/hosts would process a set of data concurrently;
3. Programming model: this is a model for process different types of data.

This is a series of problems related to find the lowest common ancestor of binary tree. If the tree node has a pointer to its parent, then it is relatively easy to find the lowest common ancestor. But a tree has only left and right pointers to its subtree.

XOR Properties

XOR is a bitwise operation that has the following properties:

This type of problems require to find the maximum/minimum pair from a list or array of values with some conditions. It certainly could be solved by brutal force, but that is not an optimized solution. Swipe from both end of the list or array could help to speed up the process. The basic idea is to reuse the previous information to obtain the current minimum/maximum results. Similar to dynamic programing approach.

1. At current location \(i\), previous extreme value upto \(i-1\) is already known;
2. By adding \(ith\) element, how to update the extreme value?

This is an interesting problem that could be solved more efficient than thought.

This type of problem is different from the simple extreme value problems in two folds:

1. It need to be an extreme value;
2. It need to to satisfy a few other conditions. Simply sorting the array could give you extreme value overall but without satisfying the second conditions. One approach is to sort the array by the second condition and then by the extreme value.

Sweep line algorithm could be used to solve a number of geometric and interval problem. It normally involves two dimensional sorting. The general idea is to sort one dimension first, and sweep through that dimension to put the other dimension to a binary tree. The basic algorithm is:

1. Define Enterning and Leaving event respectively for each of the interval or geometry shape.
2. Sort all event by one coordinate (x or y).
3. Perform sweep, when an Entering event, put the shape (interval) to a binary tree to sort it.
4. When a Leaving event, remove the shape from the binary tree.

• LeetCode - 240

• LeetCode - 139

A number of substring problems could be solved by bit mask with conversion to similar as subarray sum problems. Basic subarray sum equals K could be soved by hashmap in O(n):

1. Store number of prefix sum in hashmap.
2. Get the number of current running sum - K.

Union find is a data structure that is like the name defined. Every node in union Find has a root or parent node. It could store the root or father of a node in a array with two operations, union() and find().

• Union: join two nodes together if they are connected;
• Find: find the father or root of a node.

There are a series of interesting subsequence related problems that shares some common approach to solve them. This is a summary of them and shall be updated continuously.

Problem Statement

Split array into some subarray with conditions. Examples:

Problem Statement

Problem Statement

In a batch process world, e.g., MapReducer, the data is bounded (i.e., of a known and finite size), so the processor knows when it has finished reading its input, and generates output from there. In reality, a lot of cases, data is stream and we don’t know when the data finishes, e.g., user login or logout. If we want to process these data, we have to process them as a stream (unbounded and incremented over time). Message System is designed to process stream data. The basic model is similary to below picture.

Problem Statement

Find the maximum subarray sum of a given array.

Problem Statement

Give an array and a sliding window size that moves from left to right, find the maximum value in the sliding window.

comming soon

comming soon

Functional requirements

1. User send source code and deployment request to server;
2. Server builds the source code to binary file;
3. Server deploys the binary file to other desitinations gloably.

Functional requirements

1. Client send a long URL, return a short URL to client;
2. Client send a short URL, return a long URL if it exist and redirect to the long URL, else return error code;
3. Client send a long URL, and a customized short URL, return short URL to client;
4. Client send a long URL, and set expiration time of the tiny URL;

SQL

Structured schema. Data is stored in rows and columns. Each record has fixed schema. Columns must designed before data entry. Alternating data structure involves modifying whole database. Uses SQL query. True ACID transaction. Vertical salable. Reasons for SQL: Ensure ACID compliance, such as Bank data; Data is structured and unchanging.

A technique to break up a big database into many smaller parts. Horizontal scaling means adding more machines, which is cheaper and more feasible. Vertical scaling means improves servers.

Cache is short term memory which has limited space but is faster. It is based on the principle that recently requested data is likely to be requested again. Cache could be added in almost every layer, but is often found nearest to the front end, e.g., browsers.

Function:

1. Distribute load to difference server. Could be in L4 and L7 layer, TCP/IP, HTTP, etc.
2. Check which server is available and redirect works.  ### Algorithms:
1. Round Robin
2. Round Robin with weighted server
3. Least connections
4. Least Response Time
5. Source IP Hash
6. URL hash ### Benefit:
1. prevent request goes to unhealthy server
2. prevent overloading server
3. eliminate single point of failure

The goal of replication is to provide high available and reliable services by store the same copy of data in a few of servers. However, it is always a challenge to maintain consistency of the data.

Comming soon

Comming soon

Problem statement

Find the kth smallest/largest element in an array.

Problem statement

Given a series of data representing the candidates that is voted. Find the candidate with majority votes. Majority means more than 50%. The data could be stream data.

Palindromic substring is a hot topic in string handling problem. A series of problems are related to palindromic string or substring.

This post is about a simple item(job) recommendation system that I’ve learned and coded recently. I am trying to expand it a little and therefore record the system design based on the tiny project.

Session based authentication

Two popular libraries to map JSON data with Java objects.

This post keeps updating as my learing going on.

Segment Tree is used for immutable range sum query and update.

This is a series of six problems in stock buy and sell. All of them could be solved by dynamic programming.

Lab 4B

Next permutation is a number arragement that generating a number only more than the current one. For example, for numbers 1, 2, 3, the combinations could be:

Monotonic stack is a stack that maintain the element in the stack with increasing or decreasing property, i.e., when poping element from the stack, the elements are in sorted order. This property itself seems useless, but it can be used to solve some of the problems in LeetCode.

Lab 4A build up a Shard Master System based on Raft.

Lab 3 build up a Key Value system based on Raft.

Lab 4B

Lab 2A need to code the reliable election process that you will make sure the system electect a leader even with network failure. The basic logic follows Figure 2 from the paper.