lsmgeb89

Latency Comparison Numbers (~2012)
----------------------------------
L1 cache reference                           0.5 ns
Branch mispredict                            5   ns
L2 cache reference                           7   ns                      14x L1 cache
Mutex lock/unlock                           25   ns
Main memory reference                      100   ns                      20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy             3,000   ns        3 us
Send 1K bytes over 1 Gbps network       10,000   ns       10 us
Read 4K randomly from SSD*             150,000   ns      150 us          ~1GB/sec SSD

lsmgeb89

/*
 * Description:
 * An alternating monotonic sequence (AMS) is a monotonically increasing sequence which alternates between even and odd numbers. For example, {7,12,13,22} is an AMS, but {7,12,14,21} is not (though it is a monotonic sequence). Describe a dynamic program for finding a longest alternating monotonic subsequence of a given sequence.
 *
 * Input:
 * There are several test cases! In each test case, the first line contains an integer N (0 <= N <= 10000000). N is the length of the sequence. The following lines contain N integers that represent the sequence.
 *
 * Output:
 * For each test case, output in two lines. Between each test case, you should ouput one blank line. The first line contains an integer M, which is the length of alternating monotonic sequence. The second lines contains M integers represent the AMS of the sequence.
 *