Bret Kittle

Skill Test: The Social Network of a Word

During my time applying at different companies in the SF I’ve had the opportunity to see some interesting skills/coding tests.  I’m going to post them here and show the solutions I built.  Bare in mind the tests had a time limit so I’m giving what I came up with in the time that I had.

Problem
Two words are friends if they have a Levenshtein distance of 1. That is, you can add, remove, or substitute exactly one letter in word X to create word Y. A word’s social network consists of all of its friends, plus all of their friends, and all of their friends’ friends, and so on. Write a program to tell us how big the social network for the word “causes” is, using this word list: (https://raw.github.com/causes/puzzles/master/word_friends/word.list) .

Solution
 I decided to build a class “Word” that would contain a method for testing the Levenshtein distance between that word and an input string. Full code at: https://github.com/kittleb/north-american-adventure

class Word
  attr_accessor :name
  
  def initialize(name)
    @name = name
  end

end

The Levenshtein distance is checked like so:

def levenshtein(a,b)
    case
      when a.empty? then b.length
      when b.empty? then a.length
      else [(a[0] == b[0] ? 0 : 1) + levenshtein(a[1..-1], b[1..-1]), 1 + levenshtein(a[1..-1], b), 1 + levenshtein(a, b[1..-1])].min
    end
  end

end

Then came the problem.  The word list is huge.  On a personal machine this is a massive process.  Ruby (the language being used) doesn’t employ true multi-threading.  So, even though it wasn’t part of the process I decided to build two more methods to try and speed up the app.  One splits the work into multiple “network processes” and the other into multiple “network threads”.

def find_network_processes
    list      = []
    results   = []
    procs     = []
    num_step  = 20
    goto      = 100
    readme, writeme = IO.pipe
    
    # 1. Push all the text into an array and strip bad characters
    File.open("lib/word.list").each do |line|
      list.push(line.strip)
    end
    
    # 2. Split into batches
    for i in (0..goto).step(num_step)
      
      $stdout.reopen writeme
      readme.close
      
      # 3. Create a new Process for each batch
      procs << fork do

        # 4. Inside process loop through each item in the batch and sort based on distance
        for ii in (0..num_step).step(1)
          
          distance = levenshtein(@name,list[i+ii])
        
          if results[distance].nil?
            results[distance] = []
          end
          results[distance] << list[ii+i]
          
          puts list[ii+i]
          writeme.write list[ii+i]
          writeme.close
        end

        exit
      end
      
    end
    
    # Wait for all child processes to finish before continuing with the main process
    procs.each do |proc|  
      Process.waitpid(proc)
    end
    
    #writeme.close
    readme.each do |line|
      results << readme.read
      puts "Father says : " + results.inspect
    end
    
    return results
  end
  
  def find_network_threads
    list      = []
    results   = []
    threads   = []
    num_start = 0
    num_step  = 100
    goto      = num_start + 300
    readme, writeme    = IO.pipe
    
    # 1. Push all the text into an array and strip bad characters
    File.open("lib/word.list").each do |line|
      list.push(line.strip)
    end
    
    # 2. Split into batches
    for i in (num_start..goto).step(num_step)
      
      # 3. Create a new Process for each batch
      threads << Thread.new do
        puts "Start Thread " + (Process.pid).to_s
        # 4. Inside process loop through each item in the batch and sort based on distance
        for ii in (0..num_step).step(1)
          
          distance = levenshtein(@name,list[i+ii])
        
          if results[distance].nil?
            results[distance] = []
          end
          results[distance] << list[ii+i]
        end
        puts "End Thread " + (Process.pid).to_s
      end
      
    end
    
    threads.each do |thread|
      thread.join
    end 
    
    return results
    
  end

There’s a fine line between gambling and taking risks

And I still am not quite sure where that line is.

Every great thing that has happened in my life happened because I really went outside what I would ever consider “prudent”.  Whether it was driving across the country with no job prospects or quitting at “secure” jobs to join scrappy startups, it always felt like I was really testing my luck.

Now I’m trying to live in both San Francisco and Bangkok, and am jumping from steady jobs that control where I live and living off contract work while trying to build my own startup in Asia.

And while I honestly don’t know if now I’ve finally crossed that line and am just being stupid, I do know from every other great moment in my post-education life that I “can’t look back or I’m lost”.  There is only forward.

Developing a Ruby Gem

To get the writing juices flowing, for my first technical post I’ll show how I built a quick and simple Ruby Gem for use with Bundler.  This will show a super basic gem that accesses the Tumblr API.  For those of you that this is too simple for, don’t worry, I’m just getting my writing abilities back up to speed.  Later next week I’ll begin posting some more complex topics such as writing an HTML5 Canvas Graphics library.

First, in the console where I wanted to create my new Gem project:

bundle gem TumblrHay 

Next, In the generated project there are already the basics that I needed. First I add the required libraries and other gems for the project in my TumblrHay.gemspec file. Since I’ll be using John Nunemaker’s awesome HTTParty gem I add that as a dependency.

s.add_dependency "httparty" 

I’m not using nice TDD practices today for this, so instead I’m just going to dive into coding my gem module and classes. I open up TumblrHay.rb and get started:

require "TumblrHay/version"

module TumblrHay
  
  class Post
    include HTTParty
    @base_uri = 'http://api.tumblr.com/v2/'
  
    def self.posts(hostname)
      request = @base_uri << 'blog/' << hostname <<'.tumblr.com/posts' << '?api_key=' << TUMBLR_CONSUMER_KEY
      return self.get(request)
    end
  end

end

In the preceding code basically all I’m doing is building a Class named Post that is a part of my Gem. I give it a method self.posts which builds a string that can be sent to the Tumblr API as a GET request. The gem requires an environment variable to be defined called TUMBLR_CONSUMER_KEY. If I make the following request, I should get a request object back:

TumblrHay::Post.posts('brettles')

I can build and install my gem locally using the generated rake file and the rake command:

rake install

Viola! Modularized code!

Catching Up, And What Comes After

Hey internet.  My name is Bret Kittle.  I’m a Senior Web Engineer in San Francisco professionally working on Ruby on Rails, Node.js, CSS, and Javascript.  On the side I work on various projects.

It’s been a really long time since I last attempted blogging, but I’ve challenged myself to begin again.  My goal is to share code, projects, and experiences that could potentially help or engage the creativity and passions of other folks out there.

Over the next couple weeks I’ll be sharing info on several startups that I’ve been working on over the past year (and am close to launching), as well as technical and personal struggles that came out of those.

I’ll also be updating my personal site (http://www.BretKittle.com) and integrating this blog feed into it using Tumblr’s slick API, so check out progress there over the next couple weeks as well.

Cheers,
Bret