Hung Truong: The Blog!

Facebook Programming Puzzles – Prime Bits Revisited

So I got a comment on my original post about the Facebook Programming Puzzle called “Prime Bits” that asked:

did you get this part ?

Your implementation should have a running time faster than O(n), where n is b – a.

id like to see how you solved it.

I felt really stupid for not catching that part until I checked the Google cache of the page. Apparently Facebook added that requirement some time after April 2nd and, presumably, getting a lot of inefficient entries (mine included).

It’s also funny to note that if you look at the actual html, there’s a fun message hidden in comments that reads “with ‘efficient’ meaning whatever you think it ought to mean.” Touché, facebook, touché.

Off the top of my head, I can think of a way using dynamic programming to make the problem a lot more efficient. I’m not sure whether or not it’s just an amortization hack, or an actual better than O(n) implementation, technically.

Okay, so I went ahead and coded up the dynamic programming version. The running time actually does increase at a less than O(n) rate, so I think it counts. Maybe I’ll plot out the running time growth for good measure. I believe it’s in the neighborhood of log(n). I guess I’ll send this new version along with my resume again, and see if they’ll respond this time 🙂

Also, Rest in Peace, Facebook Guy. You’ll be sorely missed.

Ask.com on Google?

When I searched for ‘prime numbers’ just now on Google, the first hit was a sponsored link for Ask.com. You would think it’s a conflict of interest for Google to be suggesting a competitor to its users. When you think about it, though, Google is also taking money from Ask.com, literally!

It’s especially strange seeing Ask.com advertising on Google so soon after being criticized for launching a guerrilla negative ad campaign against them…

Craigslist and Google Maps Mashup Thingy: Day 5 – CakePHP

Today technically counts as day 5 of my Craigslist and Google Maps Mashup thing since I didn’t work on it at all yesterday due to getting Command and Conquer 3: Kane Edition. I got the limited edition number 73137, which is cool since it’s a palindrome!

Anyway, today I actually did work a little bit on the mashup. I spent most of my time switching out from a random php output file to a CakePHP setup. I haven’t ever used CakePHP before, but I have used Ruby on Rails quite a bit. CakePHP is sort of like PHP’s answer to rails. It copies a lot of the ideas and conventions that Ruby on Rails expects developers to follow.

Because of the similarities between CakePHP and Rails, I found it pretty simple to migrate the PHP I already had to CakePHP. I just had to learn the proper syntax to get everything working in Cake. I still think Ruby is a really beautifully simple language to write code in. Cake tries to get things looking Ruby-ish, but there’s still some weirdness involved. It’s good for me to be learning these PHP things anyway, though. I’ve put PHP on the backburner for too long.

Tomorrow, if I have time to work on the project, I think I’ll implement the actual UI side of things. I have a rough idea of how I want users to be able to interact with the site. Hopefully designing the interface will be as easy as it is in Rails.

Craigslist and Google Maps Mashup Thingy: Day 4

Today I made a bit more progress with my Craigslist Google Maps mashup thing. I setup the database table that handled the pictures for the listings, and added the images to the view as well. After that, I setup a new parser to parse the listings that can be found at the Michigan off-campus housing listings page. I’m not sure if I should make a separate page for these, or include them in the Craigslist listings…

I also came across a weird bug. When I ran the new Michigan parsing script by going to the page from a web browser, the thing would run fine, but after I uploaded to the server and ran it from the command line, it would flip out. It took me a really long time to figure out, but it turns out that I was calling a separate function by passing a value and not a reference.

I actually thought this might be a problem when writing the function, but when it worked, I forgot about the issue momentarily. The weird part is that the function works fine when you hit the .php file from a browser, and not when you run it from the command line. It must be some setting in the environment…

Besides that minor problem, everything seems to be going along smoothly. PHP has a lot of nice built in functionality for doing string manipulation, which this project has a lot of. It’s also got really nice networking and file reading capability. I guess that makes sense, since it originally came about as a tool for creating websites.

Tomorrow I’ll try to get the mashup site setup with actual options and navigation. Right now it’s just set on Ann Arbor. I’ll have to do some routing to get the many different options that people might want set up.

Craigslist and Google Maps Mashup Thingy: Day 3

Yesterday I worked on the mashup thing, but then I got sleepy and didn’t write a post about it. So here’s a post!

Basically I worked on adding the individual listings onto the Google Map with stuff like the description, address, and price. At first I thought about importing the points from some kind of xml document, but I figured the approach with just embedding it was easier.

Then I figured out how to start scraping some of the listing info from the Michigan off campus housing site. This site seems to have better listings in terms of quality and price. I think today I’ll work on getting all of that info into the database so I can map it as well.