Earlier this week, a Silicon Valley-based startup called Quora raised $11 million at an $86 million valuation from Benchmark Partners.TechCrunch’s Michael Arrington, who broke the funding news, says that Quora “has captured Silicon Valley’s imagination” ant that it is “one of the hottest private beta tickets in town. And for a question and answer site that’s saying something.”
Quora, a site where users ask and answer questions, was founded by a pair of Facebook veterans, Charlie Cheever and Mark Zuckerberg’s high school best friend, Adam D’Angelo.
Sound like a place you’d like to work? Better bone up on your programming skills. Here’s the “programming challenge” Quora insists all job applicants take:
1. Datacenter Cooling
We have some rooms in our datacenter, and we need to connect them all with a single cooling duct.
Here are the rules:
- The datacenter is represented by a 2D grid.
- Rooms we own are represented by a 0.
- Rooms we do not own are represented by a 1.
- The duct has to start at the air intake valve, which is represented by a 2.
- The duct has to end at the air conditioner, which is represented by a 3.
- The duct cannot go in multiple directions out of the intake or the AC – they must be the two endpoints of the duct.
- The duct must pass through each room exactly once.
- The duct cannot pass through rooms we do not own.
- The duct can connect between rooms horizontally or vertically but not diagonally.
Here is an example datacenter:
2 0 0 0<br /><br />0 0 0 0<br /><br />0 0 3 1<br />
There are two possible ways to run the duct here:
2--0--0--0<br /> |<br />0--0--0--0<br />|<br />0--0--3 1<br />
2 0--0--0<br />| | |<br />0 0 0--0<br />| | |<br />0--0 3 1<br />
Write a program to compute the number of possible ways to run the duct. For the above example, the correct answer is 2.
Your program should read from stdin. The input will be a series of integers separated by whitespace.
The first two integers will be W and H, with width and height of the datacenter. These will be followed by W*H more integers, specifying the 2D grid representing the datacenter.
Your program should write a single integer out to stdout: the number of possible ways to run the duct.
See how fast you can make it.
Our best solution (written in C) can solve the following test case in under 5 seconds on a 2.4GHz Pentium 4, but it’s pretty good if you can get to within 1-2 orders of magnitude of that.
7 8<br />2 0 0 0 0 0 0<br />0 0 0 0 0 0 0<br />0 0 0 0 0 0 0<br />0 0 0 0 0 0 0<br />0 0 0 0 0 0 0<br />0 0 0 0 0 0 0<br />0 0 0 0 0 0 0<br />3 0 0 0 0 1 1<br />
2. Python URI
In Python, write a class or module with a bunch of functions for manipulating a URI. For this exercise, pretend that the urllib, urllib2, and urlparse modules don’t exist. You can use other standard Python modules, such as re, for this. The focus of the class or module you write should be around usage on the web, so you’ll want to have things that make it easier to update or append a querystring var, get the scheme for a URI, etc., and you may want to include ways to figure out the domain for a URL (British-site.co.uk, us-site.com, etc.)
We’re looking for correctness (you’ll probably want to read the relevant RFCs; make sure you handle edge cases), and elegance of your API (does it let you do the things you commonly want to do with URIs in a really straightforward way?,) as well as coding style. If you don’t know Python already, then this is also an exercise in learning new things quickly and well. Your code should be well-commented and documented and conform to the guidlines in the PEP 8 Style Guide for Python Code. Include some instructions and examples of usage in your documentation. You may also want to write unit tests.
Easy as pie? OK smartie. Try:
Business Insider Emails & Alerts
Site highlights each day to your inbox.