Articles are paginated with only three posts here for example. You can set the number of entries to show on this page with the “pagination” setting in the config file.

Posts

# Tree longest path by dfs 2x

Definition of a tree (Taken from Wikipedia)
A tree is an undirected graph \(G\) that satisfies any of the following equivalent conditions:
\(G\) is connected and acyclic (contains no cycles).
\(G\) is acyclic, and a simple cycle is formed if any edge is added to \(G\).
\(G\) is connected, but would become disconnected if any single edge is removed from \(G\).
\(G\) is connected and the 3-vertex complete graph \(K_3\) is not a minor of \(G\).

Posts

# 1197. Minimum Knight Moves

It is easy see that if you start in a spot in the diagonal, you can get back to the diagonal in two moves. Say E-NE followed by N-NE, where I am using the the North, South, East and West conventions. Similarly for a knight at the x-axis you can get back to the x-axis with E-NE followed by E-SE.
Let’s take a look at the diagonal section of 4,4,4 (pink), since I can get back to the diagonal in two moves, the next section has 6,6,6 (beige).

Posts

# Tao

Aggregation difficulties content tailored to each user filter item with privacy checks for each user impossible to aggregate and filter when content is crated resolve data dependencies and privacy check each time content is viewed pull vs push social graph? extreme read demands on graph data store Memcache rapid deployment data mapping cache invalidation client code that is deployed frequently created abstractions for graphcs r/w objects (nodes) associations (edges) direct access to MySQL deprecated for graph data tyles Tao service implements objects and association model motivation encapsulating failures in the PHP API access graph easily from non-PHP serivces problems with lookaside cache architecture Inefficient edge lists KV cache is not good semantic fit for lists of edges queries must fetch the entire edge list list support would help make changes to single edge causes entire list to be reloaded requires coordination of incremental updates to cached lists Distributed control logic L-A $ control logic is run on clients clients don’t communicate with each other increases the number of failure modes difficult to avoid thundering herds Nishtala et al.

Posts

# Facebook - memcached

Requirements real-time aggregate dispersed data access hot set scale refs [1,2,5,6,12,14,34,36] Front-end cluster read heavy workload (100:1 R/W) wide fanout handle failures 10 Mops/s Q: what is a wide fanout
Multiple FE clusters single geo region control data replication data consistency 100 Mops/s Multiple regions muliple geo regions storage replication data consistency 1 Bops/s Pre-memcached High fanout data dependency graph for a small user request Look-aside cache why deletes over set

Posts

# FFT

polynomials \[ f(x) = A_0 + A_1 x + A_2 x^2 + \cdots + A_{n-1} x^{n-1} \]
roots \begin{eqnarray} x^{n} &=& 1 \\\
x &=& e^{i \frac{2\pi}{n}} \end{eqnarray}
Call \(e^{i \frac{2\pi}{n}} = w_n\) the fundamental, then there are \(n\) such roots, \(w_n^k\) for \(k = 0,\cdots,n-1\).
The fourier transform is a vector of the polynomial evaluated at each of the \(k\) roots.
\[ F(k) = f(w_n^k) \]
The FFT is a divide and conquer algorithm where instead of doing \(O(n)\) computations for each fourier coefficient \(F(k)\), we break up the problem into 2 subproblems of size \(n/2\) and do a merge which is of order \(n\).

Posts

# Errichto - segment tree

Segment tree Preliminaries The data structure in this segment tree information according to Antti Laaksonen in the Competitive Programmer’s Handbook comes from
[62] P. Stańczyk. Algorytmika praktyczna w konkursach Informatycznych, MSc thesis, University of Warsaw, 2006.
Basically the original range is stored at some offset that correspond to largest power of two that is greater or equal to the size of the range. For example a size 16 array would be stored at an offset of 16 in the array.

Posts

# Craq - Terrace and Freedman

questions what is the interface provided simple k,v store what are the guarantees discussed strong and eventual consistency chain replication where are requests handled? write at head read at tail what is the dotted line going back from tail to head reply to the “write” client - committed why is this cheaper than other topologies because of pipelining of the writes down the chain what consistency does CR achieve?

Posts

# USACO Jan 2020 Bronze - Race

\(O(1)\) solution I am surprised that the solution posted is \(O(n)\) since \(n\) can be as large as \(10^9\).
In coming up with a solution for \(O(1)\) we consider three phases. The first phase accelerates the ‘left hand’ speed until it reaches the terminal speed. If it can’t reach the terminal speed then it just reaches whatever speed it can and terminates.
The second phase is like a palindrome stage, where I remove similar increasing speeds from both ends, kind of like climbing up a tall peak from both ends.

Posts

# Minimax - alpha beta pruning

Mnemoic Minimax, alpha beta. Min comes before Max, alpha comes before beta. Minimizer uses alpha, maximizer uses beta.
Pruning alpha is passed from maximizer to minimizer. maximizer says, beat a score of 10 (it wants something greater). minimizer gets one score of 8. minimizer stops because it can’t get above 8, it is a minimizer after all so exploration will only reduce this score, and it will not be useful by the maximizer.

Posts

# Appscript - Sheets

Getting started Appscript is pretty powerful and free, it is javascript with google api for manipulating things.
Begin with a sheets document. Open tools/script editor Write in Code.gs Rename to some Run with the triangle button Ctrl + Enter to see the Log Save it Since most of the time I am operating on some selected range, you would first select on some cells before running the script.