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

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 what the following code does:

package Person;
sub new {
    my $self = {
        _firstName => undef,
        _lastName  => undef,
        _ssn       => undef,
        _address   => undef,
        _salary    => undef,
        _dept      => undef
    };
    bless $self, 'Person';
    return $self;
}

sub print {
    my ($self) = @_;
    printf( "Name:%s %s\n\n", $self->firstName, $self->lastName );
}

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]

Describe two ways to concatenate strings in Perl. Contrast and compare.

Describe what the following Perl code does:

#!/usr/bin/perl
$numArgs = $#ARGV + 1;
print "$numArgs\n";
foreach $argnum (0 .. $#ARGV) {
print "$ARGV[$argnum]\n";
}

Write code to print the contents of the following array in Perl:

@fruit = ('banana', 'orange', 'apple');

Explain what the following Perl code would output:

$banana = 2;
print "$banana\n";
print '$banana\n';

In Perl, how would you allow functions to have private variables that retain their values from call to call?

What is a good way to fetch the contents of a web page in Perl, given a URL?

What is a common way of sending email from a Perl program?

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.

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.

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 that, given a word and a dictionary will efficiently return the minimal edits (character addition or deletion) to get to a word that exists in the dictionary.

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)

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

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.