Martin
BAN USERLooking for a job in Seattle. Contact me at zaphodile@gmail.com
Node* construct_tree() {
// left means matching, right means not matching
Node* root = new Node("AP");
root->left = new Node("APP");
root->left->left = new Node("APPLE");
root->left->right = new Node("APE");
root->right = new Node("B");
root->right->left = new Node("BAB");
root->right->left->left = new Node("BABY");
root->right->left->right = new Node("BALL");
root->right->right = new Node("CAT");
}
vector<string> find_matches(string str, Node* root) {
Node* last = NULL;
Node* curr = root;
// Find the last matching node
while (curr) {
int min_len = min(str.length(), curr->str.length());
bool str_eq = str.substr(0, min_len).compare(0, curr->str.substr(min_len)) == 0;
bool too_long = str.length <= curr->str.length();
if (str_eq && too_long) { last = curr; break; }
else if (str_eq) { last = curr; curr = curr->left; }
else curr = curr->right;
}
// Now collect all the leaves under last
vector<string> matches;
queue<Node*> nodes;
nodes.push(last);
while (nodes.size() > 0) {
Node* n = nodes.pop();
if (!n->left && !n->right) matches.push_back(n->str);
if (n->left) nodes.push(n->left);
if (n->right) nodes.push(n->right);
}
return matches;
}
int distance_to_leaf(Node* root) {
vector<pair<Node*, int> > stack;
stack.push_back(make_pair(root, -1));
int maxDist = -1;
while (stack.size() > 0) {
pair<Node*, int> curr = stack.back();
Node* n = curr.first;
stack.erase(stack.end()-1);
if (!n->left && !n->right)
maxDist = max(maxDist, curr.second);
if (n->left)
stack.push_back(make_pair(curr.first->left, curr.second+1));
if (n->right)
stack.push_back(make_pair(curr.first->right, curr.second+1));
}
return maxDist;
}
I'm proposing a dynamic programming solution. Not sure if it's entirely correct, but here's the reasoning:
Let's use the string 'bcacba' as an example. If we go from left to right and consider how many permutations of this string has a higher lexicographical order, we'd get that for the first position, the permutation could be:
Any permutation that has the same character at this position (2 possibilities) AND where the rest of the sub string has a higher order.
Or
Any permutation that has a higher order character at this position (2 possibilities) AND where the rest of the sub string doesn't matter. (Because if we chose a higher order character at this position, then the final string will have higher order no matter what)
If we translate this into a formula, let's define some functions:
- S is the string, S(k) is the character at index k, S[i, j) is the sub string i->j, N is the number of characters
- P(k) is the number of higher order permutations in the sub string S[k, N)
- E(k) is the total number of characters equal to S(k) in S[k, N)
- H(k) is the total number of characters with higher order than S(k) in S[k, N)
So translated into a formula, we would get that
P(k) = E(k)*P(k+1) + H(k)*(N-k-1)!
This formula can be calculated backwards, so with 'bcacba', we would get
P(N-1) = 0 // there is only one character, so no permutation with higher order
P(N-2) = 1*0 + 1*(2-1)! = 1
'ab'
P(N-3) = 1*1 + 2*(3-1)! = 5
'abc'
'acb'
'bac'
'bca'
'cab'
P(N-4) = 2*5 + 0*3! = 10
'aabc'
'aacb'
'abac'
'abca'
'acab'
'aabc' << the two 'a's are swapped, so duplicates but different permutations
'aacb'
'abac'
'abca'
'acab'
etc.
O(n)
Consider every login/logout pair, count it if login happened prior to the given time, and logout happened after the given time.
- Martin October 13, 2012