Implement a fancier version of attr_accessor that includes validation. Complete the attr_validated code below so that the unit tests pass.

require 'test/unit'

class Dog

    def self.attr_validated(method_name, &validation)
        # Complete this method so that the unit tests pass
    end

    attr_validated :num_legs do |v|
        v <= 4
    end


end

class TestDog < Test::Unit::TestCase

    def test_good_value
        dog = Dog.new
        dog.num_legs = 3

        assert_equal 3, dog.num_legs
    end

    def test_nil_value
        dog = Dog.new
        assert_raises ArgumentError do
            dog.num_legs = nil
        end
    end

    def test_illegal_value
        dog = Dog.new
        assert_raises ArgumentError do
            dog.num_legs = 5
        end
    end

end

Suppose you have a class that performs several expensive calculations. However, during the lifetime of an object, the result of the expensive calculation won't change. Therefore, you wish to ensure that each calculation is performed only once, and that result is cached. A simple technique for this would be as follows:

class Calculator
    def expensive_calc_one
        return @result1 unless @result1.nil?
       @result1 = # Do very expensive calculation.
    end

   def expensive_calc_two
        return @result2 unless @result2.nil?
       @result2 = # Do very expensive calculation.
    end
end

If this class contained many such expensive calculations, this memoization technique would become repetitive. Can you come up with a framework that reduces this repetition by allowing one to simply mark a method as memoized and no longer have to worry about manually handling the caching?

Bonus points: There is a flaw in the simple technique. Under one set of circumstances the caching will fail and repeated calls to expensive_calc_one will result in the expensive calculation being executed again and gain. When would this occur?

You have a class Parent with a virtual method a and a class Child that implements a. You also have a several functions:

void f1(Parent p) { p.a(); }
void f2(Parent* p) { p->a(); }
void f3(Parent& p) { p.a(); }

When called with a Child instance, which method will be invoked for f1, f2 and f3?

Explain in detail what the following C++ code does:

#include <iostream>
using namespace std;

template <class T>
T GetMax (T a, T b) {
  T result;
  result = (a>b)? a : b;
  return (result);
}

int main () {
  int i=5, j=6, k;
  long l=10, m=5, n;
  k=GetMax<int>(i,j);
  n=GetMax<long>(l,m);
  cout << k << endl;
  cout << n << endl;
  return 0;
}

Describe a schema (or classes) to power an online restaurant reservation system. Describe the tables and the relationships beween the tables.

This system should allow a user to reserve a table at a restaurant for a certain time period and a certain party size.

It should allow the restauranteur to configure the system to describe their restaurant and manage reservations.

Think http://opentable.com

Write a helper method that takes either a string or a block as an input parameter and returns the input wrapped in a div with class = bubble.

Suppose you have a class Dog with two methods GetHasSpots and say_Woof. The method names do not follow your new naming conventions and you wish to rename them to has_spots? and say_woof. However, finding and correcting all references to these methods in one coding session is impractical due to a very large code base.

Thus, for some interim period of time you wish to allow both the old method names and the new methods names to work. Of course, you want to do this in the most DRY way possible, while also clearly marking the old methods as deprecated. The shell of a solution is shown below. Fill in the details of the deprecate method to make the unit tests pass.

require 'test/unit'

class Dog

    def has_spots?
        true
    end

    def woof
        "woof"
    end

    def self.deprecate(old_method, new_method)
       # Add code here that will make the unit test pass
    end

    deprecate :say_Woof, :woof
    deprecate :GetHasSpots, :has_spots?
end

class TestDog < Test::Unit::TestCase

    def test_deprecation
        dog = Dog.new
        assert_equal true, dog.GetHasSpots
        assert_equal "woof", dog.say_Woof
    end

end

Modify the + operator in Ruby so that it always adds an extra (i.e1+1=3`). When you are done the unit test below should pass.

Hint: remember that the + operator is really a method with signature def +(value) on the Fixnum class.

require 'test/unit/'

class BackToKindergartenTest < Test::Unit::TestCase
    def test_plus_one
        assert_equal 3, 1 + 1
        assert_equal 5, 2 + 2
        assert_equal 1, -1 + 1
    end
end

What is a register variable in C? When would you use one? What is the downside of using this storage class?

Complete the following Django model to illustrate how a manufacturer can make many different types of cars.

Give manufacturer a name, founding date and a country.

Give car a name, cost, engine capacity and color. Assume that the manufacturer makes cars in only {red, green, blue and pink}.

class Manufacturer(models.Model):
    # A car manufacturer

class Car(models.Model):
    # A type of car

What is the difference between pointer and reference? Please describe the two main differences.

Suppose you have a web form that allows users to upload JPG, GIF or PNG images. Before you store the images in your system, you want to convert them all to the JPG format. Design an image converter API. Sketch out all classes and interfaces that are involved.

Note: the actual code necessary to convert a JPG image to a GIF image is not the point. Just place a comment at the appropriate location where the actual conversion should occur.

Suppose you have an array of 99 numbers. The array contains the digits 1 to 100 with one digit missing. Describe four different algorithms to compute the missing number. Two of these should optimize for low storage and two of these should optimize for fast processing.

Write a fast implementation for a hash table in Java. You may use arrays and the built in int hashCode() method that returns the hash code for all Java objects.

Define the following object oriented concepts:

• Class, object (and the difference between the two)
• Instantiation
• Method (as opposed to, say, a C function)
• Static methods and classes
• Destructor/finalizer
• Inheritance
• Encapsulation
• Multiple inheritance (and give an example)
• Abstract class
• Interface/protocol (and different from abstract class)
• Method overriding
• Method overloading (and difference from overriding)
• Polymorphism (without resorting to examples)
• Method visibility (e.g. public/private/other)

Explain each of these types of joins:

• Inner Join
• Outer Join
• Left outer join
• Right outer join
• Full outer join
• Cross join

Explain big o notation and how it is useful in computer science to classify algorithms.

• What order is a hash table lookup?
• What order is determining if a number is even or odd?
• What order is finding an item in an unsorted list?
• What order is a binary search?

Describe bitwise operators AND, OR, XOR and NOT. Describe how you might use these.

How do these bitwise operators differ from logical operators?

Write the Bash statements to:

1. Count the number of files ending in .java, in the current directory that have the string "pumpkin" in the file contents?
2. Do the same, including files in any sub-directory (recursively)
3. Replace every occurrence of "pumpkin" with "banana" in each of the files

Explain what each of the following Bash statements does and the overall result:

$ (date ; ps -ef | awk ‘{print $1}’ | sort | uniq | wc -l ) >> processes.log

Name 3 top level class modifiers.

Explain the difference between an inner class and an anonymous class? When would you use these?

Can an inner class be defined inside a method? What variables can be accessed by that class?

What is CAP theorem? Describe how weakening consistency constraints can yield highly available distributed systems (e.g. databases). Give an example.

Describe consistent hashing and the advantages that it has over traditional hashing techniques. How can this technique help while scaling distributed systems, for example, distributed hash tables?

Imagine a scenario where your website's database can only handle 1,000 queries every second, and your traffic has grown enough to product 1,500 queries per second at peak times.

What can you do to deal with this problem in the short term? What's a long term solution to deal with ongoing growth in traffic?

Write a jQuery plugin to display a list of images in a Lightbox.

Contrast and compare the features of Google's BigTable and Amazon's Dynamo databases

Explain the properties, advantages and drawbacks of these different types of NoSQL databases. Give examples of each type of database e.g. CouchDB is an example of a document Oriented Database.

• Document Oriented Database
• Ordered Key/Value Store
• Eventually consistent Key/Value Store
• Graph Database
• Object Database

How does caching work in Drupal? Dicuss the page cache, block cache and CSS/JavaScript optimizations.

What modules add caching to help Drupal scale?

Explain the Drupal architecture and specifically how the following components interact:

1. Templates
2. Blocks and Menus
3. Modules
4. Hooks
5. Database: Caching, schema and the abstraction layer

What are hooks in Drupal? How are they used? Explain the function of the following hooks:

1. hook_delete
2. hook_form
3. hook_insert
4. hook_validate
5. hook_user_delete
6. hook_form_alter

Explain in detail, what's going on in the three paths through this Django form view processing code.

def contact(request):
    if request.method == 'POST': 
        form = ContactForm(request.POST) 
        if form.is_valid(): 
            # ...
            return HttpResponseRedirect('/thanks/')
    else:
        form = ContactForm()

    return render_to_response('contact.html', {
        'form': form,
    })

Complete the following Django form to include:

• A subject with a maximum length of 100 characters
• An optional, boolean, cc_myself field
• A sender field that will be validated as a correctly formatted email address

from django import forms

class ContactForm(forms.Form):
    message = forms.CharField()

Explain the difference between a mutex and a semaphore? If you need to protect access to an increment operation which one would be the best choice?

Write a program to measure how long a context switch takes on the Unix operating system.

If you have access to a function that returns a random integer from one to five, write another function which returns a random integer from one to seven.

Discuss an algorithm to traverse a tree, depth first.

Describe a schema (or classes) to power an online car rental system. Describe the tables and the relationships beween the tables.

Construct a regular expression that matches a valid email address.

Implement a function with signature find_chars(string1, string2) that takes two strings and returns a string that contains only the characters found in string1 and string two in the order that they are found in string1. Implement a version of order N*N and one of order N.

You have to debug a crashing application. You are given the source. When you run it repeatedly in a debugger you observe that it never crashes in the same place twice. It uses only the C standard library and is single threaded.

What coding errors could cause the crashes? How would you find them?

Describe the congestion avoidance algorithm in the TCP protocol.

Given a circular list of integers (when you reach the end of the list you come back to the beginning), what is the most efficient algorithm to find the smallest integer in the list?

For example: circular_list = [22, 52, 66, 82, 5, 8, 12, 19].

Given a N by N matrix of both negative and positive integers. Write an efficient algorithm to find the sub-matrix with the largest sum of all the contained elements.

Implement a function to divide two integers without using the divide operator.

Design a system to efficiently calculate the top 1MM Google search queries and create a report of these. Additionally:

• You are given twelve servers
• Each has two processors, 4GB of ram and four 400GB hard drives.
• The machines are networked
• The log data as roughly 100 Billion log lines in it.
• The log data comes in twelve, 320 Gb files.
• Each line of the files has roughly 40 search queries
• You can only use open source software or software that you write.

Given an array A[N] containing N numbers. Crate an array Output[N] where Output[i] is equal to the product of all the elements of A[N] except A[i].

For example Output[0] is the product of A[1] to A[N-1] and Output[1] is the product of A[0] and from A[2] to A[N-1].

Do this without using the division operator. Do it in O(n).

You are given a linked list of integers of length N.

N is very large and you don’t know N.

Write a function to return k completely random numbers from the list.

Do this in O(n).

Hint: Use random function rand() (returns a number between 0 and 1) and irand() (return either 0 or 1) 2.

Write a function to efficiently determine the result of a game of Tic Tac Toe.

The function takes as input the game and the sign (x or o) of the player. The function returns if this player has won the game or not.

Carefully consider both the data structure and the algorithm for your answer.

Efficiently calculate the shortest distance between two Facebook users given an API endpoint that returns all friends of a given user.

Given any integer, efficiently find the next highest integer that uses the same digits.

For example if the number is 15432, you should return 21345.

You want to check that your friend, Bill, has your accurate phone number, but you can't ask him directly. You have to write a question on a card which and give it to Ava. She will take the card to Bill and then return the answer to you.

What should you write on the card to ensure Bill can encode the message so that Ava cannot read your phone number?

Imagine you have eight balls, each of the same size.

One of the balls weights slightly more than the other seven.

Using a balance, find the heavier ball using only two weighings.

Write a function to efficiently determine if a linked list has a cycle in it.

Given two arrays of strings, A and B.

B contains every element in A, and has one additional member, for example:

* A = ['dog', 'cat', 'monkey]
* B = ['cat', 'rat', 'dog', 'monkey']

Write a function to find the extra string in B. Do this in O(n)

Express the following table as a static structure, and write a function, find_routes(source, destination) that efficiently outputs all possible routes.

Source  | Dest
~~~~~~    ~~~~
Seattle | LA
LA      | Florida
LA      | Maine
Florida | Seattle
Seattle | Florida

The solution for find_routes('Seattle', 'Florida') should be [Seattle -> Florida, Seattle -> LA -> Florida]

Write a function to efficiently convert a floating point number to a rational number. For example, given 0.125 return "1/8"

You are given a rectangular cake with a rectangular piece removed. The removed piece is of any size or orientation.

How would you cut the remainder of the cake into two equal halves with one straight cut of a knife?

Write a function that takes an unsorted integer array, and returns a three element subset whose sum is zero.

Note: This is a special case of the SUBSET-SUM problem. That problem is NP-complete, but we're only looking for subsets of 3 elements. This can be achieved in polynomial time.

Write a function that takes as input a string, and outputs that same string, with any parentheses in it balanced. Do this using the minimum number of edits.

Given a file of size 1TB, containing only 32 bit integers, describe how you would efficiently sort it. You have only 2GB of memory available.

Describe the Strategy design pattern and how you might use it in practice.

Implement it.

What's the maximum unsigned integer that you can store using n bits? What's the maximum signed integer?