shinsetsu
BAN USERSurely the search space for this problem will always be exponential no matter what you do? There are 3^(N1) combinations for applying the operators, even if you were only solving the problem for those that factorise to a single prime so F runs in exponential time not polynomial time?
 shinsetsu November 06, 2013I know I didn't realise use the domain restrictions to simplify the solution, but I can't really see how since there is no restriction on brackets (right?) for instance how can you parse some crazy complex brackets as tokens? Something like:
((4*(5X+X*(4/5))+1)*6)*(7*(X/(6+1)))+5X=0
The actual code for this seems beyond the scope of an interview but the solution I've sketched out is:
1. Parse the input string into a tree structure with = at the root and each node either an operator (+/*) or a value. The tree is structured with lower order operators higher in the tree. Take care to respect brackets when creating the tree.
2. Evaluate each side of the tree root. Each node evaluates to a composite value of x^2's, x's and a constant. Take care when multiplying two subnodes that have x^2 and x values. If you ever hit an x^3 value or higher order x, throw exception.
3. Subtract the right hand side values from the left hand side values to get something in the form ax^2 + bx + c = 0. Use the quadratic formulae to solve it.
Method 1:
The class that provides the GPS coordinates from the phone's sensor should be behind an interface and the concrete class not referenced directly by the code being tested. It should be passed into the constructor or created via dependency injection.
Create a test object that implements the interface and use dependency injection/pass it in to the code being tested. The test object returns predetermined test coordinates allowing you to test the location services logic.
Method 2:
Instead of using an interface, you could use a mocking framework and do the same thing.
If we are taking N to mean the number of total elements, let's call the dimensions X so N = X*X.
This can be beaten by using a heap to store the current set of minimum elements per array (rather than searching for the minimum each step which costs X steps). Removing minimum from heap costs log X, inserting next value costs log X.
So total complexity is O(N log(sqrt(N))
Won't LinkedHashMap degrade to a linked list though? (all hashes are the same) Which will be O(N) for remove.
Is removeCache just supposed to remove the last recently used item or a specific item? Is the cache supposed to hold a finite number of elements? Is it OK to have a really poor space complexity, reducing the number of elements the cache can hold?
What do you mean by WAP?
Here's my attempt for printing the longest bitonic sequence, it has a small bug when the longest bitonic sequence is preceded by many equal integers.
public class Bitonic {
private enum ParseState {
Ascending,
Descending
}
public static String PrintLongest(int[] input) {
String result = "";
String candidate = "";
ParseState state = ParseState.Ascending;
// we need at least 3 integers to satisfy bitonic criteria
assert input.length >= 3;
candidate += String.valueOf(input[0]);
for (int i = 1; i < input.length; i++) {
if ((input[i1] <= input[i] && state == ParseState.Ascending) 
(input[i1] >= input[i] && state == ParseState.Descending))
candidate += "," + input[i];
else if (input[i1] > input[i] && state == ParseState.Ascending)
{
candidate += "," + input[i];
state = ParseState.Descending;
}
else if (input[i1] < input[i] && state == ParseState.Descending)
{
// is this candidate longer than the current best?
if (candidate.length() > result.length())
result = candidate;
// now start building the next one
candidate = input[i1] + "," + input[i];
state = ParseState.Ascending;
}
}
// if we aren't currently descending then the current candidate doesn't work
if (state == ParseState.Descending) {
if (candidate.length() > result.length())
result = candidate;
}
return result;
}
}

shinsetsu
October 13, 2013 Open Chat in New Window
Java solution with O(N) run time and O(1) space complexity.
 shinsetsu November 11, 2013