Algorithm On All nearest smaller values problem 1. Background 1.1 All nearest smaller values problem Given an array A[0..n-1], for each element in A, search among the previous positions for the nearest position that contains a smaller
Algorithm On a side-effect of Merge Sort The problem Given an array A, we call (i, j) an important reverse pair if i < j and A[i] > 2*A[j]. Count the number of important reverse pairs. For
CS Deep dive into letter I in ACID Meaning of Isolation in ACID Most databases are accessed by multiple clients at the same time, which could lead to race condition issues when 1 transaction (txn) reads data that is concurrently modified
System Design Cache is evil !!! (Part 2) Cache invalidation problems Let's take a look again at the write path of Look-Aside pattern: clear the cache for key k after update the database. Easy as cake. Not really ... When your app
System Design Cache is evil !!! (Part 1) Cache is considered as a great mechanism to increase performance in system design. However, it often comes with many critical problems such as inconsistency, the validity of data, cache delay... To make things
Quick note on Go memory model Single goroutine excution order The compiler and processors may reorder the read and write exectuted within a single goroutine only when the reordering does not change the behaviour within that goroutine as defined
Algorithm A note on Stream Sync - The protocol behind Dropbox's sync performance Introduction File hosting services like Dropbox/ Google Drive require ability to sync files fast between clients. One of the simple techniques is to break the file into multiple fixed-size blocks so - we
System Design Point-region QuadTree and applications to System design problems. Point-region QuadTree (PR Quadtree) Introduction A rooted tree in which every node has 4 children: each node corresponds to a square in the plane each child of a node corresponds to a quadrant
CS A note on Java Garbage Collection (GC) 1. Basic What is GC: a process that looks at Heap memory and identifies which objects are in use and which are not, and deleting the unused objects. Eligibility to be GC: objects
CS Rate limiter algorithms's consideration High level design of Rate LimiterRequirement Limit the number of requests a user can send to an API within a time window: n requests/minute. Window size = 1 minute. The APIs are accessible
Security A note on CSRF attack and JWT authentication Questions What is CSRF? How to prevent CSRF? Is Same-Site Cookie the silver bullet? What is JWT authentication? Is using JWT enough to prevent CSRF? What are the considerations when implementing JWT authentication?
CS A note on Distributed Id Generator Problem Generate unique Id in distributed environment: each node can generate unique Ids. Ids need to be sortable. Snowflake a service developed by Twitter for generating Id fulfilling above requirements Snowflake structure: 64
CS Cookie security 101 What is it? a piece of data stored in browser. can be set by: client: via Javascript. server: via HTTP response header. cookie is automatically passed to server in header of request. cookies
CS A note on Consistent Hashing Rehashing problem Hash function a function that maps data of arbitrary size to fixed-size values h: U → {0, 1, . . . , m − 1}. example: h(x) = x % m collision: k1 != k2 and h(k1) == h(
CS From RSA, Diffie Hellman to TLS protocol Background The questions I want to answer: How RSA and Diffie Hellman work? Pros and cons? How TLS handshake works? Why do we need both RSA and DP in TLS, when seem like
CS A note on B-Trees and database indexes (part 2) BTree and database indexes 1. How data is stored in hard disk? Modern hard disk drives are addressed as large one-dimensional arrays of logical blocks, where the logical block is the smallest unit
CS A note on B-Trees and database indexes (part 1) Introduction Recently, I have several questions about BTree and its application - database indexes: What is BTree? Kind of a cool name, huh? What special properties make we use BTree for database indexes?
CS Notes on RAFT Consensus Protocol (part 1) Introduction Consensus problem Given a distributed system such that: the network between nodes is unreliable (1) nodes can crash (2) there is only one leader node that client can communicate with. We want
DevOps My experience with CKAD Background Certified Kubernetes Application Developer - CKAD is an exam developed by The Linux Foundation f.t Cloud Native Computing Foundation to certify your knowledge of Kubernetes (k8s) as a developer. What I
Algorithm Revising Binary search via 4 interesting problems 1. Search in Rotated Sorted Array Let's formalize the problem: we need to find a number in array A[n]: A[0 .. i] is strictly increasing A[i+1 .. n-1] is strictly increasing
Algorithm A note on Detecting cycle - Floyd algorithm Problem Detect the cycle in a Linked list, return the starting Node of the cycle if any, otherwise return NULL. E.g: return Node 2 in following linked list: Algorithm Let fast and
Algorithm Graph Algorithms for Coding Interview Apart from the well-known BFS and DFS algorithms, I find the following algorithms useful for Coding Interview.Topology sort & circle check Given directed graph, sort the nodes in graph so that, if
Algorithm A note on an interesting technique: Range addition Assume you have an array of length n initialized with all 0's and are given k update operations. Each operation is represented as a triplet: [startIndex, endIndex, inc] which increments each element of
Algorithm LC 683: K Empty Slots https://leetcode.com/problems/k-empty-slots/Solution We can come up with a naive solution: let a is array store the state of bulks, a[i] = 1/0 ie bulk i is on/off
A note on problem's series in LeetCode In this note, I category problems in LeetCode into groups that can be solved by one common technique/ algorithm. By technique and algorithm, I mean a specific and particular method, not a common
