nooreddin
BAN USERprivate static String removeOuterBraceHelper(String test){
char[] elements = test.toCharArray();
if(elements[0] != '(')
return test;
if(elements[elements.length - 1] != ')')
return test;
while(validate(test.substring(1, test.length()-1)) && test.startsWith("("))
test = test.substring(1, test.length()-1);
return test;
}
public static String removeOuterBrace(String test){
if(! validate(test) )
return "INVALID";
return removeOuterBraceHelper(test);
}
private static String removeOuterBraceHelper(String test){
char[] elements = test.toCharArray();
if(elements[0] != '(')
return test;
if(elements[elements.length - 1] != ')')
return test;
int matched = 1;
for (int i = 1; i < elements.length; i++) {
if(elements[i] == '(') {
matched++;
}
else if(elements[i] == ')') {
matched --;
if(i == elements.length - 1 && matched == 0)
if(validate(test.substring(1, test.length()-1)))
return removeOuterBraceHelper(test.substring(1, test.length()-1));
}
}
return test;
}
private static boolean validate(String test) {
char[] elements = test.toCharArray();
int i = 0;
int matchCount = 0;
for (char c:
elements) {
if(c == '(') {
matchCount++;
i++;
}
else if(c == ')') {
matchCount--;
i--;
}
if(matchCount < 0)
return false;
}
return i == 0;
}
}
A simple solution is to save in-order tree walk of one of the trees on an array, then run the algorithm on the other trees and compare it with the array. If you do not allowed to use external memory, you should run the in-order tree walk on two trees at the same time. To do this you need to jump from in-order-tree-walk1 to in-order-tree-walk2 whenever a new node is printed in the in-order-tree-walk1 and compare it with the printed node in the in-order-tree-walk2. Inside a for loop do this process for the first tree and all other n-1 trees.
The point of the problem in my opinion is to see if you can manage multiple recursion (A recursion that includes more than one function) or not.
Its easy. Create a graph. The vertex set V is a set of all stations. If there is a direct path between two station in any bus path then place an edge between those two stations in the graph and set the label of the edge be the set of bus lines that have that path. Starting from the Start run BFS until you reach to the End. The number of possible solutions is the the multiplication of the size of all sets on the shortest path.
- nooreddin February 21, 2018If each location have index of x and y then if each white chess x is between at least two black chesses x with same y and each white chess y is between at least two black chess with same x then that chess is surrounded by black chesses.
1. Sort all black chesses by x in array A in O(n lg n) time.
2. Sort all black chesses by y in array B in O(n lg n) time.
3. For each white chess search for its x in the first array in O(lg n). Compare y of this white chess with y of all matched y chesses ( in worst case it takes O(n) ). If it is between at least two of them then do the same process for x. If either of these cases does not match then ignore this chess. Otherwise continue to the next chess.
If there are n black chess and m white chess then the worse case running time of the algorithm is O( n lg n + n m ).
1. Sort all nodes based on the parent id.
2. Processes getChildren returns the first and last index of children of the parent by doing binary search on the list for the parent ID. It takes O(lg n) time.
3. Recursively print out the all the subweights by calling the subweight procedure on the root.
subweight(root)
if root = null
return 0
children <- getChildren(root.ID)
childrenWeights <- 0
for child in children
childrenWeights <- childrenWeights + subweight(child)
return root.weight + childrenWeights
in total it takes O(n lg n) time and O(n) memory.
You need to swap 1 by 1, 2 by 2, 4 by 4, 8 by 8 and so on.
If you use shifting strategy it take O(n^2), using this strategy it takes O(n log n).
a0 a1 a2 a3 a4 a5 a6 a7 b0 b1 b2 b3 b4 b5 b6 b7
(a0) (a1) (a2) (a3) (a4) (a5) (a6) (a7) (b0) (b1) (b2) (b3) (b4) (b5) (b6) (b7)
(a0 b0) (a2 b2) (a4 b4) (a6 b6) (a1 b1) (a3 b3) (a5 b5) (a7 b7)
(a0 b0 a1 b1) (a4 b4 a5 b5) (a2 b2 a3 b3) (a6 b6 a7 b7)
(a0 b0 a1 b1 a2 b2 a3 b3) (a4 b4 a5 b5 a6 b6 a7 b7)
(a0 b0 a1 b1 a2 b2 a3 b3 a4 b4 a5 b5 a6 b6 a7 b7)
Sort in ascending order of the first elements using quick sort. Then try to find the location of the second element in the sorted list using binary search on the right hand side of its greater number.
You may also sort the second part and then do one time merge. In any of these methods the running time will be O(n log n), because you have n/2 items that you don't know their order.
This is the problem of job scheduling using N jobs and K factory line. There is a greedy solution for this problem.
Sort jobs based on their finish time and select the jobs for the lines (rooms), if there is more than one line (room) that job can fit inside then select the line with the least interval of the last finished job on that line and the current job. If the job doesn't fit then drop that job and go to the next job.
private static String removeOuterBraceHelper(String test){
- nooreddin August 26, 2020while(validate(test.substring(1, test.length()-1)) && test.startsWith("("))
test = test.substring(1, test.length()-1);
return test;
}