Given an array of numbers A, find out whether it contains a 1-3-2 pattern. A 1-3-2 pattern is a subsequence of three numbers, A[i], A[j] and A[k] such that i < j < k and A[i] < A[k] < A[j]. For clarity, let's call the 1-3-2 pattern the Bronze-Gold-Silver pattern. If A[j] is Gold, then we should consider the …

Read More

Tony Hoare invented QuickSort in 1961. At the time of its publication, the best comparison-based sorting algorithm was merge sort. Merge sort divides an unordered array into two equally sized subarrays, sorts each subarray, and then merge the two subarrays to produce a sorted array. Merge sort is simple to understand. …

Read More

Problem Given an integer array A, in one step, remove all elements A[i] where A[i-1] > A[i]. Return the number of steps performed until A becomes a non-decreasing array. See examples at LeetCode 2289. Solution The naive approach executes steps one by one. Store integers in a Linked List. At each step, find all …

Read More

In distributed systems, because there are too many requests to be handled by a single server reliably, requests are handled by a cluster of servers. In order to get high availability, the technique of distributing requests to servers needs to satisfy the following three requirements. Even distribution. Each backend …

Read More

A function is monotonic if it preserves the order of its arguments, i.e., if $x \le y$, then $f(x) \le f(y)$. In this post, we examine a class of problems where the argument is an interval. By identifying monotonic functions, we can reduce the number of intervals to enumerate by an order of magnitude, from $O(n^2)$ to …

Read More

Given an array of numbers $A$, for each number $A[i]$, find the largest subarray that contains $A[i]$ and $A[i]$ is the minimum of the subarray. For example, for $A=[2, 0, 3, 5, 1, 1, 0, 2 1]$, the largest subarray for $A[4]$ is $[3,5,1,1]$. Let's represent the subarray for $A[i]$ as the left boundary $l[i]$ and right …

Read More

Given two sorted arrays of integers, $A$ and $B$, find the $K$-th smallest integer from A and B in $O(\min(\log{N}, \log{M}))$ time. $N$ and $M$ are the size of $A$ and $B$ respectively. Without loss of generality, we can assume A and B are of the same length N. Because both A and B are sorted, we can merge A and B …

Read More

I implemented a job scheduler at work recently. Each job has a unique ID and an expiration time. The job ID is immutable while the expiration time may change. The job scheduler schedules the job of the earliest expiration time. Go comes with heap.Interface and map. My first implementation uses a hashmap and a slice …

Read More