Tradeoffs in messaging oriented architectures

Messaging systems are a very important component of the data pipeline in any large scale system.   Consider a simple web application that serves all its requests online (ie directly from the source of truth data store without any preprocessing or offline index generation):


Pretty soon as load increases and horizontal scaling schemes (partitioning, replication, LB etc) have been exhausted strict consistency has to be relaxed by separating the read and write paths, which necessitates the employment of message passing (or event dispatching) across the differents components (services) in your ecosystem, resulting in (a broader version of) the following (each tier is actually Load Balanced in a cluster for high availability):screen-shot-2016-12-10-at-2-56-51-pm

Message passing in a service-oriented architecture (SOA) is very critical for scalability and availability (from enabling eventual consistency to offline processing and analytics to buffering of event firehoses and so on).   In the simplest and most abstract term, message passing can be just thought of as firing off events (user action, metrics, errors, conditions, sensor data, stock prices etc) for asynchronous consumption and processing by one or more consumers depending on application needs.    Several systems enable messaging, eg Kafka, Google PubSub, Amazon SQS, RabbitMQ, ZeroMQ, and others.  While the overarching goal is asynchronous message delivery and consumption, these systems vary greatly on delivery semantics, persistence, ordering, access pattern optimization and so on.

Delivery Semantics

When messages are sent/fired, their delivery is never guaranteed in a distributed system (due to failures, corruption, unbounded network partitions etc).   At the highest level there are 3 delivery guarantees:

  1. exactly-once – Messages are delivered exactly once, processed exactly once and “verified/acknowledged” exactly once despite the level of resiliency in a system in a scalable and cost-efficient manner.  In practice, this requires a lot of application of idempotency constraints/tricks and expensive infrastructure and coordination.
  2. at-most-once: Messages are delivered, processed, verified at most once (including never).   Unfortunately if an acknowledgment is never received by the event processor or the receiver terminated during the processing the message is lost with no traces of its status.
  3. at-least-once: Messages can be delivered repeated until a successful verification – by far the simplest guarantee to provide.

Most systems provide at-least-once guarantee, and really, it takes us a very long way.   By easing the strictness of these guarantees, implementation costs are lowered and other semantics can be built *on top* of this.  A simple and widespread of this in practise is TCP/IP which provides ordering and reliability by building on top of IP (which is unreliable and unordered).

Persistence/Durability and Consumer state

Persistence and durability of messages affect delivery and processing requirements for consumers.   This is a major tradeoff between write-only queues and message brokers.  For example write-only queues like Kafka (and Amazon Kinesis and IBM MessageHub and others) are extremely producer/publisher-centric in that messages are published (reliably and ordered) at very high rates, but ultimately it is up-to the design of the consumers (in the architecture) to ensure a meaningful processing of messages and offset advancements in the message logs/queues.  ie Messages write scaling is independent of the number (or online/offline state) of consumers.  Adversely, higher durability and persistence guarantees are required since messages may be consumed offline at a different time to when the messages were actually published (which puts an upward pressure on write latencies).

In comparison typical message brokers (like RabbitMQ and *MQ) are great for enabling complicated topic and routing strategies but come at expense of state management across the consumers (by the broker).   Additionally depending on persistence configurations, the extra cost of state management affects how inexpensively writes can be scaled (hint: it is expensive) so are suited for cases with low write rates and suited more for “online” consumers rather than offline consumption and processing of messages.   If the requirement for asynchronicity is for online consumers for immediate consumption of messages then persistence constraints can be relaxed as the need and significance of “historical” messages may be low (eg in online learning systems).

Interface to a messaging system

Despite the fact that a messaging system is essentially an abstraction for storing messages for asynchronous consumption, the tradeoffs above influence different usage scenarios.   It so happens that building on top of a simpler abstraction (like a high throughput durable ordered queue) can lead to interesting routing strategies and workflows like those possible by a more complicated message broker.   What this boils down is to let the topology of consumers (and subsequent publishers) guide your guarantees at different parts of the system which requires more fine tunning and manual approach in topology selection and design.   There are ways to build this in a more reasoned approach, which is the topic of another blog (Spoiler Alert – Stream Processing).



Machine learning @ Coursera

[TL;DR;] Machine learning is not as hard as I imagined and is a great/fun toolset to learn and Andrew Ng’s course on Coursera is the best place to start!

There is something about darkness, that brings to life all our fears. It is tempting to say this (illogical manifestation of fears) only occurs during our childhood. The slightest rattles in the attick or the creaks on the floor board is enough to unlock your wildest and horrific imaginations of perhaps the bogeyman hiding under your bed or the *monster* lurking outside your house waiting to pounce on you (something I am still terrified of as I put the garbage bins on collection night).

*But*, shine a light on the darkness the next morning and your fears vanish! The strange, seemingly inexplicable noises and phenomena you observed earlier seem absurd suddenly can be explained (racoons the roof causing the rattle, somebody walking down the kitchen to get a drink, etc).

As strange as this may seem, this fear of darkness and all that lies within is rooted in our prehistoric past.   Wierdly and worse annoyingly this fear transcends the realm of darkness and caves into our modern daily lives plainly, simply and even boringly as the FEAR OF THE UNKNOWN.

For me that fear for years has been Machine Learning.   Actually, it was a combination of fear, laziness and simply brushing off ML as simply statistics and a whole lot of heuristics.   The long thanksgiving weekend was upon me and I really really really wanted to try something different and “new”.   A lunch with a machine learning expert-colleague-friend somehow got me curious to give it a shot.  And since not a day goes by when you dont hear how awesome Andrew Ng is in the field, his ML course on Coursera seemed like the most natural place to start!

Beset by notions of the course being heavy on statistics, I’d be lying if proclaimed my eagerness to it.   However, I was curious to see what the fuss was about!   It seemed every developer, her gardener and his dog were using ML for *something*, so it could’nt really be as fearsome as I had made it to be?

You see where this is going dont you?   Like a true [hb]ollywood flick this has all the promise of taking a carefree ladies man relinquishing his bachelor lifestyle when he falls for “the one”!   Well ok let us not kid ourselves.    This is real life, not bollywood!    More like man learns to appreciate friends he seldom focussed on… or better yet hardworking family man learns to appreciate all the things his partner does for him!

Firstly on ML itself.   It is surprisingly not as heavy on statistics on I had feared.   On the contrary it is pleasantly focussed on linear algebra and from what my limited experience has shown me takes the concept of linear regression to devastating effect.   As scary as that sounds this is actually the most fun part of ML (apart from the large scale infra side of things).   Knowing this 10 years ago would have exponentially altered my life, but better than knowing this *in* 10 years time!

Secondly the course is a testament to the hardwork Andrew Ng has put in personally not only in the study of the field, but also in improving himself as a presenter.   He has clearly taken a topic that has great scope and distilled it in a clear and structured manner.   It is almost as if he has a knack for predicting the kind of questions you would have about a topic and would proceed to address it immediately.   Each lesson builds on the previous chapters and is actually very easy to follow.   Even the math is layered in such a way that the reader can take as much as they would like and go as deeply as they would want without it being a hurdle to proceed (for example the derivation of cost and gradient functions while not explained are extremely fun exercises that you should try out – coming in another blog).

Finally the choice of language.   At first being faced with Octave incited the same gasp that would be incited in any self respective developer.  But not having to implement numeric computing routines (and optimising it) is a huge blessing!    Even for an Octave/Matlab newbie (atleast not having used it for 20 years) the language and environment were painless to get (back) into.

There *are*  a couple of ways the course may have been improved.   Firstly the language.  While Octave was a pretty appropriate environment for this exercise, I am not sure the same could not have been achieved with NumPy/SciPy or in other “popular” languages.   This is not a big deal, just putting it out there.   Definitely gives me a chance to try to implement a lot of the algorithms in another language like Haskell or Swift!   And by the way if I had to *really* pick on two things about Octave – it would, oh:

  1. A lack of a good debugger.  The only way to set breakpoints it seems is via a dbstop function which is extremely unintuitive.  How about a pythonesque “break” or “set_trace” statement?
  2. This was a major annoyance for me.   1-based indexing.   This is fine when your equations actually all refer to and start with “1”.  But when you infact introduce a 0th term, just the cognitive load of translating between the indexes added a good 30% to my assignment times!

Then there were the quizzes.  Personally I am not a fan of “Exam” type assessments.   I could do assignments/projects all day!   Even within the quizzes, the numerical ones I loved as I knew how to apply the formulas I had learnt, but the ones requiring a more analysis with respect to the wording, I personally felt a bit not so much at ease with.   My OCD mind always tries to end up dissecting the hidden meaning behind how questions are worded and end up making wrong assumptions.

But overall a very effective and awesome course in teaching the concepts of ML whether you are an experienced developer or a mathematician.    Definitely recommend it (if there is still anybody out there who hasnt done the course yet!).

Design of an equation editor

Each time I buy a new laptop, I usually copy and backup the contents of my old laptop and it just keeps accumulating.   I was just taking a trip down memory lane and stumbled upon some really old code I had written (about 16 years old to be precise – here at github now). You know the code is *really* old as it is a collection of applets (yep java applets).   One thing that really caught my attention was an equation editor I wrote back then (you can get it up and running from the repo, but here is a screenshot of it):


I am still surprised it actually worked as well as it did back then given howcertifiably little I knew.

And given that I wanted blog a few of my learnings from my first machine learning course not having an easy way to do equations on wordpress (short of taking screenshots of rendered latex) rekindled my interest in an equation editor again (for the modern web?).   So In the coming posts Il go through the design of a system that allows one to easily author and host equations (and math) for the web without having to a) create multiple copies or b) copy and paste from different rendered outputs.

Our math editor must have the following essential “features”:

  1. Perform as much as possible with the keyboard (ie latex style) without having to insert a symbol by clicking at some icon (see above screenshot).
  2. No “rendering” step ie any output must be directly reflected in the editor area so that the author can see the result live in the one place as they are typing the equations/math.
  3. Allow for both short snippets of math as well as reasonably sized proofs that can span paragraphs.
  4. Hosting, sharing and privacy controls.
  5. Renderable as an image in any blogging platform without requiring plugins to be installed.
  6. Customizable templates (ie new summation templates etc) in a secure manner.

That seems like a reasonable starting point.   In the next blog, Il go into a bit more detail into a possible API/data model for our content model looks like.   It is worth noting that a lot of this will build on top of existing awesome tools like latex and MathML.


A libev tutorial and wrapper

I’ve been asked to help people out with libev example code and usage for a while but I never got around to it since I hadnt used libev in ages.  However I have a need for a simple server framework (more on this in another post).   So I figured I’d publish a simple libev tutorial.  More importantly I will create a C library that is a wrapper on top of libev to handle and maintain multiple connections in a clean and extendible way.

A quick introduction to libev is in order.  Back in the day, handling multiple network client connections was either done using multiple threads (one thread per connuction) or via asynchronous apis that multiplexed between several io events across the various connections.  Several APIs existed to enable the later (select/poll, epoll, kqueue etc).  Each of the methods had their own performance guarantees and worse still had platform dependant compatibility issues.  To get around this libevent was developed to provide a uniform interface hiding platform specific details.  Libev developed later was designed to simplify and cleanup several aspects of libevent (eg stripped down, threadsafe, low watcher overhead etc).

The core concept in libev is that of an event loop – a loop that runs continuously listening registered events and calling the associated callback functions.   Events could be io events like file descriptors ready for reads/writes, socket connections accepted etc.

With that it is time to dive in.

Let us first start with a socket server structure that is the context for all things related to a multi client TCP server:

struct LEWSocketServer {
    // A pointer to the event loop that is handling event on 
    // this server socket.
    struct ev_loop *eventLoop;

    // Host the server socket is bound to (not used for now)
    char *host;

    // Port the server is running on
    int port;

    // The socket associated with the server.
    int serverSocket;
    struct ev_io acceptWatcher;

    // A listener structure for events on this socket.
    LEWSocketServerListener *listener;

A simple server socket API would begin with being able to start a server:

SSSocketServer *ss_start_server(const char *host, 
                                int port,
                                SSSocketServerListener *listener);

SSSocketServerListener is a structure that helps clients manage the callbacks associated with the individual connections instead of having to deal directly with the libev api.

typedef struct LEWSocketServerListener {
     * Called when a connection was accepted.  This is an opportunity
     * for the handler of this method to create any connection specific data
     * to be created and returned so that any further activities on the connection
     * will be invoked on this object.
     * This method must NOT return NULL.  If it returns NULL, then the connection is refused.
    void *(*createConnectionContext)();

     * Called when data has been received for this connection from a client.
    void (*processData)(LEWConnection *connection, const char *data, size_t length);

     * Called to indicate connection was closed.
    void (*connectionClosed)(LEWConnection *connection);

     * Called to ask the connection handler for data that can be written.
     * The buffer is an output parameters to be updated by the listener.
     * Return the number of bytes available in the buffer.
    size_t (*writeDataRequested)(LEWConnection *connection, const char **buffer);

     * Called to indicate that nWritten bytes of data has been written and that the connection
     * object should update its write buffers to discard this data.
    void (*dataWritten)(LEWConnection *connection, size_t nWritten);
} LEWSocketServerListener;

The general structure of a connection follows:

  1. Server socket is in listen state
  2. When a new connection is accepted, a client socket is created and added libev’s eventloop for read events.
  3. write events for the client socket are not enabled. The level-triggered nature of libev (by default) will cause unnecessary write event callbacks even when there is no data to be sent. So a design choice made was to make the api caller responsible to initiate writes when it had data to be sent.
  4. When data is available to be read, it is sent via the listener’s processData callback (along with the connection object associated with the client).
  5. When the caller has data to write it invokes the connection’s writeable attribute.
  6. When the writeable attribute on a connection is set, the write events on the client socket are enabled which invokes the writeDataRequested method on the caller until it return 0 (bytes).
  7. Additionally the library calls the dataWritten callback on the listener so that the client can update its own write data buffers (to pop off the written/sent data).

With this the echo server now looks like:

#include "server.h"

typedef struct EchoConnection {
    char readBuffer[4096];
    int length;
} EchoConnection;

 * Called when a connection was accepted.  This is an opportunity
 * for the handler of this method to create any connection specific data
 * to be created and returned so that any further activities on the connection
 * will be invoked on this object.
 * This method must NOT return NULL.  If it returns NULL, then the connection is refused.
void *createConnectionContextCallback()
    EchoConnection *out = calloc(1, sizeof(EchoConnection));
    return out;

 * Called when data has been received for this connection from a client.
void processDataCallback(LEWConnection *connection, const char *data, size_t length)
    EchoConnection *echoconn = (EchoConnection *)lew_connection_get_context(connection);
    memcpy(echoconn->readBuffer, data, length);
    echoconn->length = length;

 * Called to indicate connection was closed.
void connectionClosedCallback(LEWConnection *connection)
    printf("Connection closed...\n");

 * Called to ask the connection handler for data that can be written.
 * The buffer is an output parameters to be updated by the listener.
 * Return the number of bytes available in the buffer.
size_t writeDataRequestedCallback(LEWConnection *connection, const char **buffer)
    printf("Write data requested...\n");
    EchoConnection *echoconn = (EchoConnection *)lew_connection_get_context(connection);
    *buffer = echoconn->readBuffer;
    return echoconn->length;

 * Called to indicate that nWritten bytes of data has been written and that the connection
 * object should update its write buffers to discard this data.
void dataWrittenCallback(LEWConnection *connection, size_t nWritten)
    EchoConnection *echoconn = (EchoConnection *)lew_connection_get_context(connection);
    echoconn->length -= nWritten;

int main(void)
    LEWSocketServerListener listener;
    listener.createConnectionContext = createConnectionContextCallback;
    listener.processData = processDataCallback;
    listener.connectionClosed = connectionClosedCallback;
    listener.writeDataRequested = writeDataRequestedCallback;
    listener.dataWritten = dataWrittenCallback;

    lew_start_server(NULL, 9999, &listener);

While there is still some work to be done to handle edge cases this would be relegated to the library rather than leaking out to the client code and most the client code is actually to do with connection logic rather than messing about with event loops.

Full source code is available at:

Elements of Programming Interviews

This is an index to the problems from THE book being solved in haskell (and counting). Some of the trivial ones will only be attempted on demand!

Chapter 5 – Primitive Types

EPI 5.1: Find the number of bits set in a number (and Parity)

EPI 5.4: Closest integers with the same weight

EPI 5.5 – Generating Power Sets

EPI 5.6 String to Integer inter conversion functions

EPI 5.7 – Generalised conversion between bases

EPI 5.8 – Spreadsheet Column Encoding

EPI 5.9 – Elias encoding and decoding

EPI 5.10 – Greatest Common Divisor

Chapter 6 – Strings and Arrays

EPI 6.1 Dutch Flag Partition

EPI 6.3 – Max Difference

EPI 6.4 – Generalized Max Difference

EPI 6.5 – Subset summing to 0 mod n

EPI 6.6 – Longest contiguous increasing subarray

EPI 6.13 – Rotating an array

EPI 6.15 – Printing a 2D array in spiral order

EPI 6.18 – Run-Length Encoding

EPI 6.19 – Reversing words in a string

EPI 6.15 – Printing a 2D array in spiral order


Given an nxm 2D array of integers, print it in spiral order.

Eg for a 3×3 matrix (with the following implicit values):

1 2 3
4 5 6
7 8 9

Would be printed as “1 2 3 6 9 8 7 4 5”


The straight forward solution is to have 4 iterations, and in each iteration to print one of the two directions (horizontal and vertical) alternatively.

However a more intuitive solution is to use vectors to create a tour starting from the index (0,0) and incrementing the next point based on the current direction and position.

First we create the concept of directions along with a couple of helper functions:

data Direction = North | East | South | West
-- Return the clockwise direction of a given direction
clockwise_of North = East
clockwise_of East = South
clockwise_of South = West
clockwise_of West = North

-- Returns the vector representing the direction
vector_of North = (0, -1)
vector_of South = (0, 1)
vector_of East = (1, 0)
vector_of West = (-1, 0)

-- The primary coordinate that will be updated when traversing in a particular direction
primary_coord North = 1
primary_coord South = 1
primary_coord East = 0
primary_coord West = 0

-- Given a direction and point, returns the next and previous points in the direction.
next_pt dir (x,y) = ((x + fst (vector_of dir)),(y + snd (vector_of dir)))
prev_pt dir (x,y) = ((x - fst (vector_of dir)),(y - snd (vector_of dir)))

Now we simply use the above helpers to start and iterate through a tour:

print_spirally width height = print_spirally' East (0,0) 0 [width, height]
        print_spirally' dir (x,y) t [w,h]
            | w == 0 || h == 0 = []
            | t < [w,h] !! curr_coord = (y * width + x + 1) : print_spirally' dir (next_pt dir (x,y)) (t+1) [w,h]
            | otherwise = print_spirally' next_dir (next_pt next_dir (prev_pt dir (x,y))) 0 [next_w,next_h]
                curr_coord = primary_coord dir
                dir_vector = vector_of dir
                next_dir = clockwise_of dir
                next_dir_vector = vector_of next_dir
                next_w = w - (abs (fst next_dir_vector))
                next_h = h - (abs (snd next_dir_vector))

Couple of things to note:

* w,h represent the “remaining” width and height in the spiral as each time there is a change in direction, the available coordinate size reduces by one (height if beginning vertically, width if beginning horizontally).
* t is the number of values printed in a given direction (when this value reaches “w” or “h” depending on the direction, direction is rotated and t is reset to 0).
* When the direction needs to change (in the otherwise) the “current” point is one beyond the last point in the direction. For this reason the next point is evaluted from the previous direction in the previous point.

EPI 6.13 – Rotate an array


Given an Array of n elements, design an algorithm for rotating an Array right by i positions. Only O(1) additional storage is allowed.


The natural solution is to start from position the value at index k to k + i, repeatedly n times. This will work well if GCD(n,i) is != 1. However a general solution is to perform m jumps of size i, l times, but each time starting from the next index.

The first helper function is to perform m jumps of “size” each starting from a given index, wrapping around if necessary. For example if A = [1,2,3,4,5,6,7,8,9,10],

m_rotations A 0 3 3

would cause the following jumps: 1 -> 4 -> 7, with A resulting in:

[1, 2, 3, 1, 5, 6, 4, 8, 9, 10]
m_rotations xs index size m = elems (m_rotations' (arrayFromList xs 0) index (xs!!index) size m)
        len = length xs
        m_rotations' arr curr_index curr_value size numleft 
            | curr_index < 0 || size <= 0 || numleft <= 0 = arr
            | otherwise = m_rotations' (arr // [(next_index, curr_value)]) next_index next_value size (numleft - 1)
                next_index = mod (curr_index + size) len
                next_value = arr!next_index

Now we create the actual rotator method that calls m_rotations k times, where k = gcd(|A|, j).

This is:

rotate_array xs j = rotate_array' xs 0
        lxs = length xs
        j' = mod j lxs
        gcd_lxs_j = greatest_common_divisor lxs j'
        numtimes = div lxs gcd_lxs_j
        rotate_array' xs start_index
            | start_index >= gcd_lxs_j = xs
            | otherwise = m_rotations ys (j' - (start_index + 1)) j' numtimes
                ys = rotate_array' xs (start_index + 1)

A simpler algorithm to perform this is very similar to reversing words in a sentence:

rotate_array_simple xs j = reverse (take j rxs) ++ reverse (drop j rxs) 
        where rxs = reverse xs

EPI 6.5 – Subset summing to 0 mod n


Given an array A, a subset of S (i0, i1, i2… ik) of A such that Sum(S) mod n = 0. This is the 0 mod n subset problem.  Find this subset.


The general case of 0 mod k is NP complete however 0 mod n can be computed efficiently O(n) time and O(n) space.  Also in the case of n, there is always guaranteed to be a solution as seen below.

First create the array mod_till_k such that

mod_till_k[i] = Sum(A[0] .. A[i]) mod n

This is implemented below:

mod_till_k :: [Integer] -> [Integer]
mod_till_k xs = mod_till_k' 0 xs
        n = length xs
        mod_till_k' :: Integer -> [Integer] -> [Integer]
        mod_till_k' _ [] = []
        mod_till_k' prev (x:xs) = curr : (mod_till_k' curr xs)
            where curr = mod (x + prev) (toInteger n)

Now if mod_till_k[x] == 0, then the subset [0,x] is a solution.
If there no x such that mod_till_k[x] == 0, then there WILL exist some a < b such that mod_till_k[a] == mod_till_k[b]. In this case the solution is [a + 1,b]

This search can done linearly with.

zero_mod_n_subset :: [Integer] -> (Integer, Integer)
zero_mod_n_subset xs = zero_mod_n_subset' 0 index_table (mod_till_k xs)
        n = length xs
        index_table = array (0, toInteger (n - 1)) [(toInteger i, -1) | i <- [0..n - 1]]
        zero_mod_n_subset' i index_table (x:xs)
            | x == 0 = (0,i)
            | index_table!x /= -1 = (index_table!x,i)
            | otherwise = zero_mod_n_subset' (i + 1) (index_table // [(toInteger x,toInteger i)]) xs

Here index_table, which is initialised to -1, keeps track of previous positions where a particular mod was last seen.

EPI 6.4 – Generalized Max DIfference

Following on from EPI 6.3, we have three generalized versions of max difference:

Problem 1. Compute the maximum value of (A[j0] – A[i0]) + (A[j1] – A[i1]) such that i0 < j0 < i1 < j1.

The simple solution is O(n^4), by iterating all combinations of i0, j0, ii1 and ji1.

This could be improved to be O(n^2) by applying the O(n) solution to each entry in the array.

A O(n) solution with O(n) space is to compute the best solution in the forward and reverse directions (similar to max_increase_from_index in EPI 6.3) and use the two values on conjunction.  This is:

max_increase_forward :: (Num a, Ord a) => [a] -> [(Integer, a, a)]
max_increase_forward [] = []
max_increase_forward (x:xs) = max_increase_forward' 0 (0,x) (x:xs)
        max_increase_forward' i curr_max [] = []
        max_increase_forward' i (j,aj) (x:xs)
            | x >= aj = (j,aj,x - aj) : (max_increase_forward' (i + 1) (j,aj) xs)
            | otherwise = (i,x,0) : (max_increase_forward' (i + 1) (i,x) xs)

max_increase_backward :: (Num a, Ord a) => [a] -> [(Integer, a, a)]
max_increase_backward xs = max_increase_backward' 0 xs
max_increase_backward' i [] = []
max_increase_backward' i [x] = [(i,x,0)]
max_increase_backward' i (x:xs)
    | x <= aj = (j,aj,aj - x) : rest
    | otherwise = (i,x,0) : rest
        rest = max_increase_backward' (i + 1) xs
        (j,aj,diff) = head rest

Now it is a matter of iterating the two results to find the maximum – done in O(n):

max_increase_k2 :: (Num a, Ord a) => [a] -> a
max_increase_k2 xs = maximumBy compare (max_increase_k2_iter fs rs)
        fs = drop 1 (take (length xs - 1) (max_increase_forward xs))
        rs = drop 2 (max_increase_backward xs)
        max_increase_k2_iter [] [] = []
        max_increase_k2_iter ((a1,a2,a3):fs) ((b1,b2,b3):rs) = (a3 + b3) : (max_increase_k2_iter fs rs)

Problem 2. Compute maximum value of Sum(A[jt] – A[it]) for t = 0 -> k-1, such that i0 < j0 < i1 < j1 < … ik – 1 < jk – 1, for a fixed k.


Problem 3. Repeat (3) where k is any value between 0 and floor(n / 2).


EPI 6.3 – Max Difference

A robot needs to travel along a path that includes several ascents and descents.  As it at ascends, it uses up energy stored in its battery.  As it descends it converts the potential energy to charge the battery.  Assume the conversion is perfect (ie descending X units restores as much as energy as was expended in an ascent of X units).  Also assume that the “distance” travelled is irrelevant and only the height determines the energy lost and gained.


Given a set of 3 dimensional coordinates which plot the ascents and descents during a robot’s path, compute the minimum battery capacity required.


The O(n^2) solution (for each index find the maximum “increase” is going forward and then find the index with the maximum increase) is:

third (a,b,c) = c

max_diff_nsquared xs = maximumBy (comparing third) 
                        [(i,j,xj - xi) | (i,xi) <- zip [0.. length xs - 1] xs, 
                                         (j,xj) <- zip [0.. length xs - 1] xs, i < j]

In the naive method, finding the maximum increase at an index is O(n^2). This can be brought down to a linear algorithm with O(n) space:

max_increase_from_index :: [Int] -> [(Int,Int)]
max_increase_from_index [] = []
max_increase_from_index (x:[]) = [(0,x)]
max_increase_from_index (x:xs)
    | x <= aj = (j,aj):max_inc_from_next
    | otherwise = (length max_inc_from_next, x) : max_inc_from_next
        max_inc_from_next = max_increase_from_index xs
        (j, aj) = head max_inc_from_next

This would return a list of triples (j,A[j]) such that for each index i. Note that the indexes of j will be in “reverse”.

To get the best i, j such that i < j and A[j] – A[i] is maximised:

lxs = length xs - 1
maximumBy (comparing third) [(i,lxs - j,aj-ai) | (i,ai,(j,aj))<- zip3 [0..((length ms) - 1)] ms ms2]

Giving the final solution of:

minimum_robot_battery :: [(Int,Int,Int)] -> (Int,Int,Int)
minimum_robot_battery xs = maximumBy (comparing third) [(i,lxs - j,aj-ai) | 
                            (i,ai,(j,aj)) <- zip3 [0..((length ms) - 1)] ms ms2]
        ms = map third xs
        ms2 = max_increase_from_index ms
        lxs = length xs - 1

Note that we dont actually have to compute the array of differences. We could have simply also passed and maintained in a “curr_max” variable which would have stored have returned the max difference at the completion of the call.

EPI 5.9 – Elias encoding and decoding


Elias encoded version of an integer X = X in binary PREPENDED by number of zeroes in the binary representation minus 1.

So Elias of encoding of 13 (binary = 1101) would be 000 1101 (3 zeroes as length of 1101 = 4).


elias_encode_int :: Int -> [Char]
elias_encode_int x = (take (len - 1) (repeat '0')) ++ xbase2
        xbase2  = intToString 2 x
        len     = (length xbase2)

elias_decode_str :: Int -> [Char] -> Int
elias_decode_str size xs = stringToInt 2 (take size xs)

elias_encode :: [Int] -> [Char]
elias_encode xs = concat (map elias_encode_int xs)

elias_decode_helper :: Int -> [Char] -> [Int]
elias_decode_helper  nzeroes [] = []
elias_decode_helper  nzeroes (f:fs)
        | f == '0' = elias_decode_helper  (1 + nzeroes) fs
        | otherwise = (elias_decode_str (1 + nzeroes) (f:fs)) : (elias_decode_helper  0 (drop nzeroes fs))

elias_decode = elias_decode_helper 0

EPI 5.8 – Spreadsheet Column Encoding


Write a function that converts excel column IDs to corresponding integers with “A” corresponding to 1 and so on.


We will modify the solution in EPI 5.6 slightly so that we have:

indexOf :: Eq a => a -> [a] -> Int
indexOf item xs
    | length firstMatched == 0 = -1
    | otherwise = fst (head firstMatched)
        matchesItem x = snd x /= item
        firstMatched = dropWhile matchesItem 
                        (zip [0 .. (length xs) - 1] xs)
digitIndices :: [Char] -> [Int]
digitIndices digits = [ indexOf (chr i) digits | i <- [0 .. 255]]
spreadsheet_column_encoding :: [Char] -> [Int]
spreadsheet_column_encoding xs = 
        sum [ digit_to_value digit pos | (pos, digit) <- dig_positions xs]
        reverse_indexes xs = [(length xs) - 1, (length xs) - 2 .. 0]
        dig_positions xs = zip  (reverse_indexes xs) xs
        symbols = ['A' .. 'Z']
        ourIndexes = digitIndices symbols
        digit_to_value digit pos = (1 + (ourIndexes !! (ord digit))) * 
                                    floor (26 ** fromIntegral pos)

EPI 5.7 – Generalised conversion between bases


Continuing on from EPI 5.6, this problem is to convert an integer encoded as S1 in base b1, to S2 in base b2:


The easiest way is to use the techniques in EPI 5.6 and simply do:

 base1ToBase2 b1 s1 b2 = intToString b2 (stringToInt b1 s1)

Anybody looking for a version without the intermediate conversion to base 10?

EPI 5.6 String to Integer inter conversion functions


Implement the following methods, which convert (signed) integers to a string and vice versa respectively:

intToString x :: Int -> [Char]

stringToInt :: [Char] -> Int

Additionally invalid strings (when converting to Int) must return an error of some sort.


Even though the question was specific to converting to and from base 10, this can be generalised to any base with *very* little changes.  The straightforward solution is:

intToString :: Int -> Int -> [Char]
intToString base x 
            | x < 0 = "-" ++ intToString base (-x)
            | x < base = [intToDigit x]
            | otherwise = (intToString base (div x base)) ++ [intToDigit (mod x base)]

stringToInt :: Int -> [Char] -> Int
stringToInt base (x:xs)
            | x == '-' = - (stringIntHelper base xs)
            | otherwise = stringIntHelper base (x:xs)
            where stringIntHelper base (x:xs)
                    | dx >= base = error ("Invalid digit: " ++ [x])
                    | length xs == 0 = digitToInt x
                    | otherwise = (dx * (floor (fromIntegral base ** fromIntegral digitsLeft))) + (stringIntHelper base xs)
                        digitsLeft = (length xs)
                        dx = digitToInt x

Here is an alternative and more intuitive version of stringToIntHelper above:

stringToIntHelper2 base xs = 
            sum [ digit_to_value digit position |
                (position, digit) <- (zip dig_positions xs)]
        dig_positions = [(length xs) - 1, (length xs) - 2 .. 0]
        digit_to_value digit position = (digitToInt digit) * 
                            floor (base ** fromIntegral position)

This version does not check if each digit is between 0 and “base” but that is a trivial check to add via a “any” check in the original input (xs).

EPI 5.5 – Generating Power Sets


The power set of an alphabet set, S is the list of all strings (of any lengths) that can be formed from the symbols in S.  There can be no repetitions however with respect to character swaps within the string.

For instance, for S = “ABC”, one possible power set is:

“”, “A”, “B”, “C”, “AB”, “AC”, “BC”, “ABC”


The simplest way to think about this as iterating through the numbers 0 to 2^|S|, where each bit in the integer represents whether the alphabet at that index in the set, S is present in the output.  So a solution for this is:

import Data.Bits

lowest_set_bit :: Int -> Int
lowest_set_bit x = x .&. complement (x - 1)

lowest_set_bit_index :: Int -> Int
lowest_set_bit_index x = floor (logBase (fromIntegral 2) (fromIntegral (lowest_set_bit x)))

set_bit_positions :: Int -> [Int]
set_bit_positions 0 = []
set_bit_positions x = (lowest_set_bit_index x) : (set_bit_positions (clear_lowest_set_bit x))

power_set :: [Char] -> [[Char]]
power_set [] = []
power_set alphabet = [str_from_int x | x <- [0 .. ((1::Int) `shiftL` numAlpha) - 1]]
    numAlpha = length alphabet
    str_from_int x = [alphabet !! i | i <- set_bit_positions x]

2010 in review

Have to say. Pretty impressed with wordpress’s “summary” feature/email/view etc..  I wonder if me lazily posting this back as a post actually counts as a post?  In which case this is my first for the year – happy new year all!


The stats helper monkeys at mulled over how this blog did in 2010, and here’s a high level summary of its overall blog health:

Healthy blog!

The Blog-Health-o-Meter™ reads This blog is doing awesome!.

Crunchy numbers

Featured image

A helper monkey made this abstract painting, inspired by your stats.

A Boeing 747-400 passenger jet can hold 416 passengers. This blog was viewed about 4,000 times in 2010. That’s about 10 full 747s.


In 2010, there were 5 new posts, growing the total archive of this blog to 42 posts.

The busiest day of the year was March 31st with 41 views. The most popular post that day was Android Hack – Parcellable in eclipse.

Where did they come from?

The top referring sites in 2010 were,,,, and

Some visitors came searching, mostly for gray code generator, django app engine, google maps captcha, django mobile, and aidl file.

Attractions in 2010

These are the posts and pages that got the most views in 2010.


Android Hack – Parcellable in eclipse March 2008


Django/Appengine Coexistence, Part 1 – Environment Specific February 2010


Mango – Mobile Django – Templates March 2010


Gray Code Generator October 2009


Carnatic Violin March 2007

New Start

Well it has happened on wednesday.  I have now started work with Macquarie bank.  Pretty excited (though a bit scared).  WMS was awesome and despite my initial disbelief I was fortunate to meet some of the smartest and, more importantly, the most passionate people I have ever met.

Wish me all luck folks.  Certainly a bit of a pain to be wearing business-y outfit to work every day but hey its small price!

Gray Code Generator

I suppose I could finally talk about it!  I had my Google interview last July.  Was an embarassement (and to myself too).  This was the final question in my interview (with none other than Lars Rassmussen).  The question was the typical one – “there is a room from which at any time only one person can either enter or exit the room – and not at the same time.  So how would you model all the states the room can be in without repetitions”.

“Simple, isnt that just Graycode?” I blurt out.  At which point I was asked to write an algorithm to actually generate all graycodes for a n-bit string.   And this was where I floundered.  Mind you I had just been through 3 and a half hours and writing an algorithm was the last thing on my mind.  It wasnt that I hadnt known how to do it, I just blanked out then then and there – half an hour close to the finish of the interview and I had lost focus.  Stupid stupid me.

Anyway I just got back from a swim and for some reason the demon of the failed interview reared its ugly head and so I figured Id attempt it here (atleast to get some closure, sob sob).  Here goes.

Here are possible gray codes for N = 1, 2, 3 and 4:

N = 1 N = 2 N = 3 N = 4
0 00 000 0000
1 01 001 0001
11 011 0011
10 010 0010
110 0110
111 0111
101 0101
100 0100

Anyway this is only one combination. Any bit could be changed in generating the sequence. The pattern here is that the first half and the second half of the code are “kind of” the same but with the first bit being 0 and 1 respectively and the rest of the bits being reverse of each other.

ie with N = 2,
first half = 00 and 01
second half = 11 and 10

So a simple algorithm would be (in pseudo-haskell):

gc 1, reverse = ["1", "0"] if reverse, else ["0", "1"]
gc N, True =
      ["1" + x for x in gc(N - 1, True) ] ++ ["0" + x for x in gc(N - 1, False) ]
gc N, False =
      ["0" + x for x in gc(N - 1, False) ] ++ ["1" + x for x in gc(N - 1, True) ]

Problem with the above is the storage required in the recursion to store the graycodes for N – 1 (and that too twice). So in python we could avoid this with generators like:

def graycode(numbits, reverse = False):
    if numbits = 1:
        if reverse:
            yield "1"
            yield "0"
            yield "0"
            yield "1"
        if reverse:
            # all the "1"s start first
            gcprev = graycode(numbits - 1, True)
            for code in gcprev:
                yield "1" + code

            gcprev = graycode(numbits - 1, False)
            for code in gcprev:
                yield "0" + code
            # all the "0" start first
            gcprev = graycode(numbits - 1, False)
            for code in gcprev:
                yield "0" + code

            gcprev = graycode(numbits - 1, True)
            for code in gcprev:
                yield "1" + code

and finally an auxilliary function to print out the codes:

def gcgen(numbits, reverse = False):
    for codes in graycode(numbits, reverse):
        print "Code: ", codes

And that was 15 minutes of thinking. Damn it why didnt it come to me last year? Could have been the difference between a googler and foogler!!! Unless ofcourse it didnt really matter and they simply thought I was just a dick@#$D!!!

API Centric Design with Django and GAE

I wasnt really sure what to call this post.  My current situation is I write django apps (well so many words within that sentence can be loosely defined).  I guess after playing with django for last two and a half years (and Google AppEngine, GAE, ever since it came out) I am at a very interesting (or frustrating) crossroad.  What platform to choose and stick with – appengine or django.  Actually I had this conundrum about a year ago and I have essentially postponed this choice by what I call API centric design (ACD).  I am pretty sure ACD is just another fancy acronymn for existing techniques out there but still bear with me.

Django can be quiet easily used with GAE.  And infact that is what I have done.  I use django entirely within GAE.  The real impedence mismatch pops its ugly head thanks to the completely different backend schemes used by GAE and Django (key-value store vs relational DB).  As much as I am not a fan of the GAE, it is a pretty good platform for prototyping.  Well its free and hence, given the state of the competition, the best choice (for now) in the price range.   So how does one use GAE for prototyping an application, leaving it out there to collect feedback (and failing early and failing often) and move the application a platform of choice when the limits are reached and the constraints in GAE are just too much?  A redesign of an app to leverage non-GAE environments is certainly not the way to go.

What I have done is only expose an API from the app point of view.  Hide the back-end specific details behinds its own (django uses to hold the data models for an applications).  Its actually a lot easier than it sounds (if it already sounds easy, then it is even easier).  What is trickier is that one would have to exercise considerable discipline in following this.  Every call in the application should call only the exposed api instead of using the data-backend related calls provided by the platforms (GAE or Django or anything else).  Even leave the implementation and the optimisation to the specific backends.

As an example, let us take the famous “counter” example.  A typical way to have counters in traditional RDBMs based platforms is to have a table that stores the rows of name/counter pairs.  For DBMSes that are strong with write’s this is great.  GAE however recommends a different approach using shards.  Check Brett Slatkin’s video on this.  So how do you choose between these two?

Firstly needs to have a variable called USING_APPENGINE (or something similar) that will be set to True if the app is running in GAE and False otherwise (ie a native django app running on the test server or on other webservers).

Suppose our counters api is as follows:

def get_counter(counter_name)

def incr_counter(counter_name, byhowmuch = 1)

Now il need 3 files for the api –, and  Only will be imported in any other part of the application requireing counters. will have the get and incr counter implementations for traditional RDBMBs and will have the same for a GAE specific implementation. will be:

from django.conf import settings

if settings.USING_APPENGINE:

from import *


from import *

Thats it.  In your calling app simply do:

import counters


counters.incr_counter(“xxx”, 10)

This is only the beginning.  Clearly this extends to other types of backends as well (ie support TokyoCabinet in the future etc).  When writing an application you shouldnt have to worry about the optimisations.  Nothing stipulates that will have to implement Brett Slatkin’s stragey when using counters in GAE, but having separate files allows for this optimisation in the future.  Let the api abstract it all away.

Ofcourse it may appear that this will explode the number of functions required in the API.  Not necessarily (ie functions having to bepeated to do filters or object creations or deletions).  Some of the common patterns are object creation, fetching an object by ID or by certain attrib/column values, deleting records.  There are others, but these are the most common ones.

So I have a base djhelpers and gaehelpers file which define object creations, deletions, searches for ANY kind of object class and each one is optimised (sort of) to that specific implementation.

For instance, in django objects can be created with the method:

def create_object(obj_class, **kwds):
    return obj_class.objects.create(**kwds)

while the GAE implementation would be:

def create_object(obj_class, **kwds):
    obj = obj_class(**kwds)
    return obj

Note these are only basic ones.  Other implementations could go through the kwds list and get the parent and id parameters to set these on the object as required.  Alternatively, you could only save optionally and so on.

So an object creation in another part of the app is simply a matter of doing:

create_object(MyObjectClass, a = 1, b = 2, c = 3)

and the object is created without having to worry about the backend type.

This is again a simple way of hiding the implementation details.  The same could be implemented using metaclasses and properties to define a DBObject class whose metaclass would be the implementation specific class for the above and other object specific methods.

Sydney Django Users Group

Well we already do have a Sydney Python group.  So I was a bit apprehensive when I created the Sydney Django Users Group.  But my goal was not to compete with SyPy (actually most of our members are FROM SyPy and we regularly visit SyPy discussions – including one last night by Alex Dong on scaling web applications).

The main goal was to have a small group focusing purely on django activity in sydney.  So far so good.  Had our first meetup last tuesday.  Modest turn out and interesting talk by Sam Cavenagh and Shaon Diwakar.  Oh and thanks heaps for Shaon and Sam for actually pushing me to organise the meetup by getting me out of my lazy zone.

And here’s for lots more activity in the sydney django community.

StartupCampSydney II

Wow that was a doozer!

Last weekend was the StartupCampSydney.  A weekend where about 6-10 teams (each with 6-8 members) build, launch and pitch a Startup in one weekend.  Yep one weekend. To be honest I never thought it would work and when asked to be part of this one, I was trying to come up with an excuse to back out of it (before my wife who I hoped would have asked me not to go, urged me to participate…) …  the urging turned out to be a blessing.. that was one of the most intense, enriching, immersed and enlightening product development excercises Ive been in.

The sheer amount of talent from all backgrounds says it all.. and ofcourse meeting and working with so much talent just makes you do things that you never realised were possible.  Our startup is – a topic/news aggregator. Check it out, we would love your feedback (please forgive us in advance for the bugs).

Check out a full coverage of SCS by Ross Dawson.

Cant wait for the next one.


At work I do games.   Again not the usual kind but the slot ones.  A good thing about where I work unlike others in the industry is that we actually have a bit of belief in technology and try to “catchup” with latest technology (usually mainstream – 5 years).  Now while this may be astonishing to some outside the industry, it is quite advanced within!  Anyhoo I am digressing.

Point was that with all this catching up we do, we recently (about 6months-1year ago) started using Lua to script a big chunk of the games so that only the core is handled by C++ and everything UI related is palmed off to Lua.  Obvious advantage is that extra builds are not required as compileable source code is not changed and configuration is a lot easier and lot less time consuming.  Again nothing new here.

The problem is that the lua scripts we invoke from C++ have no easy way of debugging them.  So our engineers had been toiling with this by using the first-class technique of peppering the code with print statements.  You would thing some methodologies would die eventually but nope.

So I figured why not simply have a debugger that takes advantage of Lua’s debug api and allow debugging of scripts remotely.  So was born LunarProbe.  My attemt at debugging lua scripts once embedded in a host language.  Even at the beginning I figured that this was a very generic thing and has no specific code for our games.  So I decided to release it on the Apache License.  You can find the code on google code.

So far it only supports C/C++ but hope to have more languages supported with the appropriate bindings in place.  The idea is simple:

  1. The lua_State object (ie the lua stack or the lua context) is god in Lua.  Essentially it is what the interpreter uses to execute scripts and lua statements “on”.
  2. A new lua stack can be opened with the lua_open command.
  3. Usually following this command, you open all the standard libraries with the luaL_openlibs.

That is it.  You do usual things like loading lua files on a particular stack.  See the lua manual for more info on this.

So where does the debugging come in?  Well each lua stack can be given a debug hook function that is called by the interpreter after certain points at runtime. eg after a line has been executed, after a function is invoked, after a function has returned etc.

What LunarProbe does is registers itself as a hook function and deals with each of the above debug events and presents it via tcp (port 9999 by default) to a remote client.  The debug server is in fact api driven.  It accepts commands from the client and returns responses (but not HTTP – to keep it simple).  This means any UI could be written easily by simply following the debug server protocol.  A reference client is provided (written in python).  The python client is supposed to be like gdb (but no where near it!! GDB – please accept my apologies for even trying a comparison!!  I know I dont deserve it.)

I wanted to write a GUI or an Eclipse plugin, but we dont use eclipse plugin at work and wx widget toolkits werent installed by default here at work.  So doing either meant having all developers install extra packages which was a huge adminstrative overhead.  At a later stage, I would like to see more coming up.  Any helpers?

Again I digress.  So how would one enable LunarProbe in stacks they are opening?  Simple.

Instead of lua_open and luaL_openlibs, simply do this:

1. Include the lunarprobe header (ensure that lunarprobe/src is in the include path):

  • #include “lpmain.h”

2. Instead of lua_open and luaL_openlibs simply do:

LUNARPROBE_NS::LuaUtils::NewLuaStack(true, true, “hello”)

This does a few things:

  1. Creates a lua stack using lua_open
  2. If the first parameter is true, then Opens standard libraries using luaL_openlibs.
  3. and if the second parameter is true, registers LunarProbe by calling LUNARPROBE_NS::LunarProbe::Attach(stack, name), where “stack” was opened in step 1.
  4. The fourth parameter (defaulting to “”) only gives a name to each of your stacks for debugging purposes.  This is very useful in the debug client to identify which stack your dealing with when the address of a stack may not be very useful or very clear.

Alternatively, you can simply call the step 3 instead of NewLuaStack if you do not want to pull out your own versions of lua_open and luaL_openlibs.

That it. This is the embedding/attaching part of the debugger.  Now the client.

The Client

lunarprobe/client includes a simple client –

I wont go into too much detail here as the “help” command is mostly self-explanatory.  Just the brief stuff.

Invoke this with:

  • python client run

or if you would like to run it from within an interpreter then:

  • import client

This brings up the LDB prompt: type in “help” to show all commands and their usage.

One distinction (actually an inconvinience) is that since multiple stacks can be debugged at the same time, any context (LP calls stacks as contexts) specific commands must pass in the address of the context.  This is not hard, just inconvinient.

To get a list of all the contexts simply type in the contexts at the prompt and press enter.  This will show all context names and their addresses.  Use these addresses with any context related commands (like step, next, continue etc).

Breakpoints at the moment can be set by filename (and linenumber) or by a function name.  However at this stage member functions are not differentiated from global functions.  So a function name breakpoint will affect ALL functions of the same name.

As mentioned this is very brief.  Apologies for that.  Il add more and more in as I improve this.

Well hopefully this project is useful for all Lua embedders out there.  Please let me know how I can improve this.  Also this project is on google code, so please let me know if you would like to contribute or extend LP.

Best of luck!!!

The Greatest Entrepreneurs

The 80s and 90s, saw a huge influx of Indian migrants to Australia (the trend still continues).  Now there is something different about these migrants.  Now what is odd about this class of migrants is most of them were in their mid 30s to mid 40s, with very comfortable lifestyles back home (by which I mean respectable jobs/positions resulting from years of hard work).  Why I think this is odd is that you would not expect people/couples with such low risk lifestyles to risk it all and jump ship to sail to the uncertain shores of a foreign land.

It is pretty easy (or comforting atleast) sitting in your parents’ basement coding or being sponsored to spend summers on startup ideas sponsored by THE man PG himself (an opportunity Id kill for), but leaving all you have with very little promise of great rewards, purely for the sake of your family, is what I consider true entrepreneurship (well children are the ultimate startups anyway).  Costs of failures are very high (hardship for entire family, loosing face, etc).  Rewards are not staggering except that life for one’s family is slightly better.

I would like to thank two such migrants who risked very comfortable jobs for the sake of their two sons.  Myself and my brother.  Mum was a very respected high-school teacher (she was my math teacher – which could explain my interest in maths).  Dad was a successful accountant.  Like others they had left it all for us.  The main reason was reverse-discrimination in the society gripped by the plague of the caste system, existing only to empower already corrupt politicians (redundant adjective). Times were hard for the first two years – time they had spent unemployed, living on government assistance.  But I am glad for those times.  It had instilled in us a passion and respect for hardwork.  Cant complain at all.  No room for becoming spoilt brats.  In fact I wonder if I can ever replicate their own dedication and values on my own kids (one day).  Atleast I know that I dont have to look far in search of role-models!

So thanks mum and dad (hope this combined post suffices for mothers’ and fathers’ days).