Monday, 28 October 2013

Using an Object's Slug as the Subdomain in Rails 3

Recently I had the problem of allowing each user in my system to have their own subdomain. There are various blog posts about subdomains in Rails, but none seem to really handle this requirement.

The way I did it was to leave my routes file intact, and use Rack middleware to rewrite urls to match the routes (this also has the advantage of not breaking existing urls).

I used the rack-rewrite gem ( to rewrite the urls as follows

 config.middleware.insert_before(Rack::Lock, Rack::Rewrite) do  
    rewrite /.*/, { |path, rack_env|  
      slug = rack_env['SERVER_NAME'].split(".")[0]  
     :if => {|rack_env|   
      rack_env["HTTP_ACCEPT"] =~ /(text\/html|application\/json)/ && !(rack_env['SERVER_NAME'] =~ /www\./i)  

Then I had to make sure all of the urls point to the correct domain and path. For this, I overwrote the url_for method as follows

 def with_subdomain(subdomain)  
   subdomain = (subdomain || "")  
   subdomain += "." unless subdomain.empty?  
   [subdomain, request.domain, request.port_string].join  
  def url_for(options = nil)  
   if options.is_a?(User)   
    return "http://#{with_subdomain(options.slug)}"  
   if options.kind_of?(Hash)  
    options[:only_path] = false  
    options[:port] = nil  
    if options[:_positional_args] && user = options[:_positional_args].find {|pa| pa.is_a?(User)}  
     options[:host] = with_subdomain(user.slug)  
     return super(options).gsub(/\/users\/\d+/, '')  
    options[:host] = with_subdomain("www")  

Thursday, 18 July 2013

The problem with using past performance to predict future results

So I've been thinking lately about how common it is in job interviews (for software developer roles) for companies to make judgements (both good and bad) about a candidate's suitability for the job based on references or experiences from years in the past. And how problematic that is.

I'm sure you've improved as a programmer in the last few years. I definitely have. And if you haven't, there is something seriously wrong.

And it's not just programming skill, but also in dealing with people, managing your time, being able to follow and suggest industry best practices, etc. All of these things are important to how well you are able to do your job.

It is so hard to even define what makes a good developer, let alone trying to predict how good someone is based on a subjective recollection of the work someone did 5 years ago; probably in entirely different circumstances.

So how far back should a company look? And if the answer is 'not very far', where does that leave companies who want to hire good software developers? What can they look at to get a decent indication of whether they should hire a candidate or not?

Recently at RailsCamp (Melbourne 2013) I heard someone say that when you're interviewing someone, you need to find out 3 things:

  1. Is the candidate capable of doing the job?
  2. Does the candidate want to do the job?
  3. Do I like this person enough to work with them?
2 and 3 seem pretty straightforward to determine. Capability on the other hand, seems much harder. I would suggest that you should put the least weight on point number 1. If the candidate really wants to do the job, and you like them, they are probably capable of doing it.

Thursday, 14 March 2013

Intersecting Discs Problem in Ruby

So I was looking at the Codility sample problems and came across the following problem.

Given an array A of N integers we draw N discs in a 2D plane, such that i-th disc has center in (0,i) and a radius A[i]. We say that k-th disc and j-th disc intersect, if
and k-th and j-th discs have at least one common point.
Write a function
int number_of_disc_intersections(int[] A);
which given an array A describing N discs as explained above, returns the number of pairs of intersecting discs. For example, given N=6 and
A[0] = 1
A[1] = 5
A[2] = 2
A[3] = 1
A[4] = 4
A[5] = 0
there are 11 pairs of intersecting discs: 0th and 1st 0th and 2nd 0th and 4th 1st and 2nd 1st and 3rd 1st and 4th 1st and 5th 2nd and 3rd 2nd and 4th 3rd and 4th 4th and 5th
so the function should return 11. The function should return -1 if the number of intersecting pairs exceeds 10,000,000. The function may assume that N does not exceed 10,000,000.
The trick here is to do a solution that works in O(N log(N)) time and O(N) space.
There was a ruby solution posted here by "user691307" as follows
 def number_of_disc_intersections(a)  
   event ={|h,k| h[k] = {:start => 0, :stop => 0}}  
   a.each_index {|i|  
     event[i - a[i]][:start] += 1  
     event[i + a[i]][:stop ] += 1  
   sorted_events = (event.sort_by {|index, value| index}).map! {|n| n[1]}
   past_start = 0  
   intersect = 0  
   sorted_events.each {|e|  
     intersect += e[:start] * (e[:start]-1) / 2 +  
            e[:start] * past_start  
     past_start += e[:start]  
     past_start -= e[:stop]  
   return intersect  

Which is a beautiful solution and runs in O(N log(N)) time and O(N) space, as we wanted. The only problem is it is very difficult to understand what it is doing and why. So in this blog post, I hope to explain the above code.
The algorithm is as follows. Imagine the initial array that we are passed in spans out forever on each side. Instead of the individual numbers we are passed in, we want to know how many discs start and stop at each position. Once we can say, for example, at index 4, 2 discs start and 1 disc ends - and do that for every index - we are able to calculate how many intersections there are.
You can see in the first 5 lines of the function it creates a new hash where the value is defaulted to another hash that set start and stop to zero. This allows us to increment using "+= 1" rather than having to check for nils. It then populates the event hash by iterating over the passed in array (a) and incrementing the start value at the lower bounds of the disc, and the stop at the upper bounds of the disc.
sorted_events = (event.sort_by {|index, value| index}).map! {|n| n[1]}

The 6th line of the function looks complicated but all it is doing is sorting by the key of the event hash (the index) and then discarding the keys and just using the values of the hash. But we can't use ".values" on the result of the sort_by, because it returns an array (hashes can't be sorted)

 past_start = 0   
 intersect = 0   
 sorted_events.each {|e|   
  intersect += e[:start] * (e[:start]-1) / 2 +   
     e[:start] * past_start   
  past_start += e[:start]   
  past_start -= e[:stop]  

Now for the really tricky part. We iterate over our sorted array of hashes which tell us how many discs start and stop at each position. There are two cases we need to worry about:
1) how many discs are already going when the new disc starts (e[:start] * past_start)
2) if multiple discs start at the same position (e[:start] * (e[:start]-1) / 2)
The first condition is fairly simple. If there are 3 discs that we're in the middle of and a new disc starts, it intersects with all 3 of them. If there are 3 discs that we're in the middle of, and 2 new discs start, each of them will intersect with the 3 existing ones, making 6 intersections.
The two lines at the bottom keep track of how many discs are currently open at each index.
The second condition is a little trickier. If multiple discs start at the same location we need to use some maths. It's the same problem you probably did in school: If 5 people all shake hands with each other, how many handshakes have there been?
To do this, because it is groups of 2, you have to pick 2. So on the first pick, there are 5 options, then once you've picked that first one, there are only 4 options. So 5 x 4 = 20. But, because when person A shakes person B's hand, it's the same as when person B shakes person A's hand, we have to divide our result by 2, so as not to double count.
This is the same with the intersections. If there are 5 new discs starting at a position, the number of intersections between them is equal to 5x4/2 = 10.

So that's it. The number of intersections at each index is n*(n-1)/2 - for if multiple discs start at that index - plus n*past_starts for when discs are already in progress when we start a new one. Add them all together and you have your solution.
I hope this has made sense to people. If not, please leave a comment and I'll try to address it asap.

Wednesday, 13 March 2013

Finding the Longest Palindrome in Ruby

Non-optimal Solution - best case O(N), worst case O(N^2)

This is a non optimal (see below for optimal solution), but much easier to understand solution.
It uses the following algorithm. At a position of the string, it compares the character at the left and right to see if they're the same. If they are, it looks one character further out on each side and compares them. And so on until it reaches an end of the string or finds the two characters are different. 
It does this at each position of the string, finding the longest palindrome centered around each position, keeping track of which is longest overall.

 def find_longest_palindrome(s)  
  longest = ""  
  0.upto s.length do |i|  
   odd = palindrome_at_position(s, i, i)  
   longest = odd if odd.length > longest.size  
   # handle even length palindromes  
   even = palindrome_at_position(s, i, i+1)  
   longest = even if even.length > longest.size  
 def palindrome_at_position(s, left, right)  
  palindrome = ""  
  while (right < s.length &&  
      left >= 0 &&  
      s[left] == s[right])  
   palindrome = s[left,(right-left+1)]  
   left -= 1  
   right += 1  

Optimal Solution - Linear time O(n)

Here is a linear time solution. Guaranteed to be 2N or fewer comparisons.
This solution is similar to the first solution but it uses findings from previous palindrome length calculations to reduce how much processing it has to do.
It takes advantage of the fact that if you know there is a large palindrome centered around one character, the characters to the immediate right of that character must be at the center of palindromes at least as long as the palindromes centered around characters to the immediate left.
When you're looking at the 'b' at index 3, you calculate that it's the center of a palindrome 7 characters long (spanning out 3 characters in each direction).
So when you go to calculate the palindrome centered around index 4 (the second 'c'), you know that it must be at least as long as the palindrome you've already calculated at index 2 (the first 'c') which is 3 characters long. 
And seeing that those 3 characters don't take you past the end of the palindrome centered around 'b' at index 3, you know that it can only be 3 characters long.

And similarly when you look at index 5 (the third 'b'), you know that its palindrome must be the same as the palindrome at index 1 (the first 'b'), which is only 1 character long.

 def longest_palindrome(str)  
  palindrome_lengths = {}  
  center = right = 0  
  # This gsub changes a string "abc" into "~a~b~c~" 
  # This is done to avoid the problem of even length palindromes    
  processed_str = str.gsub(/(\w|$)/, '~\1')  
  0.upto (processed_str.length - 1) do |i|  
    i_mirror = center - (i - center)  
    if (right > i)  
      palindrome_lengths[i] = [right-i, palindrome_lengths[i_mirror]].min  
      palindrome_lengths[i] = 0  
    while (processed_str[i + 1 + palindrome_lengths[i]] == processed_str[i - 1 - palindrome_lengths[i]])
      palindrome_lengths[i] += 1
    if (i + palindrome_lengths[i] > right)  
      center = i;  
      right = center + palindrome_lengths[i];  
  max = palindrome_lengths.values.max  
  center_index = palindrome_lengths.key(max)  
  str[(center_index - max)/2, max]