Tony's Place

I love logic/algorithm problems but during an interview I can sometime just blank out on these questions.   I don’t feel like taking a lot of time but at the same time some of the problems are quite complex if not approached in the right way.

Problem 1:

You have an array that contains 0s and 1s.   Order the array.

Now if memory and performance weren’t a factor this is as simple as doing a ones_and_zeros.sort in ruby (where ones_and_zeros is the array).

You could also build an array of 0s and 1s and then merge them but if the array huge and taking up too much memory this is less than ideal.   You could also add up all the 1s and build a new array but then you are also building a second array and iterating twice.

So the correct answer is to do this inline.

My solution is to loop through the array, replacing any 0 with a 1 and putting 0s on the front of the array.  There is the main loop index and then the zero index that points to the location of the last 0.

def sort_it!(ones_and_zeros)
 zero_index = -1
 for i in 0 .. ones_and_zeros.size
   if ones_and_zeros[i] == 0
     zero_index +=1
     unless zero_index == i
       ones_and_zeros[zero_index]=0
       ones_and_zeros[i] = 1
     end
   end
 end
 return ones_and_zeros
end

This works fine but I got stuck and came back to this problem later.  :-\   I should probably google this and see if there is a better way.

Problem 2:

Next problem was..  you have 5 bottles of pills,  1 has bad pills.  The bad bills weigh 9oz and good pills are 10oz.  You can use the scale once.  You can weigh pills, bottles or any combination but you can only use the scale once.

Now you could weigh pills 3 pills from different bottles and determine narrow down to 2 or 3 which bottle has the bad pills but we need to know which one has the bad pills.

After what seemed like an eternity I figured it out.   put 1 pill from bottle #1, 2 from #2, 3 from #3, etc on the scale.   if all the batches are were good these 15 pills would weigh 150oz.  but there are bad pills.  If they were in bottle #1 it would weigh 149oz, in #2 148oz. etc.   Isn’t this fun!    It is fun unless you are under a the pressure of a interview…  that said I guess this tests how people react under pressure as well as their logic skills.

Final problem

you need to determine what the highest floor on a 100 story building that you can drop a marble from before it will shatter on the ground.   You have 2 marbles to work with and you need to minimize the number of tries.   You could go floor 1, 2,3,4, etc but then worse case you have made 100 tries.

I immediately started thinking about dividing the problem like a binary tree.  Try floor 50, then 75 if no breakage, then 62 if it broke but you only have 2 marbles so the worse case is 50 tries.  start at 50.  breaks,  go back to 1 and progress to 49.

Now what if I moved up 5 floors at a time.  Worse case is 99 with 24 tries.   5,10,15,20,25,30,35,40,45,50,55,60,65,70,75,80,85,90,95,100,96,97,98,99

Ok, how about 10s?  10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 91, 92, 93,94,95,96,97,98,99

19 tries.  better

There must be a formula here..  assuming a fixed increment we have ceiling(floors/increment) + increment -1

This seems to work ceiling(100/10) + 9 = 19 and ceiling(100/5) + 4 = 24 check out.

Ok,  graph this thing and find the lowest point..  turns out with this technique 19 tries is the best by using 10 as the fixed increment.

But the real answer is 14 using an increment that changes.   I’m out of time for today but I’ll probably dig into that one while i sleep. 

For years I have used Ubuntu for my desktop environment and CentOS in production.  Why?   Ubuntu makes a great desktop distro and since CentOS is basically a copy of Red Hat, it is considered an enterprise OS.

The trouble with being an Enterprise OS is you avoid the latest updates to the OS and aggressively patch proven packages.   CentOS has worked fine for me up until recently and I suspect all my future deployments will use Ubuntu.  CentOS packages are lagging behind and this lag is causing pain.  Here are some examples of my recent pain points.

Every 3 months on the dot I fail my PCI compliance scan with the following error.

OpenSSH 4.3 is vulnerable Severity: Critical Problem

OpenSSH is up to version 5.8 but RedHat keeps patching 4.3.  It is totally secure, it has the latest patches but every 3 months I need to contact the scan company and prove that I have a patched release.  Not fun.

CentOS is using gcc 4.1.2.  Gcc 4.1.2 was released in 2007 and many tools are requiring newer versions to work.  Most recently I tried using opscode/chef and while the site says it works with CentOS you’ll need to update the compiler to 4.2 or higher.  This defeats the purpose of using Chef IMO.

I also find myself building things like git on CentOS that are part of the standard repository on Ubuntu.  Sure, I can start adding random repositories to get these things but I’d rather work with an OS that has them in the default/supported repository.

I’ve talking with colleagues at several other companies over the past few weeks and several are using Ubuntu Server or are planning on getting off CentOS in the near future.   A side note on Rails from my talks,  there seems to be little excitement about CoffeeScript or Sass in Rails 3.1 (just learn css and js already) and folks prefer test-unit and shoulda over rspec.    I totally agree with this sentiment. 

I did a fresh install of Ubuntu today and figured I would share the steps and packages necessary to get Ruby on Rails running.    I always miss a package or 2 and need to go back.   Here is what worked for me today.

Rails3 / Ubuntu 10.10 / MySql / Nginx / Ruby 1.9.2

Core packages

  
sudo apt-get install curl # RVM needs it and it is good to have
sudo apt-get install libcurl3-dev  # needed by several gems and nginx i think
sudo apt-get install git # RVM needs it and it is good to have
# Packages needed by rails and some popular Gems (also ssl for nginx)
sudo  apt-get install build-essential bison openssl libreadline6  libreadline6-dev curl git-core zlib1g zlib1g-dev libssl-dev libyaml-dev  libsqlite3-0 libsqlite3-dev sqlite3 libxml2-dev libxslt-dev autoconf  libc6-dev ncurses-dev
# MySql
sudo apt-get install libmysqlclient-dev  sudo apt-get install mysql-server
# needed by nginx
sudo apt-get install libpcre3-dev  #nginx

Install RVM

bash < <(curl -s https://rvm.beginrescueend.com/install/rvm)
#fix .bashrc then
rvm install 1.9.2  # or whatever ruby version you like
rvm –default use 1.9.2
gem install rails

Install Passenger/Nginx with SSL

Grab Nginx tarball

cd /tmp
wget http://sysoev.ru/nginx/nginx-0.8.54.tar.gz
tar -zxvf nginx-0.8.54.tar.gz

# install the gem
gem install passenger

# build Nginx
rvmsudo passenger-install-nginx-module

• Watch Phusion Passenger do its thing and when it asks you “Automatically download and install Nginx?”, answer 2
• Specify the directory where you unzipped the nginx source code (Please specify the directory: /tmp/nginx-0.8.54))
• Specify the directory where you want to install nginx to (/usr/local/nginx in my case)

You’ll need a init script for nginx.  Get it here and follow directions

http://wiki.nginx.org/Nginx-init-ubuntu

To start Nginx use

sudo /etc/init.d/nginx start

Now at this point your nginx.conf needs some changes.  You need to point to your Rails apps and setup passenger.

Here is my http section for /usr/local/nginx/conf/nginx.conf .. this is a dev setup.  don’t read too much into it.

http {
 passenger_root /home/tony/.rvm/gems/ruby-1.9.2-p180/gems/passenger-3.0.6;
 passenger_ruby /home/tony/.rvm/wrappers/ruby-1.9.2-p180/ruby;
 passenger_user_switching on;
include       mime.types;
 default_type  application/octet-stream;

 log_format  main  '$remote_addr - $remote_user [$time_local] "$request" '
 '$status $body_bytes_sent "$http_referer" '
 '"$http_user_agent" "$http_x_forwarded_for" "$http_host"';

 access_log  /tmp/nginx.access.log  main;
 sendfile        on;
 keepalive_timeout  65;

 server {
 listen       *:80;
 server_name  localhost;
 rails_env development;
 root   /<path to my rails app>/public;

  if ($request_method !~ ^(GET|HEAD|POST|PUT|DELETE)$ ) {
   return 444;  # block requests that Rails doesn't handle
  }
passenger_enabled on;
}
# HTTPS server
server {
  listen       443;
  server_name  localhost;
  rails_env development;
  root   /<path to my rails app>/public;
  if ($request_method !~ ^(GET|HEAD|POST|PUT|DELETE)$ ) {
    return 444;  # block requests that Rails doesn't handle
  }
  ssl                  on;
  ssl_certificate      local.crt;
  ssl_certificate_key  local.key;
  ssl_session_timeout  5m;
  ssl_protocols  SSLv2 SSLv3 TLSv1;
  ssl_ciphers  ALL:!ADH:!EXPORT56:RC4+RSA:+HIGH:+MEDIUM:+LOW:+SSLv2:+EXP;
  ssl_prefer_server_ciphers   on;
  passenger_enabled on;
  }
}

restart your Nginx if it is already running

sudo /etc/init.d/nginx restart

That’s all..  hopefully this helps someone.     My nginx.conf is much longer so hopefully I didn’t cut out anything too important.

As I keep finding in Rails 3, the Gems I used in Rails 2 no longer work or have fallen out of favor.   In Rails 2 acts_as_ferret met my searching needs but after submitting some fixes for Rails 3 and Ruby 1.9.2, I was still having issues so I moved on to Sunspot.

One of the 1st things I wanted to change with Sunspot was to make the default boolean operator OR.   This means when someone searches for “car window” they will get results that match car or window.

Not being a Solr expert my 1st thought was that all I needed to do was change

<solrQueryParser defaultOperator="AND"/>

to

<solrQueryParser defaultOperator="OR"/>

But it didn’t work.   After some research and digging through the logs I learned that Sunspot is using the dismax request handler.  To make a long story short, dismax ignores the defaultOperator and uses a minimum_match field.   The good news here is that setting this field to 1 in your search query is easy and gives you the same function as  defaultOperator=”OR”.

In your controller your search would look something like this.

@articles = Article.search do
  keywords(actual_search) {minimum_match 1}
end

Next thing I wanted was for car searches to return results for cars and other stems.   This required a 1 line change in schema.xml

In the <analyzer> block just add <filter class=”solr.SnowballPorterFilterFactory” language=”English” />

      <analyzer>
        <tokenizer class="solr.StandardTokenizerFactory"/>
        <filter class="solr.StandardFilterFactory"/>
        <filter class="solr.LowerCaseFilterFactory"/>
        <filter class="solr.SnowballPorterFilterFactory" language="English" />
      </analyzer>

Finally, because the model I am searching is small and Java eats quite a bit of memory I wanted to reduce the Solr server’s memory footprint.  This may come back to bite me as my dataset grows but for now this is working fine.  To adjust the memory parameters used when using rake sunspot:solr:start just edit your sunspot.yml file and add min_memory and max_memory lines.

development:
  solr:
    hostname: localhost
    port: 8982
    log_level: DEBUG
    min_memory: 64M
    max_memory: 64M

This will result in -Xms64M -Xmx64M being sent to java on startup.

      <analyzer>
        <tokenizer class="solr.StandardTokenizerFactory"/>
        <filter class="solr.StandardFilterFactory"/>
        <filter class="solr.LowerCaseFilterFactory"/>
        <filter class="solr.SnowballPorterFilterFactory" language="English" />
      </analyzer>

While I’ve been using WordPress for my blog for over 5 years I dig into the internals so rarely that I often forget some of the cool things I’ve learned and done. In addition to my blog I’ve used it more like a CMS system where there were only pages and no posts, in this case the site used a static front page. I haven’t written any themes from scratch but I’m pretty comfortable hacking other people’s themes and adding new features.

I should probably do this on my wiki but I’m going to try putting some useful notes here.

Viewing database queries

Recently I tried out a calendar plugin that allowed you to enter and display future events.  For some reason it only let you show events 99 days in the future. I hacked the code to let me use 3 digits and it took forever to load my events so I added the following to the bottom of my footer.php (before </body>)

<?php
if (current_user_can('administrator')){
 global $wpdb;
 echo "<pre>";
 print_r($wpdb->queries);
 echo "</pre>";
}
?>

This dumps all database queries that are made to the bottom of the page.  Turned out that the plugin was querying the database once for each date in the future.  So when I set it to 200 it was making over 200 queries.  Rather than figure out why it was coded tis way I switched to using The Events Calendar Plugin.  It lets you specify if a post is an event and then you can add details.  It works well.

Header and Footer snippets

I had an application that I wanted to use the header and footer from a live wordpress blog.  Any time the blog header/footer was updated the application would update too.  The idea here is the wordpress and application maintain the same look and feel and  navigation.

To do this I created a header.php and footer.php file in my wordpress root directory (where wp-config.php is).  The files started with

<?php
require('./wp-blog-header.php');
?>

And then I stole code from the theme header.php and footer.php files to build the code snippets needed for the header and footer for my application.  I then did server side pulls of these live files, cached them and displayed them as my application header and footer.

I guess instead of copying the code I should try to factor out the common code between the theme files and these files so I don’t repeat it.  Has anyone done this?  I haven’t tried it yet.

No HTTPS?  Use OpenId

I hate sending passwords in the clear but often the cost of SSL is more than the cost of hosting your site so we just do without.  Personally I always link my openId to my main account and use that to sign in.  My assumption is this is much more secure than sending credentials in the clear.  I use the OpenID plugin for this.  I’m happy that Google now has OpenId support via their profiles.

Caching

DB Cache Reloaded or WP Super Cache?

I’ve used both although there are times when I think a database query is faster than building all these local files.  For low traffic sites does the cache help or hurt?  I don’t have any stats here.  Just thinking out loud. 

Broken Link Checker

Some sites have a lot of links.  This plugin lets you know when you’re pointing to a dead end.  Very handy.  http://wordpress.org/extend/plugins/broken-link-checker/

Akismet

Install this or spend all day deleting spam comments.

Backups

Moving my homeowners association web site from static files to wordpress allowed us to have multiple editors but it makes backing up the system much more difficult.  Before the site consisted of about 80 files.   Now there is a database and many more things can go wrong.   I had downloaded a wordpress backup plugin a few months ago but it wasn’t ready for prime time.   At the moment my backup consists of daily mysqldumps via cron that reside with my wordpress installation.  I then rsync that to my local machine (the wordpress install with db backups).   It’s not perfect but it works for now. I guess I could share these scripts in another post.

One more thing

I forgot what I was going to say,  maybe it will come to me later tonight.   This is why I should have done this on the wiki.    I hope someone finds this useful.

Back in February 2003 we got about 2 feet of snow in Montgomery County Maryland.   The snow plows completely ignored the side streets and focused on the primary roads.

The result?   3 days after the storm my street looked like this.

When the small plows finally came they were unable to deal with the heavy/wet snow so it took them a while to clear the streets.

I hope this doesn’t happen again.  It’s not like I live in the middle of nowhere.  300 ft up my street is 7 Locks Road which was kept clear.  Unfortunately,  “up” is the operative word here and no one was able to escape before the plows came.

I’m still hoping FedEx makes it today,  but the mailman got stuck a few hours ago so I’m not counting on it.   I did make the mailman’s day by helping him get out.

Update

I’m happy to report that my street was plowed around 4PM on the 20th so we were snowed in for less than 48 hours.

I’ve been using Rackspace’s Cloud Servers for months now and I thought moving some of our standard PHP apps (like wordpress) to Cloud Sites would save me some time as a sysadmin/developer.  I also figured I would setup a database there and use it for my Rails application that runs on Cloud servers (instead of building my own or using Amazon’s RDS).

I’m sorry to say that after a few days of working with Cloud Sites, I think managing the sites myself on Cloud Servers would be easier.   Fortunately, many of the problems I am having can be easily fixed.

My issues

1) No rsync or scp access.  Installing a wordpress site via FTP or Rackspaces file manager was just plain painful.  The file manager didn’t allow me to move files and it always extracted zip files to the root directory.  Maybe it works correctly on IE?   I only run linux so I have no way of knowing.

2) No easy way to do backups.   Cloud Sites allow you to run cron jobs but the example backups build tarballs on the same host that the site is running on.  When I saw they had ruby as a cron shell option I assumed they had the CloudFiles gem installed,  but they didn’t.  I want my backups off moved off the host.  I don’t want to log into my account and download them manually.

3) No access to database binary logs.  I like to take a snapshot every 15 minutes or so in case I lose my database but this is not an option with the cloudsites database.  You could do a mysql dump from another host but you probably don’t want to do this every 15 minutes.

4) For my Cloud Server rails app there was no LAN address to access my Cloud Site database so all my queries incurred bandwidth charges.

Feature Requests (easy to hard)

1) Give people a cron job (or simple backup tab like cloud servers has) that can be used to dump their database daily to Cloud Files.  Its a win for everyone.  The user gets automated backup and you get more Cloud Files revenue.   Here is a script I run from a Cloud Server to back up my Cloud Site database nightly (I can not run it as a Cloud Site job as the CloudFiles gem is not installed on the hosts..  as i mentioned above).

def run(command)
  result = system(command)
  raise("error, process exited with status #{$?.exitstatus}") unless result
end

cf = CloudFiles::Connection.new(@account_name, @cloud_key)
container = cf.container(@directory_name)
cmd = "mysqldump -C --opt -h #{@mysql_host} -u#{@mysql_user}  "
cmd += " -p'#{@mysql_password}'" unless @mysql_password.nil?
cmd += " #{@mysql_database} | gzip > #{@backup_directory}#{@db_file}"
run(cmd)
t = container.create_object(@db_file)
t.load_from_filename "#{@backup_directory}#{@db_file}"

2) Advertise the LAN address of the Database Hosts…  of course the address given now is probably a switch that hits several DB machines.

3) Fix the File Manager.   Maybe it’s just me but on Firefox/Linux moving files doesn’t work.  A crippled version of rsync may also be nice.  I suspect there are security issues here but shell access sure would be nice.

4) This is probably hard but it would be nice if I could get access to the MySQL binary logs.

Thanks for listening. 

Last October at BarCamp DC 2 I ran a session called  “To Cloud or Not? AWS, EC2, S3 or build your own“.  Unfortunately the barcamp wiki died and my notes are gone but at the time it seemed that everyone loved Amazon’s services.   I tried using EC2 in April and while the ablity to select from several pre-configured AMIs was nice, building your own AMI should have been easier.  I wanted to configure my machine and then push a button to have my image created.   With Amazon you needed to install tools and go through several steps to create an image.

Then I found Slicehost.  It was owned by Rackspace and had servers for as little as $20/month (for a 256MB instance).   A few weeks later I stumbled on Mosso, also owned by Rackspace and it had servers for about $11/month (plus bandwidth).   Since my applications were using very little bandwidth, I moved to Mosso which is now called The Rackspace Cloud.   With the Rackspace offerings you install your operating system image, configure it and then, from their control panel you can then back it up with 1 click.  You can also schedule backups.   This was so much easier than EC2.

Then there is the pricing.  Amazon’s small instance is a big vitrual machine and at $0.10/hour it runs around $70/month (i think it was 0.12/hour when I 1st started using it).    This is probably a good price if you need that much horsepower.    What could you possibly run from a 256MB instance anyway?  Here’s what I am running.

• A full rails app using Apache/Passenger and MySql (I had to remove several unused modules from apache config and my database is small at the moment)
• Apache PHP — I don’t have a database here but I suspect there is room

I suspect a 512MB instance a safe bet for most applications and I will lilely upgrade as my traffic and database size increases.   Depending on the situation, I may just spin up more instances of the same server as redunancy is a good thing.   Sure I could run everything on 1 AWS instance but if it dies I’m really SOL.

If you ever need a bigger slice you can upgrade in the control panel with 1 click.  All your configurations and IP address are kept the same. I usually make a backup (1 click) before doing this just in case something bad happens.

Rackspace is still making improvements to their APIs and Image Management so while they don’t offer as many services as Amazon, they have offered all important features to make developer’s lives easier, IMO.

For the record, I actually backup my Rackspace Databases to Amazon’s S3, I feel better knowing my backups are in a different datacenter. 

If you sign up (and found this post helpful) please use my referral code when creating your account.  It is REF-TONYCODE

Good wiki pages have good titles and the title is usually in the URL.   This is all well and good but if you’re creating pages on a corporate wiki that is hidden from the outside world, your title may be giving away too much information.

A few days ago on twitter one of my colleagues noticed this post on twitter.

JonGretar: I think AOL is using Erlang for it’s chat system redesign.  about 6 hours ago · Reply · View Tweet

His initial thought was that all our candid discussions about Erlang on twitter gave us away.  But this wasn’t the case.

Ooops.   Fortunately our Chat Backend Redesign is not a secret and our wiki page has links to all sorts of external sites.

For those non-techies out there let me explain what a referrer is.

When you click a link on a web page, the destination site is sent information on what page sent it the traffic.  The source page is the referrer (or referer as it is misspelled in the HTTP spec).    There are several useful applications that use the referrer information that I won’t discuss here.  Naturally, Wikipedia has a good article on the subject.  http://en.wikipedia.org/wiki/Referer

What would have been worse is if we had a page called wiki.office.aol.com/wiki/Technology_Acquisitions_In_Process and someone at company X noticed this referrer in their access logs.  If company X was a public company that person might run off and buy a pile of stock based on this simple observation.

Now most wikis are public and people wouldn’t be creating pages like this in the public space.  But more and more companies have internal wikis and it is becoming common to discuss things on these pages that should not be shared with the public.    Rather than having to worry about your page titles giving away too much information I have created a mediawiki extension that will prevent referrer information from being sent to external sites.

Information on the extension can be found here.

http://www.mediawiki.org/wiki/Extension:HideReferringPage

On Saturday, I spent the day at BarCampDC2.    Like last year there were plenty of great sessions.  I really wanted to discuss Amazon’s EC2 as I think it is where most small companies should be moving their sites and I see huge business opportunities in this space.   As the session board was being built I kept looking for something on Amazon’s EC2, S3 or AWS.  I had not used the services yet, but I was determined to discuss them as I know many of the companies present were using them.   In desperation, I grabbed a pen and a post it note and wrote “To Cloud or Not? AWS, EC2, S3 or build your own“.   I owned the session and I hoped I would have a few experts in the room so I could act as a moderator instead of presenter.

The room was packed and I started out by telling everyone that I had no presentation or experience with these technologies and hoped we had some experts in the room.   As I expected there were plenty of experts in the room and we had a great discussion on what Amazon had to offer and other offerings that companies can leverage.

The room was filled with some of the greatest minds from the DC Tech scene.

More pics are here.

My notes from the session are here. Nikolas Coukouma helped clean them up and added some additional pointers.  

After my session I attended several hard core geek sessions, as usual there were many sessions I was unable to attend.   Maybe we can videotape the sessions next time?
I attended

• 11AM – Nitrogen Web Framework
• 1PM – Git
• 2PM – MySQL Optimization
• 3PM-5PM wandered through various sessions.
• 5PM – Beer!   Great presentation by Chris Williams.   I thought this was an early happy hour room but instead Chris schooled us on the history of beer.

Afterward we headed to McFadden’s where I consumed several pints of  Guinness.   Fortunately I had taken the bus and metro from my house so getting home was a non-issue.

Thanks to Center for Digital Imaging Arts at Boston University for letting us have the conference there and thanks to all the folks that helped put this together.   Can we do this again in 6 months?