Archive for June, 2011
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.
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.
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.
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.