CareerCup

Given a string and a dictionary, return an array of all the possible ways the string can be broken into different valid words.

i.e. Given `hotelfeat` return
[
	["hot", "elf", "eat"],
	["hotel","feat"]
]

For the dictionary you can assume that you either have a large set of valid words or you can call something like

public Boolean isValidWord(String str)

The method signature would look something like the following in Java:

public ArrayList<ArrayList<String>> possibleWordCombinations(String str, Dictionary dict);

A correct answer would use recursion and/or dynamic programming.

Given an array of n integers, return the maximum PMEAN of all possible array rotations, 
where PMEAN = the sum of each integer multiplied by its current location (index + 1).

For example:

The PMEANs for every rotation of the array {20, 30, 10} are:

PMEAN1 = (1 * 20) + (2 * 30) + (3 * 10) = 110
PMEAN2 = (1 * 30) + (2 * 10) + (3 * 20) = 110
PMEAN3 = (1 * 10) + (2 * 20) + (3 * 30) = 140

The max PMEAN of array {20, 30, 10} is 140.

The question is simple enough. I was able to get a working algorithm quick enough, but I failed to optimize my answer.
Hint from the interviewer:
If you have PMEANn, how can you use the result to get PMEANn+1?

Let's say you have a simple function (fibonacci/factorial) that you need to run constantly. The largest number that you will receive as input will be 1,000. How can you improve the performance of this function call?

I said not use recursion and cache the results using a data structure (i.e. a Map)
What else could you do to improve the performance?