Vikas
BAN USER
- 1of 1 vote
AnswersGiven a function
- Vikas in United States
float convex(float x)
WAP to find the minimum value of convex() between x1 and x2. convex is first monotonically decreasing and then monotonically increasing between x1 and x2.
float minima(float x1, float x2)| Report Duplicate | Flag | PURGE
Pocketgems Software Engineer / Developer Math & Computation - 0of 0 votes
AnswersIn a pocket calculator, a person is randomly typing a 8 digit number. What is the probability that the number looks the same even if the calculator is turned upside down.
- Vikas in United States| Report Duplicate | Flag | PURGE
GoDaddy Software Engineer / Developer Probability - 2of 2 votes
AnswersGiven an array, find all maximal sub-arrays in which all pairs have their sum greater than k. DP would give us a O(n^2) algorithm. Can we do better.
- Vikas in United States
suppose k = 4
-4 9 10 4 -3 8 9 -2
Answer is:
-4 9 10
9 10 4
-3 8 9
8 9 -2| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm
Copying an answer from SO:
Solution 1
I don't know if this is the same as Rem's solution, but you could solve this quite easily with a binary search tree.
Initialize an empty binary search tree and then iterate in reverse order through the array.
Insert each element in the binary search tree and then perform a count of all the elements in the tree above the value of the element. (If each subtree stores the number of elements it contains, then these operations can both be done in O(logn) if an appropriate balanced tree is used.)
The max number of successors is given by the largest count observed.
This is influenced by Venkatesh's solution - just a slightly different way to do it.
PreOrder: a b c d f g e
PostOrder: c f g d b e a
We first get the root. a is the root, (As for preorder, it starts with the root/ for post order it is the last.)
Then we locate the element immediate to root's right in pre order. i.e b
We take that b and locate in post-order. So cfgdb is left subtree and e is right subtree.
Now problem is reduced to:
Left subtree of root:
PostOrder:cfgdb
PreOrder:bcdfg(whatever is the length of PostOrder string above, we take that many chars in original PreOrder string. In this case 5)
Right subtree of root
preOrder: e (whatever is left after removing root and PreOrder substring from previous step)
PostOrder:e (whatever is left after removing root and PostOrder substring from previous step)
Repeat till the tree is constructed.
Keep two variables to store the 'max till the boundary' and 'max before the boundary'. Iterate over the elements of the array one by one and keep updating the variables. This is similar to the O(n) maximum subarray problem.
static int getMaxSubSeqNonAdjacent(int[] array) {
int sumTillBoundary = array[1];
int sumBeforeBoundary = array[0];
for (int i = 2; i < array.length; i++){
int sumBeforeBoundary2 = sumBeforeBoundary;
sumBeforeBoundary = Math.max(sumTillBoundary, sumBeforeBoundary);
sumTillBoundary = Math.max(sumBeforeBoundary2 + array[i], array[i]);
}
return Math.max(sumTillBoundary, sumBeforeBoundary);
}
@eugene.yarovoi, I had some concerns regarding quickselect.
The file may not have fixed size records. How would you implement iterating thru the file? It may not be trivial. There may be multiple integers on one line and each line may have different number of integers. Even if we have one integer per line, finding the next number would require some parsing (like find the bytes between the next 2 newlines)
Interesting use of min-heap. Could you explain your solution a bit in english - it is easier to follow than code.
Where is the heap in your code? Oh, I see, you are using priority_queue as heap. Interesting
Also, why are you multiplying items with -1?
You are only printing one solution. There may be multiple subarrays. See the question - it has an example
RepShastri Ji is well known hindi and tamil vashikaran specialist. He will give you effective and simple totke to control ...
> the max surpasser is found by iterating from index 0 and subtracting by one until a new element is found
- Vikas July 12, 2015@Yev, What is the start value of max surpasser in above step?