cristi.vlasceanu
BAN USERMy understanding is that we need to print each tree level in order, except for the last level which should be reversed.
A possible solution is to:
1) use "sentinel" NULL nodes to know where each level begins
2) maintain a vector of nodes to print, and print them at the end of each level
It seems to be working but I need to think more about possible corner cases.
typedef vector<TreeNode*> PrintList;
void bfs(TreeNode* node)
{
if (!node) return;
queue<TreeNode*> q;
PrintList list;
q.push(node);
q.push(NULL);
while (!q.empty())
{
TreeNode* v = q.front();
q.pop();
if (v == NULL)
{
//end of level, print the list
if (q.empty())
{
// last level, print in reverse order
for (PrintList::reverse_iterator i = list.rbegin(); i != list.rend(); ++i)
{
cout << (*i)->label << " ";
}
}
else
{
q.push(NULL);
for (PrintList::iterator i = list.begin(); i != list.end(); ++i)
{
cout << (*i)->label << " ";
}
}
cout << "\n";
list.clear();
}
else
{
list.push_back(v);
if (v->left) q.push(v->left);
if (v->right) q.push(v->right);
}
}
}
On a board??? Geee Gosh I thought it was for a phone screen... :)
Ok, you got a good point.
Oops I said "logarithmic", instead of O(n log n).
- cristi.vlasceanu August 26, 2009That was my point precisely: suffix trees may give a more efficient solution, but they are harder to implement, especially in an interview.
The solution for longest duplicate string that I linked to involves building a suffix ARRAY and sorting it. Which is logarithmic, but easy enough to code within the 30 minutes or so that you get in an interview.
A better solution is to concatenate the reversed string to the original string, then find the longest duplicate substring (a solution for which can be found here: http://www.cs.bell-labs.com/cm/cs/pearls/longdup.c).
Another solution for the longest duplicate string which runs in linear time involves suffix tries, but I find Bentley's Programming Pearls solution easier to code.
bool search(int key, int i = 0, int j = 0, int m = M, int n = N)
{
if (i >= m || j >= n)
return false;
int x = (i + m) / 2,
y = (j + n) / 2;
int v = matrix[x][y];
if (v == key)
return true;
if (key > v)
return search(key, i, y + 1, m, n) || search(key, x + 1, j, m, n);
// key < v
return search(key, i, j, m, y) || search(key, i, j, x, n);
}
{{
bool search(int key, int i = 0, int j = 0, int m = M, int n = N)
{
if (i >= m || j >= n)
return false;
int x = (i + m) / 2,
y = (j + n) / 2;
int v = matrix[x][y];
if (v == key)
return true;
if (key > v)
return search(key, i, y + 1, m, n) || search(key, x + 1, j, m, n);
// key < v
return search(key, i, j, m, y) || search(key, i, j, x, n);
}
}}
At a first glance I don't think that you are handling correctly the precedence of the multiplication operator over addition.
- cristi.vlasceanu August 03, 2009Another solution, in the same brute approach spirit:
#include <stdio.h>
int eval(const char* s)
{
int val = 0;
while (*s)
{
switch (*s)
{
case '+': return val + eval(++s);
case '*':
++s;
{
int rhs = 0;
for (; *s >= '0' && *s <= '9' ; ++s)
{
rhs = rhs * 10 + *s - '0';
}
val *= rhs;
}
break;
default:
if (*s >= '0' && *s <= '9')
val = val * 10 + *s++ - '0';
else
return -1;
break;
}
}
return val;
}
char out[1000] = { 0 };
void gen_expr(const char* s, int n, int i = 0)
{
if (*s)
{
out[i++] = *s;
for (int j = 0; j != 3; ++j)
{
if (j == 1) out[i++] = '+';
else if (j == 2) out[i++] = '*';
gen_expr(s + 1, n, i);
if (j) --i;
if (!s[1]) break;
}
}
else
{
out[i] = 0;
if (eval(out) == n)
printf("%s\n", out);
}
}
int main ()
{
gen_expr("1232537859", 995);
return 0;
}
There may be a simpler way, but here's what I came up with: use the selection algorithm to find the median, the count the elements equal to the median going to left, then going to the right. If the count is N / 2, report the element.
template<typename T>
bool find_half_dupes(T* a, int count, T& result)
{
const int half = count / 2;
select(a, count, half);
T median = a[half];
int c = 0;
for (int i = half; i >= 0; --i)
{
if (a[i] == median)
++c;
else
break;
}
for (int i = half + 1; i != count; ++i)
{
if (a[i] == median)
++c;
else
break;
}
if (c >= half)
{
result = median;
return true;
}
return false;
}
Here's the selection algorithm, for completeness:
//return index of pivot after partition
template<typename T>
int partition(T* a, int count, int pivotIndex)
{
if (count == 0)
return 0;
int m = -1;
T pivot = a[pivotIndex];
for (int i = 0; i != count; ++i)
{
if (a[i] <= pivot)
{
swap(a[++m], a[i]);
}
}
assert(m >= 0);
swap(a[m], a[pivotIndex]);
return m;
}
//hook for implementing pivot selection
template<typename T>
inline int select_pivot(T* a, int count)
{
return 0;
}
template<typename T>
int partition(T* a, int count)
{
int pivotIndex = select_pivot(a, count);
return partition(a, count, pivotIndex);
}
template<typename T>
void select(T* a, int count, int k)
{
int i = partition(a, count);
if (i > k)
{
select(a, i, k); // work in the left sub-array
}
else if (i < k)
{
++i;
select(a + i, count - i, k - i); // right sub-array
}
}
The selection algorithm is O(n) in the number of elements, so the whole thing is O(n).
- cristi.vlasceanu July 21, 2009How about this: build a min heap using a less operator defined like this:
//sort by weight first, then by height
bool Person::less_1(const Person& other) const
{
if (weight < other.weight) return true;
if (weight > other.weight) return false;
return height < other.height;
}
max_1 is where the shape of the heap is a perfect triangle.
Then we build another min heap, this time with the operator less_2 sorting by height first, then by weight, and again max_2 is the max number of people for which the heap has a perfect triangle shape (i.e. we discard the last level if it does not have precisely N * 2 leaves).
The final solution is max(max_1, max_2).
I assume that each level of the human tower (going from base to top) has N / 2 people than the previous one, but a circus tower could also be formed with N, N - 1, N - 2... not clear from the problem spec.
How about this: build a min heap using a less operator defined like this:
//sort by weight first, then by height
bool Person::less_1(const Person& other) const
{
if (weight < other.weight) return true;
if (weight > other.weight) return false;
return height < other.height;
}
max_1 is where the shape of the heap is a perfect triangle.
Then we build another min heap, this time with the operator less_2 sorting by height first, then by weight, and again max_2 is the max number of people for which the heap has a perfect triangle shape (i.e. we discard the last level if it does not have precisely N * 2 leaves).
The final solution is max(max_1, max_2).
I assume that each level of the human tower (going from base to top) has N / 2 people than the previous one, but a circus tower could also be formed with N, N - 1, N - 2... not clear from the problem spec.
Thoughts?
How about this: build a min heap using a less operator defined like this:
//sort by weight first, then by height
bool Person::less_1(const Person& other) const
{
if (weight < other.weight) return true;
if (weight > other.weight) return false;
return height < other.height;
}
max_1 is where the shape of the heap is a perfect triangle.
Then we build another min heap, this time with the operator less_2 sorting by height first, then by weight, and again max_2 is the max number of people for which the heap has a perfect triangle shape (i.e. we discard the last level if it does not have precisely N * 2 leaves).
The final solution is max(max_1, max_2).
I assume that each level of the human tower (going from base to top) has N / 2 people than the previous one, but a circus tower could also be formed with N, N - 1, N - 2... not clear from the problem spec.
Thoughts?
oh, and to make the list circular we need to call the function like this:
ListNode<int>* tail = NULL;
ListNode<int>* list = to_list(tree, tail);
if (tail)
tail->next = list; // make it circular
One way of doing this is with a recursive function that returns the head of the list, and also keeps track of the tail. We visit the right subtree first, then the current node (and link the tail to it), then the left sub-tree:
template<typename T>
struct ListNode
{
T value;
ListNode* next;
explicit ListNode(T v) : value(v), next(NULL) { }
};
template<typename T>
struct TreeNode
{
T value;
TreeNode* left;
TreeNode* right;
};
template<typename T>
ListNode<T>* to_list(TreeNode<T>* tree, ListNode<T>*& tail)
{
ListNode<T>* list = NULL;
if (tree)
{
list = to_list(tree->right, tail);
ListNode<T>* node = new ListNode<T>(tree->value);
if (!list)
{
list = node;
}
if (tail)
{
tail->next = node;
}
tail = node;
node->next = to_list(tree->left, tail);
}
return list;
}
Sedgewick's book Algorithm's in C++ describes joining two BST-s by using insertion at root (which in turn uses left and right rotations). The idea is to "pop" the root of the left tree, and then insert_at_root that node into the right tree. This way, the values in both left sub-trees are guaranteed to be smaller than the root in the right tree, and the values in the right sub-trees are guaranteed larger. Then you recursively join the two left trees and the two right trees.
Here's my implementation (different from the book):
template<typename T>
struct Node
{
T value;
Node* left;
Node* right;
explicit Node(T v) : value(v), left(NULL), right(NULL)
{
}
};
template<typename T>
Node<T>* rotate_right(Node<T>* node)
{
if (node)
{
if (Node<T>* left = node->left)
{
node->left = left->right;
left->right = node;
node = left;
}
}
return node;
}
template<typename T>
Node<T>* rotate_left(Node<T>* node)
{
if (node)
{
if (Node<T>* right = node->right)
{
node->right = right->left;
right->left = node;
node = right;
}
}
return node;
}
template<typename T>
Node<T>* insert_at_root(Node<T>* tree, Node<T>& node)
{
if (tree)
{
if (tree->value >= node.value)
{
tree->left = insert_at_root(tree->left, node);
return rotate_right(tree);
}
else if (tree->value < node.value)
{
tree->right = insert_at_root(tree->right, node);
return rotate_left(tree);
}
}
node.left = node.right = NULL;
return &node;
}
template<typename T>
Node<T>* join(Node<T>* left, Node<T>* right)
{
Node<T>* node = right;
if (left)
{
//save left and right links, insert_at_roots nulls them out
Node<T>* tmp_left = left->left;
Node<T>* tmp_right = left->right;
node = insert_at_root(right, *left);
node->left = join(tmp_left, node->left);
node->right = join(tmp_right, node->right);
}
return node;
}
If I remember correctly he claims that this is O(n) but I do not remember the argument. Luckily I have the book so I'll go look it up.
I recommend the book (not for its C++ coding style, though) there are some less expensive used copies available on Amazon.
Nishank, can you please clarify how the outcome has uniform distribution? If randfive() produces values in the set { 1, 2, 3, 4, 5 }, then the odds (sic) for drawing an odd number is 3/5.
Or is the output of randfive() supposed to be a closed interval at either end?
thanks.
Maintain a vector of nodes seen so far as we recursively visit the tree. In C++:
struct Node
{
int value;
Node* left;
Node* right;
};
void visit(Node* n, std::vector<int>& v)
{
if (n)
{
for (std::vector<int>::const_iterator i = v.begin(); i != v.end(); ++i)
{
matrix[*i][n->value] = 1;
}
v.push_back(n->value);
visit(n->left, v);
visit(n->right, v);
v.pop_back();
}
}
Partition the array in odd an even numbers. If there are more odd numbers than even, partition the odd numbers by the next bit and repeat. If there are more even numbers than odd, look up the duplicate in the even numbers partition.
It is similar to the selection algorithm because on average the numbers left after each iteration is about half, so the complexity is approx:
O(N/2 + N/4 + N/8 + ...) which is O(N)
C++ example for N == 8:
#include <algorithm> // for std::swap
#include <iostream>
using namespace std;
int partition(int* a, int N, int mask)
{
int m = -1;
for (int i = 0; i != N; ++i)
{
if (a[i] & mask)
{
swap(a[++m], a[i]);
}
}
return m + 1;
}
template<int N>
int findDuplicate(int (&a)[N])
{
int lower = 0, upper = N, mask = 1;
for (; mask < N; mask <<= 1)
{
int i = partition(a + lower, upper, mask);
if (i > (upper - lower) / 2)
{
upper = i;
}
else
{
lower = i;
}
}
return a[lower];
}
int main()
{
int a[] = { 2, 7, 6, 4, 5, 6, 3, 1 };
cout << findDuplicate<8>(a) << endl;
return 0;
}
You are right VK, I did not think this thru. Here's another shot at it:
For each i, we compute two numbers: the products of all numbers from input[0] to input[i], and the products from input[i] to input[N - 1].
Then, for each i, if j = index[i], the result is to[j - 1] times from[j + 1]. There might be bugs in the code below but I think the principle is correct. Thoughts?
#include <iostream>
using namespace std;
#define N 5
int input[] = { 1, 2, 3, 4, 5 };
int index[] = { 0, 1, 2, 2, 2 };
int result[N];
int to[N]; // partial products from [0 to i]
int from[N]; // partial products from [i to N)
int main()
{
for (int i = 0; i != N; ++i)
{
result[i] = 1;
}
for (int i = 0; i != N; ++i)
{
to[i] = input[i];
if (i)
{
to[i] *= to[i - 1];
}
}
for (int i = 0; i != N; ++i)
{
from[N - i - 1] = input[N - i - 1];
if (i)
{
from[N - i - 1] *= from[N - i];
}
}
for (int i = 0; i != N; ++i)
{
int j = index[i];
if (j)
{
result[i] = to[j - 1];
}
if (j < N - 1)
{
result[i] *= from[j + 1];
}
cout << result[i] << endl;
}
return 0;
}
A->R
A-R->A // at this point A is zeroed out
B->R
A-R->A // A == -B
A->R // R == -B
A-R->A // A == 0
A-R->A // A == B
@Lord Darth:
I don't think that my algorithm discards the highest element. It is a MIN heap, meaning the root is the smallest of the K; so the smallest out of the K largest is replaced each time a larger number is found, then the heap is re-established, so at all times the smallest of the K candidates is in position 0 (i.e. root)
We do not sort all N numbers because the problem states that size can be in the Gigs. Sorting in memory may not be possible, and sorting on disk is too slow.
The linear data structure (string, list or array) obtained by visiting the tree in-order does not describe the tree unambiguously, i.e. two different trees can yield the same sequence.
But I think that the pair of sequences obtained from visiting in-order and then in pre-order uniquely describes the tree (the tree can be unambiguously reconstructed from the 2 sequences).
in pseudo C++:
1) read the first K numbers out of the file (to seed the algorithm)
2) std::make_heap(0, K, std::greater) // establish a min-heap
3) for (i = K + 1; i != N; ++i) {
n = read_next_number();
if (n > heap[0]) {
heap[0] = n;
make_heap(0, K, greater); // re-establish the heap
}
}
Space complexity is O(K), Time complexity is O( N log K ). Correct?
template<typename T>
class Stack
{
struct StackNode
{
T value_;
StackNode* next_;
StackNode(T value, StackNode* next) : value_(value), next_(next)
{
}
};
union
{
StackNode* top_;
void* ptr_;
};
//prevent copying and assignment to avoid issues with ownership over top_
Stack(const Stack&);
Stack& operator=(const Stack&);
public:
Stack() : top_(NULL)
{
}
bool empty() const
{
return top_ == NULL;
}
T top() const
{
assert(!empty());
return top_->value_;
}
void push(T value)
{
StackNode* node = top_;
StackNode* newNode = new StackNode(value, node);
while (InterlockedCompareExchangePointer(&ptr_, newNode, node) != node)
{
newNode->next_ = node = top_;
}
}
void pop()
{
StackNode* node = top_;
while (InterlockedCompareExchangePointer(&ptr_, (node ? node->next_ : NULL), node) != node)
{
node = top_;
}
delete node;
}
};
Can you build the hash on disk, using lseek64? It should allow the file offset to be set beyond the end of the existing data in the file. If data is later written at this point, subsequent reads of data in the gap shall return bytes with the value 0 until data is actually written into the gap.
This on-disk hash would store offsets in the first file. Now all I need is a good scheme for dealing with hashing conflicts...
Assuming that the file is too large to fit in memory (or to be mapped into memory):
If strings are ASCII and the starting character is uniformly distributed, one could try a multi-pass approach: read all strings that start with 'a' in memory, sort them, and write'em to the output file; do another pass and read all strings that start with 'b', etc. This however does not work if all strings start with the same character (i.e. not uniformly distributed).
Another approach is to do a quicksort on disk. However, a fileseek(size / 2) may land in the middle of a string (in other words, the input file has records of variable size). We could do a first pass through the file and write the offsets where lines start down into an auxiliary file (keeping the offsets in memory may not work: assuming an average 8 character string, keeping track of offsets would require half the size of the input file on a 32-bit machine, and the same size as the input on a 64-bit system, not counting the CRLFs; so the memory constraint still holds).
The auxiliary file has records of equal size (each entry is an offset of 4 or 8 bytes, depending on the platform). We can now do a quick sort of this file on disk. The comparison function would look something like (in C++-like pseudo-code):
int compare(long lhs, long rhs) {
string lhsString = readStringFromMainFileAt(lhs);
string rhsString = readStringFromMainFileAt(rhs);
return lhsString.compare(rhsString);
}
After sorting the auxiliary offsets file, we do another pass:
foreach i in auxiliary file {
string s = readStringFromMainFileAt(i);
writeToOutput(s);
}
The runtime is 2N + O (N log N) == O (N log N) (the 2N is from the pre- and post- passes and NlogN is from qsort).
Assuming a 200 MB/s disk transfer rate, I think that a 2GB file can be sorted in a minute or less using this algorithm.
I think that A* is overkill for this problem. Trying to recursively make progress downwards and to the right produces results that are comparable, for a much simpler implementation. I think A* works better if the source and the goal square are randomly selected.
The following program implements both approaches (it initializes an M x N table, with a configurable number of "blocked" squares, which are randomly selected):
// vim: tabstop=4:softtabstop=4:expandtab:shiftwidth=4
#include <time.h>
#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
using namespace std;
typedef short coord_type;
class Table;
//Represent a square on the table as a node in a graph
class Node
{
coord_type x_;
coord_type y_;
coord_type comeFromX_;
coord_type comeFromY_;
bool blocked_ : 1; // true if it represents a blocked square on the table
bool visited_ : 1;
bool openSet_ : 1; // for A*
size_t costFromStart_; // ditto
public:
Node()
: x_(-1)
, y_(-1)
, comeFromX_(-1)
, comeFromY_(-1)
, blocked_(false)
, visited_(false)
, openSet_(false)
, costFromStart_(numeric_limits<size_t>::max())
{
}
void setCoords(coord_type x, coord_type y)
{
x_ = x;
y_ = y;
}
coord_type x() const { return x_; }
coord_type y() const { return y_; }
void setBlocked() { blocked_ = true; }
bool isBlocked() const { return blocked_; }
void setVisited(bool visited = true)
{
visited_ = visited;
if (!visited)
{
comeFromX_ = comeFromY_ = -1;
}
}
bool isVisited() const { return visited_; }
void setOpenSet(bool openSet = true)
{
openSet_ = openSet;
}
bool isOpenSet() const { return openSet_; }
void setComeFrom(const Node& node)
{
comeFromX_ = node.x();
comeFromY_ = node.y();
}
size_t heuristicToGoal(const Node& goal) const
{
#if 1 // Dijkstra
return 0;
#else
size_t h = abs(goal.x() - x()) + abs(goal.y() - y());
return h;
#endif
}
size_t costFromStart() const
{
return costFromStart_;
}
void setCostFromStart(size_t cost)
{
costFromStart_ = cost;
}
size_t costToGoal(const Node& goal) const
{
return costFromStart_ + heuristicToGoal(goal);
}
void printPath(ostream&, const Table&) const;
};
ostream& operator<<(ostream& out, const Node&);
////////////////////////////////////////////////////////////////
// ********************* helpers for A* ***********************
//
// functor that comparess costs to goal
class LessCost : public binary_function<Node*, Node*, bool>
{
const Node& goal_;
public:
explicit LessCost(const Node& goal) : goal_(goal)
{
}
bool operator()(const Node* lhs, const Node* rhs) const
{
return lhs->costToGoal(goal_) > rhs->costToGoal(goal_);
}
};
class OpenNodeSet
{
deque<Node*> nodes_;
const Node& goal_;
public:
explicit OpenNodeSet(const Node& goal) : goal_(goal)
{ }
bool empty() const
{
return nodes_.empty();
}
void push(Node& node)
{
assert(!node.isBlocked());
assert(!node.isVisited());
if (!node.isOpenSet())
{
nodes_.push_back(&node);
node.setOpenSet();
make_heap(nodes_.begin(), nodes_.end(), LessCost(goal_));
}
}
Node& pop()
{
assert(!empty());
Node& node = *nodes_.front();
node.setOpenSet(false);
nodes_.pop_front();
return node;
}
};
//
////////////////////////////////////////////////////////////////
class Table
{
coord_type width_;
coord_type height_;
Node* nodes_;
Table(const Table&);
Table& operator=(const Table&);
public:
//ctor, configures the table
Table(coord_type width, coord_type height, unsigned maxBlockCount = 0)
: width_(width)
, height_(height)
, nodes_(NULL)
{
assert(width > 1);
assert(height > 1);
size_t i = 0, size = width * height;
nodes_ = new Node[size];
for (coord_type y = 0; y != height; ++y)
{
for (coord_type x = 0; x != width; ++x, ++i)
{
nodes_[i].setCoords(x, y);
// mark maxBlockCount nodes as blocked
// the top left and bottom right are never blocked
if (maxBlockCount && i && i < size - 1)
{
if ((rand() % (size - i - 2)) < maxBlockCount)
{
--maxBlockCount;
nodes_[i].setBlocked();
}
}
}
}
}
~Table()
{
delete [] nodes_;
}
Node& nodeAt(coord_type x, coord_type y)
{
assert(x < width_);
assert(y < height_);
return nodes_[y * width_ + x];
}
const Node& nodeAt(coord_type x, coord_type y) const
{
assert(x < width_);
assert(y < height_);
return nodes_[y * width_ + x];
}
void print(ostream& out) const
{
for (coord_type y = 0; y != height_; ++y)
{
for (coord_type x = 0; x != width_; ++x)
{
Node& node = nodes_[y * width_ + x];
out << node << ' ';
}
out << "\n";
}
}
void resetVisited()
{
for (coord_type y = 0; y != height_; ++y)
{
for (coord_type x = 0; x != width_; ++x)
{
nodeAt(x, y).setVisited(false);
}
}
}
static void push(OpenNodeSet& openSet, const Node& comeFrom, Node& node)
{
if (!node.isBlocked() && !node.isVisited())
{
size_t costFromStart = comeFrom.costFromStart() + 1;
if (costFromStart < node.costFromStart())
{
node.setCostFromStart(costFromStart);
node.setComeFrom(comeFrom);
openSet.push(node);
}
}
}
//find shortest path to goal using A*
//return false if not path exists
bool shortestPath(Node& start, const Node& goal)
{
OpenNodeSet openSet(goal);
start.setCostFromStart(0);
openSet.push(start);
while (!openSet.empty())
{
Node& node = openSet.pop();
if (&node == &goal)
{
return true;
}
node.setVisited();
//add neighbors to openSet:
coord_type x = node.x();
coord_type y = node.y();
// left
if (x > 0)
push(openSet, node, nodeAt(x - 1, y));
// right
if (x + 1 < width_)
push(openSet, node, nodeAt(x + 1, y));
// top
if (y > 0)
push(openSet, node, nodeAt(x, y - 1));
// bottom
if (y + 1 < height_)
push(openSet, node, nodeAt(x, y + 1));
}
return false;
}
//simpler algo, start at upper left and work towards bottom right
bool findPath(Node& start, const Node& goal)
{
if (&start == &goal)
return true;
if (start.isBlocked() || start.isVisited())
return false;
coord_type x = start.x();
coord_type y = start.y();
//try making progress downwards:
if (y + 1 < height_)
{
Node& node = nodeAt(x, y + 1);
if (findPath(node, goal))
{
node.setComeFrom(start);
return true;
}
}
// try moving right
if (x + 1 < width_)
{
Node& node = nodeAt(x + 1, y);
if (findPath(node, goal))
{
node.setComeFrom(start);
return true;
}
}
//clog << "blocked at " << start << endl;
start.setVisited(true);
return false;
}
};
ostream& operator<<(ostream& out, const Node& node)
{
if (node.isBlocked())
{
out << "[" << node.x() << ", " << node.y() << "]";
}
else
{
out << "(" << node.x() << ", " << node.y() << ")";
}
return out;
}
ostream& operator<<(ostream& out, const Table& table)
{
table.print(out);
return out;
}
void Node::printPath(ostream& out, const Table& table) const
{
coord_type x = comeFromX_;
coord_type y = comeFromY_;
if (x >= 0 && y >= 0)
{
const Node& node = table.nodeAt(x, y);
node.printPath(out, table);
out << node << "-->\n";
}
}
int main()
{
srand(unsigned(time(NULL)));
//coord_type width = 6;
//coord_type height = 6;
//size_t blockedSquaresCount = 7;
coord_type width = 4;
coord_type height = 4;
size_t blockedSquaresCount = 3;
Table table(width, height, blockedSquaresCount);
Node& start = table.nodeAt(0, 0);
const Node& goal = table.nodeAt(width - 1, height - 1); // bottom right
cout << table << endl;
//A*
if (table.shortestPath(start, goal))
{
goal.printPath(cout, table);
cout << goal << endl;
}
else
{
cout << "no path found.\n";
}
cout << "********************************************************\n";
table.resetVisited();
//down-right simple algo
if (table.findPath(start, goal))
{
goal.printPath(cout, table);
cout << goal << endl;
}
else
{
cout << "no path found.\n";
}
return 0;
}
Before going into technical details I would ask if we have clearance from the Legal Department to store SSNs ;)
- cristi.vlasceanu May 27, 20091) It depends on how the DLL was built (and it should be documented). If it is built to use the shared C runtime (the msvcrt.dll, if you are using a Microsoft compiler), and so is your app, then it is okay to delete / free. But otherwise (DLL uses static runtime) you will very likely be getting a crash because the free or delete call in the app attempts to release memory off a different heap that the one where it was allocated from.
It is a better design to have the DLL provide factory methods, and for the classes in that DLL to have a virtual Release method (it is crucial for the method to be virtual).
2) There may be an uninitialized memory bug in the DLL. In debug mode you tend to get everything zeroed out by the runtime. Or maybe the application releases the DLL (by calling FreeLibrary) but keeps referencing objects or functions in the DLL (in debug mode that memory may not be reused right away). There may be some assert(...) side effects, or the memory layout of some class is not the same in debug versus release.
Can we use InterlockedCompareExchange or related?
- cristi.vlasceanu May 21, 2009for (int i = 0; i != n; ++i) {
result[i] = 1;
}
for (int i = 0; i != n; ++i) {
if (index[i] != i) {
result[i] *= input[i];
}
}
Would this work?
- cristi.vlasceanu May 21, 2009Here is a solution that does not require extra memory. Visiting all nodes in a tree is O(n) and the depth of a balanced tree is log(n), so the average complexity is n * log(n). Worst case is O(n * n):
#include <iostream>
using namespace std;
struct TreeNode
{
int value;
TreeNode* left;
TreeNode* right;
explicit TreeNode(int v) : value(v), left(NULL), right(NULL)
{
}
};
TreeNode* createTestTree()
{
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->left->right->right = new TreeNode(7);
return root;
}
size_t printTree(const TreeNode* node, size_t levelToPrint, size_t currentLevel = 0)
{
if (node)
{
if (levelToPrint == currentLevel)
{
cout << node->value << ' ';
return 1;
}
else if (levelToPrint > currentLevel)
{
return printTree(node->left, levelToPrint, currentLevel + 1)
+ printTree(node->right, levelToPrint, currentLevel + 1);
}
}
return 0;
}
void printTree(const TreeNode* root)
{
for (size_t levelToPrint = 0; ; ++levelToPrint)
{
if (printTree(root, levelToPrint))
{
cout << '\n';
}
else
{
break;
}
}
}
void main()
{
const TreeNode* root = createTestTree();
printTree(root);
}
Here's a solution in C++ (may not be the most effective, though). Basically it checks if the given string "s" is a palindrome. If it is, then that's the longest we can find.
If not a palindrome, look in s.substr(0, len - 1) and in s.substr(1, len - 1) and return the longest result.
#include <cassert>
#include <iostream>
#include <string>
#include <utility>
using namespace std;
static size_t distance(const pair<size_t, size_t>& p)
{
assert(p.first <= p.second);
return p.second - p.first;
}
//count how many times find_longest_palindrome is invoked
static size_t count = 0;
static pair<size_t, size_t> find_longest_palindrome(const char* s, size_t len)
{
++count;
pair<size_t, size_t> result;
#if 0
//move outwards beginning from the middle
size_t i = len / 2, j = len / 2;
if (len && len % 2 == 0)
{
assert(i > 0);
--i;
}
for (; j < len; ++j, --i)
{
assert(i < len);
if (s[i] != s[j])
{
break;
}
result.first = i;
result.second = j;
}
if (len > distance(result) + 1)
{
//inspect right hand-side substring
pair<size_t, size_t> result1 = find_longest_palindrome(s, len - 1);
if (distance(result) < distance(result1))
{
result = result1;
}
//inspect right hand-side substring
pair<size_t, size_t> result2 = find_longest_palindrome(s + 1, len - 1);
if (distance(result) < distance(result2))
{
result = result2;
++result.first;
++result.second;
}
}
#else
//work inwards from the extremities of the string
size_t i = 0, j = len ? len - 1 : 0;
result.first = 0;
result.second = j;
for (; i < j; ++i, --j)
{
if (s[i] != s[j])
{
result.second = 0;
break;
}
}
if (!result.second && len > 1)
{
//inspect right hand-side substring
result = find_longest_palindrome(s, len - 1);
//if the length found == len - 1 there's no point in inspecting
//the right hand substring
if (distance(result) < len - 1)
{
//inspect right hand-side substring
pair<size_t, size_t> result2 = find_longest_palindrome(s + 1, len - 1);
if (distance(result) < distance(result2))
{
result.first = result2.first + 1;
result.second = result2.second + 1;
}
}
}
#endif
return result;
}
string find_longest_palindrome(const string& s)
{
count = 0;
pair<size_t, size_t> r = find_longest_palindrome(s.c_str(), s.length());
#if _DEBUG
cout << '[' << r.first << ", " << r.second << ']' << endl;
cout << "string length=" << s.length() << ", number of steps=" << count << endl;
#endif
return distance(r) ? s.substr(r.first, distance(r) + 1) : string();
}
void main()
{
cout << find_longest_palindrome("abcd") << endl;
cout << find_longest_palindrome("xxbaaba") << endl;
cout << find_longest_palindrome("xxbaabaa") << endl;
cout << find_longest_palindrome("xxba") << endl;
cout << find_longest_palindrome("yyyba") << endl;
cout << find_longest_palindrome("xxbaabaawowaabx") << endl;
}
This is what I came up with:
#include <iostream>
using namespace std;
int count_digit(int n, int dig)
{
int count = 0;
while (n)
{
int q = n / 10;
int remainder = n - q * 10;
if (remainder == dig)
{
++count;
}
n = q;
}
return count;
}
void main()
{
int count = 0;
for (int i = 0; i != 35; ++i)
{
count += count_digit(i, 2);
}
cout << count << endl;
}
Vinay, yes your solution is simpler to code but it will traverse the tree twice.
- cristi.vlasceanu December 12, 2009