Hackerrank Heaps: Find the Running Median

Given in input a stream of integers, calculate their running median. As the name of this HackerRank problem suggests, we should find a solution based on heaps data structures.

However, it is difficult to avoid the temptation of trying a different approach. Since I am using Python 3 as implementation language, the insort() function from the bisect library, makes the naive solution of sorting the list of data each time a new element arrives less expensive, to the point that is accepted by HackerRank, even though is far from optimal.

Insort

Here is a possible implementation:
for i in range(n):  # 1
    item = int(input().strip())
    insort(data, item)  # 2
    pos = len(data) // 2  # 3
    result = float(data[pos])
    if len(data) % 2 == 0:
        result += data[pos - 1]
        result /= 2
    print(result)
1. I have previously read in n the number of elements that I should expect in input.
2. I insert in the list data each value I get using insort() so, keeping the list sorted. The cost of finding the right position in the list is logarithmic, hence the name bisect of the library, then we have to pay a linear cost to move to the right all the elements bigger than the current one. Still a Big-Oh n*log(n) algorithm, however, on average cheaper than sorting data each time, if we don't use an algorithm that knows it is dealing with a quasi-sorted collection.
3. Than we calculate the median, peaking the central element and, if the current size of the data list is even, also its left neighbor - in this case dividing by two.

It works find, but it sort of cheating.

Heaps

Unfortunately, the Python standard library does not support heaps so strongly as other languages do. There is a good implementation for the min heap, but here we need to work also with a max heap. The common hack, that I am going to use here, is negating the values inserted in a heap, to let it work as a max heap. Not the cleanest thing to do, however it works fine here.

I have written a class, MedianHeap, that shield the intricacies of the min/max heaps, and offer a simple interface to my solution, that gets very easy:
def solution(values):
    heap = MedianHeap()

    result = []
    for value in values:  # 1
        heap.push(value)
        result.append(str(heap.median()))

    return '\n'.join(result)
The MedianHeap constructor is trivial:
def __init__(self):
    self.left = []   # max heap
    self.right = []  # min heap
I am going to use two heaps. One the left, keeping the smaller values, that is going to be a max heap, and one on the right, a min heap that keeps the bigger values. I will be always only interested in the max value on the left and the min value on the right.

To push an element, I check if it is smaller that the max to the left, and in this case I am going to push it there, otherwise it will go to the right.
def push(self, value):
    if not self.left or value < -self.left[0]:  # 1
        heappush(self.left, -value)  # 2
    else:
        heappush(self.right, value)
1. Couple of nuisances. Before checking I must ensure the left heap is not empty. And, I have to remember my hack on the max heap, so I change the sign of the max element on it before comparing it to the current value.
2. Beside that, I simply use the heappush() function from the heapq python core library. Still, remember that the left heap is a max one, so change the sign of the value I pushing in.

After the push, we should ensure the size difference between the two heaps is minimal, zero or one, otherwise I have to balance them:
bigger = self.left if len(self.left) > len(self.right) else self.right
smaller = self.left if len(self.left) < len(self.right) else self.right
if len(bigger) - len(smaller) > 1:  # 1
    moved = -1 * heappop(bigger)  # 2
    heappush(smaller, moved)
1. If the unbalance is bigger than one, I move from the smaller heap to the bigger one. I care only of their size, left to right or the other way round is just the same.
2. Still, I should remember to swapping the sign of the element, since I am moving from a min to a max heap, or viceversa. Notice the use of the other heapq function at work here, heappop().

Getting the median element from my MedianHeap is easy:
def median(self):
    bigger = self.left if len(self.left) > len(self.right) else self.right
    smaller = self.left if len(self.left) < len(self.right) else self.right

    if bigger is smaller:
        return (self.right[0] - self.left[0]) / 2  # 1
    else:
        maxi = -1.0 if bigger is self.left else 1.0
        return maxi * bigger[0]
1. If the heaps have the same size, I should return the mean of their max/min elements. Instead of adding, I subtract them, for the hack on the max heap.
2. Otherwise I return the min/max element of the biggest heap. If the winner is the left heap, it is the max one, so I have to change its sign.

I have pushed both the full python script, the bisect insort and the heap based one, and the unit test I used for help me to develop the more complex second solution, to GitHub.

Go to the full post

Spring Prototype Bean

By default, the Spring framework creates beans as singleton. However we can instruct it to create a different bean each time a request is made specifying the prototype mode. Another couple of ways are available, to create a bean for each request or session.

I have written a simple JUnit test to see the difference between prototype and singleton.

I have created two empty classes, both of them implementing the empty interface Scoping:
@Component
@Scope(ConfigurableBeanFactory.SCOPE_SINGLETON)
public class UniqueThing implements Scoping {
}

@Component
@Scope(ConfigurableBeanFactory.SCOPE_PROTOTYPE)
public class Notepad implements Scoping {
}
The SCOPE_SINGLETON scope is the default, so usually you won't see it explicitly set in production code. Here is just to remark its existence.
The class Notepad, marked with SCOPE_PROTOTYPE is the interesting stuff.

This is what normally happens with beans:
@Test
public void testSingleton() {
    UniqueThing thing1 = context.getBean(UniqueThing.class);
    UniqueThing thing2 = context.getBean(UniqueThing.class);
    assertSame(thing1, thing2);
}
When I get a bean - here I get them through the Spring application context - the same bean is returned.

But if the bean is marked as SCOPE_PROTOTYPE, we have a different behavior:
@Test
public void testPrototype() {
    Notepad notepad1 = context.getBean(Notepad.class);
    Notepad notepad2 = context.getBean(Notepad.class);
    assertNotSame(notepad1, notepad2);
}
Each bean is a newly created one!

Reference: Advanced wiring, from Spring in Action, Fourth Edition by Craig Walls. Chapter three, section four, Scoping beans.

I pushed the code I created on GitHub, see the scoping package and the associated JUnit test case.

Go to the full post

CodeEval Reverse Words

Given a string of words, write a function that returns them in reversed order. This is CodeEval problem #8 that has a trivial Python solution.

This is what we want to get, as a python test:
def test_provided_1(self):
    self.assertEqual('World Hello', solution('Hello World'))
And the core of the solution is a mere one-liner:
' '.join(reversed(line.split()))
We split the line, getting a list of strings, reverse it, and join the result on a blank.

I pushed the complete python script to GitHub.

Go to the full post

HackerRank Trees: Is This a Binary Search Tree?

As the title suggest, the point of this hackerrank problem is checking if a tree is a BST.

Before being able to work on this problem, you should know what we are talking about. In a few words, a BST is a tree in which for each node is true that its left children are strictly smaller and the right one are strictly bigger.

In Python, if a node is represented in this way
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
We can check a tree passing its root to a recursive function like this one:
def is_bst(node, left, right):  # 1
    if node is None:  # 2
        return True
    if not left < node.data < right:  # 3
        return False
    return is_bst(node.left, left, node.data) and is_bst(node.right, node.data, right)  # 4
1. The first parameter, node, is an instance of the class Node. The other two parameters are the limit in which the value is supposed to be. 2. An empty tree is a BST. This comes handy to manage the leaves of the tree. 3. The node value should lie in the specified interval, otherwise this is not a BST. 4. If the current node passes the check, we explore the rest of the tree. On the left we restrict the interval cutting it to the right, on the right we cut it on the left. Couple of questions. What should we pass as left and right for the root? And, What if we don't want to accept an empty tree as a valid BST? I think that in Python a good solution could be having a starting call like is_bst(root) that do not check for an interval and define on its own what to do in case of None. And then it call the above is_bst() for all the other nodes.

Go to the full post

Autowiring ambiguity

I have a hierarchy of Spring Components rooted in the interface Dessert. Let's see what could go wrong when I try to autowire on them.

Here is the base interface:
public interface Dessert {
    default double getPrice() {
        return 0;
    }
}
It has three empty implementing classes named Cake, Cookies, and IceCream. For instance, here is the third one:
@Component
public class IceCream implements Dessert {
}
In my test case, I autowire a Dessert that I am going to use in the tests, like this:
@Autowired
Dessert dessert;

@Test
public void test() {
    assertThat(dessert.getPrice(), is(0.0));
}
Spring has to know which Dessert to create and wire, and this could be done by class configuration. In this case, the tester should know it, by annotating as SpringApplicationConfiguration the class, that should be defined and annotated as a Spring Configuration file, like this:
@Configuration
@ComponentScan(basePackageClasses = Dessert.class)
public class DessertConfig {
}
Do not forget to specify the component scan annotation, otherwise Spring won't see the beans, and would complain something like:
org.springframework.beans.factory.BeanCreationException:
 Error creating bean with name 'dd.sia.restaurant.DessertTest':
 Injection of autowired dependencies failed; nested exception is
  org.springframework.beans.factory.BeanCreationException:
Could not autowire field:
 dd.sia.restaurant.Dessert dd.sia.restaurant.DessertTest.dessert;
nested exception is
 org.springframework.beans.factory.NoSuchBeanDefinitionException:
 No qualifying bean of type [dd.sia.restaurant.Dessert] found for dependency:
 expected at least 1 bean which qualifies as autowire candidate for this dependency.
 Dependency annotations:
 {@org.springframework.beans.factory.annotation.Autowired(required=true)}
However, activating the ComponentScan is only the first step. Since we have three Components based on Dessert, we should say to Spring which one to choose. If we don't we are going to have a different, albeit similar, exception:
org.springframework.beans.factory.BeanCreationException:
 Error creating bean with name 'dd.sia.restaurant.DessertTest':
 Injection of autowired dependencies failed; nested exception is
 org.springframework.beans.factory.BeanCreationException:
Could not autowire field:
 dd.sia.restaurant.Dessert dd.sia.restaurant.DessertTest.dessert;
nested exception is 
 org.springframework.beans.factory.NoUniqueBeanDefinitionException:
 No qualifying bean of type [dd.sia.restaurant.Dessert] is defined:
 expected single matching bean but found 3: cake,cookies,iceCream
One way to solve this issue is annotating a Component as primary:
@Component
@Primary
public class Cake implements Dessert {
}
In this way, Spring knows that Cake is the Dessert it should pick up when it is in doubt.

We can always bypass this default, specifying a default in the autowiring:
@Autowired
@Qualifier("cookies")
Dessert dessert;
Now Spring knows that we want cookies and won't pay attention to the primary annotation.
If we don't like the name generated by Spring for the component, that is, the class name but starting lowercase, we can set it as we please, using again the Qualifier annotation, this time on the Component itself. So, for instance, I can qualify Cookies as "yummy" and use this qualification when autowiring to ask Spring to select it.

Reference: Advanced wiring, of Spring in Action, Fourth Edition by Craig Walls. Chapter three, section three, Addressing ambiguity in autowiring.

I pushed the code I have written on this stuff to GitHub. See the package restaurant for the Java classes in the Spring application, and the DessertTest for the JUnit testcase.

Go to the full post

CodeEval Prefix Expressions

The CodeEval problem #7 asks us to write a toy calculator for simple arithmetic expressions written in Polish notation. We expect only addictions, multipications, and divisions. And no inner expressions are allowed, meaning that we can safely expect to have in input firstly all the operators then operands, as integer numbers. We should give an integer answer, even though the internal process should keep correctly track of real numbers generated by divisions.

As sample we are given a unique case, that I converted in a python test:
def test_provided_1(self):
    self.assertEqual(20, solution('* + 2 3 4'))
Since we have only to deal with binary operations, we can use the clever trick of starting from the middle of the input, were we can find the first operand, moving to the left to get the list of operators and to the right for the other operands. This lead naturally to think using zip() a python implementation:
i = len(data) // 2  # 1
result = float(data[i])  # 2
for op, value in zip(reversed(data[0:i]), data[i + 1:]):  # 3
    # ...
1. Getting the central element index in the input data list.
2. Convert the first value to real number, so that floating point arithmetic is applied to the expression.
3. I zip together the left and right part of the input data. First part reversed, so that I start to center and move to the edges fetching elements.

Now, what I should do in the loop. As C programmer my instinct went to a switch on the operators, to detect which operation I have to apply. But Python has no switch, so I had to think to something smarter. I put in a dictionary the mapping between each operator and the actual piece of code I need to run in that context, in form of a lambda function, and then I simply have to lookup in it to have the job done:
mapping = {'+': lambda r, v: r + v, '*': lambda r, v: r * v, '/': lambda r, v: r / v}

# ...

for # ...
    result = mapping[op](result, int(value))
Then, after the for loop, I just have to cast the result to integer and return its value.

On GitHub you can see the unit test and the full python script.

Go to the full post

Hackerrank Queues: A Tale of Two Stacks

This Hackerrank problem asks us to emulate a queue using two stacks. The rationale for this apparently weird data structure could be that we know for sure that we are going to have a data traffic in a sort of wave on the seaside fashion. We have a huge number of pushes with (about) no peek or pop, and then a huge number of peek or pop.
The architect should have calculate that it is not worthy to implement a proper queue, maybe memory comes at a premium on that environment. Or whatever.
Actually, the real sense of it is to see in an interview if a candidate knows about stacks and queue, and how to deal with them.

As usual, before starting writing my python code, I jotted down a few tests, so to clarify to myself what I am going to do. If I get on some soft spot during development, I can always get back here and fatten up the case.
def test_enqueue(self):
    queue = MyQueue()
    queue.put(42)
    self.assertEqual(42, queue.peek())

def test_enqueue_2(self):
    queue = MyQueue()
    queue.put(42)
    queue.put(2)
    self.assertEqual(42, queue.peek())

def test_dequeue(self):
    queue = MyQueue()
    queue.put(42)
    queue.put(2)
    queue.pop()
    self.assertEqual(2, queue.peek())
As often happens in this kind of coding, we can blissfully ignore the possible exception. Here letting our MyQueue crash in case the user try to pop when it is empty is a non-issue.

I have to use to stacks. One would emulate the head of the queue, form which pop and peek would operate, the other the tail, where push will add its values. So, I found it natural to name them head and tail:
class MyQueue(object):
    def __init__(self):
        self.head = []
        self.tail = []
Being in python world, the most obvious choice is using lists as their data type.

The push method (here called "put", as suggested by the template provided) is a no-brainer. I just append the passed value to tail.
def put(self, value):
    self.tail.append(value)

Peek and pop will substantially operate in the same way, getting the data from the other stack. There is only a question. How I should ensure that the head is populate with the correct data. Let's delegate it to another method, and just write their core functionality, for the moment.
def peek(self):
    self.refill_head()
    return self.head[-1]

def pop(self):
    self.refill_head()
    return self.head.pop()

And this is the point of the exercise, refill_head(). When we get the first call to pop or peek, we need to retrieve the first value stored in the tail queue. To do that, we can simply move all data stored in that stack to the head stack. As a bonus we have also all the other data ready to be used for pop and peek. Remember that the tail stack is accessed only for pushing data, so it won't mind at all of what there is inside it. We can safely empty it any time we need more data from head. But beware, we can move it only when head is empty, otherwise we would mess up with the elements' order.
def refill_head(self):
    if not self.head:  # 1
        while self.tail:  # 2
            self.head.append(self.tail.pop())
1. If the head is not empty we can (actually, we must) delay the refilling.
2. Otherwise we move all the data from tail to head. Being both stacks, the order is respected.

No need for extra testing, the solution got accepted, and I pushed unit test and python script to GitHub.

Go to the full post

Functional interfaces

In Java everything that is not a primitive is an object. OK, but what about functions? Introducing a support for functional programming in Java 8 led to the need of give an answer to this question, and the designers decided to use the ad-hoc solution of functional interfaces.

A functional interface is a Java interface that has only one abstract method. It is a good idea to annotate it as FunctionalInterface so that it's clear what it is mean for, and let the compiler to check if it is alright. However it is not mandatory.

We can define and use any interface we like for use it in this way, but we should save to ourselves, and to our code clients, some pain using when possible the standard one, define in the java.util.function package.

Let's see a few examples.

Predicate

The predicate functional interface is defined as:
@FunctionalInterface
public interface Predicate<T> {
    boolean test(T t);

    // ...
}
I can use it if I have to write a method filter() that gets in input a list of data and filter them accordingly some requirements decided by the user.
public static <T> List<T> filter(List<T> data, Predicate<T> p) { // 1
    List<T> results = new ArrayList<>();
    for (T t: data) { // 2
        if (p.test(t)) {
            results.add(t);
        }
    }
    return results;
}
1. It takes as input a list of T and a predicate on T.
2. For each element in the list, if it pass the test defined by the caller, I add it to the list I return.

Here is a piece of code that uses the filter() method:
List<String> result = FunctionalInterfaces.filter(Arrays.asList("", "x", ""), (s) -> !s.isEmpty());
I create a list of strings and I pass it to filter() alongside a lambda function, that has to match with the expected Predicate, so the lambada input has to be a String - I could state it explicitly, but I can also leave it implicit - and it should return a boolean.
The result is a list containing just one string, namely "x".

Consumer

It is defined as:
@FunctionalInterface
public interface Consumer<T> {
    void accept(T t);

    // ...
}

Here I use it in a forEach() method that let the user specify what it should do with each element of a List:
public static <T> void forEach(List<T> data, Consumer<T> c) {
    for(T t: data) {
        c.accept(t);
    }
}
I use this forEach() to keep calculate the length of all the strings in a list:
List<String> data = Arrays.asList("Functional", "Interfaces", "in", "Java 8");
consumed = 0;
FunctionalInterfaces.forEach(data, (s) -> consumed += s.length());
assertThat(consumed, is(28));
Again, note that here the type of the lambda parameter s is inferred from T, type of the list passed to forEach() and used to determine the actual Consumer functional interface to which the lambda should refer to.
Interesting to note how the consumed variable is captured by the lambda without the need of any explicit action by programmer. This mechanism works fine only for non-local variables. Local variables can be captured only if final (at least effectively so).

Function
@FunctionalInterface
public interface Function<T, R> {
    R apply(T t);

    // ...
}

This map() method maps objects of a given type to another one, delegating to the caller the job of specifying how to do the conversion.
public static <T, R> List<R> map(List<T> data, Function<T, R> f) {
    List<R> result = new ArrayList<>();
    for(T t: data) {
        result.add(f.apply(t));
    }
    return result;
}

I use it here to convert a list of strings in a list of integers:
List<String> data = Arrays.asList("Functional", "Interfaces", "in", "Java 8");
List<Integer> result = FunctionalInterfaces.map(data, (s) -> s.length());
The compiler does a lot of job for us here. Since map() is templatized by T, the template type of the input list, and R, from the returned list, it figures out that s, passed to the lambda, is a String, so it should return an object of the class returned by the String method lenght(), that is an int, boxed to Integer.

IntBinaryOperator
@FunctionalInterface
public interface IntBinaryOperator {
    int applyAsInt(int left, int right);
}
In the example for Function, boxing the integers was an expected behavior. We need them as objects since we want them in a collection.
Other times, boxing and unboxing could be just a useless cost that we could avoid using a special functional interface like this one, that works with lambdas working on primitives.

This combine() method works on primitive integers and don't want to pay any extra costs for objects
public static int combine(int[] data, IntBinaryOperator op) {
    if(data == null || data.length != 2) {
        return 0;            
    }
    return op.applyAsInt(data[0], data[1]);
}

I could use it to decide dinamically what kind of operation applying to a couple of integers, accordingly to the lambda passed.
int result = FunctionalInterfaces.combine(new int[] {6, 7}, (a, b) -> a * b);

Supplier

@FunctionalInterface
public interface Supplier<T> {
    T get();
}

We don't have anything to pass to the lambda, and we blindly let it to create an object of the specified type.
public static <T> T aFactory(Supplier<T> s) {
    return s.get();
}

Here is a trivial example:
String result = FunctionalInterfaces.aFactory(() -> "Hello");

I pushed to GitHub a class FunctionalInterfaces with the static method having a reference to functional interfaces as parameter and a JUnit tester that shows how I called them.

Reference: Java 8 in action, section 3.4 Using functional interfaces.

Go to the full post

CodeEval Longest Common Subsequence

The CodeEval problem #6 is commonly used as an example to introduce to Dynamic Programming.
We have two strings, we want to know how many and which characters they have in common.

On CodeEval we are given a sample, I added a second test, shorter, that helped me better to develop my python script:
def test_provided_1(self):
    self.assertEqual('MJAU', solution('XMJYAUZ;MZJAWXU'))

def test_simple(self):
    self.assertEqual('HI', solution('AHOI;HI'))
Solving this problem with DP comes quite naturally. I have two strings, I put it one vertically, the other horizontally, I leave top row and left column set to zero, just to simplify the calculations, and then I scan the matrix from top-left to right, row by row, since I get to the right-bottom corner.

Cell by cell, I check if the characters in the two strings match or not. In case of matching, I get the value of the cell one step to the left, one step over, and increase it by one. Otherwise I get the values from the cell over, the cell to the left, and I keep the highest value between the two.

Here is the matrix for my simple test above:
-  -  H  I
- [0, 0, 0]
A [0, 0, 0]
H [0, 1, 1]
O [0, 1, 1]
I [0, 1, 2]
The bottom right cell tells us that there are two matches. The algorithm I am using makes a bit more laborious to get which are them. Well, not in this case, since the shorter string has size two, we already know that "HI" is the longest common subsequence. But generally speaking, we have to backtrack the job we have done, starting from the bottom-right, observing where there is a change of value in a cell compared to its neighbors, moving up to find the next border inside the matrix.

The resulting python is quite terse, so I think could help to better understand the thing.

First part, generating the matrix. In ver and hor I put the two strings. Think that ver is "AHOI" and hor is "HI", from the example above.
t = [[0 for j in range(len(hor)+1)] for i in range(len(ver)+1)]  # 1
for i in range(len(ver)):  # 2
    for j in range(len(hor)):
        t[i + 1][j + 1] = t[i][j] + 1 if ver[i] == hor[j] else max(t[i+1][j], t[i][j+1])
1. Create an all-zero bidimensional list sized +1 of the respective referenced string.
2. Loop on all the cells, and apply the algorithm that I described above. Notice that the indexes i,j are 0-based, so they are OK when referring to the strings in ver and hor. When working on the matrix, however, I adjust them adding one to refer to the current cell, row and column. I guess this is the most confusing part. Maybe following the debugger stepping in the code could help a better understanding.

Now I prepare for backtracking. Let's set a few variables:
i, j = len(ver), len(hor)  # 1
result = [None] * t[i][j]  # 2
cur = -1  # 3
1. I let i and j refer to the bottom-right cell.
2. I am going to put the result in this list. I know the size, it is stored in the bottom-left cell, I initialize each element to None, missing any better default.
3. Since I am backtracking. I am going to put the first character in the last position, and so on.

And this is the backtracking loop. Notice that I changed the convention for i, j. Here it looked to me more natural using i and j without adjustment to refer to the cells in the matrix.
while i > 0 and j > 0:
    if t[i][j] == t[i-1][j]:  # 1
        i -= 1
    elif t[i][j] == t[i][j-1]:  # 2
        j -= 1
    else:
        result[cur] = ver[i-1]  # 3
        cur -= 1
        i -= 1
        j -= 1
1. Compare the current cell with the one above. If they are the same, I can move upward.
2. I couldn't move upward, I try to move leftward.
3. I am on the verge of changing values. This means that the letter in the string (pay attention to the index, adjusted by subtracting one!) is part of the subsequence. Store it in the result, and move on.

Finally we have just to convert the result from list to a string, the usual pythonic way is a join on an empty string.

The script has been accepted with full marks. It was just a bit slow, and it consumed lot of memory. So I decided to port the code to C++, task that was easy and rewarding. Just a few minor changes, besides the obvious differences due to the languages grammars, for instance, I found easier in the backtracking to write the result backward and the reverse it by the STL function.

For full reference, I put the unit test and the python script on GitHub.

Go to the full post

Hackerrank Stacks: Balanced Brackets

This HackerRank problem is an interview classic. I have got in input a string containing only brackets, I have to ensure they are correctly balanced. It is very easy if you get you should use a stack to process them. Here I implement a solution in Python, that is interesting because we should make use here a couple of pythonic constructions.

Besides the provided samples, I added a missing important element to my unit test.
def test_provided_1(self):
    self.assertEqual(True, solution('{[()]}'))

def test_provided_2(self):
    self.assertEqual(False, solution('{[(])}'))

def test_provided_3(self):
    self.assertEqual(True, solution('{{[[(())]]}}'))

def test_too_close(self):
    self.assertEqual(False, solution('}}'))
In the last one I have only closing brackets, that's obviously a False. I feel that explicitly setting a test on this case helps to get sooner to the solution.

The idea is pushing the opening brackets on the stack and popping an element when we are examining a closing bracket. If there is no matching bracket in the stack or, worse, the stack is empty, the sequence has to be rejected.

Here is my implementation:
def solution(data):
    matches = { '(': ')', '[': ']', '{': '}' }  # 1

    stack = []  # 2
    for c in data:  # 3
        if c in matches.keys():  # 4
            stack.append(c)
        elif not stack or c != matches[stack.pop()]:  # 5
            return False
    return True if not stack else False  # 6
1. I use a dictionary to store the opening brackets as keys and the closing ones as values. That helps keeping the code compact.
2. A plain list works a as a stack.
3. Looping on the characters in the input data. Notice that there is no error handling whatsoever. This is a typical interview code, robustness would be added on demand.
4. First use of the dict in (1), I compare the character against its keys to check if it is an opening bracket. If so, I push it in the stack.
5. Otherwise, I expect it to be a closing bracket. Before popping from the stack, I should ensure it is not empty, then I use the element in the stack as key for the dict in (1) to retrieve the matching bracket, and I compare it against the actual character.
6. I get to the end of the input data without detecting any mismatch. So I return true. But only if the stack is empty, i.e., all the opening brackets have been consumed.

Solution accepted by HakerRank, test case and python script pushed to GitHub.

Go to the full post

CodeEval Detecting Cycles

Getting in input a list of integers, we should identify where a cycle starts, and return it.
It's the CodeEval problem #5, and it is easier than it looks, because, even if it is not explicitly said, the passed samples suggest that the numbers are present only once, if their are not in a cycle. Maybe we should think of them as labels in a graph, and the sequence could represent the result of a traversal algorithm that enters in an infinite loop.

I have converted the samples in python tests, I added one more just because I felt bad of risking an exception if the detected cycle was interrupted in the input sequence.
def test_provided_1(self):
    self.assertEqual('6 3 1', solution('2 0 6 3 1 6 3 1 6 3 1'))

def test_provided_2(self):
    self.assertEqual('49', solution('3 4 8 0 11 9 7 2 5 6 10 1 49 49 49 49'))

def test_provided_3(self):
    self.assertEqual('1 2 3', solution('1 2 3 1 2 3 1 2 3'))

def test_tail(self):
    self.assertEqual('1 2', solution('1 2 3 1 2'))
For how the test case look, we simply have to search for the first repetition, and then count how many elements fit in the cycle. I assumed, see the last test, that we should return only the elements in the cycle we are sure are repeated.

The core of my solution is a triple (!) for loop:
for i in range(len(data)-1):
    for j in range(i+1, len(data)):
        if data[i] != data[j]:
            continue

        size = min(j - i, len(data) - j)  # 1
        for k in range(1, size):
            if data[i+k] != data[j+k]:  # 2
                size = k
                break
        return ' '.join(data[i:i+size])
return ''
1. I loop until I find two matching numbers. At this point I ensure that this is really a loop, checking that there is a match between the following numbers on the left and on the right. I added the extra check on the list size to avoid falling off the end.
2. When I complete the check, maybe finding a spurious element, I stop looping and return the found cycle.

Solution accepted, unit test and python script pushed to GitHub.

Go to the full post

Execute around pattern and try-with-resources

Say that you have to implement in Java 8 a functionality where there is a lot of boilerplate. Instead of duplicating code in sibling methods, we can try to create a single method where the changing behavior is passed by parameter as a lambda function.

Reduced to the minimal term, here is the example of a method that we could refactor using the execute around pattern. The code is made more interesting by using the try-with-resources statement available in Java since version 7.
public static String processFileLimited(String filename) throws IOException {
    try (BufferedReader br = new BufferedReader(new FileReader(filename))) { // 1
        return br.readLine(); // 2
    }
}
1. We try to create a BufferedReader. At the end of the block, even in case of an exception, Java takes care of closing the resource. Neat.
2. This is the behavior we want to be parametrized.

Lambda is here our friend. Only a minor nuisance, we can't use a standard functional interface because here we should let our lambdas throw an IO exception, and in Java this should specified in the method signature.
@FunctionalInterface
public interface BufferedReaderProcessor {
    public String process(BufferedReader br) throws IOException;
}
Given this interface, we can refactor the above method in this way:
public static String processFile(String filename, BufferedReaderProcessor p) throws IOException {
    try (BufferedReader br = new BufferedReader(new FileReader(filename))) {
        return p.process(br);
    }
}
The boilerplate is there unchanged, the actual behavior has been externalized. It should be user resposibility to provide something sensed to be done in. Here is a couple of different ways processFile() could be called:
ExecuteAround.processFile(FNAME, (BufferedReader b) -> b.readLine());
ExecuteAround.processFile(FNAME, (BufferedReader b) -> b.readLine() + '-' + b.readLine());
As second parameter, I pass a lambda that in its body uses the BufferedReader to perform its job. A string is (implicitly) returned.

I have divided the code between the actual ExecuteAround class and its unit test. You can find both on GitHub.

Code and ideas are based on Java 8 in action, section 3.3 Putting lambdas into practice: the execute around pattern.

Go to the full post