Negative Space, and How Does it Apply to Coding

There’s a term in drawing called “negative space”. The idea is very simple: you don’t draw what’s there – you draw what’s not there.

neg_mugchair

Credit: http://www.artinstructionblog.com/an-introduction-to-negative-drawing-with-mike-sibley

NEGATIVE SPACE by Leonardo Santamaria for Satellite Citi.

In software architecture realm, we usually come up with a basic design, implement a “layout” (infrastructure of your application) and then start augmenting it by adding features and providing better coverage for different use-cases.

Defining the negative space of your program means that not only you define what it should do – but also declare what it shouldn’t. By understanding what should be the limitations of your program you can simplify the design and easily reject feature requests that are crossing these borders.

In the world or micro-services it is very easy to create a new service and sometimes the right decision is to not support a new capability in “service A” but rather push that capability into a more qualifying “service B” or even spawn up a new dedicated service.

During my work at Netflix I ran a few times into a case where we needed to implement a new capability into existing services. That capability had a complex spec and was latency-sensitive, so we created new services in order to be able to:

  1. Keep the current services simple
  2. Add a new dedicated caching layer, but more important:
  3. Make our services resilient by applying the bulkhead design pattern.

So next time you architect a piece of software don’t forget to take into account the negative space!

Advertisements
Negative Space, and How Does it Apply to Coding

Implementing a Multi-Iterator in Java

Say you had to implement a class that takes as an argument (in the constructor) Iterator<Iterator<E>> iterator and returns an iterator that can iterate all the elements under Iterator<Iterator<E>> iterator in a round-robin manner, meaning, according to the order of the numbers in the following screenshot:

sc1

I searched online and found implementations such as thisthis and even Guava but they are not helpful in our case since the order they are iterating is vertical: 1,7,13,17,2,8,14,18,3,9,4,…

So I decided to come up with my solution to the problem, and here’s what I got:

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;

/**
 * Created by alfasin on 11/15/15.
 */


public class MultiIterator<E> implements Iterator {

    List<Iterator<E>> iterators = new LinkedList<>();
    Iterator<E> current = null;

    public MultiIterator(Iterator<Iterator<E>> iterator) {
        // copy the iterators into a list
        while (iterator.hasNext()) {
            iterators.add(iterator.next());
        }
    }

    @Override
    public boolean hasNext() {
        boolean result = false;
        if (iterators.isEmpty() && (current == null || !current.hasNext())) {
            return false;
        }

        if (current == null) {
            current = iterators.remove(0);
        }

        while (!current.hasNext() && !iterators.isEmpty()) {
            current = iterators.remove(0);
        }

        if (current.hasNext()) {
            result = true;
        }
        return result;
    }

    @Override
    public E next() {
        if (current == null) {
            try {
                current = iterators.remove(0);
            } catch (IndexOutOfBoundsException e) {
                throw new NoSuchElementException();
            }
        }
        E result = current.next(); // if this method was called without checking 'hasNext' this line might raise NoSuchElementException which is fine
        iterators.add(current);
        current = iterators.remove(0);
        return result;
    }

    // test
    public static void main(String[] args) {
        List<Integer> a = new LinkedList<>();
        a.add(1);
        a.add(7);
        a.add(13);
        a.add(17);
        List<Integer> b = new LinkedList<>();
        b.add(2);
        b.add(8);
        b.add(14);
        b.add(18);
        List<Integer> c = new LinkedList<>();
        c.add(3);
        c.add(9);
        List<Integer> d = new LinkedList<>();
        d.add(4);
        d.add(10);
        d.add(15);
        List<Integer> e = new LinkedList<>();
        e.add(5);
        e.add(11);
        List<Integer> f = new LinkedList<>();
        f.add(6);
        f.add(12);
        f.add(16);
        f.add(19);
        List<Iterator<Integer>> iterators = new LinkedList<>();
        iterators.add(a.iterator());
        iterators.add(b.iterator());
        iterators.add(c.iterator());
        iterators.add(d.iterator());
        iterators.add(e.iterator());
        iterators.add(f.iterator());
        MultiIterator<Integer> it = new MultiIterator<>(iterators.iterator());
        while (it.hasNext()) {
            System.out.print(it.next() + ","); // prints: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,
        }
    }
}

A different approach would be to read all the elements, during initialization, into one list and then return an iterator of that list!

Let’s see how it works:

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

/**
 * Created by alfasin on 11/15/15.
 */

public class MultiIterator<E> {

    Iterator<Iterator<E>> iterator = null;
    List<E> elements = new LinkedList<>();

    private MultiIterator(Iterator<Iterator<E>> iterator) {
        this.iterator = iterator;
    }

    private void copyElementsInOrder() {
        List<Iterator<E>> iterators = new LinkedList<>();
        // copy the iterators into a list
        while (iterator.hasNext()) {
            iterators.add(iterator.next());
        }
        // go over the list, round-robin, and grab one
        // element from each sub-iterator and add it to *elements*
        // empty sub-iterators will get dropped off the list
        while (!iterators.isEmpty()) {
            Iterator<E> subIterator = iterators.remove(0);
            if (subIterator.hasNext()) {
                elements.add(subIterator.next());
                iterators.add(subIterator);
            }
        }
    }

    public static <E> Iterator<E> iterator(Iterator<Iterator<E>> iterator) {
        MultiIterator<E> instance = new MultiIterator<>(iterator);
        instance.copyElementsInOrder();
        return instance.elements.iterator();
    }

    // test
    public static void main(String[] args) {
        List<Integer> a = new LinkedList<>();
        a.add(1);
        a.add(7);
        a.add(13);
        a.add(17);
        List<Integer> b = new LinkedList<>();
        b.add(2);
        b.add(8);
        b.add(14);
        b.add(18);
        List<Integer> c = new LinkedList<>();
        c.add(3);
        c.add(9);
        List<Integer> d = new LinkedList<>();
        d.add(4);
        d.add(10);
        d.add(15);
        List<Integer> e = new LinkedList<>();
        e.add(5);
        e.add(11);
        List<Integer> f = new LinkedList<>();
        f.add(6);
        f.add(12);
        f.add(16);
        f.add(19);
        List<Iterator<Integer>> iterators = new LinkedList<>();
        iterators.add(a.iterator());
        iterators.add(b.iterator());
        iterators.add(c.iterator());
        iterators.add(d.iterator());
        iterators.add(e.iterator());
        iterators.add(f.iterator());
        Iterator<Integer> it = MultiIterator.<Integer>iterator(iterators.iterator());
        while (it.hasNext()) {
            System.out.print(it.next() + ","); // prints: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,
        }
    }
}

There are pros and cons to each one of these approaches:

The first approach is more complex because it requires checking and handling of many edge-cases (including catching an IndexOutOfBoundsException in case that our list of iterators is empty and throwing the proper NoSuchElementException instead).

The second approach is more concise on one hand, but on the other hand it requires copying, in-advance, all the elements (greedy) vs. the first approach which is lazy and should be preferred in cases of large datasets.

Note that the second approach implements a factory and as such it doesn’t implement the Iterator interface!

EDIT:

Now with Java 9, it’s much more elegant to create such lists (using the new collections APIs). I re-did this exercise and here’s what I got:

class MultiIterator<E> implements Iterator {

    private LinkedList<Iterator<E>> iterators = new LinkedList<>();
    private int current = 0;

    public MultiIterator(Iterator<Iterator<E>> iterator) {
        while(iterator.hasNext()) {
            iterators.add(iterator.next());
        }
    }
    /**
     * Returns {@code true} if the iteration has more elements.
     * (In other words, returns {@code true} if {@link #next} would
     * return an element rather than throwing an exception.)
     *
     * @return {@code true} if the iteration has more elements
     */
    @Override
    public boolean hasNext() {
        if (iterators.size() == 0) {
            return false;
        }
        if (iterators.get(current).hasNext()) {
            return true;
        }
        return false;
    }

    /**
     * Returns the next element in the iteration.
     *
     * @return the next element in the iteration
     * @throws NoSuchElementException if the iteration has no more elements
     */
    @Override
    public E next() {
        E next;
        try {
            next = iterators.get(current).next(); // might throw IndexOutOfBoundsException if wasn't called with hasNext()
            Iterator<E> iter = iterators.remove(current);
            if (iter.hasNext()) {
                iterators.add(iter);
            }
        } catch (IndexOutOfBoundsException e) {
            throw new NoSuchElementException();
        }
        return next;
    }

    public static void main(String[] args) {
        List<Integer> l1 = List.of(1, 2, 3, 4, 5, 6);
        List<Integer> l2 = List.of(5, 6, 7, 8);
        List<Integer> l3 = List.of(9, 10, 11, 12);
        Iterator<Iterator<Integer>> iterators = List.of(l1.iterator(), l2.iterator(), l3.iterator()).iterator();
        MultiIterator<Integer> iters = new MultiIterator<>(iterators);
        while (iters.hasNext()) {
            System.out.println(iters.next());
        }
    }
}
Implementing a Multi-Iterator in Java

Python: Six, ABC and functools.wraps

Python
Over the past week I went through some Python code in Stackstorm (hosted in GitHub), and by doing so I learned a few cool new things. Maybe ‘new’ is not the right term, but these things were new to me and I wanted to share them with you.

The code I am referring to resides in a few places in Stackstorm, the first item:

@six.add_metaclass(abc.ABCMeta)
class Access(object):
Two things here:

1. six.add_metaclass – makes Access a metaclass in a way which is compatible both with Python2 and Python3. In general, six package has a purpose of helping developers migrate their code from Python 2 to Python 3 by writing code which is compatible with both.
Hence the name: six = 2 * 3. To read more: https://pypi.python.org/pypi/six

2. abc.ABCMeta – abc is another builtin package, its purpose is to provide support for Abstract Base Classes. By making a class abstract you ensure that nobody can instantiate objects out of it.
This is useful for (at least) three purposes:
a. Maintain logic which is common to multiple classes in one place
b. force the users to implement methods which are annotated by @abc.abstractmethod (you can also force the inheriting classes to create specific class members by using the annotation @abc.abstractproperty). For more info in regards see the docs.
c. creating a singleton. I’m still not convinced about the usefulness of creating a singleton in Python (because we have modules), but assuming you want to do so, you can either create a metaclass and call its methods as ClassName.method() or extend a metaclass but not implement the abstractmethod or abstractproperty. By not implementing the abstract-methods/properties the inheriting class will become abstract as well. This technique is used in a few different places in StackStorm, if you want to see some examples, search for classes that inherit from Access.

3. This one took me a while to wrap my head around (requires a “functional programming” mind if you will):
def decorate(f):
        @functools.wraps(f)
        def callfunction(*args, **kwargs):
By calling @functools.wraps(f) we’re using a decorator inside a decorator. Not trivial…
To understand the main idea of ‘functools.wraps’, it’s easier to go through the following points/process (at least, easier for me…):
– When you decorate a function, you’re creating a new function that wraps the ‘original’ one, and return the wrapper
– The wrapper is used in order to be able to perform all kinds of tasks before/after the ‘original’ function is applied. Examples: preparing the arguments for the ‘original function’, timing how long does it take for the function to execute, add log printings before and after and etc.
– Say you have a wrapped function f, returned from a decorator, the user will then see the description (metadata) of the decorator instead of f, the original function.
– In order to avoid this confusion, @functools.wraps(f) comes into the picture: by annotating the wrapper function with @functools.wraps(f) – you’re making sure that the user of the wrapper will see the same description/metadata as the original function has. By ‘description’ I mean the function-signature (the name of the function and the names of the arguments it takes).

Hope this is helpful!
Python: Six, ABC and functools.wraps

How to calculate square root

The other day I ran into a question in Stackoverflow asking how to implement square-root calculation. I started googling it up and some implementations seemed to me very cumbersome but then I found Newton’s method which is pretty easy to implement. Translating it to Java was a matter of a few lines of code:

 
class Sqrt {
    public static void main(String[] args) {
        System.out.println(sqrt(17)); // 4.123105985575862
    }

    final static double DELTA = 0.0001;
    /**
     * Newton's method:
     *
     * X1 = X0 - f(x)/f'(x)
     * x^2 = num
     * f(x) = x^2 - num
     * f'(x) = 2*x
     *
     * X1 = X0 - (X0^2 - num) / 2*X0
     * ...
     * Xn = Xn-1 - ((Xn-1)^2 - num)/2Xn-1
     *
     * Stop condition: |num - (Xn)^2| < DELTA 
     * */ 

    public static double sqrt(double num) { 
        double x = num / 2; // starting point
        while(Math.abs(num - x * x) > DELTA) {
            x = x - ((x * x - num) / (2 * x));
        }
        return x;
    }
}
How to calculate square root

A simple calculator in Python

A while back, I wrote a simple calculator in Ruby. A few minutes ago I ran into a similar question in Stackoverflow, and decided to implement the Python version:

def is_number(s):
    try:
        float(s)
        return True
    except ValueError:
        return False


def calc(expr):
    if is_number(expr):
        return float(expr)    
    arr = expr.split('+')
    if len(arr) > 1:
        return sum(map(calc, arr))
    arr = expr.split('-')
    if len(arr) > 1:
        return reduce(lambda x,y: x-y, map(calc, arr))
    arr = expr.split('*')
    if len(arr) > 1:
        return reduce(lambda x,y: x*y, map(calc, arr), 1)
    arr = expr.split('/')
    if len(arr) > 1:
        return reduce(lambda x,y: x/y, map(calc, arr))


print calc("3+4-2 *2/ 2")    # 5

Nice, isn’t it?

A simple calculator in Python

My “most frequently used” Mac productivity tools

Alfred

I would recommend using Alfred, even without buying the power-pack it has very useful clipboard snippets:

 sc1

This way you can save commands that you’re using frequently and find them by typing “keywords” and when you press “enter” it’s paste into your clipboard/terminal. Very useful – especially when you work remotely on nodes in the cloud where you don’t have all your aliases defined.

I think that only if you buy the power-pack – you can use the workflows as well:

 sc1

The great thing about it is, that with one command/shortcut you can open multiple windows in your browser, open a terminal and connect somewhere, and basically do multiple operations simultaneously.

This is very useful in different scenarios, for example, when you are in emergency situation – it can both save time *and* make sure you’re not forgetting anything. For example, when I get paged for an incident I open the terminal and connect to our production bastion, open our public channel in hipchat to make sure we didn’t get any reports about the incident from other people in the company, open a tab in the browser with our dashboard and etc.

But Workflows are great not only in emergency situations, for instance, we have a service that, given a node-id – it provides all the information about the node (aws-account/region/instance-type/asg/etc) as well as provides links to Asgard and some other stuff. So in Alfred I have a workflow with a shortcut, and now all I have to do is type:
“loc <node-id>” (short for “locate”) and it opens that service in a new tab in my browser.

Alfred has many other features which I haven’t yet explored, but in case you decide to try it out here’s one very important tip:

under “advanced” tab there’s a “set sync folder” button. Set it to save your stuff under dropbox (or any other cloud-drive). This way you’re making sure that:

  1. you can use your Alfred setup with multiple computers
  2. it’s always backed-up – if anything happens to your computer – you haven’t lost anything (all your shortcuts, clipboard, workflows etc).
 sc3

Even without using multiple screens I find this app very useful: it provides keyboard shortcuts to resize windows, center them in the screen, and when you’re using multiple monitors – move them from one screen to another and back really easily. And yes, I agree, it is annoying you have to pay for something that you get for free as a Windows user, but I think that Apple users (unlike Windows users) are used to pay for stuff they need/want…

sc4

Captures screenshots of all/part of the screen, menus, etc. And then lets you edit and save/embed them. This app is free and I’m using it all the time – the screenshots in this post were done by Skitch!

Thanks to JS who introduced me to Alfred & Sizeup!

Disclaimer: I’m not affiliated with any of the applications above, nor I am receiving any kind of commission/royalties/etc!

 

Mosh is a command-line tool that replaces SSH. The main advantage of this terminal application is that it keeps the connection active, so even if you close your laptop, pack it in your bag, travel somewhere, open your laptop again – and you’re still connected on the same session!

My “most frequently used” Mac productivity tools

foo.bar: Rusty calculator

Last week I wrote about the code challenge foo.bar: Peculiar balance. Today I’ll tease you with another one:

Rusty calculator
================

Lab minion Rusty works for Professor Boolean, a mad scientist. He’s been stuck in this dead-end job crunching numbers all day since 1969. And it’s not even the cool type of number-crunching – all he does is addition and multiplication. To make matters worse, under strict orders from Professor Boolean, the only kind of calculator minions are allowed to touch is the Unix dc utility, which uses reverse Polish notation.

Recall that reverse Polish calculators such as dc push numbers from the input onto a stack. When a binary operator (like “+” or “*”) is encountered, they pop the top two numbers, and then push the result of applying the operator to them.

For example:
2 3 * => 6
4 9 + 2 * 3 + => 13 2 * 3 + => 26 3 + => 29

Each day, Professor Boolean sends the minions some strings representing equations, which take the form of single digits separated by “+” or “*”, without parentheses. To make Rusty’s work easier, write function called answer(str) that takes such a string and returns the lexicographically largest string representing the same equation but in reverse Polish notation.

All numbers in the output must appear in the same order as they did in the input. So, even though “32+” is lexicographically larger than “23+”, the expected answer for “2+3″ is “23+”.

Note that all numbers are single-digit, so no spaces are required in the answer. Further, only the characters [0-9+*] are permitted in the input and output.

The number of digits in the input to answer will not exceed 100.

Test cases
==========

Inputs:
(string) str = “2+3*2″
Output:
(string) “232*+”

Inputs:
(string) str = “2*4*3+9*3+5″
Output:
(string) “243**93*5++”

The solution (in Python) is surprisingly short:

def answer(normal):
    res = ''
    muls = normal.split('+')
    for mul in muls:
        if len(mul) > 1:
            local_mul = mul.split('*')
            res += ''.join(local_mul)
            res += (len(local_mul) - 1) * '*'
        else:
            res += mul 
    res += (len(muls)-1) * '+'    
    return res

That’s definitely NOT the way you should write your code…
Can you figure it out?

Hint: a similar technique was used here

foo.bar: Rusty calculator