Rails / Ajax / Autocomplete

As you all know if you're regular readers here, I started out in the Ruby web framework world with Ramaze and I'm definitely glad that I did. However, it doesn't seem like there's much of a job market for Ramaze programmers, so I've taken up using Rails, specifically Rails 3.1. There's a number of great books for Rails and the one I'd recommend is Ruby on Rails 3 Tutorial by Michael Hartl. In this book, he develops a Twitter like application in Rails starting with basic pages and moving on to more complex topics.

I've been working on a simple project for a greeting card application and I came up with a little something that might be interesting. The cards have a recipient and can have multiple signers. I added autocomplete for the recipient, but it was a bit harder for the comma separated list of signers. What I ended up doing was was simply grabbing the last piece of the list in the controller and passing that back to the view.

Here's the view code ...

 Create a Card 
<%= image_tag "card_images/#{@template.image_name}", :size => "200x200" %>
<%= form_tag ("create_from_image") do %>

    <%= label_tag("Add the recipient's email: ") %>

    <%= text_field_tag(:recipient_email, "#{@recipient_email}")%>


    <%= label_tag("Add A Greeting: ") %>

    <%= text_field_tag(:greeting, "#{@greeting}")%>


    <%= label_tag("Add the signers' emails (comma separated): ") %>

    <%= text_field_tag(:signers_email, "#{@signers}")%>


    <%= hidden_field_tag :template_id, @template.id %>

    <%= submit_tag("Preview the card!") %>
    <%= submit_tag("Send the card!") %>
<% end %>

There's nothing very interesting in here, but the main field we're interested in is the :signers_email text field.

Here's the javascript code for it ...

$(document).ready(function(){
    // Below is the name of the textfield that will be autocomplete
    $('#recipient_email, #signers_email').autocomplete({
        // This shows the min length of charcters that must be 
        // typed before the autocomplete looks for a match.
                    minLength: 2,
        // This is the source of the auocomplete suggestions. In this case a 
        // list of emails from the users controller, in JSON format.
                    source: '/users/index.json'
    })

});

What this says is that for both the recipient_email and signers_email fields, use autocomplete, send when we have two characters, and use the /users/index.json function to get the data we need.

Finally, we have the controller code ...

    def index
        @title = "All users"
        @suggestion = "Pick someone and send them a card!"
        if params[:term]
            search_term = params[:term].split(",").last.strip
            @users = User.find(:all, :conditions => ['email LIKE ?', "#{search_term}%"])
            @users_hash = []
            @users.each do |user|
                @users_hash << { "label" => user.email }
            end

        else
            @users = User.where(:active => true).paginate(:page => params[:page])
        end

        respond_to do |format|
            format.html

            # Here is where you can specify how to handle the request for "/people.json"
            format.json { render :json => @users_hash }
        end
    end

Here, we have a couple of things going on ... for the Ajax side, we'll get the params[:term] field so we know that we need to get the constrained list. First, we're going to grab the params[:term] value, which should look something like "abc@test.com, def". Here we'd like to look for emails that start with the "def" and ignore the "abc@test.com" piece. So ... we split on the comma, grab the final element in the array, and then remove any leftover spaces at the end or beginning of the string. Next, we'll create an array where each element is a hash of the form { "label" => "defghi@test.com" }. This is the form that the jquery autocomplete needs. Finally, we use the respond_to section to send this back as json.

As always, let me know if you have questions.

Majority Voting

I saw this one over at Programming Praxis. It's pretty simple with ruby, but there's one slightly interesting piece in there that might come in handy sometime. Here's the code ...

def majority(l)
    h = Hash.new(0)
    l.each { |v| h[v] += 1 }
    max = h.max {|a,b| a[1] <=> b[1]}
    max[1] >= l.length / 2.0 ? "#{max[0]} won with #{max[1]} out of #{l.length} total votes" : "No winner"
end

v1 = %w[A A A C C B B C C C B C C]
v2 = %w[A B C A B C A]

puts "v1 = #{majority(v1)}"
puts "v2 = #{majority(v2)}"

OK, so we create a Hash where the value in the key/value pair is initialized to 0 and we add one each time time we see a vote. Here's the cool part, we use the max function from Enumerable knowing that max itself uses each which will give us the key/value pair as a two element array. So, we set the function to compare the second element, the value, of the pair. The max that gets returned will also be a two element array and we use that to calculate whether there's a winner or not.

These types of problems are great for sharpening your programming skills in general and your ruby skills in particular. They're exactly the types of questions that end up on programming interview tests.

Let me know if you have questions or comments.

Centroids

Here's another one from my clustering code, slightly modified for explanatory purposes. This post was spurred by a conversation with a couple of friends when we were talking about programming, who said that programming languages mostly had the same things (i.e. everything old is new again). While I'm not completely in opposition to that, I think that some of the newer languages (read Ruby) do have a lot to offer when it comes to compactness.

Here the problem is to find the centroid of a number of points. Basically, we want the averages of all the first values of the points, the second values of the points, etc. Let's show an example ...

If we have [[x0, y0, z0], [x1, y1, z1], ... [xn, yn, zn]] as our points then the centroid would be the point given by [sum(x's) / n, sum(y's)/n, sum(z's) / n] (and here I'm too lazy to figure out how to create the capital Sigma for sum). Think about how you might solve this in your favorite programming language. In C/C++ anyway, you'd need to know in advance how many points and how many dimensions (the example above uses three, but it could be more or less). In Java, you don't need that, but I don't think you could do something like this ...

    def centroid(x)
        x[0].zip(*x[1..x.length-1]).map { |v| v.inject(:+) / v.length.to_f }
    end

OK, so what's going on here? First up we're going to take the first element of the array (above the [x0, y0, z0]) and zip it with the rest of the array with *x[1..x.length-1]. This should give us, once again from the example above [[x0, x1, ...xn], [y0, y1, ... yn], [z0, z1 ... zn]]. So basically, a new array with all the x's gathered together, the y's, etc. Now comes map. Here, we'll take each element, which is itself an array and then use inject to run through each of the items, say [x0, x1, ... xn] and sum them together. Finally, we'll divide by the length of the element to get an average. If it's hard to see this, break it into pieces and then run it through using irb. It should be a bit easier to see there.

So, what's the point here. Well, essentially you could this in any programming language or in fact any Turing machine, but the language itself can make it easier freeing you to do other things or harder.

Let me know if you have any questions or comments.

Monty Hall Problem

A friend of mine got asked this question in an interview yesterday and I thought it'd make an interesting programming problem. It goes something like this ... Suppose you're on a game show and are offered the choice of one of three doors. Behind one of the doors is a car and behind the other two are goats. Let's say you choose door number three (see Jimmy Buffet song). At this point Monty Hall shows you that behind door number one is a goat and offers to let you switch to door number two. The question is, should you do it? The easy (and incorrect answer) is that it doesn't matter. The correct answer is that, yes you should. Why? I'll let you look it up or you can just run the following program ...

possible_doors = [:goat, :goat, :car].permutation.to_a
bad_choice = 0
tries = 100000
1.upto tries do |mc|
    test_doors = possible_doors[Random.rand(possible_doors.length)]
    bad_choice += 1 if test_doors[Random.rand(test_doors.length)] == :car
end
puts "bad_choice percent = #{bad_choice.to_f / tries.to_f * 100} good_choice percent = #{100.0 - (bad_choice.to_f / tries.to_f * 100)}"

First up, we get a list of all the possible ways the doors could be arranged and set the number of times that switching would be a bad choice to 0. We'll run this 100000 times in a Monte (not Monty) Carlo loop. In the loop we get one of the possible arrangements of test doors randomly selected and then increment the bad_choice variable if the door we pick contains the car (in other words switching from where we are would be a "bad choice"). When we run this program we see that switching is a bad choice only about 33% of the time and a good choice about 66% of the time (one might guess that these are really 33.333333...% and 66.6666666%). So, then answer in this case is that yes you should switch.

Let me know if you have questions or comments.

Ruby Distance Calculation

I was just looking at a clustering algorithm and needed a distance calculation between two points in n-dimensional space. If you remember your high school geometry (or even earlier) the distance between two points in the xy plane is the sqrt((x1 - x2)**2 + (y1-y2)**2). Where the two points are represented by (x1, y1) and (x2, y2). For more dimensions, just add values inside the sqrt as in (z1-z2)**2 for a third dimension. Given that here's a one line function that I came up with

def distance(a, b)
    Math.sqrt(a.zip(b).inject(0) { |d, c| d + (c[0] - c[1]) ** 2 })
end

It's a bit tricky, so let's go through it. First we have the Math.sqrt which will just take the square root of whatever is inside it. Next the a.zip(b) will take two arrays (here the input parameters) and take the first values of each of the arrays, create a new array from them and then add that to the output array (see also this post for more information on zip). Same with the second values of the arrays and so on. For example if we have [x1, y1, z1].zip([x2, y2, z2]) this will return [[x1, x2], [y1, y2], [z1, z2]] (hopefully, this looks like something we can use to you). Next we're going to use inject to run through this array with a starting value of 0 (d) and add to it the square of the difference of the two values in the array. Finally as noted before, take the square root and return.

If you have any problems with this, break it up into multiple lines and check the intermediate values. As always, let me know if you have any questions.

Heaps

I noted in my last post that I had a technical phone interview. When it was scheduled, the HR person told me that it would include "data structures, algorithms, and architecture". I decided that it wouldn't be a bad idea to review a bit and so I got a copy of Steven Skiena's "The Algorithm Design Manual" and started rummaging through it.

One of the data structures that I came across was a heap (as in heapsort if you've forgotten). A heap is a binary tree data structure that has the property that the parent is smaller for a min-heap or larger for a max-heap than its children. They can be used for priority queues as the minimum or maximum is always at the top of the heap or for sorting assuming that you a) take the top element and then b) recalculate the tree.

The code here follows Skiena's pretty closely excepting he starts his array at 1 and I use the more natural (for me anyway) 0 start. This code also implements only a min-heap, but you should take a bit of time to see if you can figure out how to make it either a min-heap or a max-heap as an initialization parameter. A couple of other things aren't that pretty (extract_min! in particular bugs me), but mostly it's not bad and is straight forward.

So ... here's the code

class Heap
    def initialize(a)
        @q = []
        a.each { |v| insert(v) } if a
    end

    def parent(n)
        n == 0 ? -1 : (n-1) / 2
    end

    def young_child(n)
        (2 * n) + 1
    end

    def insert(v)
        @q << v
        bubble_up(@q.size-1)
    end

    def bubble_up(n)
        return if parent(n) == -1 # Root of heap, no parent 
        if @q[parent(n)] > @q[n]
            swap(n, parent(n))
            bubble_up(parent(n))
        end
    end

    def swap(n, pn)
        @q[n], @q[pn] = @q[pn], @q[n]
    end

    def min
        @q.first
    end

    def extract_min!
        m, @q[0] = @q.first, @q.last
        @q.pop
        bubble_down(0)
        m
    end
 
    def bubble_down(n)
        c = young_child(n)
        min_index = n

        0.upto(1) { |i| min_index = c+i if ((c+i) <= @q.size-1) &&(@q[min_index] > @q[c+i]) }

        if (min_index != n)
            swap(n, min_index)
            bubble_down(min_index)
        end
    end

    def sort!
        a = []
        while v = extract_min! do a << v end
        a
    end
end

h = Heap.new([12, 14, 6, 10, 8, 27, 1, 4, 9])
puts "extract_min! = #{h.extract_min!}"
puts "extract_min! = #{h.extract_min!}"
puts "extract_min! = #{h.extract_min!}"
puts "extract_min! = #{h.extract_min!}"
puts "min = #{h.min}"
puts "min = #{h.min}"
puts "sort! = #{h.sort!}"

Let me know if you have any questions or comments and if you make improvements, post those too.

Phone Interview - 1

I had a phone interview with a great company yesterday and thought I'd share some of the questions, my answers, what I think might have been better answers, and some additional potential questions that might have been asked. First, this was for a manager position and the fact that they're asking technical questions as part of the interview process and as the first interview really impressed me. It shows that they value technical abilities and respect their engineers and developers enough to hire managers that are technically capable as a top priority. We started out, as is usually the case with a bit of small talk about myself, the interviewer, and the company. Nothing too interesting there. I don't recall the actual order of the questions, but I think I got them all.

1. What are horizontal and vertical scaling? Here I knew what horizontal scaling was, but I don't believe I've heard the term vertical scaling. Horizontal scaling means adding more servers to give more processing power while vertical scaling (as I learned when I looked it up) is beefing up the capabilities of an existing server by adding say memory, CPUs, or CPU power. A reasonable follow up to this would have been to discuss the advantages and disadvantages to each.

2. What is object oriented programming? Here I discussed encapsulation and inheritance. I probably should have mentioned polymorphism and message passing. The Wikipedia article is pretty decent and wouldn't be a bad place to do a high level review for this sort of question. I was a little surprised that I didn't get a question on a specific problem. I always would as someone to list out objects and methods for a card game or for a file system (stolen I believe from Steve Yegge if I remember correctly).

3. Given an unsorted list, how would you find a duplicate element. This one was interesting because it had recently appeared on Programming Praxis. I solved it there and used a hash table. The idea is to run through each element of the list and put it on the hash table. If when you go to put it on the hash table, there's something already there, then you've found the duplicate and should return it.

4. In the above question, what's the complexity using Big O notation. Here, since we're running through the list just once, it should be O(n) where n is the size of the list.

5. How does a hash table work or how is it implemented "under the hood"? There are actually a couple of ways of implementing hash tables. I gave the answer of an array of linked lists. You have an array of size n and then use the element that you're going to put on the table to generate a hash value using a hash function. Then use this mod n and add it to the linked list that's at that element.

6. How would you count the number of 1's in an integer? This is pretty classic. Probably the easiest is to use a shift/and technique. You would "and" the value with "1" and if it's non-zero (actually it'll be 1) then add one to the bit count. Shift right and repeat until the value is 0.

7. The final question was about Design Patterns and whether I knew about them and why they're useful. My response was that they're useful in that they give us a way to discuss our designs with a common language. People were using design patterns before the GoF book, but they codified the patterns and gave them names. This makes it much easier to talk about these things.

I think that was all of the questions. We then talked a bit about the position and the company in general. As I said, I was very impressed with them and their "corporate culture".

So ... what sorts of things do you ask or have you been asked in technical phone interviews? Anything interesting or unique? Let us know in the comments.