zjzzjz
BAN USERThis can be done based on topotraverse.
1) Keep track of map M from one to people one manages, initialize everyone to be zero at the beginning
2) at each toposearch step, when a node n is ready to run, add M[n]+1 to all its successors.
3) if a cycle is detected, raise an exception
time: O(N^2 * log(N)), space O(N)
for each possible length L of a continuous subarray, find all possible NL+1 subarrays, and calculate the min/max of values in each subarray. This can be done in N.
Now the question is checking if there exists two nonoverlapped intervals: This can be done in n*log(n) after sorting the intervals by their min values.
This is a parsing program. We have a grammar like:
P = '(' Q Q ')'
Q = 0  P
So the following topdown recursion based parsing should work. The complexity is N.
int P(string &input, int &curr) {
if (input.size() >= input.size()) {
return 1;
}
if (str.at(curr++) != '(') {
return 1;
}
int d1 = Q(input, curr);
if (d1 < 0) {
return 1;
}
int d2 = Q(input, curr);
if (d2 < 0) {
return 1;
}
if (curr >= input.size()) {
return 1;
}
if (input.at(curr++) != ')') {
return 1;
}
return 1 + max (d1, d2);
}
int Q(string &input, int &curr) {
if (curr >= input.size()) {
return 1;
}
switch (input.at(curr++)) {
case '0': return 0;
case '(': return P(input, curr);
default: return 1;
}
}
int parse(string &input) {
int curr = 0;
return P(input, curr);
}

zjzzjz
October 14, 2015 Idea: revert the rightmost path
For example,
10
5 16
1 3 14 20
to
20
16
10 14
5
1 3
node* bst2maxheap(node *root, node *&min) {
if (root == nullptr) {
min = nullptr;
return nullptr;
}
node *left_heap = bst2maxheap(root>left, min);
node *right_min = nullptr;
node *right_heap = bst2maxheap(root>right, right_min);
root>right = left_heap;
root>left = nullptr;
if (right_min) {
right_min>left = root;
return right_heap;
}
return root;
}

zjzzjz
September 22, 2015 After the code is compiled to assembly, we definitely need * to calculate the offset of arr[x]. So I do not think this is correct.
How about this?
nbits = sizeof(int) * 8  1; // this is a compile time constant, there is no * at runtime.
x1 = (int)((unsigned int)(x) << nbits) >> nbits;
y = (x1 && a)  (x1 && b);
We first calculate the probability P that none of the slots have i elements, then the answer should be 1  P.
Calculating P is a traditional interview question:
find all possible M nonnegative (<=N) numbers such that their sum is N and none of them == i.
This can be done by a recursion algorithm.
std::vector<std::size_t> v;
v.reserve(M);
double g() {
return (1/M)^N;
}
void f(std::vector<std::size_t> &v, int i, double &p, int sum) {
assert(i<=M);
if (i == M) {
p += g();
return;
}
for (int j=0; j<N; ++j) {
if (sum + j < N) {
v[i] = j;
f(i+1, v, p, sum+j);
}
}
}
f(0, v, 0, 0);

zjzzjz
August 28, 2015 1) sort the (height, #number of greater values in front) pair by using height as a key
This can be done by using std::map
let this map be map1
2) have an empty sorted list1 with the #number of greater and the height as lexical key
for (auto &pair: map1) {
list1.insert(pair.second, pair.first);
}
3) list1 is the result.
Open Chat in New Window
a O(n) time and O(n) space algorithm
 zjzzjz November 11, 2015