Practicing Spark

I have used spark on an adhoc basis for work related things. It is great fun to write powerful data processing flows in spark. However I wanted to challenge myself more. Here is an interesting way to challenge yourself. Try writing some of the common coding interview puzzle questions in spark code. It is fun and exercises your spark muscles nicely. After I completed the setup of my IDE to enable local spark development, I went in hunt of a kinda easy coding puzzle which can be solved using the parallelization of spark.

The problem

I found a relatively easy coding puzzle in Hackerrank. It is the Flatland space station problem. Quoting from the problem statement:

Flatland is a country with a number of cities, some of which have space stations. Cities are numbered consecutively and each has a road of length 1 km connecting it to the next city. It is not a circular route, so the first city doesn’t connect with the last city. Determine the maximum distance from any city to it’s nearest space station.

For example, there are n=3 cities and m=1 of them has a space station, city 1 . They occur consecutively along a route. City 2 is 2–1=1 unit away and city 3 is 3–1=2 units away. City 1 is 0 units from its nearest space station as one is located there. The maximum distance is 2 .

So basically this translates to a Maximin problem, i.e. Find the maximum of the nearest space station to a city. Here is the single world java solution (Is there an optimal way of doing this? LMK in the comments :-) )

[embed]Flatlands.java

Not too hard is it?

Now for small input a single JVM can handle this fine. Imagine a scenario where the datasets is wayy larger. Now you really want to parallelize this as much as possible. Enter Spark and Scala to the rescue! (my favorite combo!). Here is the code as written in Scala and Spark.

[embed]ComputeMaximin.scala

Now if you were to throw millions of cities and tens of thousands of space stations at it. There should be no reason for it to break into a sweat!

Hope you liked this. Till next time…