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: Peculiar balance

In the past few months Google pulled “Matrix” on many Python and Java engineers: if you google terms like “python lambda” you might get pulled into “The Matrix” as well…
To me it happened on a Saturday around midnight, I googled something related to Python and suddenly the search page collapsed and became dark. There was a single sentence that said something like:
 
“You speak our language”.
 
and then it invited me to participate in a series of code-challenges.
 
As a veteran member of CodeEval I gladly stepped into the Matrix and started solving different challenges. All was good until I ran into the following: 

 

Peculiar balance
================
Can we save them? Beta Rabbit is trying to break into a lab that contains the only known zombie cure – but there’s an obstacle. The door will only open if a challenge is solved correctly. The future of the zombified rabbit population is at stake, so Beta reads the challenge: There is a scale with an object on the left-hand side, whose mass is given in some number of units. Predictably, the task is to balance the two sides. But there is a catch: You only have this peculiar weight set, having masses 1, 3, 9, 27, … units. That is, one for each power of 3. Being a brilliant mathematician, Beta Rabbit quickly discovers that any number of units of mass can be balanced exactly using this set.
To help Beta get into the room, write a method called answer(x), which outputs a list of strings representing where the weights should be placed, in order for the two sides to be balanced, assuming that weight on the left has mass x units.
The first element of the output list should correspond to the 1-unit weight, the second element to the 3-unit weight, and so on. Each string is one of:

“L” : put weight on left-hand side
“R” : put weight on right-hand side
“-” : do not use weight

To ensure that the output is the smallest possible, the last element of the list must not be “-”.
x will always be a positive integer, no larger than 1000000000.

Test cases
==========
Inputs:
    (int) x = 2
Output:
    (string list) ["L", "R"]
Inputs:
    (int) x = 8
Output:
    (string list) ["L", "-", "R"]

 
After playing a bit with numbers, I figured out my strategy:
 
Given a number x I’ll try to find the minimal integer y >=x so that y can be presented as a sum of distinct powers of 3.
I say “distinct” because the coefficients for any power of 3 can be either 0 or 1.


Example:
A good solution: 12 = 0*3^0 + 1*3^1 + 1*3^2
A bad solution: 12 = 3*3^0 + 0*3^1 + 1*3^2


The second solution is bad because one of the coefficients is 3.


So I need to find the smallest y that respects this rule. Once I’ve found such a y, and since I already know how to represent it as a series of distinct powers of 3 – it’s a good candidate for ‘R’.
Now I still need to figure out how to represent the difference y-x as a “series of distinct powers of 3″ and I’m done.


As you might already started suspecting: we cannot find such a representation for any y-x. And indeed, in case we fail, we’ll have to look for the “next y” and on and forth.
The code looked like this:

from itertools import combinations
 
def answer(x):
    """
    Main logic:
    find the closest number y >= x so such that:
    1. y is a sum of powers of 3
    2. x + z = y where z is sum of numbers, each of which is a power of 3
    3. z will be decomposed to "L" and y will be decomposed to "R" in build_list()
    """
    next = find_next_sum_of_powers(x)        
    left = represent_as_powers(next - x)   
    while list(set(left)) != left: # meaning we have the same item more than once in "left"
        # look for the next "sum of powers" and try to use it instead
        next = find_next_sum_of_powers(next + 1)        
        left = represent_as_powers(next - x)   
    right = represent_as_powers(next)
    return build_list(left, right)
 
 
def find_next_sum_of_powers(x):
    """
    Given a number x, find the closest number y
    such that y >= x and y is one of the numbers 
    returned by get_list_of_sums() and there is no number z,
    which is also returned by get_list_of_sums() such that:
    y > z > x
    """
    next = find_next_power(x)
    if x == next:
        return x
    if x <= next // 2:
        sums = []
        for list_of_sums in get_list_of_sums(x):
            for sm in list_of_sums:
                if sm not in sums:                
                    if x == sm:
                        return x                
                    if sm - x in sums:
                        return sm
                    sums.append(sm)
    else:
        return next
 
def is_power_of_3(x):
    """
    Checks if x is a power of 3
    """
    n = 0
    b = 0
    while n < x:
        n = 3 ** b    
        b += 1
    return n == x
 
 
def get_list_of_sums(x):
    """
    Generates a list of sums of powers of 3:
    1, 3, 4, 9, 10, 12, 13...
    4 = 3 + 1; 10 = 9 + 1; 12 = 9 + 3; 13 = 9 + 3 + 1; ...
    """
    workset = []
    for i in gen_next_power():         
        if i > x:
            break        
        workset.append(i) 
    res = []
    for i in range(len(workset)+1):
        for j in combinations(workset, i):
            res.append(j)      
            yield map(sum, res[1:])
 
def gen_next_power():
    """
    Generator for powers of 3
    each iteration will get the next power
    """
    pow = 0
    while True:
        yield 3 ** pow
        pow += 1
 
 
def find_next_power(x):
    """
    Given a number x find the closest 
    power of 3, y such that y > x and there
    is no power of 3, z such that  x < z < y
    """
    if x == 1:
        return x
    t = 3
    while t < x:
        t *= 3
    return t
 
def represent_as_powers(num):
    res = []
    while num > 0:
        t = find_next_power(num)
        if t > num:
           t /= 3
        res.append(t)
        num -= t
    return res[::-1]
 
def build_list(left, right):
    stop = right[-1]
    res, i = [],  0
    while 3 ** i <= stop :
        if 3 ** i in left:
            res.append("L")
        elif 3 ** i in right:
            res.append("R")
        else:
            res.append("-")
        i += 1
    return res
 
 
Now, this works. Only problem is – this approach of trying different y’s could get really expensive.
In fact, if I limited the number “retries” to a small number – I could get almost all the test-cases to pass – all but one…
 
But I wasn’t ready to give up :)
So I started googling and found this post which provided a good direction but to be honest – I didn’t understand:
1. how balanced ternary representation helps to solve our problem
2. how to translate from ternary representation to balanced ternary


These questions are coupled, and it took me some extra-reading to figure it out and what I’d like to do now – is save you the time that I spent, by trying to explain it a little better than that post, wikipedia and other resources I ran into during my investigation.


Let’s start with the second question which is pure technical, by comparing numbers in different bases, we’ll represent “balanced” with 1,0,-1:
decimal      1    2      3     4      5          
ternary      1    2      10    11     12        
balanced     1    1-1    10    11     1-1-1
Trying to follow up on the “balanced” gave me a headache… but after playing with it for a bit, and reading some search results like this answer (which explains how to add numbers in balanced-ternary form), made things much clearer:
in “balanced” we’re still using ternary-base, and the numbers 1/0/-1 are simply the coefficients of the respective power of 3. Lets demonstrate:
2 = 1*3^1 -1*3^0 = 1-1
3 = 1*3^1 + 0*3^0 = 10
4 = 1*3^1 + 1*3^0 = 11
5 = 1*3^2 -1*3^1 -1*3^0 = 9 – 3 – 1 = 1-1-1
etc
 
Once you realize the answer to #2 it’s only another small step to understand the connection to the code challenge:
Given that number x, once we find its balanced-ternary representation we can express it as a… sum of distinct powers of 3!
Now we have only a small obstacle: this sum has positive and negative elements – how do we handle it?
 
The challenge was to balance weights, which means that instead of “subtracting” the left side we can “add” the weight to the right side – like balancing equations!
The meaning of this is that the balanced-ternary form is actually the answer we’re looking for, lets take the number 5 from the previous example:
 
5 = 1*3^2 -1*3^1 -1*3^0 = 9 – 3 – 1 = 1-1-1
 
in the form of our answer – we’re looking at the result from right to left, which means that
 
1-1-1 = [-1, -1, 1] = -1*3^0 -1*3^1 + 1*3^2
and the way it helps us solving the problem is by using ‘R’ as 1*3^2 and balancing it with ‘L’ by adding to ‘L’ 1*3^0 + 1*3^1 which ends up as simply replacing letters in the reversed version of the balanced-ternary form
 
from: [-1, -1, 1]
to:   [L,  L,  R]
 
Further, if we have a zero in the balanced-ternary form it means that neither L nor R should add the respective power of 3, so we can simply replace any zero with “-” (dash).
 
We’re now ready to look at the code:
 
def answer(x):
    return to_balanced(to_ternary(x))
 
def to_ternary(x):
    """
    convert decimal into ternary
    """
    res = ""
    while x > 0:
        res = str(x % 3) + res
        x /= 3
    return int(res) 
 
def to_balanced(t):
    """
    convert ternary number into balanced-ternary
    and then to L/-/R representation
    """
    res = map(int, str(t))[::-1] # iterating the digit from right --> left
    for i in range(0, len(res)):
        # zeros will remain zeros and ones remain ones
        # the only thing we need to convert is 2 into +- (== +1-1)
        if res[i] == 2:
            res[i] = -1
            res = inc(res, i + 1)
 
    # convert from (1,0,-1) representation to (R,-,L)
    return ['-' if x == 0 else ('R' if x == 1 else 'L') for x in res]
 
 
def inc(arr, ind):
    """
    calculate the carryover
    """
    if len(arr) == ind:
        arr += [1] # prepend the last carryover
    elif arr[ind] == -1:
        arr[ind] = 0
    elif arr[ind] == 0:   
        arr[ind] = 1
    elif arr[ind] == 1: 
        arr[ind] = -1
        arr = inc(arr, ind + 1)
    else: # arr[ind] == 2
        arr[ind] = 0
        arr = inc(arr, ind + 1)
    return arr
Needless to say that this solution worked perfectly.




WALP (We Are Lazy People)

Laziness

WALP

Yesterday, one of my colleagues reminded me that I once said that I’m going to do the minimum to maintain project X. Project X is not its real name but maybe I should back up a few steps and start with providing some background:
one of the things that happens at Netflix pretty often is that teams change, responsibilities shift and as a result projects are handed off between teams. Project X is such project, it was written long time ago (more than two years back which is basically forever in our industry) by a guy that now manages another team, and was handed off to a team that currently doesn’t exist, and when that team was disassembled I was given this project.

So yesterday, the guy who wrote project X reminded my that I said I’m planning to do the minimum to maintain it. I was surprised because one of the things that doesn’t fit me is to come up with such a statement, and then I remembered: WALP.

Some people will describe it like this, but I just rather say that I’ll do the maximum to be in a condition where I have to do the minimum in order to maintain an existing project. Sounds confusing ? well, not really…

Project X was written in Python and had two major components (class-files) which became monolithic: functions that perform multiple tasks (which goes against SRP) with hundreds lines of code, a few levels of nested loops – complicated to follow and understand, a nightmare to debug and horror to test.

So, in order to be able to “do the minimum to maintain it” one of the first things I did was refactoring these two classes: breaking the logic into smaller functions, minimizing the number of arguments, working according to DRY and SRP, renaming variables and functions, adding unit-tests and while I was “shaking the tree” a few bugs were discovered and fixed as well.

There wasn’t much “fun” in it, it’s not like writing a project from scratch which is really tempting to most engineers but usually is a bad idea. It’s tempting because you think “I’ll get it right this time” or “I can do much better than that” and let’s be honest: when you’re maintaining someone else’s code – it will never “belong” to you, that other guy will always get the credit for writing this project – even if the code changed so much that it doesn’t look anything like it originally did…

Back to the story, the refactoring paid off, and it wasn’t even in the long term:
* a few bugs were found and fixed
* bugs that were discovered later on, were easier to debug and fix
* I had to write a few additional features, all were implemented very quickly, easily, without any pain and were easy to test

So yes, I AM lazy, and I’m willing to work really hard to sustain it…

How I wrote FeedMe

Breastfeeding app

A few days ago I released the first version of FeedMe, a small Android app I wrote over the last few weekends. I promised my wife to write it after our first daughter was born and we found ourselves keeping tracks of her feedings using notes that were all over the house. After a few nights that we woke up, the baby was crying, and we couldn’t find the notes anywhere around (had to go to the living room, kitchen etc) I’ve had it and decided to build this side project.

By the time I got to it, our daughter was already a few months old, and she slept through the night and there was no real need, but I promised my wife that for the second one – I’ll make sure to build it in time.

And I did!

Our second daughter was born a couple of days ago, only a few days after I released the app.

Needless to say that the app is free, and I intend to keep it so, and not only that: I plan to open source it and I’ll appreciate if other hackers will decide to contribute, add features, improve the code, or do whatever they want with it.

I will release the code together with other Bitbucket and GitHub projects, as soon as I fix the code a bit and make it presentable (I did some quick & dirty hacking in order to make it work cause I was short in time and I don’t have experience developing apps).

I’d love to get your feedback, but please don’t send feature-requests because I got plenty features & ideas I want to implement but I lack the time to do so…

Facebook interview questions

FB

Last week a friend asked me to help him prepare for a job-interview at FB. The first thing I did was pointing him to Cracking the Coding Interview which provides an excellent overview of all the main subjects an Engineer might be asked during an interview. My recommendation was to take the time and go through each and every chapter, and try to solve the questions. It’s very important not to “cheat” and try hard to solve them by yourself – otherwise you won’t improve!

Another important thing is, in case you weren’t able to solve a question and you checked out the answer – DO NOT try to memories it! instead, go on and continue solving other questions, and after a few days, try again to solve that same question. You might be surprised to find out that even though you saw the answer – it’s not always trivial to re-write it. Further, this is a good exercise that sharpens another important skill: being able to write code that expresses the algorithm we have in mind.

There’s plenty of good information available online, just Google it and you’ll find excellent blog posts such as this one, and many others.

Another smart thing my friend did was to go over job-interview websites and forums and copy questions that other candidates wrote they were asked during their interviews in FB. The following is a list of such questions:

  1. Calculate the square root of a double
  2. Given n intervals [si, fi], find the maximum number of overlapping intervals.
  3. Print all the paths from root to every leaf in a binary tree.
  4. Print the sum of all the numbers at every vertical level in a binary tree
  5. Given a set of n jobs with [start time, end time, cost] find a subset so that no 2 jobs overlap and the cost is maximum ?
  6. Given 1 trillion messages on FB and each message has at max 10 words, how do you build the index table and how many machines do you need on the cluster to store the index table ?
  7. Given a set of n jobs with [start time, end time, cost] find a subset so that no 2 jobs overlap and the cost is maximum ?
  8. Given an input array and another array that describes a new index for each element, mutate the input array so that each element ends up in their new index. Discuss the runtime of the algorithm and how you can be sure there won’t be any infinite loops.
  9. Find all the anagrams in an array of strings
  10. Combinations(n, k) – print all combinations of k out of n items
  11. Printing a binary tree L-R,
  12. Implementing a comparator function to sort files based on a certain naming convention.
  13. Implement a LRU cache
  14. Design FB newsfeed
  15. How would you query for all the Places near a given coordinate? The focus is on how to scale this to a large number of places while keeping response time to within acceptable user expectations
  16. Given a list of words, group anagrams.
  17. Find all 3 items that sum to 0 in an array.
  18. Write a function that calculates input strings with operators +,-,*,/ eg. “5+5*6″ should output 35
  19. Printing the nodes of a linked list in reverse
  20. Finding the longest palindrome in a given string
  21. Finding maximum subarray sum (similar to Kadane’s Algorithm) with the constraint that two numbers in the array that form the max sum cannot be next to each other
  22. How do you use Facebook app and what are the problems with it? How would you fix it?
  23. Design a Facebook travel app
  24. designing a system to do spam detection work and describing it in a huge flowchart, as might be done in an early but detailed product planning session. Be prepared to think on large scales.
  25. Write a palindrome-checking function
  26. Print a tree, level by level.
  27. Write all solutions for a^3+b^3 = c^3 + d^3, where a, b, c, d lie between [0, 10^5]
  28. Print a list in reverse
  29. Compute maximum profit for buying selling a stock given an array of prices for n days.
  30. Check if two binary trees are Isomorphic
  31. How would you come to an agreement if you and another senior level engineer couldn’t agree on a technical design?
  32. Write a function that takes 2 arguments: a binary tree and an integer n, it should return the n-th element in the inorder traversal of the binary tree.
  33. Add up two big integers represented in arrays.
  34. Design a system to support Facebook status update.
  35. Design the recommendation system for search keywords
  36. Given 2 very large numbers, each of which is so large it can only be represented as an array of integers, write a function to multiply them.
  37. Write a function to display a JSON string in pretty format.
  38. Write a function to check if polygon is simple based on given list of points
  39. Function to compute the number of ways to climb a flight of n steps. Taking 1, 2, or 3 steps at a time. Do it in Linear time and constant space. Example:
    n = 3.
    1 1 1
    1 2
    2 1
    3
    Ans = 4
  40. Interweave a linked list. Do it in Linear time and constant space.
    Input: A->B->C->D->E
    Output: A->E->B->D->C
  41. Given a dictionary based simple password, create all possible (special character) passwords based on a provided mapping.
    Input: face
    Map: {a -> @, 4, A}
    Output: f@ce, f4ce, fAce
  42. Get numeric number out of a roman string, linear time
    Given: mapping I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000
    Input/Output:
    II = 2, III = 3, IV = 4
    VI, VII, VIII
    IX = 9
    XL = 40,
    XLIX = 49
  43. Merge ‘k’ sorted arrays, each array may have max ‘n’ elements
  44. What would you change in Facebook?
  45. Given a sorted array, write a program to decide if two elements sum up to a third.
  46. Determine the 10 most frequent words given a terabyte of strings

Good Luck! 

Grails is Groovy!

Grails is a framework that uses the advantages of Groovy, a dynamic type language which is almost a superset of Java, and the principle of “convention over configuration” in order to supply a very easy to use and quick to develop web-applications. It relies on the JVM and Spring as well as some other technologies that are out of scope for this post (Hibernate, templates etc).

Grails is based on MVC design pattern, in case you’re not familiar with it yet – you should, but until you do I’ll give you the highlights:
MVC stands for Model-View-Controller, which separates concerns and thus eliminates dependencies between the data (model), display (view) and business logic (controller). The controller is the entry point to the app, the HTTP request is dispatched to the relevant controller which drive the data from the Model, and might process it using one or more of the Service classes and will choose the proper View for display. The View doesn’t have to be strictly “display” it could also be JSON/XML or any other representation of the data.

In the rest of this post we’ll create the helloworld example and run it – with one major added value: I’ll help you avoid the pitfalls that I ran into. Ready ?

If you already have JDK installed – good for you, if not, you’ll have to install it first (not the JRE!)
It took me less than 10 minutes to download, install and run my first “Hello World!”
All you have to do is:
1. extract the zip file into the location you want it to be
2. add the environment variable GRAILS_HOME – make it point to that folder
3. update the PATH variable to PATH="$PATH:$GRAILS_HOME/bin"

After we’re done with the installation, navigate to the location where you want the project to be created (command prompt if you’re a windows user) and type:
grails create-app hello
after a few seconds, a new directory will be created by the surprising name of…
yes you guessed right: “hello” (convention over configuration anyone?)
Lets get in by typing cd hello and create our first controller. Can you guess the command ?
grails create-controller hello
if you missed this one – don’t be upset, you’ll get the next one.
One of the lines that were printed after the last command should have been:
Created file grails-app/controllers/hello/HelloController.groovy
Open a text-editor and edit HelloController.groovy:

package hello
class HelloController {
 
    def index() {
        render "Hello World!"
    }
}

That’s it! now, can you guess how to run our app ? that’s right:
grails run-app
it starts running, looking good, it even prints:
Server running. Browse to http://localhost:8080/hello
which seems awesome, but before we get to copy the URL and paste it into the browser…

*** java.lang.instrument ASSERTION FAILED ***: "!errorOutstanding" with message
transform method call failed at ../../../src/share/instrument/JPLISAgent.c line:
844
Exception in thread "main"
| Error Forked Grails VM exited with error

Hey! that’s not a nice thing to do!
Don’t worry guys, I hear you, here’s how we can fix it:
go to: hello/grails-app/conf
and edit the file BuildConfig.groovy – comment out the following section using /* … */ like this:

/*
grails.project.fork = [
// configure settings for compilation JVM, note that if you alter the Groovy version forked compilation is required
// compile: [maxMemory: 256, minMemory: 64, debug: false, maxPerm: 256, daemon:true],
// configure settings for the test-app JVM, uses the daemon by default
test: [maxMemory: 768, minMemory: 64, debug: false, maxPerm: 256, daemon:true],
// configure settings for the run-app JVM
run: [maxMemory: 768, minMemory: 64, debug: false, maxPerm: 256, forkReserve:false],
// configure settings for the run-war JVM
war: [maxMemory: 768, minMemory: 64, debug: false, maxPerm: 256, forkReserve:false],
// configure settings for the Console UI JVM
console: [maxMemory: 768, minMemory: 64, debug: false, maxPerm: 256]
]
*/

Now for most of the readers it should work: if you’ll grails run-app paste the following URL into your browser:
http://localhost:8080/hello
you should see the link to the controller that prints “Hello World!

But… if you’re like me… all the wrong things WILL happen: another issue I had was that port 8080 was already in use. To work around that, you can run your app on a different port:
grails -Dserver.port=8090 run-app

That’s it, now you should definitely see in your browser the following page:

Hello World Controller

Hello World Controller

and once you’ll click the controller-link, you’ll receive a sweet “Hello World!” in Grails.

Update: there is actually an open bug for the issue described above, and a fix should be deployed on the next release (Grails 2.3.3)

A simple calculator in Ruby

Today I ran (again) into the following question:

  • Write a function that doesn’t use eval that calculates input strings with operators +,-,*,/ eg. “5+5*6+4/2″ should output 37

The first time I ran into this question I designed a solution, in Java, which had a SimpleCalculator class, and enam Operation which supported the four basic arithmetic operations: +-*/ each of which had an apply method etc. Very object oriented.

When I read this question today, I figured that it would be a nice exercise to do in Ruby – a few minutes later the result spread, elegantly, over less than 20 lines of code (and I bet that a professional Rubiest can do it in less)!

def is_number? expr
  return false if expr.nil?
  expr = "#{expr}"              # we need this condition in case the expr is a number
  expr.match /^(\d+|\d+\.\d+)$/ # since match() is defined only for strings
end
 
def calc(expr)  
  return expr.to_i if is_number? expr
  expr.gsub!(" ","") # clean the string from whitespaces
  # pay attention to the order: + and - should come before * and /
  # can you figure out why ?
  arr = expr.split /\+/
  return arr.inject(0){|x,y| calc(x) + calc(y) } if arr.size > 1
  arr = expr.split /\-/  
  return arr.inject(0){|x,y| calc(x) - calc(y) } if arr.size > 1
  arr = expr.split /\*/
  return arr.inject(1){|x,y| calc(x) * calc(y) } if arr.size > 1
  arr = expr.split /\//
  return arr.inject   {|x,y| calc(x) / calc(y) } if arr.size > 1
end
 
puts calc("5+5* 6+4/2.0")
#output 37

Do you have a better/shorter/more elegant solution ?
Please post it in the comments section!

Inheritance overflow…

Been fiddling with Java lately when I ran into the following cute quiz about inheritance.

Reading some articles about what’s Good/Bad in Java – I ran into the following code from an article called why Java sucks?:

class Boo{}
class Buzz extends Boo{}
 
class Play{
 
    static void foo(Boo b){
        System.out.println("in foo(Boo b)");
    }
 
    static void foo(Buzz b){
        System.out.println("in foo(Buzz b)");
    }
 
    public static void main(String...args){
        Boo b = new Buzz();
        foo(b);
    }
}
  • What would you think will be printed ?
  • Do you know why ?

Answer: variable b is declared as a reference to object of type Boo during compilation, and that’s why foo(Boo b) is chosen over the “more intuitive” option.

The reason that it works this way is that Java (as well as many other OO languages) is single dispatch. There are other languages like Common Lisp that supports “multiple dispatch”: the decision which version of a method will be called is based both on the class of the object as well as the run-time types of the arguments!

By the way, “multiple dispatch” behavior can be achieved in “single dispatch” Languages by using the Visitor pattern (described in “design patterns” book).

I started a list of my own about the things I like/don’t-like in Java and here’s the outcome:

Plus Minus
write once – run anywhere still slower than C++
Many good libraries (both java/javax as well as 3rd parties) no multiple inheritence
Garbage collection horrible character escaping when using regex
boxing can’t pass methods as a parameter
inner classes + anonymous classes handling primitives differently (why not treat them as objects?)
reduces boilerplate code every version (generics, try with resources, filters) still too verbose (open a file…)
If inner class wants to use a variable of the parent – it must be declared final
checked exceptions can be a pain with interfaces

The Free Electron Legend

free-electron

A few days ago I read the single most productive engineer that you’re ever going to meet – Free Electron which glorifies the ultimate hacker, for example, there’s a story about this computer geek which re-wrote the whole DAO layer in one week – something which took two other engineers approximately six months…

Personally, I don’t like the glorification that is done around coding “rock-stars” and programming geniuses. I rather have a collaborative environment, such that you won’t be afraid to make mistakes, but unfortunately in most of the organizations I ran into it’s more important to cover your butt and be a politician than actually be a good engineer (which includes to be able to make mistakes too!).

Anyways. it reminded me of another story, one that happened back in the 80′s. I heard this one from Mayer Goldbreg, a professor that taught a compilation course I took during my studies for a B.Sc.degree. On that course we built all our projects using a weird language called  Scheme which is a functional programming language that has a syntax that doesn’t look very appealing to the majority of object oriented programmers:

(let loop ((n 1))
  (if (> n 10)
      '()
      (cons n
            (loop (+ n 1)))))

===> (1 2 3 4 5 6 7 8 9 10)

It took some time getting used to the weird syntax with all the nested brackets (oh god – just thinking about all the times I counted opening/closing brackets…)

But I’m diverting… so back to the story: Mayer had a friend which, not surprisingly, was such a free electron. He worked for a big company that used some low-level programming language (let’s call it X) to maintain their platform. As you can imagine, maintenance was hell, not to mention adding new features or finding bugs. But that friend came up with this great idea: he wanted to write a compiler from Scheme to X – after his project will be completed life will be sweet – everything will become much easier!

This guy had just one problem, his boss was not so enthusiastic about that idea… After a few arguments his boss told him specifically that he should forget about it – but like any good free electron he didn’t…

It didn’t take him long to build that compiler, sure enough, he had a few bugs – but he fixed them and sooner than he himself expected – he would produce so many lines of generated (and unreadable) code – and it was working great: whenever he got a new assignment – it would practically take him minutes to code it in Scheme and then he would run the compiler and take another 1 hour of coffee break. He was producing the same amount of work of the entire division!

Soon enough, his manager heard the talks and came to his cubical furious. He yelled at him and then fired him. But if you think that this is the end of the story – you’re wrong.

It didn’t take long for the higher management to find out that suddenly all the tasks were taking much longer – and after a few weeks the story got all the way up – this manager call, but now he was practically begging him to come back and maintain his compiler…
He didn’t.

UPDATE: I just ran into the following session and I couldn’t agree more with these guys!

Setting up Spring web-project on IntelliJ using Maven

Till yesterday I used eclipse when I wanted to work with the combination of Spring-web/Maven projects. To be more exact I was using STS which is a version of eclipse called Juno (if I’m not mistaken – but if I do – please correct me) that comes with the relevant plugins already installed (Spring and Maven’s jars for example) and it wears an ugly green skin. It also comes with vFabric server which is a web-container (like Tomcat) that was made by VMWare, which bought Spring in order to leverage Spring to push their products.

Now, if there’s an IDE that I hate – that’s Eclipse. It’s just so slow and buggy… You can spend a couple of hours on something that doesn’t work just to find out that if you create the project from scratch – everything’s peachy, and no, clean/re-built/restart/computer-restart wouldn’t have fixed it…

If IntelliJ wasn’t an option I would definitely choose Netbeans which is the fastest Java IDE I’ve experienced, but intelliJ is a tool you fall in love with

So yesterday I decided that I’ve had it, and that I’m migrating my Spring projects to IntelliJ. In case you have an existing Maven project – it’s really easy to import and start working, but then I tried setting up a project from scratch, and after fighting with it for a couple of days I finally found out how to do it (by the way, I read a few other posts in regards which didn’t help…). I know, it should be easier and that’s a couple of black-points to JetBrains, but the effort was worthy!

In order that you won’t have to go through the same painful experience which I did, here’s a short guide on how to set up a Spring Web environment on IntelliJ. So without  a further adu:

1. create a new project from scratch

2. select “Maven module” as a type and click “Next” after filling out the project name and path

3. check the option “create from archetype” and choose “maven-archetype-webapp” from under “org.apache.maven.archetypes”. If you don’t have that option go to step 4, otherwise you can skip it and go directly to step 5.

4. In case we didn’t have the archetype, we’ll click on “add archetype” and add it manually as follows:

GroupId: org.apache.maven.archetypes
ArtifactId: maven-archetype-webapp
version: RELEASE

5. before you click on “Finish” check if the parameter M2_HOME is defined, if not, you can define it as an environment variable, or alternatively you can set it up right here:

6. once you click “Finish” a pom.xml file will be generated and some, other stuff will run on your screen, you should also see the following option to enable auto-import for Maven projects – click it!

7. goto “edit configurations”, click on the “+” button and choose the local version of Tomcat

8. Name your server, check the option to “Build artifacts” and click on the “…” right next to it. Choose the .war file and continue

9. go to the “deployment” tab and click the “+” button to add an Artifact. Again, choose the war file

10. That’s it – we’re done! If you’ll expend your project you should be able to see something like the following screenshot.

Click the green “Play” button and after Tomcat starts, you should be able to view “Hello World” jsp version on localhost