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;
}

Martin
October 13, 2012 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;
}

Martin
October 13, 2012 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)*(Nk1)!
This formula can be calculated backwards, so with 'bcacba', we would get
P(N1) = 0 // there is only one character, so no permutation with higher order
P(N2) = 1*0 + 1*(21)! = 1
'ab'
P(N3) = 1*1 + 2*(31)! = 5
'abc'
'acb'
'bac'
'bca'
'cab'
P(N4) = 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