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

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.

Explain the difference between the following quoting in Python:

my_string = 'the cat sat on the mat'
my_string = "the cat sat on the mat"
my_string = """the cat sat on the mat"""
my_string = '''the cat sat on the mat'''

Explain with the following files and directories in a basic Django project do:

mysite/
    manage.py
    mysite/
        __init__.py
        settings.py
        urls.py
        wsgi.py

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

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?

What is a design pattern and why are they useful in software development?

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)

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)

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

Explain the difference between method overloading and method overriding

What is __init__.py? Give an example of where you would use it.

Explain what a list comprehension is and write some code that illustrates an example use.

Explain the difference between a tuple and a list and give an example of where you would use each.

Explain what the following Python code does:

phrase = 'hello mommy'
print phrase[:4] + phrase[4:]

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

Write a python program that will take the following list of words as input and output a dictionary with a the frequency of each word:

words = ['apple', 'apple', 'banana', 'banana', 'banana', 'pear', 'banana', 'pear', 'pear', 'pear', 'pear', 'pear']

Write one line of readable Python code that will print the sum the integers from 1 to 100

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]

What is load balancing? Describe three different types of load balancing techniques? What problems can load balancing solve? What problems can it introduce?

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.

What is a generic view in Django? What generic views ship with Django? What do they do?

Explain what the following Django model code does? What's the relationship between topping and pizza?

class Topping(models.Model):
    # ...

class Pizza(models.Model):
    # ...
    toppings = models.ManyToManyField(Topping)

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,
    })

What is a signal in Django? Where might you use one? What's the difference between send() and send_robust()? When might you use one over the other?

What does the following code do? What's another way of doing the same thing?

from django.core.signals import request_finished
from django.dispatch import receiver

@receiver(request_finished)
def my_callback(sender, **kwargs):
    print "Request finished!"

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()

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.

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

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.

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

Write a function that takes as input a sorted array and modifies the array to compact it, removing duplicates. Also return the new length of the array.

Notes: The input array might be very large.

For example:

• input array = [1, 3, 7, 7, 8, 9, 9, 9, 10]
• transformed array = [1, 3, 7, 8, 9, 10]
• size = 6

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"

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.

Write a function that takes an array of integers and returns that array rotated by N positions.

For example, if N=2, given the input array [1, 2, 3, 4, 5, 6] the function should return [5, 6, 1, 2, 3, 4]

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 a function that takes as input a binary tree, and returns the length of the longest path.

For example, in this binary tree:

    1
   / \
  2   3
     /
    5

the answer is 2, since the path from vertex 1 to vertex 5 involves two edge traversals.

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 two numbers represented as strings, and returns the product of the numbers of a string.

The numbers can be arbitrarily large.

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

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.

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.

What is an abstract class and when might you use one?

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.