shinsetsu
BAN USERSurely the search space for this problem will always be exponential no matter what you do? There are 3^(N-1) 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*(5-X+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 sub-nodes 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 pre-determined 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[i-1] <= input[i] && state == ParseState.Ascending) ||
(input[i-1] >= input[i] && state == ParseState.Descending))
candidate += "," + input[i];
else if (input[i-1] > input[i] && state == ParseState.Ascending)
{
candidate += "," + input[i];
state = ParseState.Descending;
}
else if (input[i-1] < 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[i-1] + "," + 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;
}
}
Reppamulapaya2, Area Sales Manager at Alcatel Lucent
Jorie , a Customer services manager with more than 6 years' experience working is responsible for managing the relationships between an ...
Repnp810929, Product Security Engineer at Absolute Softech Ltd
I am Neesha , a Creative news writer with 3+ years of experience at Audio Visions. Great storytelling skills and a ...
Repharoldknopph, Android test engineer at AMD
I am a publicity writer from Atlanta USA . I create an intended public image for individuals, groups, or organizations. I ...
Repthonylermat, OOPS Experienced at 247quickbookshelp
I have been assigned based on the successful candidate's level of training and experience but will include types of ...
Repmonamore609, Android test engineer at Cisco Systems
Data entry clerks are responsible for inputting a high volume of data from multiple sources into a database, ensuring that ...
Repamritatorr, Paramedic at Capital Medical Billing
By profession, I am a paramedic in Chicago. I want to know about Indian ayurvedic treatment. I like to explore ...
Repjj2234971, Applications Developer at ABC TECH SUPPORT
My role for teaching students in a particular subject area. I specialize in a variety of subjects and fields. such ...
Java solution with O(N) run time and O(1) space complexity.
- shinsetsu November 11, 2013