# Reversing a linked list in Java

### Try Me!

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

# Prime numbers in Java

### Try Me!

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.

# Approximate the square root of a number in Java

### Try Me!

Use Newton's method to approximate the square root of a method. Newton's method is to approximate z = Sqrt(x) by picking a starting point z and then repeating:

```z = z - (z*z - x)/(2*z)
```

Pick a sensible point to stop the iteration.

# Sort an array of strings by the length of the string in Java

### Try Me!

Most languages have a built in sort method that will sort an array of strings alphabetically. Demonstrate how to sort an array of strings by the length of each string, shortest strings first.

# Design a flexible image conversion interface in Java

### Try Me!

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.

# Map the social graph by examining the contents of a user's Inbox in Java

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?

# Find the missing number in Java

### Try Me!

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.

# Mapping a graph to a relational database in Java

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?

# Implement HashTable in Java

### Try Me!

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.

# What is a Design Pattern in Java?

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

# Write a substring function in Java

### Try Me!

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

# Reverse a String in Java

### Try Me!

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

# Find one string inside another in Java

### Try Me!

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

# Print a multiplication table in Java

### Try Me!

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

# Object Oriented Concepts in Java

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
• Polymorphism (without resorting to examples)
• Method visibility (e.g. public/private/other)

# What is a hash table in Java?

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

# Big O notation in Java

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?

# Arrays Vs Linked Lists in Java

For the data structures: Array and Linked List explain:

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

# AND, OR, XOR and NOT in Java

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

How do these bitwise operators differ from logical operators?

# FF in Decimal in Java

### Try Me!

What's the value of hexadecimal FF in decimal?

# Find the largest integer in Java

### Try Me!

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

# Sum integers in a file in Java

### Try Me!

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

```1
3
27
2
2123
```

# Print odd numbers in Java

### Try Me!

Write function to print the odd numbers from 1 to 99

# Arguments in Java

How many ways can an argument be passed to a method. Explain each method.

# Access Modifiers in Java

What are different types of access modifiers? Explain what they do.

# And Finally in Java

Explain final, finalize() and finally?

# Garbage Collection in Java

Explain what Garbage Collection does. How is it normally initiated? How could you force it to run? What problems can it cause?

# this() and super() in Java

Explain thedifference between `this()` and `super()`

# Top level class modifiers in Java

Name 3 top level class modifiers.

# inner and anonymous classes in Java

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

# What is Reflection in Java

Explain what reflection is in Java and give an example of when you might use it.

# Interfaces and inheritance in Java

What is an interface in Java? Give and example of where you might use one. How does this compare to inheritance?

# Integer and int in Java

Explain the difference between Integer and int in Java and when you would choose to use one over the other.

# Accessing variables in inner classes in Java

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

# Print the contents of a file in Java

### Try Me!

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

# Separate a list of integers in Java

### Try Me!

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

# How the web works in Java

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.

# The difference between a mutex and a semaphore in Java

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?

# Random Numbers in Java

### Try Me!

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.

# Depth first tree traversal in Java

Discuss an algorithm to traverse a tree, depth first.

# Design a car reservation system in Java

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

# Email Regex in Java

Construct a regular expression that matches a valid email address.

# Characters in Strings in Java

### Try Me!

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.

# The Smallest Number in a Circular List in Java

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

# static, final and const in Java

Explain the terms static, final, and const

# Integer Matrix in Java

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 division function in Java

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

# Log Processing in Java

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.

# Products and Arrays in Java

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

# Random Numbers from Linked Lists in Java

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.

# Tic Tac Toe in Java

### Try Me!

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.

# Next highest number with same digits in Java

### Try Me!

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

# Next Palindrome in Java

### Try Me!

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

# Dictionary Distance in Java

### Try Me!

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.

# String Tokenization in Java

### Try Me!

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

# Cycle in a linked list in Java

### Try Me!

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

# Array Compaction in Java

### Try Me!

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

# Difference between string arrays in Java

### Try Me!

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)

# Travel Routes in Java

### Try Me!

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

# Floats to rational numbers in Java

### Try Me!

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

# Finding a 3 Integer Subset in Java

### Try Me!

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.

# Balancing Parentheses in Java

### Try Me!

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.

# Rotating an Array in Java

### Try Me!

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

# Least Common Multiple in Java

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.

# Longest Path in a Binary Tree in Java

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.

# The Nth Smallest Element in a Binary Tree in Java

### Try Me!

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.

# Multiplying Strings in Java

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.

# Sort a Large Array in Java

### Try Me!

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.

# Contiguous Integers with the Largest Sum in Java

### Try Me!

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

# Maximum element in a binary search tree in Java

### Try Me!

Write a function to efficiently find the fifth maximum element in a binary search tree. Try to do this without using significant additional storage.

# Coupling and Cohesion in Java

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

# Model the Animal Kingdom in Java

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

# Test Driven Development in Java

Explain the principles of test drive development.

# What is an Abstract Class in Java?

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

# What is a Final Class in Java?

### Try Me!

What is a Final class and where might you use one?

# Describe the Singleton Design Pattern in Java

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

Implement it.

# Describe the MVC design pattern in Java

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

Implement it.

# Describe the Factory Design Pattern in Java

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

Implement it.

# Describe the Observer Design Pattern in Java

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

Implement it.

# Describe the Strategy Design Pattern in Java

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

Implement it.

# Fibonacci in Java

### Try Me!

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

# Design a card game system in Java

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.