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

Write a Math module to extend the Fixnum class. This module should provide two methods. First, a class method called pi that prints out the value of pi to two significant digits. Second, an instance method called squared that squares a number. E.g. when you are finished the following should be possible:

puts Fixnum.pi
# 3.14
puts 2.squared
# 4

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?

Suppose you have the following array

stuff = [:dog,:cat,:orange,:banana]

1. How can you slice this array to create a new array [:cat,:orange]
2. Add the element :apple on to the end of the array.
3. Now take :apple back off again
4. Add the element :fish to the start of the array.
5. Now remove the element :fish.

Write a program to reverse a singly linked list? Modify that program to reverse a doubly linked list.

When opening a connection to a remote service, it's typically important to make sure that the connection (or "resource") is closed - no matter what happens in the code that uses the resource. In Java this might be done as follows:

Connection conn;
try{
  conn = new Connection("some service");
  conn.doSomething();
}
catch(Exception e){}
finally{
  conn.close();
}

This pattern is tedious and repetitious, and depends on the programmer to remember to include the finally clause. In Ruby, we can do better. Suppose we wished developers to be able to safely manage connection resources using a pattern like the following...

Connection conn = new Connection("some server")
using(conn){
   conn.doSomething();
}

Define a Kernel method using that ensures that no matter what happens within the using block, the connection is always closed.

The following code will fail with NoMethodError : private method 'dream' called for Dog

Assuming that you cannot modify the source code for the Dog class and that the method
must remain private - how can you nonetheless call this method from outside of Dog class?

class Dog
    def speak
        puts "woof"
    end

    private

    def dream
        puts "chasing a rabbit"
    end
end

dog = Dog.new
dog.speak
dog.dream

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

Start with an array of integers, 1 through 5. First, square all the elements in the array. Then, sum all the elements of the squared array.

Print out the prime numbers between 1 and 100. As a first pass, don't worry about writing an efficient algorithm. Just write clear code that is easy to follow. Once you've done that, consider different possible optimizations.

How do you share methods between different parts of your code in Ruby? Can you name three strategies for doing this? Discuss the pros and cons of each.

Suppose I have the following Array of tuples

[ ['a',1], ['b',2], ['c','3' ]

How can I convert this to a Hash?

{ 'a' => 1, 'b' => 2, 'c' => 3}

Once I've written the algorithm, how would I make it generally available throughout my Ruby application?

What will original and copy evaluate to in each of the following examples? Explain why there is a difference.

original = "hello"
copy = original
copy << " there"
puts copy
puts original

original = "hello"
copy = original
copy += " there"
puts copy
puts original

In each example below indicate whether or not we should be asserting true or false. (E.g. what should the ? be?).

Explain the difference between ==, eql and equal?

str1 = "chitter"
str2 = "chitter"

assert_equal ?, str1 == str2
assert_equal ?, str1.eql?(str2)
assert_equal ?, str1.equal?(str2)
assert_equal ?, str1.object_id == str2.object_id

sym1 = :chatter
sym2 = :chatter

assert_equal ?, sym1 == sym2
assert_equal ?, sym1.eql?(sym2)
assert_equal ?, sym1.equal?(sym2)
assert_equal ?, sym1.object_id == sym2.object_id

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.

Assume that you have access to an employee's email Inbox, and that you can parse the content of their emails, including the email headers.

1. How can you use this to deduce their first-degree connections?
2. What kind of heuristics can you come up with to quantify the strength of these first-degree connections?
3. How can you use this to deduce their second-degree connections?
4. How can you use this to deduce their third-degree connections?

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.

1. Describe how you would store a social graph in a relational database.
2. Describe an efficient algorithm to determine whether or not person X is a 2nd degree connection of person Y.
3. Describe an efficient algorithm to determine whether or not person X is a 3rd degree connection of person Y.
4. How can you make #3 very quick. E.g. how does Linked In compute 3rd degree connections quickly?

Write a string to find a substring in a given string. Do this in O(n) or better

Write an iterative function to reverse a string. Do the same thing as a recursive function.

Write a function to implement strstr() i.e. find the first occurrence of one string inside another string.

Write a program to print out a multiplication table, from 1x1 to 12x12. This should look like:

   1   2   3   4   5   6   7   8   9  10  11  12
   2   4   6   8  10  12  14  16  18  20  22  24
   3   6   9  12  15  18  21  24  27  30  33  36
   4   8  12  16  20  24  28  32  36  40  44  48
   5  10  15  20  25  30  35  40  45  50  55  60
   6  12  18  24  30  36  42  48  54  60  66  72
   7  14  21  28  35  42  49  56  63  70  77  84
   8  16  24  32  40  48  56  64  72  80  88  96
   9  18  27  36  45  54  63  72  81  90  99 108
  10  20  30  40  50  60  70  80  90 100 110 120
  11  22  33  44  55  66  77  88  99 110 121 132
  12  24  36  48  60  72  84  96 108 120 132 144

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)

Describe the difference between a class instance variable and a class variable in Ruby. Which bears more resemblance to a static field in Java?

What is the output of the following code? Explain.

def some_method
    x = "World"
    yield("Hello")
end

x = "Ruby"
some_method{|y| puts "#{y} #{x}!"}

What is a hashtable? Give an example of a type of problem that a hashtable is useful for.

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?

For the data structures: Array and Linked List explain:

• Where you might use them
• Operations that are commonly supported (add, insert etc)

In Ruby, there are three methods for converting a block into a Proc object (see below). Discuss the differences between these three choices.

b1 = Proc.new{|x| x + 1}
b2 = lamba{|x| x + 1}
b3 = proc{|x| x + 1 }

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

How do these bitwise operators differ from logical operators?

What's the value of hexadecimal FF in decimal?

Write a program to find the largest integer in an array of integers.

Write a function that sums up integers from a text file that looks like the following:

1
3
27
2
2123

Write function to print the odd numbers from 1 to 99

Write a program to open a file for reading and print out its entire contents

Write a function to take the following list and return one list of odd numbers and one list of even numbers:

ints = [1,21,53,84,50,66,7,38,9]

A user types the following URL into their browser: http://www.foo.com/bar.php

Explain in detail how this would cause a page to appear in their browser, with images, interactive elements (Ajax), styled paragraphs of text etc.

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.

Explain what a deadlock is in multithreaded programming

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].

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.

Write a function that takes an integer and returns the smallest number that is greater than the given number which is a palendrome.

For example, if the input was 111 the next palindromic number would be 121.

Write a function, tokenize_string(input_string, delimiter_list) that returns a list of strings that are separated by the delimiters.

For example: tokenize_string("How now, Mrs. Brown Cow") returns ['How', 'now', 'Mrs', 'Brown', 'Cow']

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 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.

The least common multiple of a set of integers is the smallest positive integer that is a multiple of all of the integers in the set.

Write a function that takes an array of integers and efficiently calculates and returns the LCM.

Write function that takes a binary tree and efficiently returns the Nth smallest element.

For example, if N=4, and the tree looks like:

    3
   / \
  2   5
 /   / \
1   4   6

The function should return 4.

Write a function that takes as input a binary tree, and prints out each level of the tree on a newline. For example:

    a
   / \
  b   c
 /   / \
d   e   f

will output:

a
b c
d e f

Write a function that takes a an array of integers, and returns the contiguous subsequence of integers with the largest sum.

Explain the terms "coupling" and "Cohesion". Is low coupling and high cohesion desirable? Why?

Model the animal kingdom as a set of classes. Discuss the species, their behavior and properties.

Explain the principles of test drive development.

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

Implement it.

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

Implement it.

Write a function to return the Nth number of Fibonacci sequence.

Design the schema or the classes to implement a library for building card games with. This library should make it easy to build games like Rummy, Poker, Hearts, Whist etc.

Outline the implementation for two of the most important methods of the Deck class.