mozy

Yes, we really will be giving away $20,000 on Saturday April 14th to the winners of the BDS Coding Deathmatch.

Why are we doing this?

Two reasons:

Yes, this is a thinly disguised recruiting effort to find the best local engineers.
Incentivizing technical awesomeness is always a good thing.

Rules

You must be over 18 years of age.
You must be a full-time resident of Utah.
You must be eligible for full-time employment in the US.
No teams. This contest is for individuals.
You must be willing to give us your SSN if you want the cash prize (for the IRS).

Please note that although we are looking for the most awesome programmers in the area, the winner has absolutely no obligation regarding employment at Mozy. This contest is just that: a contest.

Prizes

Eight contestants will make it to the final round, and all eight of those finalists will win cash prizes. Each finalist will receive prize money based on the following formula:

Where x is your placement in the final round.

Winners of the previous deathmatch may compete, but they are not eligible to win cash prizes this time around (we're trying to spread the love here).

April 14th Deathmatch Schedule

10:00 AM	Round 1 (~1 hour) online at http://mozy.com/contest
12:00 PM	Round 2 (~1 hour) online at http://mozy.com/contest
4:00 PM	Final Round (~1.5 hours) at 774 East Utah Valley Drive, American Fork, UT

Keep in mind that if you make it to the final round, you are guaranteed to win some prize money, so even if American Fork is a bit of a drive for you it's well worth it.

The following languages are permitted:

C
C++
Java
Ruby
Python
C#
Lisp
Perl
PHP

All source code must be in a single file. If you are using a compiled language, the compilation command that you want to use must appear at the beginning of your source file.

When applicable, problems will show sample input and the corresponding correct output. The actual problem input will also be given, and your code should assume that the input is coming via standard input (stdin) and your code should print results to standard output (stdout.) You can assume all input will be valid in the context of the problem (ie. your code will not have to check for invalid or garbage input.)

All problems will be timed, and to complete a problem you need to cut & paste your code, and your answer into two text boxes on the problem web page and click the submit button.

To participate in the next round, you will need to re-login. Upon logging in, you will be told whether or not you qualified for the next round.

Round 1 and 2 will consist of several problems. They are all timed. At the end of the time limit for each problem, the page will refresh and go on to the next problem. If you have not submitted your code and answer in the given time, you will be able to continue with the round, but obviously submitting your code and answer is preferable.

About the Final Round:

Only a handful of participants will qualify for the final round. The winner of the final round will not only need to produce the correct answer, but their code will need to produce the correct answer in least amount of execution time (wall-clock.) Yes, we realize some languages will have an advantage in this regard - but the trade-off between ease of implementation and performance is part of the challenge. Note that it will be held here at our office in American Fork.

Proceed to Registration »

Sample Question 1

All questions will be timed, and this particular one should be able to be finished in less than 5 minutes. We'll post some more of these over the next couple of weeks.

We are looking for sequences of n > 0 integers where the absolute values 
of the differences of successive elements are included in the set of 
numbers 1 through n - 1. For instance,

4 1 2 3

is a match, because the absolute differences are 3, 1, and 1, respectively 
where n is 4.

8 6 2

is not a match, because the absolute differences are 2 and 4 respectively 
where n is 3.

The definition implies that any sequence of a single integer is a match.  
Write a program to determine whether each of a number of sequences is a match.

== Input ==

Each line of input contains a sequence of n integers where n < 1024.

== Output ==

For each line of input generate a line of output printing 'match' or 'not a match'.

== Example Input ==

5 3 2 -4
2 1 2 4 7
-3 2 1 4 3 3 6
3 4 6 7 3 4 5 12 14 -4 -9 -18 5 22 41 43 29 17 -2 7 19 22 23 24
3 9

== Example Output ==

not a match
match
not a match
match
not a match

Sample Question 2

This is an example of a question that wouldn't require source code to be submitted. Order these asymptotic bounds by rate of growth:

n log n
n^3
sqrt n
n!
ln ln n
n
2^n
n^2
log n
e^n

Sample Question 3

This was a 15-minute problem in the last deathmatch.

  Pascal's triangle is formed by writing numbers in staggered rows 
  such that the sum of any two numbers in one row is found directly 
  below and between the two numbers. The first five rows of the 
  triangle are as follows:

      1
     1 1
    1 2 1
   1 3 3 1
  1 4 6 4 1

  Pascal's triangle exhibits patterns present in binomial expansions, 
  fibonacci sequences, catalan numbers, the fractal Sierpinski 
  triangle, multi-level marketing scams, and more.

  We can produce similar triangles with different 'outer' initial 
  numbers. for example, with '2' we would get:

              2
           2     2
        2     4     2
     2     6     6     2
  2     8    12     8     2

  write a program to produce the nth row of pascal's triangle, given i, 
  the initial outer number. the output should list the numbers of that 
  row on a single line with single spaces between each number. 

  Sample input:

  2 6

  Sample output:

  2 10 20 20 10 2

  Real input:

  12 12
  100 5
  11 20

Sample Question 4

This was a 15-minute problem in the last deathmatch.

  On planet Pisa there are these cute little furry creatures called 
  Fibs. Here are some fun facts about Fibs:

  * Fibs like to reproduce. We don't know how they do it, exactly, 
    but every breeding pair produces another male and female pair 
    exactly once every year.
  * Fibs never die. They just keep reproducing forever.
  * Fibs don't start reproducing until they are exactly five years 
    old. A male and female pair both reaching their fifth birthday 
    will produce a new male/female pair that very day.
  * Planet Pisa started out with two Fibs, a male and a female, 
    born at the same time. (From where? We don't know.)

  It has now been 75 years since the first Fibs were born on Pisa. 
  How many Fibs are there now?

  Your program should read from stdin the number of years since the 
  first Fibs were born, and output to stdout how many Fibs there
  are on Pisa after that many years.

  Example:

  At 5 years, there would be 4 Fibs.
  At 10 years, there would be 16 Fibs.
  At 20 years, there would be 280 Fibs.

  Input:

  75