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

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

For the data structures: Array and Linked List explain:

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

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]

Discuss an algorithm to traverse a tree, depth first.

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.

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.

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

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 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 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 to efficiently find the fifth maximum element in a binary search tree. Try to do this without using significant additional storage.