## little-eyes

BAN USER
Comments (5)

Reputation 35

Page:

1

Comment hidden because of low score. Click to expand.

Comment hidden because of low score. Click to expand.

0

of 0 vote

This solution is a good one, but it cost extra O(n) space. Is there any solution for O(1) extra space?

- little-eyes September 13, 2012Comment hidden because of low score. Click to expand.

0

of 0 vote

@kurskk141, this solution is still not perfect, we still need to figure out the min 3 negative. So the solution must be in max 3 positive, max 3 negative and min 3 negative. Of course the length of the array should be larger than 9.

- little-eyes July 17, 2012Comment hidden because of low score. Click to expand.

1

of 1 vote

I don't think "the largest 3 numbers" is the right solution, the numbers may be negative, right? two negative numbers' product is still positive. Look at the following example:

6 3 2 -100 -101

The first 3 number is 6 3 2, the product = 36. But the largest product here should be 6 * -100 * -101.

Comment hidden because of low score. Click to expand.

1

of 3 vote

```
void postOrderTraversalIterative(BinaryTree *root) {
if (!root) return;
stack<BinaryTree*> s;
s.push(root);
BinaryTree *prev = NULL;
while (!s.empty()) {
BinaryTree *curr = s.top();
// we are traversing down the tree
if (!prev || prev->left == curr || prev->right == curr) {
if (curr->left) {
s.push(curr->left);
} else if (curr->right) {
s.push(curr->right);
} else {
cout << curr->data << " ";
s.pop();
}
}
// we are traversing up the tree from the left
else if (curr->left == prev) {
if (curr->right) {
s.push(curr->right);
} else {
cout << curr->data << " ";
s.pop();
}
}
// we are traversing up the tree from the right
else if (curr->right == prev) {
cout << curr->data << " ";
s.pop();
}
prev = curr; // record previously traversed node
}
}
```

This solve in O(n) time and O(h) space, where h is the depth of the tree.

- little-eyes July 10, 2012Page:

1

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

I am thinking of this way:

- little-eyes September 18, 20121. we need to go from "start" to "end", then we have to cover a base distance = sum(x_i), which is go directly from start -> d_1 to d_n -> end.

2. the different patterns can be split into pieces like d_i to d_j, which means you can go back and forth between d_i and d_j as many times as you want, as long as the total distance does not exceed Z.

3. So the value P = Z - sum(x_i) can be regarded as the total distance used to go back-and-forth in any pair (d_i, d_j). Each time you made a back-and-forth between (d_i, d_j), it cost 2*x_i.

4. Then you can use DP to calculate the combinations of using x_i to make up the sum equals to P. Each x_i can be used for multiple time. Then final combinations is the total number of patterns.

5. If you need to print all the patterns, you need to search, but in a memoization way. The worst case time complexity could be O(n*P).

Does it make sense??